Big Integers in Turbo Pascal 3.01A (1)

One of the unexpected delights of upgrading my RC2014 with the CP/M expansion has been discovering Turbo Pascal. Unexpected, because the last time I used Pascal for anything was sometime during the 1980s and I’d barely given the language a thought since.

But Turbo Pascal 3.01A is wonderful. It’s a very close implementation of the Wirth ‘standard’, generates fast executable code and has a really good editor. (This is a very low bar on CP/M, where ED reigns supreme). Granted, using Ctrl-K followed by d to exit the editor (and then having to remember to hit S to save the file before finally leaving the compiler) is somewhat idiosyncratic, but then as a long-time user of ‘vi’ I guess it’s every bit as sensible as typing <esc>:wq

The big limitation of Turbo Pascal compared with (say) MBASIC is the maximum integer size. They’re implemented as 16bit signed values – which gives a MAXINT of just 32,767. Ouch. Not much fun if you’re obsessed with prime number algorithms (who, me?). But … I could implement a user defined big integer type … couldn’t I?

A quick toot on Mastodon resulted in turning up no-one who would admit to trying such a thing in Pascal. A quick search of the interwebs found plenty of mentions of arbitrary precision arithmetic libraries in Java, Python, PHP and C++, but nothing in Pascal. There was little in the way of encouragement to others who had asked before on sites like stack overflow (“Why would you do such a thing? *snort*, just use xyz library for abc language like everyone else does” was the tone of most responses). There were some vaguely useful explanations on Wikipedia, but I seemed to be pretty much on my own. Just how I like it!

Much later on, towards the end of my own implementation work, I unearthed a very good explanation written by Bastian Molkenthin of the way he’d implemented a big integer library in C. Bastian’s recursive division function formed the inspiration for the one I implemented in Pascal after it became painfully obvious that an approach based on repeated subtraction was going to be hideously slow if the denominator was very much smaller than the numerator. But I’m getting ahead of myself …

The project goals I set were:

1. To implement signed integer addition, subtraction, multiplication, division and modulo, the logical comparison operators and a (positive) integer square root function.
2. To have some error checking in the library – e.g. returning NaN if a divide by zero was attempted or if an operation would mean that the maximum integer size would be exceeded.
3. To write something that would be portable enough to work on Turbo Pascal under CP/M 2.2 on the RC2014 and Free Pascal running on a Raspberry Pi with minimal differences.
4. To write a sieve of Eratosthenes prime number generator as a final test harness for the code.

Getting started is always the hardest part of the project, so I decided to start by writing a function to multiply two large integers, But first, what was I going to use to represent large integers in Pascal? Having looked at various approaches based on arrays and records, I decided that simplicity was best for the time being. So I chose the Turbo Pascal ‘string’ type (allowing an integer of up to 255 digits to be stored – take that, MAXINT!) and hid it behind a user defined type called BigInt. At least this way I figured I would be able to change tack if needed later.

Multiplication

Implemented using the ‘long multiplication’ approach taught in my 1970s primary school. The heart of the algorithm (leaving aside number validity and negative number handling) is simple:

1. Work out the maximum length of the result by adding the length of the two operands together.
2. Initialise the result to all zeros (e.g. if the multiplication requested was 51×25, then the initial result is 0000).
3. Working from the units column, multiply each of the digits in the first operand by all of the digits in the second operand, adding them to the result and dealing with carrys as necessary. For the example above:
   • Units: 1×5 = 5 with no carry, 5×5 = 5, carry 2, so 51×5 = 255
   • Units: = 0 (as this is the tens digit being processed), Tens: 1×2 = 2 with no carry, 5×2 = 0, carry 1, so 51×20 = 1,020
   • The total is therefore 1,275.
4. Remove any leading zeros from the result (and deal with the cases where one or both of the operands was negative).

In Pascal, the code fragment described above looks like this:

...      
 
{ Initialise the result as all zeros to start }
for i := 1 to (len1+len2) do
  out:= out + '0'; { num1, num2 and out are of type BigInt, which is a string }
idxcounter := 0;
{ Work backwards through the first number }
  for i := len1 downto 1 do
  begin
    carry := 0;
    idx := len1+len2-idxcounter;
    currnum := ord(num1[i])-ord('0');
    { Multiply this digit by every digit in the second number }
      for j := len2 downto 1 do
      begin
        total := (ord(num2[j])-ord('0'))*currnum+carry+(ord(out[idx])-ord('0'));
        carry := total div 10;
        out[idx] := chr((total mod 10)+ord('0'));
        idx := idx-1;
        { Loop while we still have digits to carry }
        while carry > 0 do
        begin
          total := ord(out[idx]) - ord('0') + carry;
          carry := total div 10;
          out[idx] := chr((total mod 10)+ord('0'));
          idx := idx -1
        end;
        idxcounter := idxcounter + 1
      end; {j loop - num2}
    end; {i loop - num1}
    { Remove leading zeros from the result }
    out := zapzeros(out,len1+len2); { zapzeros is a utility function I wrote for this purpose }

... 

If you’re still with me at this point, the next post in this series deals with addition and subtraction.