From: Peter Seibel
Subject: Bignum limits
Date: 
Message-ID: <m3fz2jun0p.fsf@javamonkey.com>
Are there current Common Lisp implementations wherein bignums are
limited by something other than sheer available memory? For example,
an implementation might use some representation that otherwise limits
the maximum size of a bignum.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp

From: Thomas F. Burdick
Subject: Re: Bignum limits
Date: 
Message-ID: <xcvmzwrjcrg.fsf@conquest.OCF.Berkeley.EDU>
Peter Seibel <·····@javamonkey.com> writes:

> Are there current Common Lisp implementations wherein bignums are
> limited by something other than sheer available memory? For example,
> an implementation might use some representation that otherwise limits
> the maximum size of a bignum.

CMUCL and SBCL limit you to ARRAY-TOTAL-SIZE-LIMIT number of bytes.
On 32-bit systems that makes the largest representable number 2^(2^29 - 1)
From: Paul F. Dietz
Subject: Re: Bignum limits
Date: 
Message-ID: <admdndi9EIuLlCjcRVn-2g@dls.net>
Peter Seibel wrote:

> Are there current Common Lisp implementations wherein bignums are
> limited by something other than sheer available memory? For example,
> an implementation might use some representation that otherwise limits
> the maximum size of a bignum.

CLISP has a rather small limit.  Running up against it is the sole remaining
reason CLISP fails in the random tester.

	Paul
From: Peter Seibel
Subject: Re: Bignum limits
Date: 
Message-ID: <m3oeh6ubq4.fsf@javamonkey.com>
"Paul F. Dietz" <·····@dls.net> writes:

> Peter Seibel wrote:
>
>> Are there current Common Lisp implementations wherein bignums are
>> limited by something other than sheer available memory? For example,
>> an implementation might use some representation that otherwise limits
>> the maximum size of a bignum.
>
> CLISP has a rather small limit.  Running up against it is the sole remaining
> reason CLISP fails in the random tester.

Really? In my experimentation it seemed to have a limit that was as
large or larger than Allegro or SBCL.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Paul F. Dietz
Subject: Re: Bignum limits
Date: 
Message-ID: <W9qdneN9E9bGjSjcRVn-tA@dls.net>
Peter Seibel wrote:

> Really? In my experimentation it seemed to have a limit that was as
> large or larger than Allegro or SBCL.

I wasn't seeing overflows in the latter two (except for some type propagator
overflows in SBCL).

	Paul
From: Peter Seibel
Subject: Re: Bignum limits
Date: 
Message-ID: <m3k6ruu9vs.fsf@javamonkey.com>
"Paul F. Dietz" <·····@dls.net> writes:

> Peter Seibel wrote:
>
>> Really? In my experimentation it seemed to have a limit that was as
>> large or larger than Allegro or SBCL.
>
> I wasn't seeing overflows in the latter two (except for some type
> propagator overflows in SBCL).

I tried (expt 2 (expt 2 20)) in Allegro (7.0), SBCL (0.8.16), CMUCL
(18e), and CLISP (2.33.2). Allegro signaled an error with a message
about "Attempt to create an integer that is too large to represent".
SBCL died a horrible death. CMUCL signaled an error with the message
"The absolute value of 1048576 exceeds *INTEXP-MAXIMUM-EXPONENT*."

CLISP, on the other hand, printed a bunch of digits--I didn't check
that they were right. ;-) However (expt 2 (expt 2 21)) in CLISP
signaled an error with the message "overflow during multiplication of
large numbers."

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Fred Gilham
Subject: Re: Bignum limits
Date: 
Message-ID: <u7hdmyltm9.fsf@snapdragon.csl.sri.com>
> I tried (expt 2 (expt 2 20)) in Allegro (7.0), SBCL (0.8.16), CMUCL
> (18e), and CLISP (2.33.2). Allegro signaled an error with a message
> about "Attempt to create an integer that is too large to represent".
> SBCL died a horrible death. CMUCL signaled an error with the message
> "The absolute value of 1048576 exceeds *INTEXP-MAXIMUM-EXPONENT*."

Note that the CMUCL error is continuable and if you continue it will
produce a result.

-- 
Fred Gilham                                   ······@csl.sri.com
Lisp has jokingly been called "the most intelligent way to misuse a
computer". I think that description is a great compliment because it
transmits the full flavor of liberation: it has assisted a number of
our most gifted fellow humans in thinking previously impossible
thoughts.   E. Dijkstra
From: Nikodemus Siivola
Subject: Re: Bignum limits
Date: 
Message-ID: <cp4177$iqitf$2@midnight.cs.hut.fi>
>> I tried (expt 2 (expt 2 20)) in Allegro (7.0), SBCL (0.8.16), CMUCL
>> (18e), and CLISP (2.33.2). Allegro signaled an error with a message
>> about "Attempt to create an integer that is too large to represent".
>> SBCL died a horrible death. CMUCL signaled an error with the message

From SBCL's NEWS file for 0.8.17:

  * fixed bug #350: bignum-printing is now more memory-efficient,
    allowing printing of very large bignums, eg. (expt 2 10000000).
    (reported by Bruno Haible)

Cheers,

 -- Nikodemus
From: Lisp rules!
Subject: Re: Bignum limits
Date: 
Message-ID: <1102391313.800442.246970@f14g2000cwb.googlegroups.com>
Peter Seibel wrote:
> "Paul F. Dietz" <·····@dls.net> writes:
>
> > Peter Seibel wrote:
> >
> >> Really? In my experimentation it seemed to have a limit that was
as
> >> large or larger than Allegro or SBCL.
> >
> > I wasn't seeing overflows in the latter two (except for some type
> > propagator overflows in SBCL).
>
> I tried (expt 2 (expt 2 20)) in Allegro (7.0), SBCL (0.8.16), CMUCL
> (18e), and CLISP (2.33.2). Allegro signaled an error with a message
> about "Attempt to create an integer that is too large to represent".
> SBCL died a horrible death. CMUCL signaled an error with the message
> "The absolute value of 1048576 exceeds *INTEXP-MAXIMUM-EXPONENT*."
>
> CLISP, on the other hand, printed a bunch of digits--I didn't check
> that they were right. ;-)
...

(expt 2 (expt 2 20)) works well with LWM 4.4b. (Takes a wile on my
lowly 500MHz) Confirmed as the correct answer by Mathematica v5.0.
Olivier
From: Paul F. Dietz
Subject: Re: Bignum limits
Date: 
Message-ID: <i5adnZA33vXOiyjcRVn-hg@dls.net>
Peter Seibel wrote:
> "Paul F. Dietz" <·····@dls.net> writes:
> 
> 
>>Peter Seibel wrote:
>>
>>
>>>Really? In my experimentation it seemed to have a limit that was as
>>>large or larger than Allegro or SBCL.
>>
>>I wasn't seeing overflows in the latter two (except for some type
>>propagator overflows in SBCL).
> 
> 
> I tried (expt 2 (expt 2 20)) in Allegro (7.0), SBCL (0.8.16), CMUCL
> (18e), and CLISP (2.33.2). Allegro signaled an error with a message
> about "Attempt to create an integer that is too large to represent".
> SBCL died a horrible death. CMUCL signaled an error with the message
> "The absolute value of 1048576 exceeds *INTEXP-MAXIMUM-EXPONENT*."
> 
> CLISP, on the other hand, printed a bunch of digits--I didn't check
> that they were right. ;-) However (expt 2 (expt 2 21)) in CLISP
> signaled an error with the message "overflow during multiplication of
> large numbers."

Huh.  I don't understand the behavior, then.

	Paul
From: Juho Snellman
Subject: Re: Bignum limits
Date: 
Message-ID: <slrncra8tt.5fs.jsnell@sbz-31.cs.Helsinki.FI>
<·····@javamonkey.com> wrote:
>I tried (expt 2 (expt 2 20)) in Allegro (7.0), SBCL (0.8.16), CMUCL
>(18e), and CLISP (2.33.2). Allegro signaled an error with a message
>about "Attempt to create an integer that is too large to represent".
>SBCL died a horrible death.

In SBCL's case that smallish bignum was created just fine, but the
bignum printer used up all the memory:

* (defvar *a* (expt 2 (expt 2 28)))
*A*
* (integer-length *a*)
268435457

I believe Nikodemus Siivola fixed the excessive memory usage in SBCL
0.8.17.

-- 
Juho Snellman
"Premature profiling is the root of all evil."
From: Christophe Rhodes
Subject: Re: Bignum limits
Date: 
Message-ID: <sqk6rueysc.fsf@cam.ac.uk>
Peter Seibel <·····@javamonkey.com> writes:

> "Paul F. Dietz" <·····@dls.net> writes:
>
>> Peter Seibel wrote:
>>
>>> Really? In my experimentation it seemed to have a limit that was as
>>> large or larger than Allegro or SBCL.
>>
>> I wasn't seeing overflows in the latter two (except for some type
>> propagator overflows in SBCL).
>
> I tried (expt 2 (expt 2 20)) in Allegro (7.0), SBCL (0.8.16), CMUCL
> (18e), and CLISP (2.33.2). Allegro signaled an error with a message
> about "Attempt to create an integer that is too large to represent".
> SBCL died a horrible death. CMUCL signaled an error with the message
> "The absolute value of 1048576 exceeds *INTEXP-MAXIMUM-EXPONENT*."
>
> CLISP, on the other hand, printed a bunch of digits--I didn't check
                            ^^^^^^^

Key point.  Generating an object and printing an object aren't
necessarily of equal complexity (particularly in ye olde and crufty
implementations...)

Christophe
From: Paul F. Dietz
Subject: Re: Bignum limits
Date: 
Message-ID: <K-OdnY6J0-LXJSjcRVn-rw@dls.net>
Peter Seibel wrote:

> Really? In my experimentation it seemed to have a limit that was as
> large or larger than Allegro or SBCL.

Here's a test that passes on SBCL but causes an error on CLISP
(overflow during multiplication of large numbers):

(deftest misc.455
  (let*
   ((fn1
     '(lambda (a b c)
        (declare (type (integer 0 60800) a))
        (declare (type (integer -1040239995 3) b)) (declare (type (integer 60 91) c))
        (declare (ignorable a b c))
        (declare (optimize (speed 0) (space 1) (safety 2) (debug 3) (compilation-speed 2)))
        (reduce #'(lambda (lmv2 lmv5) (* (+ lmv2 b) lmv2 lmv2 lmv2 b))
	       (list (elt '(8066437 4402428 2382002 3547413 8249946 1140219)
			  (min 5 (max 0 c))) 0 a 0 0 0 0 0 0) :end 9)))
    (fn2
     '(lambda (a b c)
        (declare (notinline reduce * + list elt min max))
        (declare (optimize (debug 2) (safety 3) (space 2) (speed 1) (compilation-speed 2)))
        (reduce #'(lambda (lmv2 lmv5) (* (+ lmv2 b) lmv2 lmv2 lmv2 b))
	       (list (elt '(8066437 4402428 2382002 3547413 8249946 1140219)
			  (min 5 (max 0 c))) 0 a 0 0 0 0 0 0) :end 9)))
    (vals '(41816 -711407207 74))
    (v1 (apply (compile nil fn1) vals))
    (v2 (apply (compile nil fn2) vals)))
   (if (eql v1 v2) :good (list v1 v2)))
  :good)


	Paul
From: Bruno Haible
Subject: Re: Bignum limits
Date: 
Message-ID: <cq6fdu$brg$1@laposte.ilog.fr>
Paul F. Dietz <·····@dls.net> wrote:
>
> Here's a test that passes on SBCL but causes an error on CLISP
> (overflow during multiplication of large numbers):
>
> (deftest misc.455
>  (let*
>   ((fn1
>     '(lambda (a b c)
>        (declare (type (integer 0 60800) a))
>        (declare (type (integer -1040239995 3) b)) (declare (type (integer 60 91) c))
>        (declare (ignorable a b c))
>        (declare (optimize (speed 0) (space 1) (safety 2) (debug 3) (compilation-speed 2)))
>        (reduce #'(lambda (lmv2 lmv5) (* (+ lmv2 b) lmv2 lmv2 lmv2 b))
>	       (list (elt '(8066437 4402428 2382002 3547413 8249946 1140219)
>			  (min 5 (max 0 c))) 0 a 0 0 0 0 0 0) :end 9)))
>    (fn2
>     '(lambda (a b c)
>        (declare (notinline reduce * + list elt min max))
>        (declare (optimize (debug 2) (safety 3) (space 2) (speed 1) (compilation-speed 2)))
>        (reduce #'(lambda (lmv2 lmv5) (* (+ lmv2 b) lmv2 lmv2 lmv2 b))
>	       (list (elt '(8066437 4402428 2382002 3547413 8249946 1140219)
>			  (min 5 (max 0 c))) 0 a 0 0 0 0 0 0) :end 9)))
>    (vals '(41816 -711407207 74))
>    (v1 (apply (compile nil fn1) vals))
>    (v2 (apply (compile nil fn2) vals)))
>   (if (eql v1 v2) :good (list v1 v2)))
>  :good)

This test effectively tests whether bignums with 2113110 bits are supported.
In clisp, the bignum limit is around 2097120 bits. It would be possible to
support bignums with up to 536870880 bits (= 67 MB per number!), but it's
actually better for a developer if the implementation gives a clear
diagnostic of the problem - bignum overflow - early than when it fills
memory with bignums that each take a minute for display and 20 MB of
size.

This is what happens when you try not only to compute the bignum with
2113110 bits, but also its square root:
* (defvar a)
* (progn (setq a (reduce #'(lambda (lmv2 lmv5)
                             (* (+ lmv2 -711407207) lmv2 lmv2 lmv2
                             -711407207))
                         '(1140219 0 41816 0 0 0 0 0 0) :end 9))
         nil)
* (integer-length a)
* (defvar b)
* (progn (setq b (isqrt (abs a))) nil)
CLISP says "overflow during multiplication of large numbers"
ACL 6.2 says "Attempt to create an integer which is too large to represent."
SBCL works fine but explodes later, while trying to print a or b, is killed
by the OS and loses the session's data.
GCL 2.5.3 says "Caught fatal error [memory may be damaged]".
CMUCL 19a and Lispworks 4.3 take eternities.

Someone who really wants to do number-crunching with so large integers
needs FFT multiplication anyway, i.e. either GCL with a particularly
tuned and patched GMP, or special-purpose packages like CLN or
Piologie.

Bruno
From: Camm Maguire
Subject: Re: Bignum limits
Date: 
Message-ID: <54ekhl7zng.fsf@intech19.enhanced.com>
Greetings!

Bruno Haible <·····@clisp.org> writes:

> Paul F. Dietz <·····@dls.net> wrote:
> >
> > Here's a test that passes on SBCL but causes an error on CLISP
> > (overflow during multiplication of large numbers):
> >
> > (deftest misc.455
> >  (let*
> >   ((fn1
> >     '(lambda (a b c)
> >        (declare (type (integer 0 60800) a))
> >        (declare (type (integer -1040239995 3) b)) (declare (type (integer 60 91) c))
> >        (declare (ignorable a b c))
> >        (declare (optimize (speed 0) (space 1) (safety 2) (debug 3) (compilation-speed 2)))
> >        (reduce #'(lambda (lmv2 lmv5) (* (+ lmv2 b) lmv2 lmv2 lmv2 b))
> >	       (list (elt '(8066437 4402428 2382002 3547413 8249946 1140219)
> >			  (min 5 (max 0 c))) 0 a 0 0 0 0 0 0) :end 9)))
> >    (fn2
> >     '(lambda (a b c)
> >        (declare (notinline reduce * + list elt min max))
> >        (declare (optimize (debug 2) (safety 3) (space 2) (speed 1) (compilation-speed 2)))
> >        (reduce #'(lambda (lmv2 lmv5) (* (+ lmv2 b) lmv2 lmv2 lmv2 b))
> >	       (list (elt '(8066437 4402428 2382002 3547413 8249946 1140219)
> >			  (min 5 (max 0 c))) 0 a 0 0 0 0 0 0) :end 9)))
> >    (vals '(41816 -711407207 74))
> >    (v1 (apply (compile nil fn1) vals))
> >    (v2 (apply (compile nil fn2) vals)))
> >   (if (eql v1 v2) :good (list v1 v2)))
> >  :good)
> 
> This test effectively tests whether bignums with 2113110 bits are supported.
> In clisp, the bignum limit is around 2097120 bits. It would be possible to
> support bignums with up to 536870880 bits (= 67 MB per number!), but it's
> actually better for a developer if the implementation gives a clear
> diagnostic of the problem - bignum overflow - early than when it fills
> memory with bignums that each take a minute for display and 20 MB of
> size.
> 
> This is what happens when you try not only to compute the bignum with
> 2113110 bits, but also its square root:
> * (defvar a)
> * (progn (setq a (reduce #'(lambda (lmv2 lmv5)
>                              (* (+ lmv2 -711407207) lmv2 lmv2 lmv2
>                              -711407207))
>                          '(1140219 0 41816 0 0 0 0 0 0) :end 9))
>          nil)
> * (integer-length a)
> * (defvar b)
> * (progn (setq b (isqrt (abs a))) nil)
> CLISP says "overflow during multiplication of large numbers"
> ACL 6.2 says "Attempt to create an integer which is too large to represent."
> SBCL works fine but explodes later, while trying to print a or b, is killed
> by the OS and loses the session's data.
> GCL 2.5.3 says "Caught fatal error [memory may be damaged]".

Just an update here -- the latest stable GCL is 2.6.5, and here we
get:

GCL (GNU Common Lisp)  2.6.5 ANSI    Sep  3 2004 17:56:58
Source License: LGPL(gcl,gmp), GPL(unexec,bfd)
Binary License:  GPL due to GPL'ed components: (READLINE BFD UNEXEC)
Modifications of this banner must retain notice of a compatible license
Dedicated to the memory of W. Schelter

Use (help) to get some basic information on how to use GCL.

>(defvar a)(defvar b)
(time (progn (setq a (reduce #'(lambda (lmv2 lmv5)
                             (* (+ lmv2 -711407207) lmv2 lmv2 lmv2
                             -711407207))
                         '(1140219 0 41816 0 0 0 0 0 0) :end 9))
         nil))
(integer-length a)
(time (progn (setq b (isqrt (abs a))) nil))


A

>
B

>
real time       :      0.400 secs
run-gbc time    :      0.410 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
NIL

>
2113110

>
real time       :     10.910 secs
run-gbc time    :     10.770 secs
child run time  :      0.000 secs
gbc time        :      0.090 secs
NIL

(Xeon 2.66Ghz machine)

The deftest version Paul supplied above also passes in GCL cvs head
(aka 2.7.0), the version we are using for this test suite.  Presumably
it would work in 2.6.5 too, but some of the definitions in the ansi
test suite support files rely on recent ansi compliance fixes in
HEAD. 


> CMUCL 19a and Lispworks 4.3 take eternities.
> 
> Someone who really wants to do number-crunching with so large integers
> needs FFT multiplication anyway, i.e. either GCL with a particularly
> tuned and patched GMP, or special-purpose packages like CLN or

I've suggested in the past that various distributions, notably Debian,
ship gmp in a fashion that would select the optimally tuned version
for the running cpu at runtime, like we do now with atlas.  I haven't
followed through with this, as I've yet to see an example in lisp
where one can actually see the difference between SSE and generic
arithmetic for example -- the lisp overhead is still too great, at
least on the test problems I've come up with so far.

Take care,

> Piologie.
> 
> Bruno
> 
> 

-- 
Camm Maguire			     			····@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah
From: Olivier Drolet
Subject: Re: Bignum limits
Date: 
Message-ID: <1103587141.835800.316680@z14g2000cwz.googlegroups.com>
Bruno Haible wrote:
> Paul F. Dietz <·····@dls.net> wrote:
> >
> > Here's a test that passes on SBCL but causes an error on CLISP
...
> CMUCL 19a and Lispworks 4.3 take eternities.
>

Does the following (LWM 4.4 on a 500MHz PPC G4) match your definition
of eterinties?  ;-)


CL-USER 7 > (time (progn (setq b (isqrt (abs a))) nil))
Timing the evaluation of (PROGN (SETQ B (ISQRT (ABS A))) NIL)

user time    =    208.170
system time  =      1.030
Elapsed time =   0:03:47
Allocation   = 4187876 bytes
153 Page faults
NIL

Cheers,

Olivier
From: Pascal Bourguignon
Subject: Re: Bignum limits
Date: 
Message-ID: <87pt14zexz.fsf@thalassa.informatimago.com>
"Olivier Drolet" <·······@mac.com> writes:

> Bruno Haible wrote:
> > Paul F. Dietz <·····@dls.net> wrote:
> > >
> > > Here's a test that passes on SBCL but causes an error on CLISP
> ...
> > CMUCL 19a and Lispworks 4.3 take eternities.
> >
> 
> Does the following (LWM 4.4 on a 500MHz PPC G4) match your definition
> of eterinties?  ;-)
> 
> 
> CL-USER 7 > (time (progn (setq b (isqrt (abs a))) nil))
> Timing the evaluation of (PROGN (SETQ B (ISQRT (ABS A))) NIL)
> 
> user time    =    208.170
> system time  =      1.030
> Elapsed time =   0:03:47
> Allocation   = 4187876 bytes
> 153 Page faults
> NIL

Indeed, when you have the dentist's drill in a mollar, 
3 min 47 sec IS an eternity.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
You never feed me.
Perhaps I'll sleep on your face.
That will sure show you.
From: Raffael Cavallaro
Subject: Re: Bignum limits
Date: 
Message-ID: <2004122217425250073%raffaelcavallaro@pasdespamsilvousplaitdotmaccom>
On 2004-12-20 07:09:34 -0500, Bruno Haible <·····@clisp.org> said:

> SBCL works fine but explodes later, while trying to print a or b, is killed
> by the OS and loses the session's data.

Actually, under Mac OS X sbcl 0.8.17 prints both a and b without 
problem. Granted, it takes a few seconds, but sbcl does not terminate 
after doing this:

* (defvar a)

A
* (progn (setq a (reduce #'(lambda (lmv2 lmv5)
                             (* (+ lmv2 -711407207) lmv2 lmv2 lmv2
                             -711407207))
                         '(1140219 0 41816 0 0 0 0 0 0) :end 9))
         nil)
; in: LAMBDA NIL
;     #'(LAMBDA (LMV2 LMV5) (* (+ LMV2 -711407207) LMV2 LMV2 LMV2 -711407207))
;
; caught STYLE-WARNING:
;   The variable LMV5 is defined but never used.
; compilation unit finished
;   caught 1 STYLE-WARNING condition

NIL
* (defvar b)

B
* (time (progn (setq b (isqrt (abs a))) nil))

Evaluation took:
  33.22 seconds of real time
  32.67 seconds of user run time
  0.16 seconds of system run time
  0 page faults and
  4,742,976 bytes consed.
NIL
* a
[very large bignum snipped]

* b

[very large integer snipped]

Maybe you meant something else? I notice (or rather, sbcl notices for 
me) that lmv5 is unused in the computation that sets a.

BTW, LWM 4.4 can compute both a an b, but hangs trying to print a.

regards,

Ralph
From: Svein Ove Aas
Subject: Re: Bignum limits
Date: 
Message-ID: <cp2l0b$eil$1@services.kq.no>
Peter Seibel wrote:

> Are there current Common Lisp implementations wherein bignums are
> limited by something other than sheer available memory? For example,
> an implementation might use some representation that otherwise limits
> the maximum size of a bignum.
> 
Plenty. For example, in SBCL you're limited to somewhere between 2^28 and
2^29 bits.
From: Svein Ove Aas
Subject: Re: Bignum limits
Date: 
Message-ID: <cp2lis$i95$1@services.kq.no>
Svein Ove Aas wrote:

> Peter Seibel wrote:
> 
>> Are there current Common Lisp implementations wherein bignums are
>> limited by something other than sheer available memory? For example,
>> an implementation might use some representation that otherwise limits
>> the maximum size of a bignum.
>> 
> Plenty. For example, in SBCL you're limited to somewhere between 2^28 and
> 2^29 bits.

The reason being, you need to represent the length of the bignum somehow,
usually by a fixnum. Also, it so happened that no more fitted into SBCL's
virtual address space. I can only assume it used a sparse array, either
from the OS's point of view or SBCL's.
From: Peter Seibel
Subject: Re: Bignum limits
Date: 
Message-ID: <m34qizui29.fsf@javamonkey.com>
Svein Ove Aas <·········@aas.no> writes:

> Peter Seibel wrote:
>
>> Are there current Common Lisp implementations wherein bignums are
>> limited by something other than sheer available memory? For example,
>> an implementation might use some representation that otherwise limits
>> the maximum size of a bignum.
>> 
> Plenty. For example, in SBCL you're limited to somewhere between 2^28 and
> 2^29 bits.

Yup--after I posted it occured to me to do some "science" and I
discovered that all the Lisp's I have lying around have limits around
that range.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Frode Vatvedt Fjeld
Subject: Re: Bignum limits
Date: 
Message-ID: <2hbrd7vzce.fsf@vserver.cs.uit.no>
Peter Seibel <·····@javamonkey.com> writes:

> Are there current Common Lisp implementations wherein bignums are
> limited by something other than sheer available memory? For example,
> an implementation might use some representation that otherwise
> limits the maximum size of a bignum.

I'll answer by a counter-question: For Movitz I chose a representation
of bignums that limits them to 2^14 bigits, or 2^19 bits. That should
make the biggest integer about 2^524288, or 10^104857. Does anyone
know of a practical situation where this can be insufficient?

-- 
Frode Vatvedt Fjeld
From: Pascal Bourguignon
Subject: Re: Bignum limits
Date: 
Message-ID: <873byj12a6.fsf@thalassa.informatimago.com>
Frode Vatvedt Fjeld <······@cs.uit.no> writes:

> Peter Seibel <·····@javamonkey.com> writes:
> 
> > Are there current Common Lisp implementations wherein bignums are
> > limited by something other than sheer available memory? For example,
> > an implementation might use some representation that otherwise
> > limits the maximum size of a bignum.
> 
> I'll answer by a counter-question: For Movitz I chose a representation
> of bignums that limits them to 2^14 bigits, or 2^19 bits. That should
> make the biggest integer about 2^524288, or 10^104857. Does anyone
> know of a practical situation where this can be insufficient?

Big integers are useful in:
    - precise rationals,
    - arithmetic theory,
    - Goedelification(*),
    - crytography,
and not much more I can think of.

So, apart for cryptography, I don't see much use of big integers in a
kernel. 


(*) like: using a single big integer to represent a bitmap or even a
    pixmap:
      (defun color-at (pixmap x y)
         (ldb (byte 32 (+ x (* *row* y))) pixmap))
      (defun set-color-at (pixmap x y pixel)
         (dpb pixel (byte 32 (+ x (* *row* y))) pixmap)) ;; :-P

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
The world will now reboot; don't bother saving your artefacts.
From: Bruno Haible
Subject: Re: Bignum limits
Date: 
Message-ID: <cq1ubc$11a$1@laposte.ilog.fr>
Pascal Bourguignon wrote:

> Big integers are useful in:
>    - precise rationals,
>    - arithmetic theory,
>    - Goedelification(*),
>    - crytography,
> and not much more I can think of.
>
> So, apart for cryptography, I don't see much use of big integers in a
> kernel. 

Big integers are also useful to avoid undefined behaviour that appears
due to overflow or wrap-around of limited-size integer variables. This
is highly useful for increasing the security of a kernel.

For example, the Java ProgressBar class contains code with the
explicit purpose that the progress bar always grows and never shrinks.
By exploiting an overflow in 32-bit 'int' arithmetic, I could
manipulate it in such a way that the progress bar comes back to 0%
after it has attained 100%.

What I can do with a Java class, people can also do with a kernel's
system call. Then you find it mentioned on Bugtraq...

Bruno