question on karatsuba multiplication

Question

I want to implement Karatsuba's 2-split multiplication in Python. However, writing numbers in the form

A=c*x+d

where x is a power of the base (let x=b^m) close to sqrt(A).

How am I supposed to find x, if I can't even use division and multiplication? Should I count the number of digits and shift A to the left by half the number of digits?

Thanks.

Answer 1

Almost. You don't shift A by half the number of digits; you shift 1. Of course, this is only efficient if the base is a power of 2, since "shifting" in base 10 (for example) has to be done with multiplications. (Edit: well, ok, you can multiply with shifts and additions. But it's ever so much simpler with a power of 2.)

If you're using Python 3.1 or greater, counting the bits is easy, because 3.1 introduced the int.bit_length() method. For other versions of Python, you can count the bits by copying A and shifting it right until it's 0. This can be done in O(log N) time (N = # of digits) with a sort of binary search method - shift by many bits, if it's 0 then that was too many, etc.

Answer 2

You already accepted an answer since I started writing this, but:

What Tom said: in Python 3.x you can get n = int.bit_length() directly. In Python 2.x you get n in O(log2(A)) time by binary-search, like below.

Here is (2.x) code that calculates both. Let the base-2 exponent of x be n, i.e. x = 2**n.

First we get n by binary-search by shifting. (Really we only needed n/2, so that's one unnecessary last iteration). Then when we know n, getting x,c,d is easy (still no using division)

def karatsuba_form(A,n=32):
    """Binary-search for Karatsuba form using binary shifts"""
    # First search for n ~ log2(A)
    step = n >> 1
    while step>0:
        c = A >> n
        print 'n=%2d step=%2d -> c=%d' % (n,step,c)
        if c:
            n += step
        else:
            n -= step
        # More concisely, could say: n = (n+step) if c else (n-step)
        step >>= 1
    # Then take x = 2^(n/2) ˜ sqrt(A)
    ndiv2 = n/2
    # Find Karatsuba form
    c = (A >> ndiv2)
    x = (1 << ndiv2)
    d = A - (c << ndiv2)
    return (x,c,d)