Anatoli Tubman: > How can I *efficiently* print (i.e. find the decimal, or in > general N-ary, representation of) large Integers, like factorial of 10000? > > The implementation of showInt taken from Standard Prelude: ... > (2) crawls like hell (when fixed with strictness). > I don't know whether the slowness is because of GC, or because of > slowness of quotRem. Anyway, 100000! can be computed much, > much faster than printed (using GHC). > > So, can printing be done any faster? > > I realize that the issue is mostly theoretical. No one in real > life needs to print numbers so large. > -- > Anatoli Tubman <[EMAIL PROTECTED]> ================ No, I don't have the answer. I object only to the last sad remark that we don't need it *really* in practice. We do. The arithmetic compression algorithm, which is one of the best among the lossless schemes, transforms a huge file into a huge number (ok., not "big", but long, essentially equivalent to a very long binary fraction). The decoder "prints" such number. How to do it incrementally is far from trivial, but it has been done, and that's why people use more often a *worse* Huffman coding. Arithmetic "bit-stuffing" is patented... On the other hand, we cannot be sure that the long integer algorithms in Haskell are really efficiently implemented, sometimes I have the impression that a few things have been thrown-in without too much thinking about the optimization. A typical case is the rational package. If you read an appropriate passage from the II-nd volume of Knuth, you will see some simple but clever tricks reducing the num/den explosion by recognizing the possibility of simplification before computing the common denominators. The Prelude (at least of Hugs) uses the high-school techniques. === Did anybody try to verify the efficiency of a cascading algorithm: first you split the numbers in chunks `mod` 100000000 (e.g.), which goes much faster than slicing this horrible sausage `mod` 10, then print sequentially the chunks. The numbers involved are much smaller then, and the complexity is substantially reduced. (Anyway, some time ago I wrote a completely crazy program which computed and printed 2000 digits of the decimal expansion of PI reconstructed from a hexadecimal fraction. It worked on my small laptop (even under this primitive OS which Hans Aberg dislikes), but: 1. I represented those fractions as lists, not as huge blocks that Integers are, 2. Their processing was as lazy as it could be, or even more. ) Salutations distinguées. Jerzy Karczmarczuk Caen, France.
