News for hackers. Stuff that matters.
Re:Fast prime numbers by dalke on Friday February 18, 2011 @11:06AM (#2235932)
Where "fast" is defined as "involves disk reads" and "prime numbers" should have the qualifier "under 200." The algorithm is brute force testing of all values up to sqrt(n), which is worse than the one the ancient Greeks used.
Re:Fast prime numbers by stcredzero on Friday February 18, 2011 @11:17AM (#2235983)
If you want to deal with "real man's" prime numbers (those large enough to be used for secure cryptography) there are fast probabilistic tests which can quickly ensure confidence greater than the probability of your machine not getting blown up by lightning.

http://en.wikipedia.org/wiki/Primality_test

Re:Fast prime numbers by joemanaco on Friday February 18, 2011 @02:17PM (#2236803)
yes, it's brute force, and the there are much faster algorithms. I just wanted to show, that it's possible to move expensive calculations to compile time with C++ Templates.
Re:Fast prime numbers by dalke on Friday February 18, 2011 @06:06PM (#2237673)
Then the article is woefully mistitled. If I was doing this in C I would just write the code to generate a static table, so this isn't that useful of an good example except as very basic pedagogy. Also, you should show how the compiler time increases if you want it to compute, say, the 200th prime.
Re:Fast prime numbers by joemanaco on Friday February 18, 2011 @06:27PM (#2237726)
Hmmm, I'm thinking you're right. I've renamed it to "How to move prime calculation from execution to compile time". I hope this title fits better with the content.
Re:Fast prime numbers by dalke on Saturday February 19, 2011 @07:11AM (#2238917)
Hey, this is HN. We're supposed to argue and talk past each other with no changes in what we've done or believe. ;)

(And yes, it does fit better.)

Cheers.

Re:Fast prime numbers by IChrisI on Friday February 18, 2011 @11:23AM (#2236008)
Moving a slow algorithm to compile time, or precomputing it, does not make it faster. This title is wrong.
Re:Fast prime numbers by JoachimSchipper on Friday February 18, 2011 @11:12AM (#2235959)
Are you just submitting everything from your company's blog?
Re:Fast prime numbers by rkneufeld on Friday February 18, 2011 @11:53AM (#2236161)
Behold, MR.Prime!

https://github.com/rkneufeld/mr_prime

It's a little ruby Miller-Rabin primality tester I wrote with my friend in Crypto class that can handle ~500 digit primes in less than a few seconds. I think my friend also wrote a C extension for it - super fast.

Edit: spelling.

Re:Fast prime numbers by eqdw on Friday February 18, 2011 @12:04PM (#2236223)
IIRC, it was sub-second speed when he was done optimizing.

I wrote a non-optimized version of this in Ruby, ran in ~10sec. Then I rewrote it in C, and it was <1ms runtime for 20-100 digit inputs. Yay algorithms!

Re:Fast prime numbers by ajays on Friday February 18, 2011 @11:29AM (#2236034)
Such abuse of the templating system is why I dislike C++.
Re:Fast prime numbers by joemanaco on Friday February 18, 2011 @02:13PM (#2236778)
It's why I love C++ :-)