Right after I switched to Ruby with respect to solving ProjectEuler.net problems, I realized that there's actually no number-theoretical Ruby libraries at all. Of course, I could just turn to some more advanced tools like PARI-GP or switch to, say, Python which has nzmath library. But: 1) I love Ruby. 2) Number-theoretical algorithms are themselves useful to know and understand for I'm sorta mathematician ;-)
Thus I decided to write my own library. And now, I suppose, it even might be useful for somebody else.
Well, what has been implemented so far?
- Eratosphenes sieve
- Factorization by trial division.
- Common multiplicative functions: moebius, sigma, phi, pi.
- Jacobi symbol
- Powermod (works with negative powers also whenever the inverse exists)
- N-th fibonacci number
- Fast factorial computation by PrimeSwing algorithm
- Multiplicative order
- Miller-Rabin primality test
The gem is at rubygems.org/gems/ruby-numtheory; Thanks to the existence of rake-compiler, precompiled version for Windows is also available.
The features to be implemented in the near future are some more primality tests (I hope I will eventually understand AKS), and roots modulo n (at least Tonelli-Shanks algorithm). Maybe, something else.
No comments:
Post a Comment