Programming the 80’s way #3

Introduction to Integers.

One of my favorite tasks using a small system like our ZX Spectrum is to overcome limitations imposed on integers and floating-point numbers.

In ZX Basic, integers have a width of 16 bits (plus sign) allowing you to manipulate numbers between -65.535 and 65.535, and once out of this range, you’re venturing into floating point numbers wilderness.

In Forth, unless you can rely on some floating-point library, all math is integer math, and usually Z80 implementations uses 16-bits single-precision integers and 32-bits double-precision integers, so expanding the range to a wider interval of integers that lie between -2.147.483.648 and 2.147.483.647.

The lack of floating-point and engineering notation is not so bad because the trade-off is a faster speed and great simplicity, by defining suitable fine-grained unit-of-measure like “millimeters” instead of “thousandth of meter”, for instance.

On the other hand, irrational constant numbers, like “Greek-Pi”, that have an infinite number of decimal places, cannot be exactly represented neither using floating-points nor double precision integers, and in Forth, it is very common to exploit irrational constant numbers via Rational Approximation.

The concept behind this useful technique is that any irrational number can be represented by a rational approximation. For example, 355/113 is a very good approximation of “pi” with an error of less than one part in a million.

For instance, the formula to calculate the circumference of a circle can be coded directly as

    : CIRCUMFERENCE  ( n1 -- n2 ) 
      2* 355 113 */ 
    ;

in particular, the definition  */   is the typical scaling operator that takes a single-precision integer multiplies it by a number (355 in our case) and divides it by another (113 in our case) but ensuring a double-precision intermediate result to avoid loss of precision.

 

Triple-precision integers

My v-Forth implementation provides a definition  UM* to multiply two single-precision numbers and get a double-precision number, and a definition  UM/MOD  to divide a double-precision number and get two single-precision numbers quotient and reminder.

It seems there is little way to use some “triple-precision” [1] integer i.e. 48-bits of precision, but I’ll show how I had the chance to code an improved definition of  */   that operates on a double-precision integer passing through a “triple-precision” integer so we can improve our previous version of CIRCUMFERENCE to cope with “double-precision” integer and use a “triple-precision”  intermediate result using this new definition  M*/   

    : CIRCUMFERENCE  ( d1 -- d2 )  
      2DUP D+      \ double the radius
      355 113 M*/ 
    ;

Here below, I expose the implementation of such  M*/   using the math definitions already available UM* and UM/MOD.

In the following definition explanation, each symbol represents a single-precision unsigned integer, that is a number between 0 and 65535, so we can think of it as we were using some “65536-based” math.

  1. we can split the double-precision integer  d  into its two components dH and dL and then multiply them by m separately getting two double-precision integer a and b, we split in aH, aL and bH, bL.
  2. we have to add  aH part to b obtaining c, we split in cH, cL. This way we now have three single-precision integers cH, cL, aL, that represents our triple-precision intermediate value integer.
  3. We can perform one first division, dividing c by n obtaining quotient q1 and reminder r1.
  4. We compose r1 and aL that is the double-precision number we now divide by n to obtain quotient q2, while remainder r2 is discarded for our purposes.
\     dH dL  x
\         m  =
\ ----------
\     aH aL
\  bH bL   
\ ----------
\  cH cL aL  :  n  =  q1  q2
\     r1 aL
\ 
: M*/     ( d m n -- d2 ) 
  2dup xor 3 pick xor >R     \ keep track of final sign
  abs >R abs >R 
  swap R@ UM* rot R> UM*     \ 1. multiply by m and get a and b
  rot 0 D+                   \ 2. obtain c
  R@ UM/MOD                  \ 3. divide n into c giving quotient and reminder
  rot rot R> UM/MOD          \ 4. divide n into the composition r1+aL 
  nip swap                   \ discard reminder r2 and reorder the two partial-quotients
  R> D+-                     \ determine final sign.
;

 

For example:

500000. CIRCUMFERENCE D.

prints

3141592

In conclusion, using just some Arithmetic we overcame the native 32-bit Forth limitation.

[1] Forth Application Techniques – Elizabeth D. Rather and the technical staff of FORTH Inc. – 2000 Forth Inc.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.