Big Integers in Turbo Pascal 3.01A (2)

Posted on by

Addition

This follows a similar process to the multiplication algorithm provided that the operands are either both positive or negative. If they’re both negative numbers then the sign of the result will be negative, so it’s stored and applied at the end of the calculation.

...
  
begin
    { Initialise the result as all zeros to start }
    for i := 1 to lenmax do
      insert('0',out,i);

    { Work backwards through the first number }
    { and store it in the result }
    j := lenmax;
    for i := len1 downto 1 do
    begin
      out[j] := num1[i];
      j := j-1
    end;

    { Work backwards through the second number }
    { and add it into the result, dealing with }
    { carrys as necessary }
    j := lenmax;
    for i := len2 downto 1 do
    begin
      currnum := ord(num2[i])+ord(out[j])-2*ord('0');
      out[j] := chr((currnum mod 10)+ord('0'));
      carry := currnum div 10;
      j := j-1;
      if carry > 0 then
        ci := j;

      { Loop while we still have digits to carry }
      while carry > 0 do
      begin
        currnum := ord(out[ci]) - ord('0') + carry;
        carry := currnum div 10;
        out[ci] := chr((currnum mod 10)+ord('0'));
        ci := ci -1
      end; { carry loop }
    end; { i loop }

    { Remove leading zeros from the result }
    out := zapzeros(out,lenmax);

...

If either operand (but not both!) is negative, the addition function calls the subtraction function to calculate the result.

Repeated addtion

Subtraction

There are quite a few checks carried out on the operands before attempting subtraction. In brief:

  • If the first operand is positive and the second is negative, then the sign of the second operand is removed and the addition function is called to calculate the result.
  • If the first operand is negative and the second is positive, then the sign of the first operand is removed and the addition function is called. The sign is reversed before the result is returned.
  • If both operands are negative, the sign of the second operand is reversed and then the operands are reversed before evaluation – for example, -5 – -7 becomes -5 + 7 which in turn is evaluated as 7 – 5 by the core of the subtraction function.
  • One final check works out which operand is the larger, If the first operand is the largest, then a straightforward nines complement addition is used. If the second operand is largest, then a nines complement addition plus 1 gives the 10s complement of the desired result. (The nines complement function, like zapzeros, is implemented separately as a function ‘internal’ to the library).
...

{ If num1 is largest, then can go ahead and use nines complement }
    if gt(num1,num2) then
    begin
      num1 := nines(num1);    { Subtraction is 9s complement of num1 ... }
      out := add(num1,num2);  { added to num2 ...                        }

      { if length(out) < length(num1) must add   }
      { leading 0s before 9s complement of out   }
      if length(out) < length(num1) then
        for i := 1 to length(num1)-length(out) do
          insert('0',out,1);
      out := nines(out);      { and then the 9s complement of the result }
    end
    else
    begin
      if gt(num2,num1) then
      begin
        num2 := nines(num2);
        temp2 := add(num1,num2); { We now have the 10s complement of the }
        temp2 := add('1',temp2); { desired result ...                    }
        for i := 1 to length(temp2) do
          insert('0',temp1,1);
        insert('1',temp1,1);     { We have a power of 10 greater than    }
                                 { 10s complement of result to use ...   }
        temp1 := nines(temp1);   { Get the 9s complement and follow the  }
        out := add(temp1,temp2); { earlier algorithm to completion       }
        if length(out) < length(temp1) then
          for i := 1 to length(temp1)-length(out) do
            insert('0',out,1);
        out := nines(out);
        out := zapzeros(out,length(out));
        insert('-',out,1);       { and finally flip the sign ! }
      end
      else
      begin
        out := '0'               { The two numbers were equal! }
      end;
...

Comparison functions

If you’ve looked at the code for the subtraction function, you’ll have seen one of the comparison functions (gt) used. There are six of these implemented in the library. Three of them carry out the real work of all six – namely gt (greater than), lt (less than) and eq (equal to). The other three (ge, le and ne) make use of calls to gt, lt and eq for their implementation. As an example, here’s the heart of the code for gt: 

... 
      { Pad both numbers to the same length }
      if (len1 > len2) then
        for i := 1 to len1-len2 do
          insert('0',num2,1);
      if (len2 > len1) then
        for i := 1 to len2-len1 do
          insert('0',num1,1);

      { Work out the largest number }
      tgt := FALSE;
      found := FALSE;
      i := 1;
      while (i <= length(num1)) and (found = FALSE) do
      begin
        if (num1[i]>num2[i]) then
        begin
          found := TRUE;
          tgt := TRUE
        end;
        if (num1[i]<num2[i]) then
        begin
          found := TRUE
        end;
        i := i+1
      end;
...

Part 3 of this series will cover the division and square root functions, before part 4 covers benchmarking the library with a prime number generator …