Million Digits of E, Sqrt(2), Pi
More puzzles, more fun.
Besides acm oj and projecteuler, i also like to solve the puzzles on spoj. The ACM/ICPC rules are rather limited -- you have to submit the src code (only one file) in java or c/c++. ProjectEuler is much more free: it just accepts the final answer -- you are free to use any tools/langs as you like. Spoj stands kinda in between: it still accepts a one-file-src but you can use a lot of languages (just to name a few: bash, perl, lua, lisp, python, haskell, c, asm, etc.). In other words, it's hard to not to find your favorite language there. But you cannot use any external src or libs (only standard feature or lib of the langauge is allowed).
Among many interesteting puzzles, spoj has some challenge problems. These problems are not simply checked right-or-wrong. Instead it makes the rank based on its problem-specific scoring: usually precision, sometimes code-length. Take the following three for example:
The rules are same: given limited time and code-length, calculate the value in as many decimal digits as possible.
All three problems involve arbitrary-precision computations -- you either implement your own FFT or use those languages that have bignum built in (like java, python or haskell).
- Digits of e -- just use the Taylor expansion with Binary-Splitting.
- Digits of sqrt(2) -- Newton iteration (note that each iteration doubles the precision).
- Digits of pi -- use Chudnovsky series with Binary-Splitting.
For the underlying magic algorithms, see the those wonderful papers/docs. Here's a reference implementation for pi digits using gmp -- claims to be the world's fastest -- for as many as billion digits. Also, mpmath has some interesting implementations as well.
I myself dont bother to implement a FFT in c/c++ (and i doubt i could write a fast enough version in 4K code). Python is really slow for this (sorry, sad, but true) . Haskell's Integer is using the fast(est) gmp. Not only it's fast, it's very convenient and leads to (much) shorter and cleaner code. You can see the ranks. Also specific ranks in your favorite languages.
Other interesting ones might be:
- Make the src as short as possible. Perl is the ruler for this. But you can try to be the top 1 on a specific language ranking.
- Compress and uncompress in one file. The hard part is how to dump the compressed data in src file.
- Magic Markov. Write code to generate code, with special craft.
