Feature: add multiplication by modulo: e.g. mulm

[GoogleCodeExporter]

There is a possibility to divide a/b mod m.
How about introduction of a*b mod m?

Likely the operation will be more affective then a*b and then division by 
modulo.

Original issue reported on code.google.com by Oleg.Kli...@gmail.com on 10 Oct 2012 at 9:16

[GoogleCodeExporter]

I've tried this in the past and the overhead for invoking a 3 argument function 
is greater than evaluating an expression like (a op b) % m. If a and b are less 
than m, then there isn't a more efficient way to calculate (a*b) mod m easily 
available in GMP. It may be more efficient if a and/or b are much greater than 
m, or if I create a new number type where all calculation are reduced mod m.

I'll let you know if I do any experiments.

Original comment by casevh on 11 Oct 2012 at 4:21

• Changed state: Accepted
• Added labels: Type-Enhancement, Priority-Low
• Removed labels: Type-Defect, Priority-Medium

[GoogleCodeExporter]

And for the case you describe, theoretically the calculation might be 
comparable to [ (a mod m) * (b mod m) ] mod m...
Well, even for comparable a / b / m, it possibly can be optimized, similarly to 
the algorithm for power calculation - value b can be represented as a bit-mask, 
and a can be multiplied by b, bit by bit (each time on 2 power bit #), each 
time taking mod operation.
Hard to say, experiments needed. Would be interesting to know the results, if 
you will perform such.

Original comment by Oleg.Kli...@gmail.com on 11 Oct 2012 at 8:58

[GoogleCodeExporter]

I'm starting to look at changes to make for version 2.1. I've thought of three 
different approaches to support modular arithmetic.

1) Add function addm(), mulm(), etc. that accept three arguments. This is 
probably the easiest version but the function lookup overhead make this slower 
that the trivial code: (a+b)%m.

2) Use the context manager that is normally used to control floating point 
arithmetic and add a modulus option to the context. For example:

with gmpy2.local_context(modulus=100):
    x = 60 + 70  # x is 30

3) Create a new integer type mpzm that initialized with a value and modulus. 
Arithmetic with two mpzm instances would return another mpzm instance but mixed 
mpzm/other_integer_type arithmetic would return an mpz. It would most likely be 
an error if the modulus of the two mpzm instances were different.

Do you have any opinions on the three options?

Thanks for any feedback!
Case

Original comment by casevh on 15 Apr 2013 at 3:52

[GoogleCodeExporter]

I would rather prefer the 1st alternative - it's more flexible from the point, 
if you would like at some point to make their implementation different - 
optimized somehow, compared to "normal" 'add' and other calls.

I also don't think that function lookup overhead will be that significant so it 
should be taken into account, and even then, I doubt that such overhead will be 
higher than in alternatives 2 and 3.

About other alternatives, I've the following thoughts - which might be wrong, 
you know better how it really works :)
Alt. 2 puts responsibility to put the correct modulus on the user - it might be 
easier for implementation n gmpy side, but might be non-trivial for user of 
gpmy to put the right modulus and might require extra actions to determine it 
first. For example, when using float type, I spent quite a few minutes to 
understand, why the result was wrong, until I realize that I need to tune the 
context.
Alt.3 could easily lead to the errors, as I see it. Like in Alt.2 it will be 
necessary to put modules (which should be known first), then to "control" on 
the "user" side that it is the same modulus in all places, and if accidentally 
in run-time it will be so that one of the values have higher modulus, what's 
then - convert all other values, handle such case in gmpy, ...?

Because of reasons above, I would prefer alt.1, which is more "friendly" 
compared to others.

Original comment by Oleg.Kli...@gmail.com on 15 Apr 2013 at 7:47

[GoogleCodeExporter]

Thanks for your comments. I will implement option 1. I'll try a combination of 
options 2 and 3 as an experiment to see if it really is faster. If you don't 
mind testing, I'll let you know when I have something suitable for testing.

Original comment by casevh on 16 Apr 2013 at 5:27

[GoogleCodeExporter]

No problem, I can look into - at least for "mulm", which I wanted some time 
ago. I still have a source of program, where the multiply by modulo was needed, 
and can compare earlier version with the new version of library, once it is 
ready.

Original comment by Oleg.Kli...@gmail.com on 16 Apr 2013 at 5:48

[GoogleCodeExporter]

I'd definitely vote for option 3. Basically I want to work with a fix modulos.

Be very careful on conversion though. I suggest mpzm + mpz raise an error, and 
one has to use a function to convert mpzm to mpz

I'd suggest an option 3+: an mpzm with m a prime. This should save a lot of 
work. (Z/p is a field, Z/m is just a ring. Everything is invertible mod p 
unless it is 0 mod p.) 

Some people may also want mpzm with m a power of 2. 

Original comment by temp.us...@gmail.com on 27 Apr 2013 at 5:47