Arbitrary length integer in Ada

Question

Hello!

I am currently teaching myself Ada and though I could begin by tackling some of the more conventional problems to get started.

More specifically I try to calculate the factorial n!, whereas n>100. My implementation so far is:

with Ada.Text_IO;
with Ada.Integer_Text_IO;

use Ada.Text_IO;

procedure Factorial is 
    -- define a type covering the range beginning at 1 up to which faculty is to
    -- be computed.
    subtype Argument is Long_Long_Integer range 1..100;

    -- define a type that is large enough to hold the result
    subtype Result is Long_Long_Integer range 1..Long_Long_Integer'Last;
    package Result_IO is new Ada.Text_IO.Integer_IO(Result); use Result_IO;

    -- variable holding the faculty calculated.
    fac : Result := 1;

begin
    -- loop over whole range of ARGUMENT and calculate n!
    for n in ARGUMENT loop
     fac := (fac * n);
    end loop;
end;

The problem is obviously that even Long_Long_Integer is may too small for this and throws a CONTRAINT_ERROR exception for n>20.

Is there a package that implements arbitrary-sized integers?

Thanks!

PS: I did opt against recursion because I wanted to explore loops in this exercise. But otherwise please comment on all aspects of the code (style, best-practices, error..)

Answer 1

Hello Arne,

The Ada Crypto Library supports big unsigned numbers (Big_Numbers). You can download the lib from http://sourceforge.net/projects/libadacrypt-dev/. I recommend checking out the svn. The Big_Numbers multiplication function of the current release has a minor bug.

You can compile the lib with the current GNAT compiler from the AdaCore Libre site.

The lib will not compile under gcc-4.3 or gcc-4.4 because of a bug in gcc.

Finally, I will give you a small exmple how to multiply two 512-bit Big_Numbers from the LibAdaCrypt.

package Test.Big_Numbers is

with Crypto.Types.Big_Numbers;

pragma Elaborate_All(Crypto.Types.Big_Numbers);

package Big is new Crypto.Types.Big_Numbers(512);
    use Big;
    use Big.Utils;
end Test.Big_Numbers;



package body Test.Big_Numbers is

x : Big_Unsigned := To_Big_Unsigned("16#57C19F8F7866F8633AC1D25B92FC83B4#");
Y : Big_Unsigned := To_Big_Unsigned("16#FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF60#");

x := X * Y;
Put_Line(X);

end Test.Big_Numbers;

 
Best regards
   Christian

Answer 2

From what I gather, every Ada compiler comes with arbitrary length arithmetic built-in. It is required to support named numbers (typeless numeric constants) the way the language has them defined.

Given that, its a shame the standard didn't provide us users standard access to that facility. Then again, usable for what the compiler needs, and usable for general use might often be two different things.