Big Integers in Turbo Pascal 3.01A (4)
As promised, time for a little bit of benchmarking using a common prime number algorithm. To build a little suspense, I compiled and ran my code under Free Pascal 3.04 on a Raspberry Pi B – an original 2012 version with 256Mb RAM that normally does duty as my audio server.
Sieve of Eratosthenes
The algorithm used (BigInt version) is in the code snippet below. The inbuilt Integer version is identical, swapping BigInts for Integers (or LongInts (32 bit) on the Raspberry Pi version) and the comparison, square root, modulo and add functions for their inbuilt counterparts.
...
type Primea = array [1..255] of BigInt;
var primearray: Primea;
limit, next: BigInt;
primecount : Integer;
function sieve(var number: BigInt; var pc: integer; var p: primea): boolean;
var count :Integer;
var sr, test :BigInt;
var foundprime :Boolean;
begin
sr := isqrt(number);
count := 1;
foundprime := TRUE;
while ((count <= pc) and foundprime) do begin
test := p[count];
if le(test,sr) and (modulo(number,test)='0') then
foundprime := FALSE;
count := count+1
end;
sieve := foundprime
end;
begin
limit := '100'; { Find all primes less than limit }
primecount := 0;
next := '3';
write('2');
while (le(next,limit)) do
begin
if sieve(next,primecount,primearray) then
begin
if primecount < 255 then
begin
primecount := primecount+1;
primearray[primecount] := next
end;
write(', ',next)
end;
next := add(next,'2')
end;
writeln(' ')
end.Raspberry Pi Model B Results
| All primes < n | Inbuilt LongInt (32 bit) type | BigInt type | Performance difference (magnitude) |
|---|---|---|---|
| 100 | 0.02s | 0.07s | 3.5x |
| 1,000 | 0.05s | 0.97s | 19.4x |
| 10,000 | 0.27s | 16.5s | 61.1x |
| 32,000 (*) | 0.85s | 71.0s | 83.5x |
| 100,000 | 2.3s | 302s | 131x |
| 1,000,000 | 22.3s | 5,993s | 269x |
Unsurprisingly the library is slower than using an inbuilt type … but it gets exponentially slower as the number of primes generated increases. This suggests there’s plenty of room for improvement!
If you’re of a nervous disposition, look away now as I’m about to attempt the same benchmark on a RC2014 with 64K RAM with a Z80 processor under CP/M. This may take some time …
RC2014 Results
| All primes < n | Inbuilt Integer (16 bit) type | BigInt type | Performance difference (magnitude) |
|---|---|---|---|
| 100 | 1s | 73s | 73x |
| 500 | 4s | 912s | 228x |
| 1,000 | 10s | — | — |
| 10,000 | 140s | — | — |
| 32,000 | 445s | — | — |
Even allowing for the difference in computational speed of a Z80 processor running at 7.3728MHz and a single core ARM1176JZF-S running at 700MHz, these figures indicate that there’s plenty of optimisation potential left to find, or alternatively, that I should stop working on this project now. But where would be the fun in that?
The fifth and final post in this series will cover some thoughts on optimisation and provide a link to all the code I’ve produced so far, should anyone else feel inclined to take this further.