Continuous Python Multiplication

Question

I need an algorithm faster than the current normal long-running multiplication in Python.

I tried to find a decent implementation of Karatsuba, 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 can see, this is nothing complicated, just a few multiplications. But it has to process numbers with up to 100,000 digits in less than 2.5 seconds.

I need a function fragment or just a link to some implementation of a quick multiplication function or something that helps.

Answer 1

You could take a look at the implementation of the DecInt module (a clean version of Python (Toom-Cook) is available, although it will probably be the fastest when using gmpy ).

Answer 2

I am the author of the DecInt library (decimal integer), so I will make a few comments.

The DecInt library was specifically designed to work with very large integers that need to be converted to decimal format. The problem with converting to decimal format is that most libraries of arbitrary precision store values ​​in binary format. This is the fastest and most efficient way to use memory, but the transition from binary to decimal is usually slow. Converting Python to binary and decimal conversion uses the O (n ^ 2) algorithm and slows down quickly.

DecInt uses a large decimal place (usually 10 ^ 250) and stores a very large number in 250-digit blocks. Converting a very large number to decimal format is now done in O (n).

A naive or cool school, multiplication has a run time of O (n ^ 2). Python uses the Karatsuba multiplication, which has an O (n ^ 1.585) run time. DecInt uses a combination of Karatsuba, Toom-Cook, and Nussbaumer convolutions to get O (n * ln (n)) runtimes.

Although DecInt has much higher overhead, the combination of O (n * ln (n)) multiplication and O (n) transform will ultimately be faster than Python O (n ^ 1.585) and O (n ^ 2) multiplication conversion.

Since most calculations do not require each result to be displayed in decimal format, almost every library uses binary code with arbitrary precision, as this simplifies the calculation. DecInt targets a very small niche. For sufficiently large numbers, DecInt will be faster for multiplication and division than native Python. But if you are after pure performance, a library such as GMPY will be the fastest.

I'm glad you found DecInt useful.

Answer 3

15.9 ms on my slow laptop. This is a seal that slows you down. Converting binary numbers to decimal numbers is quite slow, which is a necessary step for printing it. If you need to display the number, you should try the already mentioned DecInt ChristopheD.

DecInt will slow down multiplication, but make printing a lot faster.

 In [34]: a=2**333000 In [35]: len(str(a)) Out[35]: 100243 In [36]: b=2**333001 In [37]: len(str(b)) Out[37]: 100244 In [38]: timeit c=a*b 10 loops, best of 3: 15.9 ms per loop 

Here is an example with a slightly modified version of your code. Note that converting a string of 100,000 characters to long already takes ~ 1 second on this computer.

 In [1]: def f(a): ...: if(a<0): ...: a=a*-1 ...: a=((a*(a+1)/2)-1) ...: else: ...: a=(a*(a+1))/2 ...: return a ...: In [2]: a=3**200000 In [3]: len(str(a)) Out[3]: 95425 In [4]: timeit f(a) 10 loops, best of 3: 417 ms per loop 

Answer 4

I suggest you get the Sage math tool , which has almost every Python math tool ever made in one package. See if Sage has a good, fast, precision accuracy math tool that suits your needs.