The other day, I was trying to do some arithmetic with very large
numbers and to my surprise, kcl ran out of bignum stack. I found
that in kcl you cannot calculate (expt 2 40000). I need a package
for common lisp in which I can do arbitrary presicion arithmetic.
If anyone is aware of any such package, I would be very grateful
if he/she could tell me how to get it.
Thanks
Tushar Saxena
······@cs.albany.edu
From: Robert Boyer
Subject: Re: Arbitrary Precision Arithmetic Package for Common Lisp
Date:
Message-ID: <lbumbuINNnc@ai.cs.utexas.edu>
In article <······················@cs.albany.edu> ······@cs.albany.edu (Tushar Saxena) writes:
>
>The other day, I was trying to do some arithmetic with very large
>numbers and to my surprise, kcl ran out of bignum stack. I found
>that in kcl you cannot calculate (expt 2 40000). I need a package
>for common lisp in which I can do arbitrary presicion arithmetic.
>If anyone is aware of any such package, I would be very grateful
I just tried (time (numberp (expt 2 40000))) in AKCL 1.615 on a Sparc
2, and it took .666 seconds. I have no idea whether that is fast or
slow, but it certainly didn't run out of any sort of space.
······@cs.albany.edu (Tushar Saxena) writes:
>The other day, I was trying to do some arithmetic with very large
>numbers and to my surprise, kcl ran out of bignum stack. I found
>that in kcl you cannot calculate (expt 2 40000). I need a package
>for common lisp in which I can do arbitrary presicion arithmetic.
>If anyone is aware of any such package, I would be very grateful
>if he/she could tell me how to get it.
I'm not sure what you're looking for. (How would an "arbitrary
precision arithmetic" package differ from normal bignums? Are you
referring to something like "bigfloats"? ...)
In any case your computation, (EXPT 2 40000), is only 40K bits long,
which is only about 5Kbytes. It's hard to believe that a lisp
implementation ran out of space on it (Yes, common lisp >should< be
able to handle integers of the size (EXPT 2 40000)).
A possibility I can imagine as being possible (but not necessarily
likely) is that you ran out of space trying to print the number. That
would be both time and space consuming (and pretty uninteresting,
probably).
Incidentally, if you are using (EXPT 2 40000) as an interim step in a
multiplication, or an integer division, you can always get by with
ASH, usually more efficiently. I'm not a KCL user, so I can't
duplicate your test, but it seems unlikely that it ran out of space on
your original example.
Maybe there has been a little confusion about where the error occurred.
Computing (expt 2 40000) works fine, but don't try to display it:
>(expt 2 40000)
Error: Value stack overflow.
Fast links are on: do (use-fast-links nil) for debugging
Error signalled by PRIN1.
Broken at PRIN1. Type :H for Help.
>>
Was that the original poster's problem?
--Juergen Wagner
·······@csli.stanford.edu
········@iao.fhg.de
From: Robert Boyer
Subject: Re: Arbitrary Precision Arithmetic Package for Common Lisp
Date:
Message-ID: <lc10hhINN5s6@ai.cs.utexas.edu>
In article <·····················@Csli.Stanford.EDU> ·······@Csli.Stanford.EDU (Juergen Wagner) writes:
>Maybe there has been a little confusion about where the error occurred.
>Computing (expt 2 40000) works fine, but don't try to display it:
>
>>(expt 2 40000)
>
>Error: Value stack overflow.
>Fast links are on: do (use-fast-links nil) for debugging
>Error signalled by PRIN1.
>Broken at PRIN1. Type :H for Help.
>>>
>
>Was that the original poster's problem?
>
>--Juergen Wagner
>·······@csli.stanford.edu
>········@iao.fhg.de
Allocating more stack intially, as in (setq si::*multiply-stacks* 4),
seems to get past the (expt 2 40000) printing problem you mention.
Here are a couple of relevant entries from doc/DOC for AKCL-1-615.
*MULTIPLY-STACKS*
Variable in SI package:
If this variable is set to a positive fixnum, then the next time through the
TOP-LEVEL loop, the loop will be exited. The size of the stacks will be
multiplied by the value of *multiply-stacks*, and the TOP-LEVEL will be called
again. Thus to double the size of the stacks:
>(setq si::*multiply-stacks* 2)
[exits top level and reinvokes it, with the new stacks in place]
>
We must exit TOP-LEVEL, because it and any other lisp functions
maintain many pointers into the stacks, which would be incorrect when the
stacks have been moved. Interrupting the process of growing the stacks,
can leave you in an inconsistent state.
MULTIPLY-BIGNUM-STACK
Function in the SI package:
Args: (n)
Increase the internal bignum stack by a factor of N. Normally space on this
stack is recovered after each complete lisp expression is evaluated. However
if you are dealing with large integers, you may need to use this function
to increase the stack.