Anonymous user
Talk:AKS test for primes: Difference between revisions
→This isn't AKS
(→This isn't AKS: added comments about testing 99,999,989 for primality.) |
|||
Line 28:
:: ''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)
::: That's because "the algorithm from the v6 paper" referenced above is completely different from what this task implements. I can list at least one implementation of the v6 algorithm that take 10-20k and ~10 seconds to do this, and never use a number larger than a native int (32 or 64 bit). As an aside, using AKS improvements gets it down to under 1k and a few milliseconds. Eventually AKS does start taking large amounts of memory, but the improvements help a lot and overall speed becomes the bottleneck. [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 19:10, 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)
| |||