From: Ben P. - L. <ben...@be...> - 2001-10-09 20:03:14
|
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 S. <sd...@gn...> - 2001-10-09 20:37:25
|
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 <5.1...@su...> > * 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 <ben...@be...> 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: > > *** - 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! -- 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 P. - L. <ben...@be...> - 2001-10-09 22:45:13
|
At 04:35 PM 10/9/01 -0400, you wrote: >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. 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 F. <fr...@ro...> - 2001-10-09 23:04:24
|
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 P. - L. <ben...@be...> - 2001-10-09 23:13:23
|
At 05:57 PM 10/9/01 -0500, you wrote: >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 That was my guess too, but I was wondering if someone knew that was the case. Ben Pharr |