Fixed point numbers

[Asmusr]

My little article on differential calculations was very well received, so here's one about another favorite of mine: fixed point numbers.

In assembly our data are stored as either bytes (8-bit) or words (16-bit). For storing numbers we usually consider these bits as representing pure binary numbers, but there are alternatives like BCD, which are beyond the scope of this article.

We can use a word to hold an unsigned integer between 0 and 65535, or, if we need both positive and negative numbers, we can choose to consider a word a 2's complement number in the range -32768 to 32767.

Unsigned:
------------------------
     0: 0000000000000000
     1: 0000000000000001
 32768: 1000000000000000
 65535: 1111111111111111

|

Signed 2's complement:
------------------------
-32768: 1000000000000000
    -1: 1111111111111111
     0: 0000000000000000
     1: 0000000000000001
 32767: 0111111111111111

How do we represent numbers that are not integers but have a fractional part? For instance if we have sprites that should move less than one pixel per frame. In BASIC we have floating point numbers that can hold a wide range of values, but those are expensive in both speed and storage. In assembly - and especially for games development - we want something smaller and faster.

What we can do is to decide that binary numbers represent fractions of real numbers rather than integers. So instead of deciding that 000000110 represents the integer 6 we could choose that it represents 6/100. The number 10000110 would then represent (128+6)/100 = 134/100 = 1.34. This works, but dividing by 100 to find the integer part is costly compared to other operations in assembly, so we usually choose a scale of 128 or another multiple of 2 that we can divide or multiply by using binary shifting alone.

If our scale is 128 and we consider a 16-bit word, 9 bits are used to represent the integer part and 7 bits are used to represent the fraction.

     1: 000000001.0000000
  1.34: 000000001.0000110
   0.5: 000000000.1000000
  2.25: 000000010.0100000
   127: 111111111.0000000

We can call this representation 9.7 fixed point. It depends on the task how many bits we need to allocate - or can allocate - to the fractional part. 8.8 fixed point numbers are particularly easy to work with since the integer part is simply the most significant byte. This is very useful for sprite positions where we can just send the MSB to the VDP, but if the required range of the integer part is beyond -128 - 127 (signed) or 0 - 255 (unsigned) we need to allocate fewer bits to the fraction and more bits to the integer part.

It's easy to do calculations on fixed point numbers if we obey a few simple rules:

- Addition and subtraction can only be done on numbers with the same number of fractional bits. If they don't have the same number of fractional bits, one of them has to be shifted first. We can use the usual addition and subtraction assembly instructions - also for signed numbers.

- Multiplication can be done on fixed point numbers with any number of fractional bits. If the first number has 8 fractional bits and the second number has 6 fractional bits we end up with a result with 8+6=14 fractional bits, so we need to shift this 6 places right to end up with 8 fractional bits again.

- Division works the opposite way, so if we divide a number with f1 fractional bits by a number with f2 fractional bits we get f1-f2 fractional bits. To end up with f1 fractional bits we can shift the first number left f2 positions *before* performing the division (if we do it after we will lose precision).

With multiplication and division we have to remember that the assembly instructions and unsigned, so the sign might have to be cleared before and reassigned after the instruction. However, if we multiply small numbers where the result doesn't exceed 16 bits, we can actually use the mpy instruction as it is on signed numbers (trust me!).

[+TheBF]

Very cool. This has direct application in C and Forth as well.

 

C and Forth programs have traditionally made heavy use of integers vs floating point for efficiency too.

 

Thanks for these academic insights into things.

[sometimes99er]

Very nice. Thanks.

[RXB]

Extended Basic uses all of them.

I even posted he XB Source code in GPL and ROMs that show how XB does this.

Some of the code is overly complicated to keep with TI being a Calculator Company.

[Willsy]

I'd really like a fixed point library for TurboForth. That would be awesome.

[Asmusr]

I'd really like a fixed point library for TurboForth. That would be awesome.

 

If you create a fixed point library, one of the first decisions is how much information you want to store about each FP number. Do you store just the binary number and leave it to the user of the library to specify how many places to shift the result after a multiplication, for instance? Or do you store the number of fractional bits for each FP number and use this to shift automatically? You can also store whether a FP number is signed or not. If it's unsigned you can speed up multiplications and divisions. If you store the number of fractional bits you can report an error if you try to add or subtract numbers with different number of fractional bits, or you can scale the numbers automatically. You also need to decide how to handle overflows, do you just ignore them, or report an error, or return the maximum possible result?

[Asmusr]

Extended Basic uses all of them.

I even posted he XB Source code in GPL and ROMs that show how XB does this.

Some of the code is overly complicated to keep with TI being a Calculator Company.

 

Do you mean it's using floating point? This is fixed point.

[+TheBF]

 

If you create a fixed point library, one of the first decisions is how much information you want to store about each FP number. Do you store just the binary number and leave it to the user of the library to specify how many places to shift the result after a multiplication, for instance? Or do you store the number of fractional bits for each FP number and use this to shift automatically? You can also store whether a FP number is signed or not. If it's unsigned you can speed up multiplications and divisions. If you store the number of fractional bits you can report an error if you try to add or subtract numbers with different number of fractional bits, or you can scale the numbers automatically. You also need to decide how to handle overflows, do you just ignore them, or report an error, or return the maximum possible result?

 

Many of the old Forth systems resorted to a 32 bit library for fixed point math to prevent overflow.

I have never thought about creating a 16 bit version. I would be useful for scientific applications if you were data logging low voltages and currents I suppose.

Interesting...

 

The creator of Forth made a couple of operators to help with 16bit overflow in calculations.

 

One is '*/' called "star-slash". Arguments are ( n, multiplier, divisor ) and it returns 16bit int.

You use it to scale values that could overflow on the multiply operation because the mpy is mixed math producing a 32 bit product

 

The other handy one is called M+ which takes 2 ints and returns a 32bit int.

 

B

[+TheBF]

Hey Mark,

 

I think you already have a fixed point library!

 

299.99 fixed point is still just 29999 internally.

 

What Forth does is provides a set of words to format any number as fixed point numbers.

 

First you need this little word set. Believe it or not this allows arbitrary number formatting in

114 bytes of code on a 16 bit machine.

 

( All these routines assume a 32 bit number on the stack (ie: 2 16 bit ints) which makes

them much more practical for money programs.

 

From CAMEL99 source code

: UD/MOD      ( ud1 u2 -- u3 ud4)
              >R 0 R@ UM/MOD -ROT R> UM/MOD ROT ;         \ 32/16->32 divide

: HOLD   ( char -- )        -1 HP +!  HP @ C! ;               \ decr. HOLD pointer HP, Store char at the address contained in HP
\ : >DIGIT ( n -- c)          DUP 9 > 7 AND + 30 + ;          \ convert n to ascii digit c (*Moved to ASM word because it is in a loop)
: <#     ( --)              #PAD HP ! ;                       \ initialize Hold Pointer to end of the number buffer (#pad)
: #      ( ud1 -- ud2)      BASE @ UD/MOD ROT >DIGIT HOLD ;   \ convert 1 digit & store at HP, return remainder
: #S     ( ud1 -- ud2)      BEGIN  # 2DUP OR 0=  UNTIL ;      \ convert all digits in ud1. ud2 will be 0 (the remainder)
: #>     ( ud1 -- c-addr u) 2DROP HP @ #PAD OVER - ;          \ return a stack string (address, length)  of the converted number
: SIGN   ( n -- )           0< IF [CHAR] -  HOLD THEN ;      \ if 'n'<0  add '-' char  string created in #PAD

Then you use these routines to make your number formats.

The simplest is below;

: U.     ( u -- )  S>D  <#  #S  #>  TYPE SPACE ;  \ print 'u' as an un-signed integer 

But here is signed dollar formatting

\ From CAMEL Forth source code Brad Rodriguez
: DNEGATE  ( d -- d)  SWAP INVERT SWAP INVERT 1 M+ ;
: ?DNEGATE ( d1 n -- d2) 0< IF DNEGATE THEN ; \  negate d1 if n negative
: DABS     ( d1 -- +d2 )  DUP ?DNEGATE ; \ absolute value dbl.prec.

CHAR . CONSTANT '.'
\ from STARTING Forth, Brodie
: .$    ( n -- ) S>D  TUCK DABS  <#  # # '.' HOLD  #S ROT SIGN  [CHAR] $ HOLD  #>  TYPE SPACE ;

Works like this:

 

29950 .$ $299.50

 

-30095 .$ $-300.95

Edited May 12, 2017 by TheBF

[Willsy]

Brian

 

I already have a 32 bit library. It has a ton of words in it including hold and <# etc.

 

Maybe I could extend it to provide fixed point?

[RXB]

 

Do you mean it's using floating point? This is fixed point.

It uses all of them depending on the routines but only returns Floating Point and Decimal.

The ROM even has a Binary converter it uses sometimes but never outputs any of these features.

 

Seemed odd that TI would restrict this so much on the TI99/4A?

[+TheBF]

Brian

 

I already have a 32 bit library. It has a ton of words in it including hold and <# etc.

 

Maybe I could extend it to provide fixed point?

 

I think it should be pretty straightforward with all that.

 

It really is just creating the output operators for the fixed size you want to use isn't it?

Or am I missing something?

 

All the maths will work out of the box.

 

I suppose you could "tart" things up with a special vocabulary or even an infix parser.

 

Depends what you want I guess.

 

B

[Willsy]

Yeah I guess so. If I had a word to define how many decimal places one requires and base it all on 32 bit integers it should be fairly straightforward.

 

I mean, if I want 2 decimals then everything is internally multiplied by 100 right?

 

I'd keep it simple so you couldn't have mixed decimal lengths. You decide up front how many decimal places you want to work with.

[+TheBF]

Had to step away.

 

Yes I believe that's it in a nut shell.

And with 32bit math you can build a financial package that 's good to

21 474 836 pounds sterling and 47 P or so. :-)

[+mizapf]

These are the fixed point routines that I actually used in my FRACTALS program, which makes use of the on-chip RAM of the TMS9995 in the Geneve. Sorry for the sparse comments; I can try to add them if anyone is interested.

 

 

*   Fixed point routines
*
*     Format:    LI   R0,VALUE1
*                LI   R1,VALUE2
*                LI   R2,RESULT
*                BLWP @FXMUL
*
*         => VALUE1*VALUE2=RESULT
*
*                LI   R0,VALUE1
*                LI   R1,VALUE2
*                BLWP @FXADD
*
*         => VALUE1+VALUE2=VALUE1
*
*
*   Fixed point format: 8 bytes
*   2 bytes integer
*   6 bytes fraction
*
*   xxxx.yyyy yyyy yyyy
*
MATWS  EQU  >F020
SIGN   EQU  >F048
INCR   EQU  >F080
FMOVE  EQU  >F072
FXADD  EQU  >F044
FXMUL  EQU  >F040
FMULOC EQU  >F090
* ====================on-chip=======================
ONCHIP DATA MATWS,FMUL       FXMUL
       DATA MATWS,>F04A      FXADD
       DATA 0
       MOV  *R13,R3          F04A
       MOV  R13,R12
       MOV  @2(R13),R4
       LI   R8,3
       LI   R6,6
       A    R6,R4
       A    R6,R3
FADD1  A    *R4,*R3
       JNC  FADD2
       MOV  R3,R7
       BL   @INCR
FADD2  DECT R4
       DECT R3
       DEC  R8
       JOC  FADD1
FADD3  RTWP
FMOVEL MOV  *R11+,R0          FMOVE
       MOV  *R11+,R1
       MOV  *R0+,*R1+
       MOV  *R0+,*R1+
       MOV  *R0+,*R1+
       MOV  *R0,*R1
       RT
       MOV  R7,R5             INCR
INCR1  DECT R5
       C    R5,*R12
       JL   INCR2
       INC  *R5
       MOV  *R5,*R5
       JEQ  INCR1
INCR2  RT
FMUL3  DECT R4                FMULOC
       A    R10,R7
       A    R6,R3
       CLR  R8
FMUL4  MOV  *R4,R0
       JNE  FMUL4A
       CLR  R8
       DECT R7
       DECT R4
       C    R4,R9
       JHE  FMUL4
       JMP  FMUL6A
FMUL4A MOV  *R3,R1
       JEQ  FMUL4B
       MPY  R0,R1
       A    R8,R2
       JNC  $+4
       INC  R1
FMUL4B A    R2,*R7
       JNC  $+6
       BL   @INCR
FMUL5  MOV  R1,R8
       MOV  R1,R2
       DECT R3
       DECT R7
       C    R3,*R13
       JHE  FMUL4A
       C    R7,*R12
       JL   FMUL6
       A    R8,*R7       so we don't lose carry
FMUL6  C    R4,R9
       JH   FMUL3
FMUL6A B    @FMULCN
* ==============================================
** Change sign
CHSIGN MOV  R0,R1
       AI   R1,8
CHSGN1 DECT R1
       C    R1,R0
       JL   CHSGNE
       MOV  *R1,R2
       JEQ  CHSGN1
       NEG  *R1
CHSGN2 DECT R1
       C    R1,R0
       JL   CHSGNE
       INV  *R1
       JMP  CHSGN2
CHSGNE RT
** Multiplication routine
FMUL   MOV  R13,R12
       MOV  *R12+,R3
       MOV  *R12+,R4
       MOV  R4,R9
       MOV  *R12,R7
       CLR  @SIGN
       MOV  *R3,R1
       JEQ  FMUL1
       JGT  FMUL1
       INV  @SIGN
       MOV  R3,R0
       BL   @CHSIGN
       C    R3,R4
       JNE  FMUL1
       NEG  @SIGN             same factors
       JMP  FMUL2             don't change sign
FMUL1  MOV  *R4,R1
       JEQ  FMUL2
       JGT  FMUL2
       INV  @SIGN
       MOV  R4,R0
       BL   @CHSIGN
FMUL2  MOV  R7,R8
       LI   R6,7
       CLR  *R8+
       DEC  R6
       JNE  $-4
       LI   R6,8
       LI   R10,6
       A    R10,R7
       A    R6,R4
       CLR  R2
       DECT R3
       B    @FMULOC           use on-chip routine
      
FMULCN AI   R7,10
       MOV  *R7,R0
       JEQ  FMUL8
       JGT  FMUL8
FMUL7  BL   @INCR
FMUL8  MOV  @SIGN,R0
       JEQ  FMULE
       JGT  FMULE
       MOV  *R12,R0
       BL   @CHSIGN
FMULE  RTWP

...
       LI   R0,ONCHIP    Copy the math routines
       LI   R1,>F040     to the on-chip RAM
OCC    MOV  *R0+,*R1+
       CI   R1,>F0D6
       JNE  OCC

[+TheBF]

Cool so these are 64 bit math operations. I just may re-code these in Forth Assembler and give them a try.

 

Thanks!