bignums in clisp

[((( 1/f )))]

dear forum,

I'm very new to LISP but not to programming, and my main interest is experimental mathematics.

I wanted to know how big the numbers could be for calculation, and I was under the assumption that one could go anywhere as long as the computer didn't crash. It appears that the limit is:

2^2097089 - 1 and any command will overflow beyond that. I just calculated the
number of digits roughly in my version of clisp ( 2.48) running on a linux box:

>(length (write-to-string (- (expt 2 2097085) 1)))
631286

Is there any way to increase this to a much higher, arbitrary limit?

-------------------------------------------------------
(((1/f)))

[Pascal J. Bourguignon]

"((( 1/f )))" <fad...@gmail.com> writes:

> dear forum,
>
> I'm very new to LISP but not to programming, and my main interest is experimental mathematics.
>
> I wanted to know how big the numbers could be for calculation, and I was under the assumption that one could go anywhere as long as the computer didn't crash. It appears that the limit is:
>
> 2^2097089 - 1 and any command will overflow beyond that. I just calculated the
> number of digits roughly in my version of clisp ( 2.48) running on a linux box:
>
>>(length (write-to-string (- (expt 2 2097085) 1)))
> 631286
>
> Is there any way to increase this to a much higher, arbitrary limit?

Obviously, you can compute a number that's 1 bigger than the limit
you're saying: (expt 2 2097085).

But otherwise you're right, there's a limit.

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[Sam Steingold]

> * ((( 1/f ))) <snq...@tznvy.pbz> [2012-09-12 02:34:46 -0700]:

>
> I wanted to know how big the numbers could be for calculation, and I was
> under the assumption that one could go anywhere as long as the computer
> didn't crash. It appears that the limit is:
>
> 2^2097089 - 1 and any command will overflow beyond that. I just calculated the
> number of digits roughly in my version of clisp ( 2.48) running on a linux box:

the limits are documented here:
http://www.clisp.org/impnotes/num-concepts.html#num-const

>>(length (write-to-string (- (expt 2 2097085) 1)))
> 631286
>
> Is there any way to increase this to a much higher, arbitrary limit?

http://www.cygwin.com/acronyms/#PTC


--
Sam Steingold (http://sds.podval.org/) on Ubuntu 12.04 (precise) X 11.0.11103000
http://www.childpsy.net/ http://mideasttruth.com http://www.memritv.org
http://www.PetitionOnline.com/tap12009/ http://iris.org.il http://dhimmi.com
In every non-trivial program there is at least one bug.

[Ian Clifton]

Sam Steingold <s...@gnu.org> writes:

>> * ((( 1/f ))) <snq...@tznvy.pbz> [2012-09-12 02:34:46 -0700]:
>>
>> I wanted to know how big the numbers could be for calculation, and I was
>> under the assumption that one could go anywhere as long as the computer
>> didn't crash. It appears that the limit is:
>>
>> 2^2097089 - 1 and any command will overflow beyond that. I just
>> calculated the
>> number of digits roughly in my version of clisp ( 2.48) running on a
>> linux box:
>
> the limits are documented here:
> http://www.clisp.org/impnotes/num-concepts.html#num-const

Wow, I never realised that (in clisp) long-floats can represent even
bigger numbers than bignums.
--
Ian ◎

[Barry Margolin]

In article <k44gnl$o33$1...@news.ox.ac.uk>,

But not to with as much precision.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[Kaz Kylheku]

On 2012-09-28, Barry Margolin <bar...@alum.mit.edu> wrote:
> In article <k44gnl$o33$1...@news.ox.ac.uk>,
> Ian Clifton <ian.c...@chem.ox.ac.uk> wrote:
>
>> Sam Steingold <s...@gnu.org> writes:
>>
>> >> * ((( 1/f ))) <snq...@tznvy.pbz> [2012-09-12 02:34:46 -0700]:
>> >>
>> >> I wanted to know how big the numbers could be for calculation, and I was
>> >> under the assumption that one could go anywhere as long as the computer
>> >> didn't crash. It appears that the limit is:
>> >>
>> >> 2^2097089 - 1 and any command will overflow beyond that. I just
>> >> calculated the
>> >> number of digits roughly in my version of clisp ( 2.48) running on a
>> >> linux box:
>> >
>> > the limits are documented here:
>> > http://www.clisp.org/impnotes/num-concepts.html#num-const
>>
>> Wow, I never realised that (in clisp) long-floats can represent even
>> bigger numbers than bignums.
>
> But not to with as much precision.

They are not "bigger", just more, err, "magnitudinous"!

Bigger means, strictly, occupying more RAM. :)

[RG]

In article <201209281...@kylheku.com>,

Anyone interested in big numbers should read this:

http://mrob.com/pub/math/largenum.html

http://mrob.com/pub/perl/hypercalc.html

rg

[Barry Margolin]

In article <201209281...@kylheku.com>,
Kaz Kylheku <k...@kylheku.com> wrote:

It obviously depends on the context. I'm pretty sure he meant it in the
normal, mathematical sense, in which 10 is bigger than 9.

[Nils M Holm]

RG <rNOS...@flownet.com> wrote:
> Anyone interested in big numbers should read this:
>
> http://mrob.com/pub/math/largenum.html

Definitely! This article changed my perspective on large numbers.

--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org

[Ian Clifton]

I suppose it would be possible—not perhaps sensible, but possible—to
have a Lisp implementation whose bignum type had a length which could
expand as necessary beyond integer to itself become a bignum of the same
kind. Such a Lisp could represent any integer, I guess.

--
Ian ◎

[Paul Wallich]

Aren't you going to run out of memory long before then? Perhaps there
should be bignums with some kind of sparse-byte or runlength encoding.

paul

[Pascal J. Bourguignon]

So you don't read the links given to you. Interesting.

[Pascal J. Bourguignon]

Of course. There are a finite number of integers whose lengths are
smaller than the number of particules in the Universe. On the other
hand, there are an infinite number of integers whose lengths are bigger
than the number of particules in the Universe. Such a trivial truth
doesn't seem to be known even by "educated" people. I despair of
humanity.

[Ian Clifton]

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

> Ian Clifton <ian.c...@chem.ox.ac.uk> writes:
>
>> Barry Margolin <bar...@alum.mit.edu> writes:
>>
>>> In article <201209281...@kylheku.com>,
>>> Kaz Kylheku <k...@kylheku.com> wrote:
>>>
>>>> They are not "bigger", just more, err, "magnitudinous"!
>>>>
>>>> Bigger means, strictly, occupying more RAM. :)
>>>
>>> It obviously depends on the context. I'm pretty sure he meant it in the
>>> normal, mathematical sense, in which 10 is bigger than 9.
>>
>> I suppose it would be possible—not perhaps sensible, but possible—to
>> have a Lisp implementation whose bignum type had a length which could
>> expand as necessary beyond integer to itself become a bignum of the same
>> kind. Such a Lisp could represent any integer, I guess.
>
> So you don't read the links given to you. Interesting.

I did briefly read and enjoy (some of) the links, and I did hint that my
suggestion wasn’t entirely sensible!
--
Ian ◎

[Paul Wallich]

I certainly despair of its sense of humor.

[Ian Clifton]

Sorry! I just thought it was interesting that such a scheme could (I
think) be implemented (although you’d have to work out how to do
indexing of data structures by bignum etc), even though we all know it
couldn’t possibly work in any useful sense. I recall that Bart Simpson
once lined up several police bull‐horns, the output of one feeding into
the microphone of the next, in order to produce a stupendously loud
sound. Of course this wouldn’t work either, but you could attempt the
experiment.

--
Ian ◎

[Pascal J. Bourguignon]

Ian Clifton <ian.c...@chem.ox.ac.uk> writes:

> Sorry! I just thought it was interesting that such a scheme could (I
> think) be implemented (although you’d have to work out how to do
> indexing of data structures by bignum etc), even though we all know it
> couldn’t possibly work in any useful sense. I recall that Bart Simpson
> once lined up several police bull‐horns, the output of one feeding into
> the microphone of the next, in order to produce a stupendously loud
> sound. Of course this wouldn’t work either, but you could attempt the
> experiment.

Well we're speaking of lisp here, so there's a solution. It's easy to
represent a number bigger than the universe in lisp: just use a sexp!

(↑↑↑↑ 3 3)

(↑27↑ 3 3)

(lessp '(↑27↑ 3 3) (add '(↑27↑ 3 3) '(↑↑↑↑ 3 3)))

(defun ↑ (x y) (expt x y))
(defun ↑↑ (x y) (expt x (expt y y)))
(defun ↑↑↑ (x y) (expt x (expt y (expt y y))))
(defun ↑↑↑↑ (x y) (expt x (expt y (expt y (expt y y)))))

(↑↑ 3 3) --> 7625597484987

(↑↑↑ 3 3) can't be computed on current hardware, but you can still
represent this number, as the sexp (↑↑↑ 3 3), like you can represent 100
as: (* (expt 5 2) (expt 2 2)) or some other sexp.

And you can write functions like add and lessp that compute
symbolically. (You can use a theorem prover to implement them).

(defun add (a b)
(cond
((and (numberp a) (numberp b))
(+ a b))
((and (numberp a) (zerop a)) b)
((and (numberp b) (zerop b)) a)
(t `(+ ,a ,b))))

(add '(↑27↑ 3 3) '(↑↑↑↑ 3 3))
--> (+ (↑27↑ 3 3) (↑↑↑↑ 3 3))

[Nils M Holm]

Pascal J. Bourguignon <p...@informatimago.com> wrote:
> (defun ? (x y) (expt x y))
> (defun ?? (x y) (expt x (expt y y)))
> (defun ??? (x y) (expt x (expt y (expt y y))))
> (defun ???? (x y) (expt x (expt y (expt y (expt y y)))))

If you get tired of inventing ????'s (sorry, only ASCII here), notice
that the operator can be generalized for more then 4 ?'s as:

(f (- n 1) x (f n x (- y 1)))

where F is the function implementing the operators and N is the order
of the operator (number of ?'s). See also: hyper operator.

Here's an implementation in Scheme: http://t3x.org/s9fes/hyper.scm.html

[Don Geddis]

"Pascal J. Bourguignon" <p...@informatimago.com> wrote on Wed, 03 Oct 2012:
> Well we're speaking of lisp here, so there's a solution. It's easy to
> represent a number bigger than the universe in lisp: just use a sexp!

It seems like you're heading down the path of using textual character
representations, to describe big numbers. Surely, before too long,
you'll just follow the standard sequence of such inventions, and wind up
at the usual
busy-beaver(99)
which likely beats any other number you could describe with a similar
small number of characters.

But presumably, people are looking for a representation of a large
integer N, such that the representation is capable of referring to any
of the integers from 1..N.

It kind of changes the problem, if you're just trying to describe (a
few, special) very big numbers in a small number of characters.

-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ d...@geddis.org
You might be an economist if you refuse to sell your children because they
might be worth more later. -- Yoram Bauman