mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2019-12-23, 15:38   #1
pxp
 
pxp's Avatar
 
Sep 2010
Weston, Ontario

191 Posts
Default PRP-test issue

A PRP-test on a 74685-digit Leyland number submitted December 21 is still "in queue" two days later while a 76029-digit Leyland number submitted four hours later got PRP'd within the day.
pxp is offline   Reply With Quote
Old 2019-12-25, 18:44   #2
DukeBG
 
Mar 2018

3×43 Posts
Default

There are 9,068 PRP tests queued right now. Someone is overzealous with that button. FactorDB shouldn't be forced to PRP numbers that big. Anyone is better advised to run such PRPs on their own hardware.
DukeBG is offline   Reply With Quote
Old 2019-12-25, 22:07   #3
pxp
 
pxp's Avatar
 
Sep 2010
Weston, Ontario

191 Posts
Default

Quote:
Originally Posted by DukeBG View Post
There are 9,068 PRP tests queued right now. Someone is overzealous with that button. FactorDB shouldn't be forced to PRP numbers that big. Anyone is better advised to run such PRPs on their own hardware.
FactorDB has a built-in limit on the size of numbers it is willing to PRP so it isn't forced to do anything. As to the number of tests in the queue, I don't know how they come about or how big the numbers are but I have never had a PRP test on a number (and I have submitted one every three or four days on average for the last four years) take more than a few hours. And I run the PRP tests in Mathematica before I ever try them in FactorDB so I already know their status. The FactorDB result is simply a clickable reference to the number in an online compilation.

But you're missing the point. There is a number supposedly "in queue for a PRP-test" since 21 December 2019 but I have added four more numbers to that queue since then (two just yesterday) and all four have been PRP'd in a matter of hours. So the number "in queue" is apparently not really in queue since it has become obvious that it will never get to the front. It was this matter to which I wanted to bring attention in case anyone else had a similar experience.
pxp is offline   Reply With Quote
Old 2019-12-26, 03:58   #4
axn
 
axn's Avatar
 
Jun 2003

23×607 Posts
Default

FactorDB PRP queue is LIFO. So the ones that are submitted recently gets processed before the older ones. Currently 9043 numbers are in queue. Noone knows where your number is within that queue. When the queue runs down to 0, yours would have been done as well.

Go to http://factordb.com/status.php and look at the pending column against the "Combined N-1/N+1-method" line (under Primality Proofs section) to keep track of the queue size.

Oh, and btw, when there are certificates to be processed, that gets priority, so the PRP queue will have to wait even further.
axn is online now   Reply With Quote
Old 2019-12-26, 04:12   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

59×103 Posts
Default

Quote:
Originally Posted by axn View Post
FactorDB PRP queue is LIFO.
That's a stack.

Perhaps the confusion here is the incorrect term "queue".
retina is online now   Reply With Quote
Old 2019-12-26, 04:44   #6
axn
 
axn's Avatar
 
Jun 2003

23·607 Posts
Default

Quote:
Originally Posted by retina View Post
That's a stack.

Perhaps the confusion here is the incorrect term "queue".
You're correct. That is not the expected behavior of "queue", but it is what it is. Note that factor db itself doesn't use any terminology -- it is just a term that we used in the discussion.
axn is online now   Reply With Quote
Old 2019-12-26, 13:59   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·13·83 Posts
Default

I also tried finding the number on the list of numbers with unknown status. I eventually succeeded, and also found an obviously-related number. The list is sorted by number of digits only. I had to resort to trial-and-error to fill in the "Digits" field to bring the requisite number of digits into range. The filled-in fields didn't copy-paste; I had to fill them in in the quoted portion.

Why the number of digits that worked, worked, is a mystery to me.

Quote:
Select range
Type U
Digits 74537
Per page [1..5000] 100
Skip first [0..50000] 49800

<snip>

1100000001419038845 3927^20780+20780^3927<74685> 74685
1100000001124344011 (2^248137+1)/2466453988659<74685> 74685
1100000001095527907 ((42^23008+1)^2-2)/189744822551<74685> 74685
1100000001285702986 7876323509...29<74685> 74685
1100000001197804384 3672515801...31<74685> 74685
1100000001233661196 (2^372156+1)/(2^124052+1)/241<74685> 74685
1100000001236671432 1683512024...11<74685> 74685
1100000001420823039 (3927^20780+20780^3927+1)/2<74685>
<snip>
Dr Sardonicus is offline   Reply With Quote
Old 2019-12-31, 13:40   #8
MDaniello
 
MDaniello's Avatar
 
May 2019
Rome, Italy

5×7 Posts
Default

That massive number of tests in stack made me wonder if someone was "clearing" some digit interval in the Unknown status list. Given that is taking a really long time to test those numbers, they should be far down the list. (Question: is PRP testing time exponential in number size? By size i mean digits)

By looking at the distribution graph i found this.
I then checked some numbers in the list on either side of the dips in the graph for PRP button availability: The numbers between 149012 and 149142 digits are in the stack, while numbers above 149159 digits are not. (Apparently, you can't PRP test numbers with 150 kilodigits and bigger)

Of course i didn't check each number, just randomly sampled them in those intervals. Because the bulk of the numbers are beetween 149041 and 149142 digits (around 100 bins, and for each bin we have numbers in a range from 30 to 70, the total number of numbers (sorry for the repetition) is expected to be beetween 3000 and 7000. So, either i missed something/overapproximated in my back-of-the-envelope calculation, or a significative part, but not all of the numbers in th stack, are >149 kilodigits.
MDaniello is offline   Reply With Quote
Old 2019-12-31, 13:55   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×5×359 Posts
Default

Quote:
Originally Posted by MDaniello View Post
(Question: is PRP testing time exponential in number size? By size i mean digits)
It is O(log(n)^2*log(log(n))) (if my memory serves me correctly). A rule of thumb is if the number is twice as long it takes 4 times as long to PRP test.
paulunderwood is online now   Reply With Quote
Old 2020-01-01, 12:06   #10
DukeBG
 
Mar 2018

100000012 Posts
Default

Quote:
Originally Posted by axn View Post
Note that factor db itself doesn't use any terminology -- it is just a term that we used in the discussion.
Are you sure?

But I agree that not only this should have been called a stack, or rather actually implemented as a queue, not as a stack, it also should have been auto-reordered to have smallest numbers served first, like it actually does for primality certificates processing. Oh well.

Quote:
FactorDB has a built-in limit on the size of numbers it is willing to PRP so it isn't forced to do anything.
Sure, it has a size limitation, but just because it's capable of doing some PRP tests in reasonable time doesn't mean it should.

If you've only submitted these two numbers, that's no problem. Someone else who submitted 9K numbers (by which i mean "added to the queue for PRP processing"), a lot of which, I presume, take 10-20 minutes each, is a problem. There's always more than enough smallest "status=unknown" numbers for FDB to auto-work on, people asking for their numbres to be worked on first is an avenue I believe should be much more limited. Or uploading residues should be implemented in some way, though I don't think there's a reliable way to check them without doing a full test again which kinda defeats the purpose.

Last fiddled with by DukeBG on 2020-01-01 at 12:09
DukeBG is offline   Reply With Quote
Old 2020-01-01, 13:04   #11
axn
 
axn's Avatar
 
Jun 2003

113708 Posts
Default

Quote:
Originally Posted by DukeBG View Post


Quote:
Originally Posted by DukeBG View Post
it also should have been auto-reordered to have smallest numbers served first, like it actually does for primality certificates processing. Oh well.
There is one use case where it makes sense to do the latest one first --when we have a PRP and we want to do another prp test on it with a different base interactively, we want it to be done immediately instead of going into a queue. Otherwise I agree.

Quote:
Originally Posted by DukeBG View Post
There's always more than enough smallest "status=unknown" numbers for FDB to auto-work on
FactorDB auto PRP test is limited to < 20,000 digits. Why? The numbers around this size takes 5-10 seconds only. IMO, it should've auto worked on everything under 100k digits (smallest ones moving to the top of the queue, natch). Currently, the only way to make FactorDB work on these smaller unknowns is to submit them.
axn is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
DC performance issue cuBerBruce Information & Answers 2 2017-07-10 13:43
GWNUM issue ET_ Software 4 2017-06-15 09:52
32/64 bit gmp-ecm issue... WraithX GMP-ECM 15 2016-12-19 17:42
That's odd ... ubuntu-13.10 ecm issue fivemack GMP-ECM 12 2015-06-05 02:02
Torture Test Issue xavion Software 5 2003-07-08 02:10

All times are UTC. The time now is 07:02.

Sat Feb 27 07:02:40 UTC 2021 up 86 days, 3:13, 0 users, load averages: 1.54, 1.71, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.