Skip to main content
supplied wikipedia link, marked up quoted code as such, nits
Source Link

I recently implemented Karatsuba Multiplication as ana personal exercise. I wrote my implementation in Python following the pseudocode provided on wikipediapseudocode provided on wikipedia:

procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* calculates the size of the numbers */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* split the digit sequences about the middle */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 calls made to numbers approximately half the size */
  z0 = karatsuba(low1,low2)
  z1 = karatsuba((low1+high1),(low2+high2))
  z2 = karatsuba(high1,high2)
  return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)
procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2

/* calculates the size of the numbers / m = max(size_base10(num1), size_base10(num2)) m2 = m/2 / split the digit sequences about the middle / high1, low1 = split_at(num1, m2) high2, low2 = split_at(num2, m2) / 3 calls made to numbers approximately half the size / z0 = karatsuba(low1, low2) z1 = karatsuba((low1+high1), (low2+high2)) z2 = karatsuba(high1, high2) return (z210^(2*m2)) + ((z1-z2-z0)*10^(m2)) + (z0)

My question is about final merge of the z0z0, z1z1, and z2z2. z2
z2 is shifted mm digits over (where mm is the length of the largest of two multiplied numbers). Instead
Instead of simply multiplying by 10^(m)10^(m), the algorithm uses 10^(2*m210^(2m2)* where m2m2 is m/2m/2.

I tried replacing 2*m22*m2 with mm and got incorrect results. I think this has to do with how the numbers are split but I'm not really sure whatswhat's going on.

I recently implemented Karatsuba Multiplication as an personal exercise. I wrote my implementation in Python following the pseudocode provided on wikipedia:

procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* calculates the size of the numbers */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* split the digit sequences about the middle */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 calls made to numbers approximately half the size */
  z0 = karatsuba(low1,low2)
  z1 = karatsuba((low1+high1),(low2+high2))
  z2 = karatsuba(high1,high2)
  return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

My question is about final merge of the z0, z1, and z2. z2 is shifted m digits over (where m is the length of the largest of two multiplied numbers). Instead of simply multiplying by 10^(m), the algorithm uses 10^(2*m2) where m2 is m/2.

I tried replacing 2*m2 with m and got incorrect results. I think this has to do with how the numbers are split but I'm not really sure whats going on.

I recently implemented Karatsuba Multiplication as a personal exercise. I wrote my implementation in Python following the pseudocode provided on wikipedia:

procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2

/* calculates the size of the numbers / m = max(size_base10(num1), size_base10(num2)) m2 = m/2 / split the digit sequences about the middle / high1, low1 = split_at(num1, m2) high2, low2 = split_at(num2, m2) / 3 calls made to numbers approximately half the size / z0 = karatsuba(low1, low2) z1 = karatsuba((low1+high1), (low2+high2)) z2 = karatsuba(high1, high2) return (z210^(2*m2)) + ((z1-z2-z0)*10^(m2)) + (z0)

My question is about final merge of z0, z1, and z2.
z2 is shifted m digits over (where m is the length of the largest of two multiplied numbers).
Instead of simply multiplying by 10^(m), the algorithm uses 10^(2m2)* where m2 is m/2.

I tried replacing 2*m2 with m and got incorrect results. I think this has to do with how the numbers are split but I'm not really sure what's going on.

Source Link
Solomon Bothwell
  • 1.1k
  • 2
  • 12
  • 21

Karatsuba Multiplication Implementation

I recently implemented Karatsuba Multiplication as an personal exercise. I wrote my implementation in Python following the pseudocode provided on wikipedia:

procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* calculates the size of the numbers */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* split the digit sequences about the middle */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 calls made to numbers approximately half the size */
  z0 = karatsuba(low1,low2)
  z1 = karatsuba((low1+high1),(low2+high2))
  z2 = karatsuba(high1,high2)
  return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

Here is my python implementation:

def karat(x,y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return x*y
    else:
        m = max(len(str(x)),len(str(y)))
        m2 = m / 2

        a = x / 10**(m2)
        b = x % 10**(m2)
        c = y / 10**(m2)
        d = y % 10**(m2)

        z0 = karat(b,d)
        z1 = karat((a+b),(c+d))
        z2 = karat(a,c)

        return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)

My question is about final merge of the z0, z1, and z2. z2 is shifted m digits over (where m is the length of the largest of two multiplied numbers). Instead of simply multiplying by 10^(m), the algorithm uses 10^(2*m2) where m2 is m/2.

I tried replacing 2*m2 with m and got incorrect results. I think this has to do with how the numbers are split but I'm not really sure whats going on.