Talk:AKS test for primes: Difference between revisions
Repaired 25 September 2016 by WillNess – Thanks !
(Found references to what they call "The AKS Test" in texts over 100 years old.) |
(Repaired 25 September 2016 by WillNess – Thanks !) |
||
| (3 intermediate revisions by 3 users not shown) | |||
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)
::: 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)
Line 41 ⟶ 45:
:::: I agree with you on both of your complaints. I also have not seen implementations of the advanced versions (which, as you say, are not deterministic). - [[User:CRGreathouse|CRGreathouse]] ([[User talk:CRGreathouse|talk]]) 15:57, 25 February 2014 (UTC)
==Formulae rendered invisible to most browsers by cosmetic edits at 22:42, 28 August 2016==
Under-tested cosmetic edits, made to the task page at 22:42, 28 August 2016, have left the task description formulae completely invisible to all browsers which display the graphic file version of formulae rather than processing the MathML (this is, in fact, the majority of browsers). The MediaWiki processor does not currently expect the redundant spaces which were injected into <math> tags, and generates syntactically ill-formed HTML if they are introduced. Other aspects of these cosmetic edits may further compound the problem. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 08:48, 21 September 2016 (UTC)
: Repaired 25 September 2016 by [[User:WillNess|WillNess]] – Thanks ! – [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 16:36, 25 September 2016 (UTC)
| |||