Another interesting problem I solved recently on SPOJ was EVAL (Digits of
e). It is a challenge problem, and it involved printing the largest number of digits of e as possible (upto 1 million digits), within the time-limit of 25 seconds. (SPOJ processors are single core 733 MHz Pentium III processors AFAIK).
As far as I know, there is no way to actually find the digits, than using one of the series used for finding the value of e. One of the series is, Taylor’s series.
e(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ..
Thus, the value of
e, can be calculated by substituting x=1. However, to obtain the value accurately upto 1 million digits is no small task. It requires arbitrary floating point ops.
Let me paint the picture better. The
M_PI constant in C++ is correct upto 17 digits. Using Taylor’s series and the long double datatype, you can get to only 19 digits.
I resorted to Python, and the its in-built bignum library using the Decimal module. Using the Brother’s series expansion, the best I could get was a little more than 1000 digits, when using psyco.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Then, I switched to Ruby, and used the BigDecimal module to get nearly 30k digits in time.
1 2 3 4 5 6 7 8 9 10 11
However, I think I can do much better in C++ if i have a good arbitrary-precision floating point operations library.
Any suggestions and pointers to better solutions are invited.