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