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

From Michael Ferguson@21:1/5 to All on Tue Dec 21 21:57:08 2021
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:

procedure Test is
package Time_IO is new Fixed_IO(Duration);
solution : Unbounded_String;

rop : Big_Integer;
sum : Big_Integer := 0;

begin

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

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;

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Mark Lorenzen@21:1/5 to Michael Ferguson on Wed Dec 22 00:25:26 2021
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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From AdaMagica@21:1/5 to All on Wed Dec 22 03:14:12 2021
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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From AdaMagica@21:1/5 to All on Wed Dec 22 03:32:23 2021
See RM 1.1.3(2).
I guess this limit is just a transient arbitrary limit until Ada 2022 is standardized.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From AdaMagica@21:1/5 to All on Wed Dec 22 08:04:29 2021
Bignum_Limit : constant := 200;
RM 2.2(14) limiits the line length and the length of lexical elements to 200.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Luke A. Guest@21:1/5 to Michael Ferguson on Wed Dec 22 17:01:56 2021
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?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Ben Bacarisse@21:1/5 to Michael Ferguson on Wed Dec 22 17:43:46 2021
Michael Ferguson <michaelblakeferguson@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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Niklas Holsti@21:1/5 to AdaMagica on Wed Dec 22 19:37:45 2021
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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Michael Ferguson@21:1/5 to Luke A. Guest on Wed Dec 22 09:27:56 2021
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.

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Niklas Holsti@21:1/5 to Michael Ferguson on Wed Dec 22 19:48:42 2021
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.

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Michael Ferguson@21:1/5 to Niklas Holsti on Wed Dec 22 10:02:41 2021
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.

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.

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.

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Niklas Holsti@21:1/5 to Michael Ferguson on Wed Dec 22 21:05:18 2021
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!)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Mark Lorenzen@21:1/5 to Michael Ferguson on Wed Dec 22 11:26:48 2021
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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Paul Rubin@21:1/5 to Michael Ferguson on Wed Dec 22 12:31:32 2021
Michael Ferguson <michaelblakeferguson@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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Niklas Holsti@21:1/5 to Mark Lorenzen on Wed Dec 22 22:43:49 2021
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

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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Paul Rubin@21:1/5 to Michael Ferguson on Wed Dec 22 12:39:42 2021
Michael Ferguson <michaelblakeferguson@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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Simon Wright@21:1/5 to AdaMagica on Wed Dec 22 20:34:20 2021

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Dmitry A. Kazakov@21:1/5 to Luke A. Guest on Thu Dec 23 09:54:34 2021
On 2021-12-23 09:31, Luke A. Guest wrote:
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).

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Luke A. Guest@21:1/5 to Niklas Holsti on Thu Dec 23 08:31:11 2021
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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From AdaMagica@21:1/5 to Niklas Holsti on Thu Dec 23 03:41:13 2021
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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Niklas Holsti@21:1/5 to AdaMagica on Thu Dec 23 14:18:34 2021
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).

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Ben Bacarisse@21:1/5 to Niklas Holsti on Thu Dec 23 14:01:47 2021
Niklas Holsti <niklas.holsti@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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Jeffrey R.Carter@21:1/5 to Michael Ferguson on Thu Dec 23 16:48:17 2021
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

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From AdaMagica@21:1/5 to All on Fri Dec 24 01:09:53 2021