How to boost efficiency for large number modulus multiplications in Python

Question

I am using python3 without any tailored library for some simple arithmetic. The operation that dominates computational efficiency is a multiplication of many 2048 bit values:

length=len(array)
res=1
for x in range(length):
       res=(res*int(array[x]))
       ret=res%n2

To give you an insight it takes ~3940 seconds to make 10000 multiplications moduli a number for every multiplication for an:

Intel Core i5 CPU M 560 @ 2.67GHz × 4 with 8GB of memory, running Ubuntu 12.04 32bit machine.

Would it make sense to boost it up using a library like gmpy2 or there would not be any advantage?

you can write your own function / class for multiplication using strings might not be the best way — advocateofnone
– advocateofnone, Commented Feb 18, 2015 at 12:57
there has to be a copy&paste error in your code. also, what is n2? — user3850
– user3850, Commented Feb 18, 2015 at 12:59
@curious: that Python is designed from the beggining, in 1991, to have for iterating over a sequence of items, not counting up numbers, and using those numbers as indexes to the items you should want in the first place, like in C or Javascript. thus Python is optimized -both in readability and performance to use for item in array: and not for x in range(len(array)): ... array[x] — jsbueno
– jsbueno, Commented Feb 19, 2015 at 13:38

nelfin · Accepted Answer · 2015-02-18 13:32:20Z

6

You seem to be calculating the product of all the numbers first then taking the remainder, rather than exploiting the properties of modular multiplication: a * b * c mod p == (a * b mod p) * c mod p. This takes very little time at all to multiply 10,000 2048-bit numbers modulo some n:

In [1]: import random

In [2]: array = [random.randrange(2**2048) for i in range(10000)]

In [3]: n = random.randrange(2**2048)

In [4]: prod = 1

In [5]: %%time
   ...: for e in array:
   ...:         prod *= e
   ...:         prod %= n
   ...: 
CPU times: user 210 ms, sys: 4.07 ms, total: 214 ms
Wall time: 206 ms

For you, I would suggest:

array = map(int, array)
prod = 1
for x in array:
    prod *= x
    prod %= n2

answered Feb 18, 2015 at 13:32

nelfin

1,0598 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

curious Over a year ago

What's the difference from your last snippet code compared with mine apart from the mapping ?Actually i am not doing what you are saying. i am producing intermediate modular products for each multiplication

nelfin Over a year ago

The difference is you calculate prod = prod * e and prodfin = prod % n on each iteration, whereas the second snippet I posted calculates prod = prod % n (which makes prod smaller, simplifying the multiplication without affecting the final result). If you really need the intermediate multiplicands, then you will suffer from the quadratic explosion of prod and moving to a C-based GMP library will give you only a multiplicative speed up at best.

Collectives™ on Stack Overflow

How to boost efficiency for large number modulus multiplications in Python

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related