Arithmetic

Here is a compendium of arithmetic routines implemented in the instruction set for GreenArrays' C18 computer. Most have been tested, but you should verify that they're suitable for your use. In particular, exactly how to code them depends upon what other words exist. And any restriction as to the range of numbers can simplify code.

I hope the stack effect of these simple words is obvious. If not, I'll include a stack comment. But multiply and divide leave the addend on the stack. It is often unnecessary and always a nuisance to remove. Call it an abandoned number, which I'll indicate by . (and multiple such by ..) in comments.

Integer Functions

Arithmetic uses + which can often be optimized

The C18 has no subtract instruction, but there are several ways to accomplish subtraction. With a and b on the stack (b on top):

Classic Forth: subtract b from a
- . + 1 . +
or
negate +
with negate defined below
Subtract a from b
- . + -
Subtract b from a with result one less
- . +
with 1 to be added later. Often a single fix-up constant can be added at the end of an expression. Sometimes it doesn't matter.

These are simple functions, often useful:

negate - 1 . + ;
abs -if - 1 . + then ;
max - over . + - -if drop ; then + ;
min - over . + - -if + ; then drop ;

Double-precision Add

In this section, a double-precision (36-bit) number has its low-order 18 bits on top of the stack. Such numbers range from -34,359,738,368 to 34,359,738,367.

The ALU must be in add-with-carry mode, which means the code must be compiled at an address with the 200 bit set. The words +cy and -cy set and reset this bit in the current code address.

Carry must usually be clear to start adding. It will remain clear if the last + doesn't overflow.

Clear carry (carry mode) (This code is usually in a node's ROM, address 2d3.):

clc dup dup or dup + drop ;

Add an unsigned 18-bit number to a 36-bit number (carry mode, carry clear):

+u + push 0 + pop ;

Negate a 36-bit number:

-d - push - pop 1 +u ;

If -d falls into +u, it must end with a .

Shift left a 36-bit number:

In carry mode, carry clear
2*d dup + push dup + pop ;
Without carry
2*d -if push - 2* - pop 2* ;
then push 2* pop 2* ;

Shift right a 36-bit number:

2/d 2/ 2* a! +* a ;

Sign-extend an 18-bit number to 36 bits:

sign dup push dup -if or - pop ; then or pop ;

Add 2 36-bit numbers (carry mode, carry clear):

+d a! push a . + a! pop . + a ;

Add a signed 18-bit number to a 36-bit number:

+s sign +d ;

+s can fall into +d.

Integer Multiply

Multiply is implemented with the +* instruction, with the multiplier in register A and multiplicand in S. It adds S to T if A0 is 1, then does a 36-bit shift of T and A right.

The multiplicand is often left on the stack. The carry bit is not used or changed by the +* instruction.

Unsigned multiplier, signed multiplicand, 36-bit signed product:

* a! 0 17 for +* unext a ;

If the multiplier is signed, its high-order bit indicates a subtract:

* a! 0 16 for +* unext - . +* - a ;

Unsigned multiply, necessary for multiple-precision arithmetic. From Michael:

Two 18-bit unsigned numbers yield 36-bit unsigned product
If multiplicand is negative, add multiplier to high-order product
u* uu-hl over a! 0 8 for +* . +* unext
push -if drop pop . + a ;
then drop drop pop a ;
From Greg: putting 2 +*s inside unext saves 9 ns

Multiply and add x:

*+ nxn-n a! 17 for +* next drop drop a ;

A faster 18-bit product can be computed from 2 numbers whose bits add up to 18; say 9 and 9. the multiplier (top of stack) is a normal right-justified unsigned integer. The signed multiplicand is expected to be left-shifted the number of bits in the multiplier. The product will be an 18-bit signed integer.

* a! 0 8 for +* unext ;

Integer Divide

This code is expects a positive double-precision dividend and a positive divisor that's been set negative, to produce a positive remainder and quotient.

Divide is slower than multiply, since there is no divide step instruction. In carry mode with carry undefined:

/mod hld-rq a! 17 for begin dup + push dup +
dup a . + -if drop pop *next dup + ;
then over or or pop next dup + ;

(This code is usually in a node's ROM, address 2d5.) The loop starts with a 2*d. The carry of a . + will be used by the following dup + , thus building the quotient in T. Carry is clear upon exit if the numbers were such as produce a reasonable result.

If the dividend is signed:

-/mod push over -if drop -d pop /mod - 1 . + ; then drop pop /mod ;

For a single-precision divide with a small quotient, this is shorter and faster, without carry:

/mod nd-rq a! 3ffff for dup a . + -if drop pop - ; then next

The quotient is counted by next. No ; since next never stops (unless you divide by 0).

The quotient is on top, so:

/ /mod push drop pop ;
mod /mod drop ;

*/ is a classic Forth word. It multiplies a number by a ratio. With 3 numbers on the stack, the top is the divisor. The 36-bit intermediate product preserves precision:

*/ push * pop / ;

Integer Square-Root

An algorithm similar to divide produces a 16-bit square-root from a 32-bit number:

sqrt 2*d 2*d push push 0 pop 10000
loop if a! over 2* over - . + a . +
-if - push drop a or pop dup
then drop pop 2*d push a 2/ loop ;
then drop drop pop drop ;

Fraction Multiply

The simplest fractions have 17 fraction bits and a sign bit. Thus fractions from .1ffff to -1.00000 can be represented. The addend can be either fraction or integer.

For fractional arithmetic it's useful to define 1. In this context:

1. 1ffff ;

Then to convert fractions to/from decimal numbers:

.f 1. 10000 */ ;
.0 10000 1. */ ;

If the multiplier is positive:

*. a! 0 17 for *+ unext a -if drop - 2* - ; then drop 2* ;
*. * -if drop - 2* - ; then drop 2* ;

If the multiplier is signed, its high-order bit indicates a subtract:

*. a! 0 16 for *+ unext - . *+ - a -if drop - 2* ; then drop 2* - ;

The most convenient fractions have 16 fraction bits, an integer bit and a sign bit. This allows 1.0000 to be represented. However, the product of 2 fractions must be less than 1.ffff.

1. 32678 ;

16-bit code requires an additional left shift to the 17-bit code:

*. *.17 a 2* -if drop - 2* - ; then drop 2* ;

Fraction Divide

Dividing an 18-bit number by a 16-bit fraction requires expanding the dividend to 36-bits with a low-order 0:

/. push 0 pop / ;

Fraction Square-Root

sqrt. 1. * sqrt ;

Multiple-precision Add

Multiple-precision numbers are stored as an array in RAM, low-order at low address. The largest number is 32 words, since 2 such will fit in 64-word RAM. 2^18^32 is a large number, roughly 10^173. Set a number to 0:

0n a a! 0 n for dup !+ unext drop ;

With b a on the stack, b is added into a. Both addresses are discarded. n is the number-1 of 18-bit words in such numbers. In carry mode:

+n ba n for push a! @+ push a pop pop a! @ . + !+ a next drop drop ;

Defining the word +c to add with carry, allows using ordinary + to increment an address, without changing the carry:

+cy +c + ; -cy
+n ba a! n for dup b! @b @ +c !+ 1 + next drop ;