#10836: primitive root is broken
-----------------------------------+----------------------------------------
Reporter: kcrisman | Owner: was
Type: defect | Status: needs_review
Priority: critical | Milestone: sage-4.7
Component: number theory | Keywords:
Author: Karl-Dieter Crisman | Upstream: Reported upstream.
Developers deny it's a bug.
Reviewer: | Merged:
Work_issues: |
-----------------------------------+----------------------------------------
Comment(by kcrisman):
{{{
sage: for i in range(10^2):
....: n = randrange(10^50)
....: try:
....: primitive_root(n)
....: except:
....: pass
}}}
I've gotten big error rates on this in the old one - 70% or more of the
primitive roots were erroneous. Something like this takes 11 seconds in
both versions, though.
But there definitely is a slowdown for some numbers:
{{{
sage: sage: timeit('primitive_root(10^50+151)')
25 loops, best of 3: 17.6 ms per loop
sage: sage: timeit('pari(10^50+151).znprimroot()')
625 loops, best of 3: 1.46 ms per loop
}}}
Before, both took about the same amount of time.
Another data point, possibly irrelevant:
{{{
sage: timeit('try:\n primitive_root(randrange(10^60))\nexcept:\n
pass')
5 loops, best of 3: 97.9 ms per loop
sage: timeit('try:\n pari(randrange(10^60)).znprimroot()\nexcept:\n
pass')
5 loops, best of 3: 200 ms per loop
}}}
The variation is extremely wide on this, as one might expect, and
sometimes one is faster, sometimes another. I've gotten from 25 to 300 ms
for both commands, irrespective of before/after the patch. I did once get
1.85 ''seconds'' for the new primitive_root, so it seems it is sometimes
slower, but I also got as long as 1.24 s for the pari version, and neither
of these bad times came close to always happening - much more important
were the particular random numbers chosen.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10836#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en.
