Fixed-point arithmetic (Forth)
From LiteratePrograms
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.
Contents |
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 point addition and subtraction simply use integer addition and subtraction.
: 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
Links
For more information in using fixed-point in Forth, see the chapter The Philosophy of Fixed Point in Leo Brodie's Forth primer Starting Forth.
| Download code |