Fixed-point arithmetic (Forth)

From LiteratePrograms
Jump to: navigation, search

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

[edit] 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 ;

[edit] 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.

[edit] 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

[edit] 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
hijacker
hijacker
hijacker
hijacker