1

I'm currently reading a book called Algorithms Illuminated Part 1: Basics and came across a bit discussing about Karatsuba Multiplication. The example says "a number x with an even number n of digits can be expressed in terms of two n/2-digit numbers, its first half a and second half b:

x = 10^(n/2) * a + b. y = 10^(n/2) * c + d.

xy = (10^(n/2) * a + b) * (10^(n/2) * c + d) = 10^n * (a * c) + 10 ^(n/2) (ad + bc) + b*d."

the example is using numbers 5678 * 1234 with 56 = a, 78 = b, 12 = c, and 34 = d

I am having trouble grasping where this 10^n/2 * a + b came from, how did they go from n/2 - digits into this representation? Also why is this and n/2 considered a recursive function? Does it not need to call itself to be considered recursive? Why is there relevance with even or odd for the n?

I have tried graphing the equation with both even and odd Ns. I also looked up the definition of recursive function and they say its a function that calls itself. I am trying to understand why n/2 is considered a recursive algorithm. I am missing the context in how the author managed to get to this equation.

mrRobot9
  • 15
  • 5

1 Answers1

2

One way to think of recursive algorithms is that they break down the problem into smaller/easier sub-problems of the same type, that then can be solved by the same algorithms.

The recursive part of Karatsuba Multiplication is not explicity shown in your example, but consider you have some function "karatsuba(x,y)" that multiplies two numbers x and y.

By your formula xy = 10^n * (a * c) + 10 ^(n/2) (ad + bc) + bd

As you can see this formula requires you to calculate several other products (ac, ad, bc, bd ). a,b,c,d and are smaller (half the number of digits of x and y. So you could express karatsuba(x,y) as

karatsuba(x,y) = 10^n * karatsuba(a,c) + 10^(n/2) * (karatsuba(a,d) + karatsuba(b,c) ) + karatsuba(b,d)

I hope the "recursiveness" is more clear now.

Note: You need some mechanism to handle the base case of the algorithm (like when x or y are single/few digits )

Christian Sloper
  • 7,440
  • 3
  • 15
  • 28