CODEWITHSUNDEEP
pythonalgorithmkaratsuba
ken
ken

Reputation: 35

I want to implement Karatsuba Multiplication in python

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

Upvotes: 2

Views: 1294

Answers (1)

r3mainer
r3mainer

Reputation: 24557

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")

Upvotes: 6

Related Questions