Fixed-point arithmetic (Forth)

Forth has for a long time used fixed-point arithmetic for high-precision arithmetic. Forth is often targeted to microcontrollers which only have integer operations. It is only recently that Forth has gained a floating-point wordset for modern processors.

Structure of a fixed point number

The idea is that the high-order bits in your word represent the integer portion of the number and the low order bits represent the fractional portion of the number. You can choose how many bits to use for each part depending on the accuracy required for your application. A common choice is to use 24 bits for integers and 8 bits for the fraction.

``` 8 constant fract-bits
: int>fixed ( n -- f ) fract-bits lshift ;
: fixed>int ( f -- n ) fract-bits rshift ;
1 int>fixed constant 1F
1F 2/ constant 1/2F
: fixed>fract ( f -- n ) 1F 1- and ;
```

Fixed point arithmetic

``` : fixed>round ( f -- n ) 1/2F + fixed>int ;
```

Fixed point multiplication and division require rescaling to get the number back into correct range after using a double-precision multiply. The Forth word */ is tailored for this operation. The intermediate multiply is double precision in order to avoid overflow.

``` : *f ( f g -- f*g ) 1f */ ;
: /f ( f g -- f/g ) 1f swap */ ;
```

If you wish to multiply or divide a fixed-point number by a standard integer, then you can use the standard multiply and divide operators.

Example: Mandelbrot set

As an example of fixed point use, here is a text mode Mandelbrot set generator. It is using 18.14 fixed point numbers, and was used to test Open Firmware implementations. (In Open Firmware, >>a is signed right shift and the default base is hexadecimal.)

``` hex : f* * e >>a ; : sq over dup f* ; 4666 dup negate do 4000 dup 2* negate do
i j 1e begin 1- ?dup while -rot sq sq 2dup + 10000 < while - i + -rot f* 2* j +
rot repeat 2drop drop bl else bl a + then emit 2drop 268 +loop cr 5de +loop
```

Or in a more readable form which works on any ANS Forth:

```<<mandelbrot.f>>=
hex
4000 constant 1fixed
4666 constant 1.1fixed
10000 constant 4fixed
decimal
1fixed  3 * 80 / constant xinc
1.1fixed 2* 24 / constant yinc
: *f ( f g -- f*g ) 1fixed */ ;
: sq ( f -- f f*f ) over dup *f ;
: mandel
1.1fixed dup negate do
1fixed dup 2* negate do
i j 30                 ( initial point x,y and max iteration count )
begin  1- ?dup
while  -rot sq sq
2dup + 4fixed <
while  - i +
-rot *f 2* j + rot
repeat 2drop drop          \ exit from second while
space
else   ." *"               \ exit from first while
then 2drop
xinc +loop
cr
yinc +loop ;
mandel
```