BigInteger support in DWScript

pi-blackDWScript now has support for the BigInteger type, which supports numbers with as many decimals as the memory allows.

This support comes in two flavors, either through a MPIR dll (a GMP fork) or through Rudy Velthui’s BigIntegers unit.

The support can be added by having a reference to the relevant units in your project.

Implementations

The BigIntegers implementation is in the dwsBigIntegerFunctions.RV unit, note that at the moment there are some buffer overflow issues, so it should be considered experimental.

The MPIR/GMP implementation is in dwsBigIntegerFunctions.GMP unit, which requires an mpir.dll. That DLL should be placed somewhere your binary can access, or you can use the dwsMPIR.Bundle unit, which will bundle the DLL into your executable.

The MPIR bundle unit adds the dll as a resource of the executable, and extracts it when needed to the temporary folder (a cryptographic SHA-3 hash is used to name and check the extracted dll, providing both version management and tamper-proofing). The bundling is only supported for 32 bits at the moment, and the dll was compiled with Visual C++ 2015, so you may need to install the Visual C++ 2015 redistributable on older systems.

Sample code

The BigInteger type in scripts supports all the usual operators as well as a variety of functions and helpers.

For illustration, below is a Rabin-Miller primality test for a prime sextuplet. Note that there is an IsPrime function/helper available which leverages the MPIR, so the Rabin-Miller code below is really for illustration.

function RabinMiller(n : BigInteger; k : Integer) : String;
begin
   if n <= 1 then exit 'prime';
   if not n.IsOdd then exit 'multiple of two';

   var d := n - 1;
   var s := 0;

   while not d.IsOdd do begin
      d := d div 2;
      s += 1;
   end;

   for var i := 1 to k do begin

      var a := 2 + RandomBigInteger( n-4 );

      var x := a.ModPow(d, n);
      if (x = 1) or (x = n - 1) then
         continue;

      for var j := 1 to s-1 do begin
         x := x.ModPow(2, n);
         if x = 1 then
            exit 'composite1';
         if x = n-1 then
            break;
      end;
      if x <> n-1 then
         exit 'composite2';
   end;
   Result := 'probably prime';
end;

// from Riecoin block 500
var n := BigInteger('40378229068348060265902071710277325464903647442059563624162746921011818446300065249638243017389009856122930741656904767');
if not Odd(n) then exit;

for var k := 0 to 22 step 2 do begin
   Print('n+' + k.ToString + ' : ');
   PrintLn(RabinMiller(n+k, 6));
end;

One thought on “BigInteger support in DWScript

Comments are closed.