Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?

[Michael Ferguson]

I just started using the Big_Integer library that is a part of the 202X version of ADA.

It is repeatedly described as an "arbitrary precision library" that has user defined implementation.

I was under the impression that this library would be able to infinitely calculate numbers of any length, but there is clearly a default limit of 300 digits.

Is there any way to get rid of this problem?

Here is some example code:

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Real_Time; use Ada.Real_Time;
with Ada.Numerics.Big_Numbers.Big_Integers;
use Ada.Numerics.Big_Numbers.Big_Integers;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

procedure Test is
package Time_IO is new Fixed_IO(Duration);
start_time, end_time : Ada.Real_Time.Time;
elapsed_seconds : Ada.Real_Time.Time_Span;
solution : Unbounded_String;

rop : Big_Integer;
sum : Big_Integer := 0;

begin
start_time := Ada.Real_Time.Clock;

for i in 1..700 loop
rop := To_Big_Integer(i) ** Natural(i);
sum := sum + rop;
end loop;
solution := To_Unbounded_String(sum'Image);


end_time := Ada.Real_Time.Clock;
elapsed_seconds := end_time - start_time;
Put("Solution: " & solution'Image); New_Line; New_Line;
Put("Program completed in ");
Time_IO.Put(To_Duration(elapsed_seconds), Fore => 0, Aft => 3);
Put(" seconds");
end BigTest;

[Mark Lorenzen]

On Wednesday, December 22, 2021 at 6:57:10 AM UTC+1, Michael Ferguson wrote:
> I just started using the Big_Integer library that is a part of the 202X version of ADA.
>
> It is repeatedly described as an "arbitrary precision library" that has user defined implementation.
>
> I was under the impression that this library would be able to infinitely calculate numbers of any length, but there is clearly a default limit of 300 digits.
>

How did you determine the limit of 300 digits? I see nothing in your example, that would imply such a limit. Are you sure that you are not reaching a line length limit in Text_IO or maybe a limit in the Image attribute?

Regards,
Mark L

[AdaMagica]

There is a limit
Bignum_Limit : constant := 200;
in System.Generic_Bignums body, function Normalize, lines 1100ff.

I do not see an implementation advice, implementation permission or implementation requirement about such limits in A.5.5, A.5.6.

But there is somewhere in the RM a paragraph stating that implementation may pose limits on certain features. I just cannot find the place in the RM.

[AdaMagica]

See RM 1.1.3(2).
I guess this limit is just a transient arbitrary limit until Ada 2022 is standardized.

[AdaMagica]

> Bignum_Limit : constant := 200;
RM 2.2(14) limiits the line length and the length of lexical elements to 200.

[Luke A. Guest]

On 22/12/2021 05:57, Michael Ferguson wrote:
> I just started using the Big_Integer library that is a part of the 202X version of ADA.
>
> It is repeatedly described as an "arbitrary precision library" that has user defined implementation.
>
> I was under the impression that this library would be able to infinitely calculate numbers of any length, but there is clearly a default limit of 300 digits.

What are you doing that requires that number of digits?

[Michael Ferguson]

I am working on ProjectEuler.net problem number 48.

The questions asks you to sum the numbers n^n for (2 <= n <= 1000) and determine what the last ten digits of this number are.

Obviously, this is quite a trivial problem when using any arbitrary precision library.

I had incorrectly determined that 700^700 had 300 digits, in fact 700^700 = 3.7E1991.

However, my code strictly breaks when the loop range is set to 683, which 683^683 = 8.12E1935.

So, that is interesting that the Big_Integer type works numbers of just under 2000 digit length despite Bignum_Limit : constant := 200.

[Niklas Holsti]

On 2021-12-22 18:04, AdaMagica wrote:
>> Bignum_Limit : constant := 200;
> RM 2.2(14) limiits the line length and the length of lexical elements to 200.

To express it more clearly, RM 2.2(14) requires implementations to
support lines and lexical elements of /at least/ 200 characters, but
/allows/ implementations to support longer lines and lexical elements.

I'm not sure if GNAT supports more than 200 characters, though. And of
course an Ada program that uses more than 200 characters may not be
portable to compilers that support only 200.

But I don't see any direct logical connection to the number of digits
that Big_Integers can support. While one cannot write a big-number
literal longer than a line or longer than the maximum length of a
lexical element, that should not directly limit the size of big-number
values in computations.

[Ben Bacarisse]

Michael Ferguson <michaelbla...@gmail.com> writes:

> On Wednesday, December 22, 2021 at 11:02:03 AM UTC-6, Luke A. Guest wrote:
>> On 22/12/2021 05:57, Michael Ferguson wrote:
>> > I just started using the Big_Integer library that is a part of the 202X version of ADA.
>> >
>> > It is repeatedly described as an "arbitrary precision library" that has user defined implementation.
>> >
>> > I was under the impression that this library would be able to
>> > infinitely calculate numbers of any length, but there is clearly a
>> > default limit of 300 digits.
>>
>> What are you doing that requires that number of digits?
>
> I am working on ProjectEuler.net problem number 48.
>
> The questions asks you to sum the numbers n^n for (2 <= n <= 1000) and
> determine what the last ten digits of this number are.
>
> Obviously, this is quite a trivial problem when using any arbitrary
> precision library.

Does Ada's Big_Integer type work with modular ranged types?

--
Ben.

[Niklas Holsti]

On 2021-12-22 19:27, Michael Ferguson wrote:
> On Wednesday, December 22, 2021 at 11:02:03 AM UTC-6, Luke A. Guest wrote:
>> On 22/12/2021 05:57, Michael Ferguson wrote:
>>> I just started using the Big_Integer library that is a part of the 202X version of ADA.
>>>
>>> It is repeatedly described as an "arbitrary precision library"
>>> that has user defined implementation.

Surely not "user defined"? Possibly "implementation defined".

>>> I was under the impression that this library would be able to
>>> infinitely calculate numbers of any length,

I have the same impression (up to Storage_Error, of course).

>> but there is clearly a default limit of 300 digits.
>> What are you doing that requires that number of digits?
>
> I am working on ProjectEuler.net problem number 48.
>
> The questions asks you to sum the numbers n^n for (2 <= n <= 1000)
> and determine what the last ten digits of this number are.
>
> Obviously, this is quite a trivial problem when using any arbitrary
> precision library.
>
> I had incorrectly determined that 700^700 had 300 digits, in fact
> 700^700 = 3.7E1991.
>
> However, my code strictly breaks when the loop range is set to 683,
> which 683^683 = 8.12E1935.

How does it break? Some exception, or something else?

Mark Lorenzen suggested in an earlier post that the limit might be in
the Big_Integer'Image function. The package
Ada.Numerics.Big_Numbers.Big_Integers has some other output operations
that you could try:

function To_String (Arg : Valid_Big_Integer; ...) return String;

procedure Put_Image (Buffer : ... ; Arg: in Valid_Big_Integer);

Of course those might be internally linked to the 'Image function and
have the same possible limitation.

[Michael Ferguson]

Not 100% sure what modular types are but I did try to do something like the following

subtype VeryBigInteger is Big_Integer range 0 .. 10E10000;

which gave "error: incorrect constraint for this kind of type"

Niklas also gave me an epiphany as the exact error my program gives for the upper limit is

raised STORAGE_ERROR : Ada.Numerics.Big_Numbers.Big_Integers.Bignums.Normalize: big integer limit exceeded

I had thought that since the end of this error said big integer limit exceeded it was a problem with the library, but now I'm starting to think I need to get GNAT to allocated more memory for the program.

[Niklas Holsti]

On 2021-12-22 20:02, Michael Ferguson wrote:
> On Wednesday, December 22, 2021 at 11:48:46 AM UTC-6, Niklas Holsti
> wrote:
>> On 2021-12-22 19:27, Michael Ferguson wrote:
>>> On Wednesday, December 22, 2021 at 11:02:03 AM UTC-6, Luke A.
>>> Guest wrote:
>>>> On 22/12/2021 05:57, Michael Ferguson wrote:
>>>>> I just started using the Big_Integer library that is a part
>>>>> of the 202X version of ADA.
>>>>>

[snip]

> Not 100% sure what modular types are

Types declared with "mod N" instead of "range A .. B", as in:

type Eight_Bits is mod 256;

which declares an unsigned type with a range 0 .. 255 and wrap-around
arithmetic.

Modular types are not connected to Big_Integers, except that the
particular problem you are trying to solve could be computed "mod
10**10" because it asks for only the last 10 digits. However, the
Big_Integers package does not directly support computations "mod"
something (perhaps this should be an extension in a later Ada standard,
because such computations are quite common).

Using "mod 10**10" operations in solving the problem would limit the
number of digits in all intermediate results drastically.

> but I did try to do something like the following
>
> subtype VeryBigInteger is Big_Integer range 0 .. 10E10000;
>
> which gave "error: incorrect constraint for this kind of type"

Indeed, such a range constraint is valid only for (visibly) scalar
types, which Big_Integer is not (it is a private type).

> Niklas also gave me an epiphany as the exact error my program gives
> for the upper limit is
>
> raised STORAGE_ERROR :
> Ada.Numerics.Big_Numbers.Big_Integers.Bignums.Normalize: big integer
> limit exceeded
>
> I had thought that since the end of this error said big integer limit
> exceeded it was a problem with the library, but now I'm starting to
> think I need to get GNAT to allocated more memory for the program.

Perhaps. However, the very specific exception message ("big integer
limit exceeded") suggests that this exception is not a typical
Storage_Error (say, heap or stack exhaustion) but may indeed stem from
exceeding some specific limit in the current Big_Integer implementation
in GNAT.

The size of your problem, with only a few thousand digits, suggests that
heap exhaustion is unlikely to happen. However, if the Big_Integer
computations are internally recursive, and use stack-allocated local
variables, stack overflow could happen, so the first thing to try would
be to increase the stack size. Unfortunately, for the main subprogram
that has to be done with some compiler or linker options which I don't
recall now. (We should really extend pragma Storage_Size to apply also
to the environment task, by specifying it for the main subprogram!)

[Mark Lorenzen]

On Wednesday, December 22, 2021 at 6:27:57 PM UTC+1, Michael Ferguson wrote:
> On Wednesday, December 22, 2021 at 11:02:03 AM UTC-6, Luke A. Guest wrote:
> > On 22/12/2021 05:57, Michael Ferguson wrote:
> > > I just started using the Big_Integer library that is a part of the 202X version of ADA.
> > >
> > > It is repeatedly described as an "arbitrary precision library" that has user defined implementation.
> > >
> > > I was under the impression that this library would be able to infinitely calculate numbers of any length, but there is clearly a default limit of 300 digits.
> > What are you doing that requires that number of digits?
> I am working on ProjectEuler.net problem number 48.
>
> The questions asks you to sum the numbers n^n for (2 <= n <= 1000) and determine what the last ten digits of this number are.

Interesting. Assume that the problem is related to the maximum size of lexical elements, can't you then use the "rem" function from Big_Integers to determine the last 10 digits e.g. by something like this Last_10_Digits = My_Very_Large_Number rem To_Big_Integer(1) ** 10?

This should give you a value of type Valid_Big_Integer consisting of up to ten digits that you can obtain the integer representation of.

Regards,
Mark L

[Paul Rubin]

Michael Ferguson <michaelbla...@gmail.com> writes:
> I am working on ProjectEuler.net problem number 48. ...

> Obviously, this is quite a trivial problem when using any arbitrary
> precision library.

The thing about Euler problems is they usually want you to figure out a
clever math trick to get to the solution, rather than using brute
calculation. In the case of this problem, you want to reduce all the
intermediate results mod 1e10 (which fits in an int64 easily, though not
quite in an int32). That gets rid of the need for bignums.

[Simon Wright]

AdaMagica <christ-u...@t-online.de> writes:

> There is a limit
> Bignum_Limit : constant := 200;
> in System.Generic_Bignums body, function Normalize, lines 1100ff.

This is the maximum length of a Digit_Vector, where

subtype SD is Interfaces.Unsigned_32;
-- Single length digit

type Digit_Vector is array (Length range <>) of SD;
-- Represent digits of a number (most significant digit first)

I think this should give a maximum value of ~10**2000.

I printed out sum'image'length; the last value before the exception was
1937.

[Paul Rubin]

Michael Ferguson <michaelbla...@gmail.com> writes:
> However, my code strictly breaks when the loop range is set to 683,
> which 683^683 = 8.12E1935.
>
> So, that is interesting that the Big_Integer type works numbers of
> just under 2000 digit length despite Bignum_Limit : constant := 200.

I wonder if the limit is 6400 bits (200 * 32 bit words) or something
related to that. 2**6400 is roughly 3.9e1926 if my math is right.

[Niklas Holsti]

On 2021-12-22 21:26, Mark Lorenzen wrote:
> On Wednesday, December 22, 2021 at 6:27:57 PM UTC+1, Michael Ferguson
> wrote:
>> On Wednesday, December 22, 2021 at 11:02:03 AM UTC-6, Luke A. Guest
>> wrote:
>>> On 22/12/2021 05:57, Michael Ferguson wrote:
>>>> I just started using the Big_Integer library that is a part of
>>>> the 202X version of ADA.
>>>>
>>>> It is repeatedly described as an "arbitrary precision library"
>>>> that has user defined implementation.
>>>>
>>>> I was under the impression that this library would be able to
>>>> infinitely calculate numbers of any length, but there is
>>>> clearly a default limit of 300 digits.
>>> What are you doing that requires that number of digits?
>> I am working on ProjectEuler.net problem number 48.
>>
>> The questions asks you to sum the numbers n^n for (2 <= n <= 1000)
>> and determine what the last ten digits of this number are.
>
> Interesting. Assume that the problem is related to the maximum size
> of lexical elements, can't you then use the "rem" function from
> Big_Integers to determine the last 10 digits e.g. by something like
> this Last_10_Digits = My_Very_Large_Number rem To_Big_Integer(1) **
> 10?

You no doubt meant To_Big_Integer (10), not To_Big_Integer(1).

But it should be possible to write directly "... rem 10_000_000_000",
and even if that constant is too large for the Integer type, because
Big_Integer has the Integer_Literal aspect (assuming GNAT already
implements it).

[Luke A. Guest]

On 22/12/2021 19:05, Niklas Holsti wrote:

> Big_Integers package does not directly support computations "mod"
> something (perhaps this should be an extension in a later Ada standard,
> because such computations are quite common).

Is mod overloadable?

[Dmitry A. Kazakov]

It is as any operator.

P.S. For large numbers one needs rather full division than separate /,
mod, rem.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[AdaMagica]

Niklas Holsti schrieb am Mittwoch, 22. Dezember 2021 um 20:05:21 UTC+1:
> However, the
> Big_Integers package does not directly support computations "mod"

It does A.5.6(18/5).

[Niklas Holsti]

Yes, there is a "mod" operator for Big_Integer. My point was that there
are no Big_Integer operations, such as multiplication, that are
intrinsically modular in the same way as the operations for modular
types are. So the only way to perform a modular multiplication of
Big_Integers is to first multiply the numbers in the usual way,
producing a possibly very large product, and then apply "mod" to reduce
that product.

In my imperfect understanding, intrinsically modular big-number
computations can be much more efficient than such post-computation
applications of "mod", at least if the modulus is not itself a big number.

[Ben Bacarisse]

Niklas Holsti <niklas...@tidorum.invalid> writes:

> In my imperfect understanding, intrinsically modular big-number
> computations can be much more efficient than such post-computation
> applications of "mod", at least if the modulus is not itself a big
> number.

Yes, there are efficient algorithms for "x * y mod n" so almost all "big
num" libraries provide a function to do it. Ada has the type system for
the mod operation to be explicit in the type.

--
Ben.

[Jeffrey R.Carter]

On 2021-12-22 06:57, Michael Ferguson wrote:
>
> I was under the impression that this library would be able to infinitely calculate numbers of any length, but there is clearly a default limit of 300 digits.

As it appears from the rest of the discussion that there is a limit in the
implementation of the pkg, you could try using PragmARC.Unbounded_Numbers.Integers

https://github.com/jrcarter/PragmARC/blob/Ada-12/pragmarc-unbounded_numbers-integers.ads

where the implementation restricts a number to Integer'Last "digits" or the
available heap memory, whichever is less.

Note that with recent versions of GNAT for 64-bit processors, the "digits" will
be 64 bits.

--
Jeff Carter
"There's no messiah here. There's a mess all right, but no messiah."
Monty Python's Life of Brian
84

[AdaMagica]

with Ada.Numerics.Big_Numbers.Big_Integers;
use Ada.Numerics.Big_Numbers.Big_Integers;
procedure Ausprobieren is
I: Big_Integer := (1E1000 + 1) / 3;
S: String := I'Image;
begin
Put_Line (S'Last'Image);
Put_Line (I'Image);
end Ausprobieren;

No problem here.