Monday 18 December 2017

python - How to multiply big numbers faster?

itemprop="text">

I was experimenting with multiplying
large numbers in python. For my purpose I was trying to evaluate.




2*odd*(4*odd^2 + 7)/3
- 6*odd^2 - 3


Now my
question boils down to how to multiply numbers faster in python. is it faster to do it
with float? The answer seems no. Take a simpler example with





n*(n+1)/2




My
idea was that the following code is
faster




product =
1
if n % 2 == 0:
product *= n/2
product *=
n
else:
product *= (n+1)/2
product *= n
return
product



Why
would this be faster? Well you would not have to divide the huuge number
n*(n+1) by two. However one does waste a calculation checking
the number modulo2. Perhaps try exception is faster?



So my question boils down to. How does one
compute the product and division of very large numbers in python? Here is my working
code. Not asking for specifically speed improvements on this code. But the more broad
question on how to deal with division and multiplication of large numbers. My numrange
is around 10^(10^6)
atm.



def
spiral_sum_fast(num):
rem = num % 6
if rem % 2 == 0:

raise Exception("The sidelength must be a odd number")
odd = 1 + num /
2

odd_squared = 2 * odd**2

if rem % 3 ==
0:
temp = odd / 3
temp *= 8 * odd_squared + 14

else:
temp = (4 * odd_squared + 7) / 3
temp *= 2 * odd

return temp - 3 * odd_squared - 3



if __name__
== '__main__':

k = 10**(10**6) + 1

spiral_sum_fast(k)

class="post-text" itemprop="text">
class="normal">Answer



In general
you should specialised libraries for specialised jobs. In your case dealing with large
numbers and getting optimal speed might require this. Have a look at this this href="http://jasonstitt.com/c-extension-n-choose-k" rel="nofollow">blog
which deals with big numbers and makes speed comparisons between pure Python and using
the GNU Multiple Precision Arithmetic
Library
from Python, which results in a big performance improvement.


No comments:

Post a Comment

php - file_get_contents shows unexpected output while reading a file

I want to output an inline jpg image as a base64 encoded string, however when I do this : $contents = file_get_contents($filename); print &q...