On Sun, Dec 21, 2008 at 10:14 PM, Alasdair <[email protected]> wrote:
>
> These seem to be the offending lines from power_mod:
>
> apow = a
> while n&1 == 0:
> apow = (apow*apow) % m
> n = n >> 1
> power = apow
>
> Maybe the final line should be changed to
>
> power = apow % m
Possibly, since that would work. However, I outline what I think is
the right fix for this issue in the trac ticket, which is more than
just doing that. (And of course, it wold be nice to only do the
"power = apow % m" if necessary.)
>From the ticket:
---------------
Note above that power_mod(11,1,7) should return 4. The fix is to look
at the *pure python* code that defines power_mod in rings/arith.py
and:
1. change it to use some much more intelligent compiled code, i.e.,
either the powermod or powermod_ui methods when the first input
coerces to ZZ, and
2. when a doesn't coerce to ZZ, just revert to the existing Python
code, but make sure to throw in an {{{%m}}} somewhere before returning
the answer.
3. Add a doctest like this that illustrates non-integer input for
the first argument to power_mod:
{{{
sage: power_mod(3*x, 10, 7)
4*x^10
}}}
4. There is an inconsistency in that the Integer method for
power_mod is called "powermod" instead of "power_mod". I think the
Integer method should be changed, for consistency with the naming
conventions used throughout sage (namely, be generous with
underscores).
--------------------
Doing 1 above will result in major speedups. E.g., here is a simple
example where using the powermodm_ui method is over 15 times faster:
sage: timeit('power_mod(11,997,7)')
625 loops, best of 3: 74.1 µs per loop
sage: timeit('11.powermodm_ui(997,7)')
625 loops, best of 3: 4.71 µs per loop
sage: 74.1/4.71
15.7324840764331
William
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
