Steve Bennett <[EMAIL PROTECTED]> writes to hugs-users...
> [..]
> 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).
(2n)! = (1*2n)*(2*(2n-1))*...*(n*n) >= n^n - if i do not mistake.
In the calculus guides they, probably, prove something stronger.
So, the number of bits in 111111! is more than
55000*(log_2 55000) > 15*55000
Multiplying such numbers may cost a penny.
I have heard, there exist good algorithms using the fast Fourie
transformation: s*(log s) operations, s the number of digits in n.
This is instead of more than s^2 of "usual" methods.
See the book of Aho, Hopcroft, Ulman.
-- To [EMAIL PROTECTED] ----------------------------
But why ghc-4.04 behaves so strange?
Consider
putStr $ shows (product [1..n] ::Integer) "\n" where n = ...
For n = 1000, ./run +RTS -M3m outputs the result fast.
For -M2m reports in-sufficient space.
But for n = 9000, -M3m
it does not report anything, swapping to the disk heavily. ALARM!
Why it touches the disk?
This is the binary distribution ghc-4.04-linux-i386-unknown.
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
