Question of multiplication karatsuba

Question

I want to implement Karatsuba double multiplication in Python. However, writing numbers in the form

A=c*x+d 

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

How can I find x if I cannot 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

Nearly. You do not shift A half the number of digits; you change 1. Of course, this is effective only if the base is cardinality 2, since the “shift” in base 10 (for example) must be performed with multiplications. (Edit: alright, alright, you can multiply with shifts and additions, but it's a lot easier with a power of 2.)

If you use Python 3.1 or higher, counting a bit 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 moving it directly to 0. This can be done in O (log N) time (N = # digits) using a kind of binary search method - shift by many bits if it is 0 then it was too much etc.

Answer 2

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

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

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

First we get n by binary search by shift. (In fact, we only needed n / 2, so one unnecessary last iteration). Then, when we know n, getting x, c, d is easy (still without 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) 

Answer 3

Your question has already been answered in the article that you referred to: "The main step of Karatsuba works for any base B and any m, but the recursive algorithm is most effective when m is n / 2, rounded up" .. n , which is the number of digits , and 0 <= value_of_digit <B.

Some perspectives that may help:

You are allowed (and required!) To use elementary operations, such as number_of_digits // 2 and divmod(digit_x * digit_x, B) ... in school arithmetic, where B is 10, you need (for example) that divmod(9 * 8, 10) creates (7, 2) .

When implementing arithmetic of a large number on a computer, B is usually made with the greatest power of 2, which will support the operation of elementary multiplication. For example, in a CPython implementation on a 32-bit machine, B is selected equal to 2 ** 15 (i.e. 32768), because then product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF; product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF; works without overflow and without taking into account the sign bit.

I'm not sure what you are trying to achieve with a Python implementation that uses B == 2, with numbers represented by Python intuitions, whose C implementation already uses the Karatsuba algorithm to multiply numbers that are large enough to make it worthwhile. It cannot be speed.

As a training exercise, you can try to present the number as a list of numbers, with basic B being an input parameter.