IntXLib4Pascal

[Xor-el]

TIntX is a Pascal port of IntX arbitrary precision Integer library with fast, about O(N * log N) multiplication/division algorithms implementation. It provides all the basic arithmetic operations on Integers, comparing, bitwise shifting etc. It also allows parsing numbers in different bases and converting them to string, also in any base. The advantage of this library is its fast multiplication, division and from base/to base conversion algorithms. all the fast versions of the algorithms are based on fast multiplication of big Integers using Fast Hartley Transform which runs for O(N * log N * log log N) time instead of classic O(N^2).

Code Example

Here is a sample of code which uses TIntX to calculate 42 in power 1048576 (which is 2^20 (1 shl 20)):

Code: Pascal  [Select][+][-]

1. uses //including only the non-obvious
2. SysUtils, uIntX, uEnums;
3.  
4. procedure Calc();
5. var
6.   valA, valB: UInt32;
7.   Delta: Double;
8.  
9. begin
10.   valA := GetTickCount;
11.   TIntX.Pow(42, 1048576);
12.   valB := GetTickCount;
13.   Delta := (valB - valA) / 1000;
14.   ShowMessage(Format('time elapsed is %f seconds', [Delta]));
15. end;
16.  
17. procedure TForm1.Button1Click(Sender: TObject);
18.  
19. begin
20.   Calc();
21.   TIntX.GlobalSettings.MultiplyMode := TMultiplyMode.mmClassic;
22.   Calc();
23. end;

First 'Calc()' call uses fast multiplication implementation (which is default),
second, classic one. On my machine (Windows 10 Update 2, Intel Core i3 2.53 GHz,
6 GB RAM), Compiled with 64 bits, first call took 0.30 seconds while the second one
took 17.91 seconds.Resulting number has 1,702,101 digits.


Some other functions implemented internally by me are

 

IntegerSquareRoot (Integer SquareRoot)
  Square
  GCD (Greatest Common Divisor (HCF))
  LCM (Least Common Multiple)
  AbsoluteValue (Get Absolute Value of a Negative TIntX)
  Bézouts Identity
  InvMod (Modular Inverse)
  Factorial
  IntegerLogN (base, number) (Gets IntegerLog of a number using a specified base)
  Ln (The natural logarithm)
  Log10 (The base-10 logarithm)
  LogN (Logarithm of a number for a specified base)
  Random (Now Uses PcgRandom Instead of Mersemme Twister)
  Modular Exponentiation (ModPow)
  IsProbablyPrime (based on Miller Rabin Primality Test)

As you can see, TIntX implements all the standard arithmetic operators using operator overloading so its usage is transparent for developers, like if you're working with usual Integers.

download

https://github.com/Xor-el/IntXLib4Pascal

[howardpc]

Thanks for sharing this library.
It looks impressive.
On my machine results for your simple example were 0.21s for the fast routine and 8.84s for the classic routine.
(I had to remove a reference to the C: drive in the package unit output directory to get it to compile successfully on my Linux system).

Edit: This is with an 8-core x86-64 cpu on Linux Mint. Altering the optimization level between -O1 and -O4 makes no significant difference to the times obtained.

[Xor-el]

wow,
thanks for benchmarking.
my test conditions are

compiled for win 64 x86-64 in release mode.
optimization level 4.

edit

on my Ubuntu installation

first routine (fast) finishes in 0.36 secs
second routine (classic) finishes in 17.85secs.