New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
primitive root is broken #10836
Comments
comment:1
From one of the Pari developers:
|
Changed upstream from Not yet reported upstream; Will do shortly. to Reported upstream. Developers deny it's a bug. |
comment:2
Ergo, we will have to catch such cases in an effort to remain mathematically correct. |
comment:3
Pretty easy to fix but there are some choices regarding speed and whether we now believe in pari's ispower function.
Long story short, Integers(n).multiplicative_generator is very fast for primes, but otherwise slow. Trying to mix the two (using multiplicative_generator for primes and pari for everything else) winds up being slower than pari for small primes and faster for large ones; could branch on size but not sure if the speed benefit would be worth the complexity. I don't have a good sense for Python overheads at the microsecond level. |
comment:4
From some correspondence with myself, William, and the Pari team, where it becomes clear that their implementation has the rather useful virtue of being very very fast:
So we will keep using their very fast function and wrap it with something that checks for sensible input, but adding documentation like
to the documentation for our |
Author: Karl-Dieter Crisman |
comment:5
Well, I have a provisional patch, but because I am very unfamiliar with how gp/GP/Pari/PARI interact with Sage, this might be really kludgy. Also, I have observed the following perplexing behavior in testing (in Sage or Pari):
Should this size difference really make such a huge difference? I would estimate the second computation took about a second. The slowness is all in Pari, too; in Sage I get the same thing. I would think these were not such large numbers.
This also happens in Sage 4.6.2, so it's nothing unusual. Am I just getting unlucky with numbers that have really big primitive roots? Maybe; I just put a problem to that effect on a take-home exam... On the other hand, when I quit after having done these breaks, I get
type stuff, so maybe I'm not crazy. Anyway, for the purposes here, the problem is finding a doctest where the Sage version takes a long time without the Pari one taking a long time. I tried lots and lots of things. Any ideas? Anyway, maybe this patch is better than WRONG answers, so here is a patch to look at. |
Attachment: trac_10836-primitive.patch.gz |
comment:6
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:
Before, both took about the same amount of time. Another data point, possibly irrelevant:
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. |
comment:7
Hopefully someone can review this during Sage Day 29? It's mathematically wrong currently... |
comment:8
I think maybe there's a little too much duplication with all the branches? ISTM it's simpler to implement the condition exactly from the definition given, with something like
where each condition group matches exactly one of the classes of allowed arguments in the docstring. I find this is also marginally faster on average for successful calls. But I think we should check n for the existence of a primitive root before we call pari, because when testing it I came across this (4.6.2):
Similarly for 2465, 3458, 4930. This is a pari bug not an interface bug, as working directly with the console shows the same issue. |
comment:9
If you can find a quicker way to write that, this is fine. I was hoping to speed things up by checking certain cases first, such as primes. Branching can be confusing, you are right. More precisely, it's what Pari claims is user input error. I actually explicitly didn't do this because we didn't want to slow down the checking of primitive roots for legitimate input, which this would do for huge numbers - that is the whole idea behind Pari's thinking. At this point, I'd appreciate the input of someone who actually needs primitive roots of huge numbers! The question is whether we want the bottleneck with legitimate or non-legitimate input. If it really is that long for a four-digit number, maybe we go with your idea; that's pretty bad. |
comment:10
Well, it hasn't stopped after half an hour.. I don't quite follow you about the speed, though. Before every "return ans" for n > 5 you either (1) test primality, (2) test for a prime power, or (3) once again test for a prime power, so ISTM you're not avoiding the cost of doing the tests on legitimate input, you're just doing it after the znprimroot call instead of before. (And we get very similar times for large legitimate input, which is what I'd expect if I'm right.) If we really want a super-fast way to do this when needed -- and like you I suspect, I have zero need for primitive roots of huge numbers so I have no idea if this matters at all in practice |
comment:11
Yes, you are right about this. I forgot that the number isn't actually returned until then :) Yeah, I thought about proof=False, but wanted to keep it short to start - adding keywords sometimes turns into a mess. If you want to post a second patch with these ideas, we can review it jointly very easily. To me, it's half a dozen of one and six of the other, although I am surprised myself about
taking so long. |
comment:12
Wow, regarding
That's seriously messed up! This is a case where there is no primitive root. So it's the "undefined" behavior mentioned in the pari docs -- just take forever. Anyway, looking over this thread, it seems to me that the docstring in the patch is very good as is, but the code should be completely changed to only call pari after explicitly checking the condition for there to be a primitive root (as explained in the docstring). |
Attachment: trac_10836.patch.gz apply only this patch |
Changed author from Karl-Dieter Crisman to Karl-Dieter Crisman, William Stein |
comment:14
Nice use of Should we throw a better error message than
for non-integer input? Or is it enough to say that there isn't a primitive root? I guess same question for negatives. "No primitive root" seems somewhat cryptic. Putting 'needs info'; I can also upload a reviewer patch if you think that's okay. We would check for that after we actually got the primitive root, so it wouldn't slow anything down. Otherwise the patch looks good, and if William thinks |
Reviewer: William Stein, Karl-Dieter Crisman |
Apply only this patch |
This comment has been minimized.
This comment has been minimized.
comment:18
Attachment: trac_10836.2.patch.gz Had to fix one tiny thing for the note to look right. Positive review. Apply only attachment: trac_10836.2.patch. |
Changed author from Karl-Dieter Crisman, William Stein to Karl-Dieter Crisman, William Stein, Jeroen Demeyer |
This comment has been minimized.
This comment has been minimized.
comment:20
My additional patch needs review. |
Attachment: 10836_additional.patch.gz |
comment:21
Whoah, Nelly! I see the 'niceification'. But two points.
|
comment:22
Replying to @kcrisman:
Well, I think we should decide what we do with negative integers: either raise an exception or return a sensible value. It seemed artificial to me not to allow negative numbers. Also PARI/GP computes primitive roots of negative numbers. |
comment:23
Well, what we say does refer to just multipl. gp. mod n, so ok. But should definitely make sure not to say we give smallest prim root. So 'needs work' to fix that. But this is pretty bad not to have fixed, so let's try to get it in asap. |
comment:24
Replying to @kcrisman:
Why not? If you things like "this is pretty bad not to have fixed", at least say why. |
comment:25
Replying to @jdemeyer:
Because the PARI documentation says that it no longer gives the smallest prim root, except for primes. Or at least the changeset I saw a while ago says this - please don't ask me to find it. Presumably something about the internal algorithm changed? Oh, I see what you mean now! "Pretty bad to not have fixed" meant the actual ticket. Wrong mathematics! Not the tiny change I am mentioning above. I'm sorry for the possible misinterpretation. |
comment:26
Replying to @kcrisman:
But this is consistent with my patch. In this patch, I write "If |
Changed reviewer from William Stein, Karl-Dieter Crisman to William Stein, Karl-Dieter Crisman, Jeroen Demeyer |
comment:27
My humble apologies. I don't know why I thought it said "A primitive root of That means we should, in theory, fix " and "assumed to be a positive integer possessing a primitive root" But I agree that unless it's very easy to update the patch for this, this should go in. So I'm inclined to put positive review. Docs look right, still passes tests. |
comment:28
Replying to @kcrisman:
Actually, I think both of these statements are 100% correct in the patch.
Here, we are talking about exponents which are allowed to be zero, so this is correct.
This is also correct because PARI's behaviour for negative arguments to |
comment:29
I clearly need more sleep. You're right on the second count, and I copied the wrong thing on the first count: "A primitive root exists if Which in theory then should say something about |
Merged: sage-4.7.alpha4 |
Pari has a major bug in its primitive root:
Note that this DOES work correctly with whatever Pari is in Sage 4.4.4.
Apply attachment: trac_10836.2.patch and attachment: 10836_additional.patch.
Upstream: Reported upstream. Developers deny it's a bug.
CC: @williamstein @adeines
Component: number theory
Author: Karl-Dieter Crisman, William Stein, Jeroen Demeyer
Reviewer: William Stein, Karl-Dieter Crisman, Jeroen Demeyer
Merged: sage-4.7.alpha4
Issue created by migration from https://trac.sagemath.org/ticket/10836
The text was updated successfully, but these errors were encountered: