Anonymous user
Talk:AKS test for primes: Difference between revisions
→This isn't AKS: added comments about testing 99,999,989 for primality.
(Found references to what they call "The AKS Test" in texts over 100 years old.) |
(→This isn't AKS: added comments about testing 99,999,989 for primality.) |
||
Line 26:
The time growth for an AKS implementation should be ~3-4x longer for each 10x input size increase. Testing 99999989 should be somewhere in the range of 10 seconds for C code implementing the algorithm from the v6 paper. This is of course all different by implementation, but this should give some clue.
:: ''Should be ... 10 seconds'' might be wishful thinking. The problem is not the CPU time used but the amount of (virtual) memory that is (will be) used. For the REXX test for 2,211, the biggest coefficient number computed was 668 decimal digits. Larger numbers caused the exhausting of virtual memory (the REXX that I use is limited to around 2 Gbytes). -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 08:55, 26 August 2014 (UTC)
An aside, I'm a bit confused by their talk, especially at the end, that "this is a fast test". It's ''ridiculously'' slow. Nobody uses this test in practice. It's very important in the theory, as it is deterministically polynomial time. But the constants are horrendously large. See, for example, [http://maths-people.anu.edu.au/~brent/pd/UMS10t4.pdf Brent 2010] "AKS is not a practical algorithm. ECPP is much faster." This includes run times of hundreds of years for numbers that ECPP does in a few seconds. [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 16:27, 21 February 2014 (UTC)
| |||