Power with modulu

[Bengt Richter]

On Sun, 05 Dec 2004 12:59:40 +0200, Roie Kerstein <sf_kersteinroie at bezeqint.net> wrote:

>Hello!
>
>I want to compute a**b%c for very long numbers.
>Computing a**b and then applying modulu is not practical, since it takes
>ages.
>There is a built-in optional parameter to the long.__pow__(a,b[,modulu]),
>and it works well.
>My question is: How can I write it is a form of an expression, like a**b?
>I prefer not to fill my script with calls of the form long.__pow__(a,b,c).
>
You could subclass long to use a fixed modulus stored as a class variable,
and make a factory function to return a class for a particular modulus, e.g.,

 >>> def mmod(modulus):
 ...     class M(long):
 ...         def __pow__(self, p):
 ...             return type(self)(long.__pow__(self, p, self.modulus))
 ...         def __repr__(self): return 'M(%s %%%s)'% (long.__repr__(self), self.modulus)
 ...     M.modulus = modulus
 ...     return M
 ...
 >>> M  = mmod(7)
 >>> M
 <class '__main__.M'>
 >>> M(2**55)
 M(36028797018963968L %7)

note that print will use the __str__ method of the underlying long
 >>> print M(2**55)
 36028797018963968
 >>> print M(2**55)**1
 2

I made the power operation return the same type
 >>> M(10)
 M(10L %7)
 >>> M(10)**1
 M(3L %7)
 >>> M(10)**2
 M(2L %7)
 >>> M(10)**3
 M(6L %7)
 >>> M(10)**4
 M(4L %7)

But if you use another operation, the result will be converted to the dominant type,
since the only operation I overrode was __pow__. But you could override them all, by hand
or automate the wrapping with a metaclass.

 >>> M(10)**4 *1
 4L
 >>> M(10)**4 +0
 4L
 >>> M(10)**4 +0.0
 4.0
 >>> M(10)**4 *1e1
 40.0

You could also make M take an optional initialization parameter to override what's set with mmod.
Or if you override all the time, not bother with mmod. Depends on what you need & how you are
going to use the stuff.

Regards,
Bengt Richter