Big Integers in Turbo Pascal 3.01A (5)

In the mid 1980s I owned a rear-engined Skoda Rapid. It had a ‘go faster’ stripe on each side, which made no difference to the underlying power of the 1.3 litre engine and 5 speed gearbox. My first efforts at optimising the performance of this library are rather like that stripe. They involve no changes to the underlying efficiency or complexity of the core algorithms. Instead, I’ve looked for things that are easy to implement. Algorithmic improvements will be saved for a v2 at some indeterminate point in the future, or I may just buy the equivalent of a Caterham 7 instead.

Enough of the tortured analogies. This is what I’ve done to the code.

• Removing calls to ord(‘0’) and replacing them with a constant. Impact – none visible. My guess is the compiler spots this and makes the substitution at compile time.
• Removing lots of superfluous semicolons (statement separators). I always forget to leave out semicolons before an ‘end’. They don’t harm the logic of the code, but they do insert an unnecessary ‘no operation’. Impact – none visible. Again. my guess it that the compiler is smart enough to remove these at compile time – it’s a common enough error made in Pascal programs.
• Streamlined the zapzeros function. This removes leading zeros from the result of some calculations. The code originally looked like this:

function zapzeros(num: BigInt; len: Integer): BigInt;
var i,j: Integer;
    out: BigInt;
begin
  out := '';
  i := 1;
  while (i < len) and (num[i]='0') do
    i :=  i + 1;
  if (i = len) and (num[i]='0') then { Result is 0 }
    out := '0'
  else
    for j := i to len do
      out := out+num[j];
  zapzeros := out
end;

It now looks like this – the loop has been replaced with a copy statement and the test on the ‘while’ loop has been reversed to check for the most common ending first.

function zapzeros(num: BigInt; len: Integer): BigInt;
var i: Integer;
begin
  i := 1;
  while (num[i]='0') and (i < len) do
    i :=  i + 1;
  zapzeros := copy(num,i,len+1-i)
end;

Impact – around a 5% speed improvement on generating the primes from 1 to 100 – 69s instead of 73s. By far the largest portion of this improvement comes from the use of the compiler’s copy function. Given the overhead of function calls it would probably make sense to inline the code but I haven’t done that so far … maintainability and readability have won out for the moment.

• Removal of the ‘isnum’ function. This was adding complexity of O(Σ length(BigInt parameters)) for every function call in the library. Its inclusion meant that you got a predictable ‘NaN’ result if you tried to use any function on non-numeric BigInts (strings), but it was hugely expensive in execution time.

function isnum(num: BigInt): Boolean;
var i: Integer;
    out: Boolean;
begin
  out := TRUE;
  if length(num) <= 0 then
    out := FALSE
  else if not(num[1] in ['-','0'..'9']) then
    out := FALSE
  else
  begin
    i := 2;
    while (i <= length(num)) and (out=TRUE) do
    begin
      if not(num[i] in ['0'..'9']) then
        out :=FALSE;
      i := i+1
    end;            { Yes, it even had unnecessary empty statements ... }
  end;
  isnum := out
end;

Impact – around a 50% improvement in execution speed when combined with the zapzeros change – bringing the time to generate the primes from 1 to 100 down from 69s to 37s.

There are other ‘go faster stripe’ improvements that can be made (for example, inlining the nines’ complement function), but they’re now starting to produce diminishing returns. Fundamentally a move away from replicating junior school maths in the library to more efficient algorithms is required … but that’s a reasonable amount of effort. And it’s summer. So I’m going to be spending it driving my Caterham 7 instead.

The library and documentation is available in this GitHub repository if anyone feels tempted to have a go at improving it before the winter sets in 🙂