Discussion:
need more explain about Integer type in Haskell
(too old to reply)
coolkid
2009-01-11 15:46:16 UTC
Permalink
I'm using WinHugs to study Haskell. I know that Integer type in
Haskell is unbounded. Does that mean we can use the function with any
big integer. eg "435435443543532343543254324325435" ?
Ertugrul Söylemez
2009-01-11 19:45:52 UTC
Permalink
Post by coolkid
I'm using WinHugs to study Haskell. I know that Integer type in
Haskell is unbounded. Does that mean we can use the function with any
big integer. eg "435435443543532343543254324325435" ?
Yes.


Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
coolkid
2009-01-12 02:01:00 UTC
Permalink
Post by Ertugrul Söylemez
Post by coolkid
I'm using WinHugs to study Haskell. I know that Integer type in
Haskell is unbounded. Does that mean we can use the function with any
big integer. eg "435435443543532343543254324325435" ?
Yes.
Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)http://blog.ertes.de/
I'm using WinHugs to study haskell. I define a factorial function:
fac :: Integer->Integer
fac n
| (n == 0) = 1
| otherwise = (fac (n-1)) * n

But when I run is with the parameter like this
"435435443543532343543254324325435". It show an error :"ERROR - C
stack overflow"
What happened?
Thanks for helping
Erik de Castro Lopo
2009-01-12 04:44:55 UTC
Permalink
fac :: Integer->Integer
fac n
| (n == 0) = 1
| otherwise = (fac (n-1)) * n
But when I run is with the parameter like this
"435435443543532343543254324325435". It show an error :"ERROR - C
stack overflow"
What happened?
You are aware aren't you, that your factorial function is recursive?

That is when you call fac on your really big number, it calls fac on
ones less than your really big number which calls fac on one less
than that ....... and so on down to when n == 0.

Every single one of those recursive calls requires stack space and
your stack is simply not big enough to hold it all.

The other problem you are going to have is that even if you make
that tail recursive, you are trying to calculate the factorial
of a very, very large number and i doubt your computer memory is
large enough to hold the result.

Erik
--
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"No Silicon Heaven? Preposterous! Where would
all the calculators go?" -- Kryten, Red Dwarf
Dirk Thierbach
2009-01-12 09:47:29 UTC
Permalink
fac :: Integer->Integer
fac n
| (n == 0) = 1
| otherwise = (fac (n-1)) * n
But when I run is with the parameter like this
"435435443543532343543254324325435". It show an error :"ERROR - C
stack overflow"
What happened?
Your function is not tail-recursive. Try

fac :: Integer -> Integer
fac n = product [1..n]

and make sure it is strict (e.g. with GHC, compile with -O, no idea
how to do that in WinHugs).

BTW, don't expect an answer for "435435443543532343543254324325435".
With Stirling approximation

logfac b n = n * logBase b (n / exp(1)) + 0.5 * logBase b (2 * pi * n)

So

Prelude> logfac 10 435435443543532343543254324325435
1.402303704118515e34

means the result has 10^34 decimal digits, or in base 2

Prelude> logfac 2 435435443543532343543254324325435
4.658352072275911e34

that's 4*10^34 bits, or

Prelude> 4*10^34 / 8 / 1024^3
4.656612873077393e24

about 4000000000000000000000000 GB of memory, if I didn't make a
stupid mistake somwhere. I doubt you can buy this much memory
somewhere, much less find a CPU to address all of it :-)

Above some point, the results of the factorial function will get large, so
you'll run out of memory. Nothing you can do about that.

- Dirk
coolkid
2009-01-12 10:39:14 UTC
Permalink
Post by Dirk Thierbach
fac     :: Integer->Integer
fac n
| (n == 0)                     = 1
| otherwise            = (fac (n-1)) * n
But when I run is with the parameter like this
"435435443543532343543254324325435". It show an error :"ERROR - C
stack overflow"
What happened?
Your function is not tail-recursive. Try
  fac :: Integer -> Integer
  fac n = product [1..n]
and make sure it is strict (e.g. with GHC, compile with -O, no idea
how to do that in WinHugs).
BTW, don't expect an answer for "435435443543532343543254324325435".
With Stirling approximation
  logfac b n = n * logBase b (n / exp(1)) + 0.5 * logBase b (2 * pi * n)
So
  Prelude> logfac 10 435435443543532343543254324325435
  1.402303704118515e34
means the result has 10^34 decimal digits, or in base 2
  Prelude> logfac 2 435435443543532343543254324325435
  4.658352072275911e34
that's 4*10^34 bits, or
  Prelude> 4*10^34 / 8 / 1024^3          
  4.656612873077393e24
about 4000000000000000000000000 GB of memory, if I didn't make a
stupid mistake somwhere. I doubt you can buy this much memory
somewhere, much less find a CPU to address all of it :-)
Above some point, the results of the factorial function will get large, so
you'll run out of memory. Nothing you can do about that.
- Dirk
thanks for helping.
Ingo Menger
2009-01-13 10:30:41 UTC
Permalink
Post by Dirk Thierbach
fac     :: Integer->Integer
fac n
| (n == 0)                     = 1
| otherwise            = (fac (n-1)) * n
But when I run is with the parameter like this
"435435443543532343543254324325435". It show an error :"ERROR - C
stack overflow"
What happened?
Your function is not tail-recursive. Try
  fac :: Integer -> Integer
  fac n = product [1..n]
and make sure it is strict (e.g. with GHC, compile with -O, no idea
how to do that in WinHugs).
BTW, don't expect an answer for "435435443543532343543254324325435".
And not only for the memory.
Try this:

down 0 = 1
down n = down (n-1)

down 435435443543532343543254324325435

While your CPU runs hot, approximate the following: If a miraculous
computer could do 1 billion (i.e. thousand millions) recursions per
second and if this computer existed at the time of the big bang 15
billion years ago and started the computation then, would the result
be ready yet?

Continue reading on narkive:
Search results for 'need more explain about Integer type in Haskell' (Questions and Answers)
8
replies
Help with math?
started 2006-10-07 15:20:58 UTC
mathematics
Loading...