On Mon, Jun 8, 2009 at 7:13 PM, <[email protected]> wrote: > By the way, my discussion about "perfect power" is simply my > attempt to: > > 1. improve my limited J knowledge. > 2. Attempt to re-implement the AKS primality algorithm in > J.
That would be fine, but I would ignore efficiency concerns in this case and go for simplicity and accuracy instead. > I did think "Detecting Perfect Powers in Essentially Linear > Time" would give me a fast routine. > I guess it rather means, it would in be the fastest > implementation > in that particular language whether it the language is Java, > C/C++, matlab or J. > > Am I wrong in thinking this? Yes, actually, I think you are overlooking two issues: [1] Linear time talks about the rate of growth in time of an algorithm as some other element grows. But it talks about the slope of the curve and not the magnitude at any point on the curve. Hypothetically, a linear curve will eventually fall below increasing curves, but computers are finite, and constant factors may mean that this never actually happens before exceeding the capacity of the computer. [2] That this algorithm is "almost linear" does not automatically mean that other algorithms are worse. But if you are in this for learning, these issues should not be obstacles -- instead they become avenues of investigation. FYI, -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
