Hi,
I am writing code in Mac Common Lisp, that uses BIGNUM's a lot (for
representing sets). I use EXPT a lot, and when I just copied my code to
Allegro 4.3 on our Ultra-2 to get some more power and memory, was
immediately faced with the fact that ACL cannot handle (EXPT 2 (EXPT 2
32)). It seems a shame my little laptop is more capable than this behemoth
Sun on my desk :-)
Steele (1990) has the CL definition to be (EXPT rational power-number).
and goes onto say if power-number is an integer, then the result is a
rational (which is a subset of the integers if my number theory is
correct).
Now in the standard, it says "CL in principle imposes no limit on the
magnitude of an integer; storage is automatically allocated as necessary
to represent large integers".
It then goes onto define FIXNUM's as ones easy to handle for an
implementation and BIGNUM's as the rest.
So... I'll let you be the judge, but here is the trace:
USER(27): (setfx (expt 2 32))
USER(28): (describe x)
4294967296 is a BIGNUM.
It is 33 bits wide
USER(29): (expt 2 x)
Error: the value of COUNT is 4294967296, which is not of type FIXNUM.
[condition type: TYPE-ERROR]
Cheers,
Winton
In article <························@semantics.stanford.edu>,
Winton Davies <·······@cs.stanford.edu> wrote:
> Now in the standard, it says "CL in principle imposes no limit on the
>magnitude of an integer; storage is automatically allocated as necessary
>to represent large integers".
Since current computers are all finite, there will always be some limit
that an implementation places on bignum size. If nothing else, you'll run
out of virtual memory eventually. Many implementations divide memory into
several spaces for different types of objects. And Unix typically allows
the system administrator and the user to place limits on the size of a
single process (to prevent a single user from using up all the VM on the
system).
>USER(27): (setfx (expt 2 32))
>USER(28): (describe x)
>4294967296 is a BIGNUM.
> It is 33 bits wide
>USER(29): (expt 2 x)
>Error: the value of COUNT is 4294967296, which is not of type FIXNUM.
> [condition type: TYPE-ERROR]
If ACL requires the power-number argument to be a fixnum, that's a bug,
since the CL spec clearly says that it can be any type of number.
Note that (expt 2 (expt 2 32)) will require at least (expt 2 29) bytes to
store it. That's half a terabyte. Does your Sun have that much swap
space? Franz might have decided to restrict integer power-numbers to
fixnums, since they didn't think any VM could store much more than that.
I find it difficult to believe that MCL was able to handle this -- that's
alot of virtual memory for a Macintosh as well! If it did, my only guess
is that MCL may have a representation for bignums that uses some kind of
run-length encoding, or maybe just handles low-order zero bits efficiently
(by representing the shift separately). What happens if you try (1- (expt
2 (expt 2 32))) or (random (expt 2 (expt 2 32)))? The first should be
storable efficiently with RLE (it has a long run of 1's instead of a long
run of 0's), but the second is not likely to have many very long runs (some
probability guru could presumably tell us the likely distribution of run
lengths).
--
Barry Margolin
BBN Corporation, Cambridge, MA
······@bbnplanet.com
(BBN customers, call (800) 632-7638 option 1 for support)
* Winton Davies
| I am writing code in Mac Common Lisp, that uses BIGNUM's a lot (for
| representing sets). I use EXPT a lot, and when I just copied my code to
| Allegro 4.3 on our Ultra-2 to get some more power and memory, was
| immediately faced with the fact that ACL cannot handle (EXPT 2 (EXPT 2
| 32)). It seems a shame my little laptop is more capable than this
| behemoth Sun on my desk :-)
(you would have received a better answer by mailing ····@franz.com.)
the answer to your question is also right there in the User Guide, Chapter
3 Implementation and Extensions, Section 3.2 Data Types, page 3-7. I
quote:
Bignums may be as large as 2**[1,048,576]
the reference for Common Lisp is now ANSI X3.226:1994 Programming Languages
-- Common Lisp. the definition of the system class _integer_ goes as
follows:
An integer is a mathematical integer. There is no limit on the
magnitude of an integer.
this definition makes an interesting implementation challenge, to put it
mildly. it is, in fact, not possible to implement Common Lisp integers
_without_ an arbitrary limit. however, `expt' is not specified to take
just a fixnum for exponent.
if you need more than 1 megabit integers, Franz, Inc, will most probably
accomodate you. let them know and work with them.
now, if you don't actually _need_ 4 gigabit integers, I think it's a bit
silly to argue about it, but in terms of strict adherence, you've pointed
to something that might be worth persuing, namely the error you got. talk
with Franz. I have not found a more helpful group of people in my 15-year
career as a programmer. (I don't have any ties to Franz, Inc, other than
being a very happy customer.)
#\Erik
--
my other car is a cdr
In article <························@semantics.stanford.edu>,
·······@cs.stanford.edu (Winton Davies) writes:
> Hi,
>
> I am writing code in Mac Common Lisp, that uses BIGNUM's a lot (for
> representing sets). I use EXPT a lot, and when I just copied my code to
> Allegro 4.3 on our Ultra-2 to get some more power and memory, was
> immediately faced with the fact that ACL cannot handle (EXPT 2 (EXPT 2
> 32)). It seems a shame my little laptop is more capable than this behemoth
> Sun on my desk :-)
> [...]
(EXPT 2 (EXPT 2 32)) needs at least (EXPT 2 32) bits to represent it,
that's 536870912 Bytes. Does your "little laptop" have half a gigabyte of
RAM?
--
------------------------------------------------------------------------
Andreas Wolpers
DFKI GmbH Tel.: (++49) 681 9325 523
Stuhlsatzenhausweg 3 or 681 302 5348
66123 Saarbruecken Fax: (++49) 681 9320 580
Germany or 681 302 5341