Bulat Ziganshin schrieb: > Hello Henning, > > Tuesday, August 25, 2009, 6:11:00 PM, you wrote: > >>> digits = iterate (`div` 10) >>> takeWhile (>0) >>> length > >> This needs quadratic time with respect to the number of digits, doesn't >> it? > > why?
Because division by 10 needs linear time. > i think that `show` uses pretty the same way to build list of > digits, so we just omit unneeded computations I hope that 'show' will not need quadratic time but will employ a more efficient algorithm that is certainly implemented in the GNU multiprecision library. I assume that a division by 10^(2^k) will require about 2^k * k operations. At least, it should be considerably faster than repeatedly dividing by 10. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
