I want to implement Karatsuba Multiplication in python

Question

I want to implemented Karatsuba Multiplication in python.

But I get the right answer when the number is large.

Can anyone tell me where my code is wrong？

Karatsuba Multiplication Implementation is not right when x is very large.

import math
def fun1(x,y):
    if x <= 100  or y<=100:
        return x*y
    else:
        n = int(math.log10(x)) + 1
        print(n)
        #split x
        a = int(x//(10**int(n/2)))
        b = int(x%(10**int(n/2)))
        #split y
        c = int(y//(10**int(n/2)))
        d = int(y%(10**int(n/2)) )
        print('=======')
        print(a,b,c,d)
        s1 = fun1(a,c)
        s2 = fun1(b,d)
        s3 = fun1(a+b, c+d) - s1 -s2

        return 10**(n) * s1 + 10**int(n/2) * s3 + s2
x = 3141592653589793238462643383279502884197169399375105820974944592
y = 3141592653589793238462643383279502884197169399375105820974944592
res = fun1(x,y)
print(res)

Here comparison of results:

mine: 9871629289354805781531825310608443798018906328629821071675205208766177059699451037253550917606373321601467241501439093564279364
x**2: 9869604401089358618834490999876151135313699407240790626413349374285977301132874762146178862115173871455167598223967837470046464

Possible duplicate of [Karatsuba Multiplication Implementation](https://stackoverflow.com/questions/42324419/karatsuba-multiplication-implementation) — Jerrybibo, Jul 17 '18 at 05:08
[Karatsuba Multiplication Implementation](https://stackoverflow.com/questions/42324419/karatsuba-multiplication-implementation) is not right when the x is very large. — ken, Jul 17 '18 at 05:29
The solution from [this answer](https://stackoverflow.com/a/42324537/5606836) under the above mentioned post does the calculation correctly. — Jerrybibo, Jul 17 '18 at 05:45
Not a python coder so I might be wrong but you are using `math.log10(x)` that implies `double/float` variables which can not hold bigint. also using `log` for multiplication seems wrong (`log` is more complex operation) the same goes for `**` and `/`. On integers use powers of 2 and bit shifting/masking instead. if you insist on `log` use integer `log2` (count how many shifts are needed until result is zero). see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) for some ideas — Spektre, Jul 17 '18 at 07:02
@Spektre That's not the issue here. `log` is used to guess the number of digits of the input and is not needed to be particularly precise (and obviously if the number of digits doesn't fit bigint, we have bigger issues). Agreed on using log2 and shifting being better than log10 and `**`, but that's not where the error comes from. — Amadan, Jul 17 '18 at 08:24

r3mainer · Answer 1 · 2018-07-17T08:24:04.813

The problem is in the last line of your function:

return 10**(n) * s1 + 10**int(n/2) * s3 + s2

When n is even, this works OK, but when n is odd, you're multiplying s1 by a power of 10 one larger than required — s1 should be shifted exactly twice as many places left as s3.

I refactored your code a bit. This should work:

import math, random

def karatsuba(x,y):
    if x <= 100  or y<=100:
        return x * y
    else:
        n = 10 ** int(math.log10(x) / 2.0 + 0.5)
        a, b = x // n, x % n
        c, d = y // n, y % n
        s1 = karatsuba(a,c)
        s2 = karatsuba(b,d)
        s3 = karatsuba(a+b, c+d) - s1 - s2
        return n * n * s1 + n * s3 + s2

for i in range(100):
    x = random.randint(1, 2**1024)
    y = random.randint(1, 2**1024)
    assert karatsuba(x,y) == x * y
else:
    print("OK")

I want to implement Karatsuba Multiplication in python

1 Answers1