question on karatsuba multiplication

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) c开发者_如何学运维lose 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.

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.

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)

Your question is already answered in the article to which you referred: "Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up" ... n being the number of digits, and 0 <= value_of_digit < B.

Some perspective that might help:

You are allowed (and required!) to use elementary operations like number_of_digits // 2 and divmod(digit_x * digit_x, B) ... in school arithmetic, where B is 10, you are required (for example) to know that divmod(9 * 8, 10) produces (7, 2).

When implementing large number arithmetic on a computer, it is usual to make B the largest power of 2 that will support the elementary multiplication operation conveniently. For example in the CPython implementation on a 32-bit machine, B is chosen to to be 2 ** 15 (i.e. 32768), because then product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF; works without overflow and without concern about a sign bit.

I'm not sure what you are trying to achieve with an implementation in Python that uses B == 2, with numbers represented by Python ints, whose implementation in C already uses the Karatsuba algorithm for multiplying numbers that are large enough to make it worthwhile. It can't be speed.

As a learning exercise, you might like to try representing a number as a list of digits, with the base B being an input parameter.