comp.lang.ada
 help / color / mirror / Atom feed
* Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
@ 2021-12-22  5:57 Michael Ferguson
  2021-12-22  8:25 ` Mark Lorenzen
                   ` (3 more replies)
  0 siblings, 4 replies; 24+ messages in thread
From: Michael Ferguson @ 2021-12-22  5:57 UTC (permalink / raw)


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;

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22  5:57 Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits? Michael Ferguson
@ 2021-12-22  8:25 ` Mark Lorenzen
  2021-12-22 11:14 ` AdaMagica
                   ` (2 subsequent siblings)
  3 siblings, 0 replies; 24+ messages in thread
From: Mark Lorenzen @ 2021-12-22  8:25 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22  5:57 Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits? Michael Ferguson
  2021-12-22  8:25 ` Mark Lorenzen
@ 2021-12-22 11:14 ` AdaMagica
  2021-12-22 11:32   ` AdaMagica
                     ` (2 more replies)
  2021-12-22 17:01 ` Luke A. Guest
  2021-12-23 15:48 ` Jeffrey R.Carter
  3 siblings, 3 replies; 24+ messages in thread
From: AdaMagica @ 2021-12-22 11:14 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 11:14 ` AdaMagica
@ 2021-12-22 11:32   ` AdaMagica
  2021-12-22 16:04   ` AdaMagica
  2021-12-22 20:34   ` Simon Wright
  2 siblings, 0 replies; 24+ messages in thread
From: AdaMagica @ 2021-12-22 11:32 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 11:14 ` AdaMagica
  2021-12-22 11:32   ` AdaMagica
@ 2021-12-22 16:04   ` AdaMagica
  2021-12-22 17:37     ` Niklas Holsti
  2021-12-22 20:34   ` Simon Wright
  2 siblings, 1 reply; 24+ messages in thread
From: AdaMagica @ 2021-12-22 16:04 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22  5:57 Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits? Michael Ferguson
  2021-12-22  8:25 ` Mark Lorenzen
  2021-12-22 11:14 ` AdaMagica
@ 2021-12-22 17:01 ` Luke A. Guest
  2021-12-22 17:27   ` Michael Ferguson
  2021-12-23 15:48 ` Jeffrey R.Carter
  3 siblings, 1 reply; 24+ messages in thread
From: Luke A. Guest @ 2021-12-22 17:01 UTC (permalink / raw)


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?

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 17:01 ` Luke A. Guest
@ 2021-12-22 17:27   ` Michael Ferguson
  2021-12-22 17:43     ` Ben Bacarisse
                       ` (4 more replies)
  0 siblings, 5 replies; 24+ messages in thread
From: Michael Ferguson @ 2021-12-22 17:27 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 16:04   ` AdaMagica
@ 2021-12-22 17:37     ` Niklas Holsti
  0 siblings, 0 replies; 24+ messages in thread
From: Niklas Holsti @ 2021-12-22 17:37 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 17:27   ` Michael Ferguson
@ 2021-12-22 17:43     ` Ben Bacarisse
  2021-12-22 17:48     ` Niklas Holsti
                       ` (3 subsequent siblings)
  4 siblings, 0 replies; 24+ messages in thread
From: Ben Bacarisse @ 2021-12-22 17:43 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 17:27   ` Michael Ferguson
  2021-12-22 17:43     ` Ben Bacarisse
@ 2021-12-22 17:48     ` Niklas Holsti
  2021-12-22 18:02       ` Michael Ferguson
  2021-12-22 19:26     ` Mark Lorenzen
                       ` (2 subsequent siblings)
  4 siblings, 1 reply; 24+ messages in thread
From: Niklas Holsti @ 2021-12-22 17:48 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 17:48     ` Niklas Holsti
@ 2021-12-22 18:02       ` Michael Ferguson
  2021-12-22 19:05         ` Niklas Holsti
  0 siblings, 1 reply; 24+ messages in thread
From: Michael Ferguson @ 2021-12-22 18:02 UTC (permalink / raw)


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

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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 18:02       ` Michael Ferguson
@ 2021-12-22 19:05         ` Niklas Holsti
  2021-12-23  8:31           ` Luke A. Guest
  2021-12-23 11:41           ` AdaMagica
  0 siblings, 2 replies; 24+ messages in thread
From: Niklas Holsti @ 2021-12-22 19:05 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 17:27   ` Michael Ferguson
  2021-12-22 17:43     ` Ben Bacarisse
  2021-12-22 17:48     ` Niklas Holsti
@ 2021-12-22 19:26     ` Mark Lorenzen
  2021-12-22 20:43       ` Niklas Holsti
  2021-12-22 20:31     ` Paul Rubin
  2021-12-22 20:39     ` Paul Rubin
  4 siblings, 1 reply; 24+ messages in thread
From: Mark Lorenzen @ 2021-12-22 19:26 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 17:27   ` Michael Ferguson
                       ` (2 preceding siblings ...)
  2021-12-22 19:26     ` Mark Lorenzen
@ 2021-12-22 20:31     ` Paul Rubin
  2021-12-22 20:39     ` Paul Rubin
  4 siblings, 0 replies; 24+ messages in thread
From: Paul Rubin @ 2021-12-22 20:31 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 11:14 ` AdaMagica
  2021-12-22 11:32   ` AdaMagica
  2021-12-22 16:04   ` AdaMagica
@ 2021-12-22 20:34   ` Simon Wright
  2 siblings, 0 replies; 24+ messages in thread
From: Simon Wright @ 2021-12-22 20:34 UTC (permalink / raw)


AdaMagica <christ-usch.grein@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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 17:27   ` Michael Ferguson
                       ` (3 preceding siblings ...)
  2021-12-22 20:31     ` Paul Rubin
@ 2021-12-22 20:39     ` Paul Rubin
  4 siblings, 0 replies; 24+ messages in thread
From: Paul Rubin @ 2021-12-22 20:39 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 19:26     ` Mark Lorenzen
@ 2021-12-22 20:43       ` Niklas Holsti
  0 siblings, 0 replies; 24+ messages in thread
From: Niklas Holsti @ 2021-12-22 20:43 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 19:05         ` Niklas Holsti
@ 2021-12-23  8:31           ` Luke A. Guest
  2021-12-23  8:54             ` Dmitry A. Kazakov
  2021-12-23 11:41           ` AdaMagica
  1 sibling, 1 reply; 24+ messages in thread
From: Luke A. Guest @ 2021-12-23  8:31 UTC (permalink / raw)


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?

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-23  8:31           ` Luke A. Guest
@ 2021-12-23  8:54             ` Dmitry A. Kazakov
  0 siblings, 0 replies; 24+ messages in thread
From: Dmitry A. Kazakov @ 2021-12-23  8:54 UTC (permalink / raw)


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).
> 
> Is mod overloadable?

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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22 19:05         ` Niklas Holsti
  2021-12-23  8:31           ` Luke A. Guest
@ 2021-12-23 11:41           ` AdaMagica
  2021-12-23 12:18             ` Niklas Holsti
  1 sibling, 1 reply; 24+ messages in thread
From: AdaMagica @ 2021-12-23 11:41 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-23 11:41           ` AdaMagica
@ 2021-12-23 12:18             ` Niklas Holsti
  2021-12-23 14:01               ` Ben Bacarisse
  0 siblings, 1 reply; 24+ messages in thread
From: Niklas Holsti @ 2021-12-23 12:18 UTC (permalink / raw)


On 2021-12-23 13:41, AdaMagica wrote:
> 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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-23 12:18             ` Niklas Holsti
@ 2021-12-23 14:01               ` Ben Bacarisse
  0 siblings, 0 replies; 24+ messages in thread
From: Ben Bacarisse @ 2021-12-23 14:01 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-22  5:57 Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits? Michael Ferguson
                   ` (2 preceding siblings ...)
  2021-12-22 17:01 ` Luke A. Guest
@ 2021-12-23 15:48 ` Jeffrey R.Carter
  2021-12-24  9:09   ` AdaMagica
  3 siblings, 1 reply; 24+ messages in thread
From: Jeffrey R.Carter @ 2021-12-23 15:48 UTC (permalink / raw)


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

^ permalink raw reply	[flat|nested] 24+ messages in thread

* Re: Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits?
  2021-12-23 15:48 ` Jeffrey R.Carter
@ 2021-12-24  9:09   ` AdaMagica
  0 siblings, 0 replies; 24+ messages in thread
From: AdaMagica @ 2021-12-24  9:09 UTC (permalink / raw)


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.

^ permalink raw reply	[flat|nested] 24+ messages in thread

end of thread, other threads:[~2021-12-24  9:09 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-12-22  5:57 Ada.Numerics.Big_Numbers.Big_Integer has a limit of 300 digits? Michael Ferguson
2021-12-22  8:25 ` Mark Lorenzen
2021-12-22 11:14 ` AdaMagica
2021-12-22 11:32   ` AdaMagica
2021-12-22 16:04   ` AdaMagica
2021-12-22 17:37     ` Niklas Holsti
2021-12-22 20:34   ` Simon Wright
2021-12-22 17:01 ` Luke A. Guest
2021-12-22 17:27   ` Michael Ferguson
2021-12-22 17:43     ` Ben Bacarisse
2021-12-22 17:48     ` Niklas Holsti
2021-12-22 18:02       ` Michael Ferguson
2021-12-22 19:05         ` Niklas Holsti
2021-12-23  8:31           ` Luke A. Guest
2021-12-23  8:54             ` Dmitry A. Kazakov
2021-12-23 11:41           ` AdaMagica
2021-12-23 12:18             ` Niklas Holsti
2021-12-23 14:01               ` Ben Bacarisse
2021-12-22 19:26     ` Mark Lorenzen
2021-12-22 20:43       ` Niklas Holsti
2021-12-22 20:31     ` Paul Rubin
2021-12-22 20:39     ` Paul Rubin
2021-12-23 15:48 ` Jeffrey R.Carter
2021-12-24  9:09   ` AdaMagica

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox