Subject: [clisp-list] overflow during multiplication of large numbers

From: Ben Pharr - Lists <[email-masked]>
Date: Tue Oct 9 13:04:06 2001

I have programmed a partially iterative function to calculate Ackermann's 
function. The iterative part is for cases of m=0 through m=3. Anything 
above that is done with recursion. I have compiled the function. A(4, 2) 
can be calculated in a fraction of a second. The result is a number with 
more than 19,000 digits. However, A(4, 3) gives me an error. It says:

*** - overflow during multiplication of large numbers

This occurs within a second of executing the function. I am doing this on 
Debian Linux, so I thought maybe the ulimit was getting in the way. ulimit 
is set to unlimited, and I have 320MBs of RAM. I thought maybe unlimited 
wasn't really unlimited, so I set it to 300MB and tried again with the same 
results.

While it is possible A( 4, 3) would cause an overflow, I don't think it's 
taking enough time to find out, given how quickly A(4, 2) is computed. Can 
anyone give me some advice. Thanks!

Ben Pharr

---

From: Sam Steingold <[email-masked]>
Date: Tue Oct 9 13:38:07 2001

Ackermann's function grows fast.
No, not just fast, but _VERY FAST_.
A(4,1) = 2^16 - 3
A(4,2) ~ 2^(A(4,1))
A(4,3) ~ 2^(A(4,2))

if you to represent a number X with log X bits, then A(4,1) is a
16-bit (2 byte) number, while A(4,2) is an 8kB number.
now, A(4,3) is a 2^(2^16) - bit number.
there isn't a word for this monster.
there isn't enough matter in the observable universe to record it.
if google is 10^100 (~2^333), then A(4,3) is about google^197.
there are fewer than a google particles in the universe.

I hope I am sufficiently clear.

> * In message <[email-masked]>
> * On the subject of "[clisp-list] overflow during multiplication of large numbers"
> * Sent on Tue, 09 Oct 2001 15:03:16 -0500
> * Honorable Ben Pharr - Lists <[email-masked]> writes:
>
> I have programmed a partially iterative function to calculate
> Ackermann's function. The iterative part is for cases of m=0 through
> m=3. Anything above that is done with recursion. I have compiled the
> function. A(4, 2) can be calculated in a fraction of a second. The
> result is a number with more than 19,000 digits. However, A(4, 3)
> gives me an error. It says:
> 
> This occurs within a second of executing the function. I am doing this
> on Debian Linux, so I thought maybe the ulimit was getting in the
> way. ulimit is set to unlimited, and I have 320MBs of RAM. I thought
> maybe unlimited wasn't really unlimited, so I set it to 300MB and
> tried again with the same results.
> 
> While it is possible A( 4, 3) would cause an overflow, I don't think
> it's taking enough time to find out, given how quickly A(4, 2) is
> computed. Can anyone give me some advice. Thanks!

-- 
Sam Steingold (http://www.podval.org/~sds)
Support Israel's right to defend herself! <http://www.i-charity.com/go/israel>
Read what the Arab leaders say to their people on <http://www.memri.org/>
XFM: Exit file manager? [Continue] [Cancel] [Abort]

---

From: Ben Pharr - Lists <[email-masked]>
Date: Tue Oct 9 15:46:10 2001

>I hope I am sufficiently clear.

So what you're trying to say is that it's a big number? :-)  Just kidding. 
I knew it was a large number, but I wasn't quite grasping HOW big. Thanks 
for explaining that to me.

I'm still not sure why it overflows without eating up more than 1.1% of my 
memory. Can anyone explain that to me? I realize it doesn't matter in this 
particular situation, but it might in the future.

Ben Pharr

---

From: Nathan Froyd <[email-masked]>
Date: Tue Oct 9 16:05:06 2001

Ben Pharr - Lists wrote:

> So what you're trying to say is that it's a big number? :-)  Just 
> kidding. I knew it was a large number, but I wasn't quite grasping HOW 
> big. Thanks for explaining that to me.
> 
> I'm still not sure why it overflows without eating up more than 1.1% of 
> my memory. Can anyone explain that to me? I realize it doesn't matter in 
> this particular situation, but it might in the future.

It's possible (not being an expert on CLISP internals) that the bignum 
code inside of CLISP is smart enough to recognize when you give it 
operands that are far larger than it can ever hope to operate on.  So 
A(4,2) calculates quickly, is really huge, and it overflows some 
internal limit.

-Nathan

---

From: Ben Pharr - Lists <[email-masked]>
Date: Tue Oct 9 16:14:06 2001

At 05:57 PM 10/9/01 -0500, you wrote:
>A(4,2) calculates quickly, is really huge, and it overflows some internal 
>limit.
>
>-Nathan

That was my guess too, but I was wondering if someone knew that was the case.

Ben Pharr