> < ^ Date: Wed, 09 Feb 1994 14:24:00 +0100
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: Range limits
Thomas Bending writes in his e-mail message of 1994/02/08

There seems to be an upper limit on the integers that can form the end of
a Range - 10^8 works but 10^9 doesn't. Furthermore I think the error
message this causes is rather misleading:

gap> Length([1..10^9]);
Error, Range: <high> must be an integer
gap> Length([10^9..10^9+1]);
Error, Range: <low> must be an integer
gap> IsInt(10^9);

I can't find any documentation on this - am I missing something?

Internally GAP distinguishes between three types of integers.
Integers between -2^28 and 2^28-1 called *small integers*,
integers larger than 2^28-1 called *large positive integers*,
and integers less than -2^28 called *large negative integers*.

Large integers are represented by a pointer to a block of memory (called
a bag) where the individual digits (in base 2^16) are stored. For small
integers no pointer is used. Instead the value is stored immediatly
(after shifting it two bits to the left and adding one, so that it is
possible to distinguish between immediate integers and pointers).

In certain places GAP needs immediate integers. One place are ranges,
i.e., in [<low>..<high>] <low> and <high> must be small integers. This
may get fixed in the near future. Another place are indices into lists,
i.e., in '<list>[<index>]' <index> must be a small integer. To fix this
one would first have to implement a sparse representation for lists where
the amount of memory allocated for a list depends on the number of
assigned entries. With the current dense representation the amount of
memory depends on the largest position of any assigned entry. So the
list 'l := []; l[10^9] := 1;' would need '4*10^9' bytes, clearly more
than most machines have. To implement such a sparse representation and
then allow large integers as indices is not among our immediate plans.

Cleary a better error message would be desirable. And, I agree, it would
also be nice if the documentation mentioned this problem.


-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]