Serge D. Mechveliani wrote:
Who can tell, please, how read string :: Integer is implemented in ghc-7.4.1 ? Is it linked from the GMP (Gnu Multi-Precision) library?
I believe your numbers simply were not large enough. I changed strs n to be strs n = if n == 0 then [""] else [d : ds | ds <- strs (pred n), d <- digits] (which changes the answer but avoids holding on to tons of memory) and ran the program for m = powers of 2 up to 128: 1 real 0m0.392s 2 real 0m0.447s 4 real 0m0.575s 8 real 0m0.995s 16 real 0m1.885s 32 real 0m3.695s 64 real 0m7.826s 128 real 0m17.344s (best run out of 9 each time) This looks super-linear already; in the end it should be quadratic. Bertram