On Fri, 12 Nov 1999, Steve Bennett wrote:
> Hi all,
> A while ago someone asked me what 111111! (factorial) is and I tried
> to find out in hugs, but ran into a 'control stack overflow' at around
> 3500 using a simple recursive factorial function and about 6000 using
> foldl.
>
> Ok, maybe 111,111! is asking a bit much...but would it be possible to
> write a factorial function that wouldn't stack overflow? Like it would
> crash some other way...not enough memory, taking too long, etc etc?
> Stack overflow just seems a little ungraceful :)
>
> (PS: if anyone knows of a way of estimating the value of a factorial,
> I'd also appreciate that).
fac n = foldl' (*) 1 [1..n] -- Prelude.foldl' uses O(1) stack
mult x n = x + (log n)
fac_log n = foldl' mult 1 [1..n]
fac_log10 n = (fac_log n) / (log 10)
? length( show (fac 111))
181
(3638 reductions, 7392 cells)
? fac_log10 111
180.681
(3053 reductions, 4086 cells)
? length( show (fac 11111))
40130
(514281 reductions, 53102637 cells, 231 garbage collections)
? fac_log10 11111
40129.8
(300053 reductions, 400086 cells, 1 garbage collection)
I do not have time to run (fac 111111), but one can easily find the number of
digits in it
? fac_log10 111111
512394.0
(3000053 reductions, 4000087 cells, 16 garbage collections)
Ilya Beylin email: [EMAIL PROTECTED]
Department of Computing Sciences, http://www.cs.chalmers.se/~ilya/
Chalmers University of Technology, phone: +46-31-772-1079
SE-41296 Gothenburg, Sweden fax: +46-31-165655
