-
Notifications
You must be signed in to change notification settings - Fork 1
Home
Here are a few notes about the code here and some things that could potentially be done with it.
Most of the code here is ported from programs at Peter Luschny's fast factorial page. I was learning Go, doing some Project Euler problems, and doing some Rosetta Code tasks and was intrigued by these amazingly fast algorithms.
Luchny has a nicely optimized prime number sieve. It's so simple and clean that it's really hard to beat, especially for the rather modest needs of say, Project Euler problems. I don't think any major changes would be appropriate to the code.
Another algorithm I found intriguing was Melissa O'Niell's sequential sieve.. It was fun to implement and runs plenty fast but can't compete with the low overhead of the Luschny sieve. Still, one improvement I worked on but never finished was a dynamic wheel sizer. The idea is that you typically know about how large of a prime you plan to generate, and for a given estimate, there is an optimal wheel size. So, just as with the constructor for a regular sieve, if you supply this target, the program can generate an appropriate wheel and use that.
Also intriguing was use of the Miller-Rabin algorithm for strong probable primes (SPRP) to deterministically test for primes up to some proven limit for a set of bases. It currently handles only 32-bit primes because the widest fixed width integer product available in go is 64 bits. Given that bases are known for testing all 64 bit primes, an obvious improvement would be to add a 64x64=128 bit multiply function. Oh, and a 128 % 64 = 64 bit mod function.
The fourth prime number algorithm here is a segmented sieve. It adds a little bit of cache awareness to make a nice speed improvement to the Luschny sieve for larger numbers of primes. This was inspired by Tomás Oliveira e Silva's Fast implementation of the segmented sieve of Eratosthenes. Still, I only used his cache observations. It would be nice to revisit this code and implement his factor selection algorithm, which makes it practical to sieve far greater ranges of primes.
Otherwise, if this is turning into a collection of prime number algorithms, there are plenty to add. Algorithms that are popular but simple-minded or otherwise bad might be nice to add for benchmark comparison. An Atkin's sieve would be nice, especially to see a point where it outperforms the segmented sieve.
Luschny has a parallel algorithm, but when I coded it, it didn't perform significantly better. You might speculate about overhead or primitive scheduling in Go, but really I think the algorithm doesn't have much margin for parallelization. It's multiplying a bunch of numbers, progressively larger ones, and so the final multiply of the two biggest numbers is going to dominate the total time. I suspect the biggest opportunity for speed up is parallelizing that final multiply. Go has a nice Karatsuba multiplier already, parallelizing even that one final multiply should represent a significant improvement for large factorials.
There's another problem though. The program currently stalls a little past 1e6! when implementations in Java and C can easily go to 1e8!. I'm afraid it's a garbage problem. It needs research.
I find the Split recursive algorithm amazing for competing so well with the prime number based algorithms, yet being very compact and not requiring prime numbers. I don't understand it well, but I wonder if the principles behind it could be used to make a fast binomial algorithm. Or maybe a fast MulRange for math/big.
This is currently not much more that a couple of functions needed by other packages in the integer tree here. There may be significantly faster algorithms out there. There are certainly much more comprehensive packages out on the internet that contain this sort of primitive functions.
OEIS. Working Project Euler problems, I wrote code to generate a number of OEIS sequences. I have no amazing algorithms or comprehensive set of these, but it might be nice to post what I have. I did a little bit of work on this. Not sure it's ready to post.
Factorization. I've written no code at all here, but I'd love to implement a GNFS.