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

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

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