Python long multiplication

Question

I'm in need of an algorithm faster than the current normal Python long multiplication.

I tried to find a decent Karatsuba implementation, but I can't.

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

As you see, it's nothing complicated, just a few multiplications. But it has to handle numbers with up to 100000 digits in under 2.5 sec.

I'd like some snippet of a function or just a link to some implementation of a faster multiplication function, or anything that helps.

Answer 1

I'm the author of the DecInt (Decimal Integer) library so I'll make a few comments.

The DecInt library was specifically designed to work with very large integers that needed to be converted to decimal format. The problem with converting to decimal format is that most arbitrary-precision libraries store values in binary. This is fastest and most efficient for utilizing memory but converting from binary to decimal is usually slow. Python's binary to decimal conversion uses an O(n^2) algorithm and gets slow very quickly.

DecInt uses a large decimal radix (usually 10^250) and stores the very large number in blocks of 250 digits. Converting a very large number to decimal format now runs in O(n).

Naive, or grade school, multiplication has a running time of O(n^2). Python uses Karatsuba multiplication which has running time of O(n^1.585). DecInt uses a combination of Karatsuba, Toom-Cook, and Nussbaumer convolution to get a running time of O(n*ln(n)).

Even though DecInt has much higher overhead, the combination of O(n*ln(n)) multiplication and O(n) conversion will eventually be faster than Python's O(n^1.585) multiplication and O(n^2) conversion.

Since most computations don't require every result to be displayed in decimal format, almost every arbitrary-precision library uses binary since that makes the computations easier. DecInt targets a very small niche. For large enough numbers, DecInt will be faster for multiplication and division than native Python. But if you are after pure performance, a library like GMPY will be the fastest.

I'm glad you found DecInt helpful.