www.retrosoftware.co.uk
http://www.retrosoftware.co.uk/forum/

Fixed-point 8-bit multiplication
http://www.retrosoftware.co.uk/forum/viewtopic.php?f=73&t=349		 Page 1 of 2
Author:  RichTW [ Fri Sep 18, 2009 3:41 pm ]
Post subject:  Fixed-point 8-bit multiplication
To avoid veering off-topic in Thomas's line drawing thread, I thought I'd start a new one about multiplication.

Beebs don't multiply numbers very well. Even with the kind of routine I put on the wiki, we're still limited to multiplying unsigned numbers and getting an unsigned result.

Now, there are many occasions (e.g. in a 3D game) where you want to be able to do the equivalent of:
Code:
x = r * SIN(angle)

Obviously, SIN(angle) is a fractional value between -1.0 and 1.0, and one thing the Beeb definitely does not excel in is floating point! Other relatively modern platforms which don't have floating point hardware either (e.g. the Nintendo DS) get around this limitation by fetching the sine value multiplied by a constant, multiplying the two values, and then dividing afterwards by the same constant:
Code:
x = r * (SIN(angle) * 256) / 256

If the constant is a nice round power of two, this is a cheap operation. This representation of a fractional value multiplied by a constant is called 'fixed point'.

Well, we know all that anyway. Wouldn't it be nice if we could do this on a Beeb?

In Thomas's thread, I was trying to find an efficient way to represent a value between -1.0 and 1.0, which we could easily multiply by, in order to yield the elusive value of x, above! Obviously, it would be better if the fixed-point value fit nicely into 8 bits, and with as little wastage as possible. The main problem is the asymmetry of the two's complement representation - we can store values from -128 to +127, which means that if we use 128 as our fixed point constant, we can happily store -1.0, but we can't reach 1.0.

To cut a long story short, I realised that we can actually use 127 as our constant (in other words, so that -1.0 is represented by -127, and +1.0 is represented by +127), and then write a multiply routine which automatically divides the result of a*b by 127.

This turns out to be really easy, because we already use a table to lookup the result of the multiplication.

Recall:
Code:
(a+b)^2 = (a^2 + b^2 + 2ab)   -> (I)
(a-b)^2 = (a^2 + b^2 - 2ab)   -> (II)

(I)-(II) yields:
(a+b)^2 - (a-b)^2 = 4ab

=> ab = f(a+b) - f(a-b)

where f(x) = x^2 / 4

So, it follows that if we were simply to divide this table by a further 127, we would automatically get a divide by 127 for free!
Code:
ab / 127 = f(a+b) - f(a-b)

where f(x) = x^2 / 4 / 127

Obvious really!

The next thing we need to do is make sure it works with signed inputs. The above method will only work with unsigned inputs, so we have to do some other stuff in order that it works well.

The naïve solution is to write code like this:
Code:
Remember sign of (val1 EOR val2)
If sign of val1 is negative, negate val1.
If sign of val2 is negative, negate val2.
Multiply val1 * val2.
If the sign we remembered was negative, negate the result.

However, this costs cycles, and also means that the case where any of the inputs is negative is slower than the case where both inputs are positive.

A better solution is to do the table lookup and subtract in different ways, depending on the two signs of the inputs (4 different possibilities).

For example, in the cases where the result needs to be negated, we do the table lookup with positive indices as required, but then reverse the order of the subtraction, like this:
Code:
a*b = f(a-b')-f(a+b')  where b' is -b


Anyway, here's a bit of code which does the trick. It executes in an average of 58 cycles (including the subroutine call and return), which is pretty quick!

Code:
\\   ***********************************************************************************************
\\   *
\\   *   Fixed-point multiplication
\\   *
\\   *   Essentially this is a routine which multiplies two signed 8-bit numbers, and divides the
\\   *   result by 127.  It does this very quickly! (58 cycles on average, including the subroutine
\\   *   call).
\\   *
\\   *   This is useful because we can multiply the values in our sine table by 127 (allowing us to
\\   *   correctly represent 1.0 and -1.0), and multiply this by another sine value, or a vertex
\\   *   coordinate (in the range -127..+127) without losing any magnitude or precision.
\\   *
\\   *   The multiplication technique used is the old favourite:
\\   *
\\   *      a*b = f(a+b) - f(|a-b|), where f(x) = a^2 / 4, with x = 0..255
\\   *
\\   *   Because a byte can only represent -128..127, we have to limit the input range to -127..127,
\\   *   otherwise it would be possible to calculate -128*-1.0 (= an out of range result: 128!).
\\   *
\\   *   The result is an approximation due to various rounding errors, but tests show that:
\\   *      75% of the results are accurate to within +/-0.5
\\   *      99% of the results are accurate to within +/-1.0
\\   *
\\   *   This should be ok for now!
\\   *
\\   ***********************************************************************************************

val1 = &70
val2 = &71


ORG &4000

\\-------------------------------------------------------------------------------------------------
\\   Multiply X * cos(Y)
\\
\\   X is in the range -127..127, and can be thought of as a fixed-point number if you wish, where
\\      127 represents 1.0.
\\   Y is an angle between 0..255, such that 360 degrees is represented by 256.
\\
\\   Result returned in A
\\-------------------------------------------------------------------------------------------------

.MultiplyByCosine
   TYA
   CLC
   ADC #64
   TAY
   ; fall through


\\-------------------------------------------------------------------------------------------------
\\   Multiply X * sin(Y)
\\
\\   X is in the range -127..127, and can be thought of as a fixed-point number if you wish, where
\\      127 represents 1.0.
\\   Y is an angle between 0..255, such that 360 degrees is represented by 256.
\\
\\   Result returned in A
\\-------------------------------------------------------------------------------------------------

.MultiplyBySine
   LDA SineTable,Y
   TAY
   ; fall through
   

\\-------------------------------------------------------------------------------------------------
\\   Multiply X * Y
\\
\\   Both X and Y are signed numbers in the range -127..127.
\\   One or both of them is considered as a fixed-point number, where 127 represents 1.0.
\\
\\   Result returned in A
\\-------------------------------------------------------------------------------------------------
   
.SignedMultiplyFixed
{
   STX val1                     ; store these two values, we will need to do
   STY val2                     ; arithmetic with them later
   CLC                           ; clear C in anticipation
   
   TYA:BMI val2neg                  ; handle cases where val2 is negative
   
   \\ If we get here, val2 is positive
   
   TXA:BMI val1neg_val2pos
   
   \\ If we get here, val1 is positive and val2 positive.
   \\ This is the straightforward f(val1+val2) - f(|val1-val2|)

   ; On entry, A contains val1, C is clear
   .val1pos_val2pos
   ADC val2
   TAX                           ; X = val1+val2 (in range 0..255)
   
   SEC
   LDA val1
   SBC val2                     ; val1-val2 (in range -127..127)
   BCS skipnegate                  ; see if val1-val2 was negative
   EOR #255                     ; if so negate it to yield a positive value
   ADC #1
   SEC                           ; set C flag in anticipation
   .skipnegate
   TAY                           ; Y = |val1-val2| (in range 0..127)
   
   LDA MultTable,X                  ; C guaranteed to be set here
   SBC MultTable,Y
   RTS
   
   \\ If we get here, val1 is negative and val2 is positive.
   \\ The method being used requires unsigned numbers, so we do the table lookup with -val1.
   \\ We would then need to negate the result at the end, but in order to save this,
   \\ we just reverse the subtraction of the two table lookups, i.e.
   \\     f(|val1-val2|) - f(val1+val2)
   \\ However, as we just said, we use -val1, so what we now get is:
   \\     f(|-(val1+val2)|) - f(val2-val1)
   \\   = f(|val1+val2|) - f(val2-val1)

   ; On entry, A contains val1, C is clear
   .val1neg_val2pos
   ADC val2                     ; val1+val2 (in range -127..127)
   BCS skipnegate2                  ; see if val1+val2 was negative
   EOR #255                     ; if so negate it to yield a positive value
   ADC #1
   SEC                           ; set C flag in anticipation
   .skipnegate2
   TAX                           ; X = |val1+val2| (in range 0..127)
   
   LDA val2                     ; C guaranteed to be set here
   SBC val1
   TAY                           ; Y = val2-val1 (in range 0..255)
   
   SEC
   LDA MultTable,X
   SBC MultTable,Y
   RTS
   
   \\ If we get here, val2 is negative
   
   .val2neg
   TXA:BMI val1neg_val2neg

   \\ If we get here, val1 is positive and val2 is negative
   \\ This is similar to the last case; we need to negate the result, and do the table
   \\ lookup with -val2, so we end up with:
   \\     f(|val1+val2|) - f(val1-val2)
   
   ; On entry, A contains val1, C is clear
   .val1pos_val2neg
   ADC val2                     ; val1+val2 (in range -127..127)
   BCS skipnegate3                  ; see if val1+val2 was negative
   EOR #255                     ; if so negate it to yield a positive value
   ADC #1
   SEC                           ; set C flag in anticipation
   .skipnegate3
   TAX                           ; X = |val1+val2| (in range 0..127)
   
   LDA val1                     ; C guaranteed to be set here
   SBC val2
   TAY                           ; Y = val1-val2 (in range 0..255)
   
   SEC
   LDA MultTable,X
   SBC MultTable,Y
   RTS
   
   \\ If we get here, val1 is negative and val2 is negative
   \\ As well as negating the result, we have to do the table lookup with -val1 and -val2.
   \\ So, this leaves us with:
   \\    f(-(val1+val2)) - f(|val2-val1|)

   ; On entry, A contains val1, C is clear
   .val1neg_val2neg
   ADC val2                     ; val1+val2 (in range -255..0)
   EOR #255
   ADC #0
   TAX                           ; X = -(val1+val2) (in range 0..255)
   
   SEC
   LDA val2
   SBC val1                     ; val2-val1 (in range -127..127)
   BCS skipnegate4                  ; see if it was negative
   EOR #255                     ; negate it again if so
   ADC #1
   SEC                           ; set C flag in anticipation
   .skipnegate4
   TAY                           ; Y = |val2-val1| (in range 0..127)
   
   LDA MultTable,X                  ; C guaranteed to be set here
   SBC MultTable,Y
   RTS
}
.EndOfSignedMultiplyFixed


\\ Here are the tables, align them to a page boundary
\\ 512 bytes in total... not so bad, really.

ALIGN 256

\\ Sine/cosine table, values multiplied by 127

.SineTable
FOR n, 0, 255
   a = SIN(n/128*PI) * 127
   IF a >= 0
      EQUB INT(a + 0.5)
   ELSE
      EQUB INT(a - 0.5)
   ENDIF
NEXT

\\ Table used by the multiplication routine to perform (a*b)/127

.MultTable
FOR n, 0, 255
   EQUB INT((n*n / 4) / 127 + 0.5)
NEXT


...and here is a zip of the BeebAsm source and a .ssd image containing a test program, so you can see that it really works! :)

Attachments:
Beeb3D.zip [4.07 KiB]
Downloaded 12 times
Author:  ThomasHarte [ Sat Sep 19, 2009 12:27 am ]
Post subject:  Re: Fixed-point 8-bit multiplication
On the Sam I had the benefit of lots of memory and the ability to page RAM over the entire memory space and a CPU that can do 16bit arithmetic and indirect lookups very quickly. So I've got a 2.8 fixed point scheme in normal two's complement form, with the positive half of the related (x^2)/4 occupying the bottom 1024 bytes of memory and the negative half occupying the top 1024 bytes. And then the multiply routine to get BC*DE is just:
Code:
      ld h, d
      ld l, e
      add hl, bc         ; get a + b

      ex de, hl
      and a
      sbc hl, bc         ; get a - b
      sla h            ; get address of a - b
      ld c, (hl)
      inc h
      ld b, (hl)         ; bc now contains (a - b)^2

      ex de, hl
      sla h            ; get address of a + b
      ld e, (hl)
      inc h
      ld d, (hl)         ; de now contains (a + b)^2

      ex de, hl
      and a
      sbc hl, bc
      ret
:
Blunt, but good enough. Matrices are actually composed in 2.14 form, because composition happens almost never happens compared to the application of matrices (by which point the relevant matrix has been pushed down to 2.8) and it does make things visibly smoother. So it was a concession to appearance beyond what I'd be confident to make on the Electron at least.

Looking at that code, my immediate thought is that I may have taken the pragmatic decision that an error of 1/256 is acceptable for not bothering to clear carry before the sbc. But maybe I'm missing something.

Re: using base 127, it's something I considered but discarded because subsequently multiplying by numbers larger than a byte superficially seems to be a major headache. But maybe I'm being dense somehow?

My best Electron-oriented plan was essentially similar to that proposed by you on the other thread; 8bits for the fractional part, and a high byte with a single bit of integer precision and a separate sign bit (not two's comp, a separate bit). Then multiplication is xor the sign bits, copy the other low byte if either has the notional integer bit set, do a table multiply otherwise. Actually, I figured it'd probably be safer to do the low-byte table multiply then use the single integer bits as decision variables on adding single extra copies of the complete original low bytes, given that low precision often pushes lengths of things just a little above 1 if you're doing compound transforms ala Elite. Maybe I'm way off though.
Author:  RichTW [ Sat Sep 19, 2009 8:11 am ]
Post subject:  Re: Fixed-point 8-bit multiplication
forget it...
Author:  RichTW [ Sat Sep 19, 2009 8:50 am ]
Post subject:  Re: Fixed-point 8-bit multiplication
If the post above hasn't deleted itself, just ignore it for the moment... there's some problems with it - will update with a corrected version later.
Author:  RichTW [ Sat Sep 19, 2009 9:23 am ]
Post subject:  Re: Fixed-point 8-bit multiplication
ThomasHarte wrote:
Looking at that code, my immediate thought is that I may have taken the pragmatic decision that an error of 1/256 is acceptable for not bothering to clear carry before the sbc. But maybe I'm missing something.

Doesn't the AND A do that on the Z80?

I need to rethink the 16-bit multiplication stuff... I think there's a simple way to handle it but I need to think longer.
Author:  SteveO [ Sat Sep 19, 2009 9:42 am ]
Post subject:  Re: Fixed-point 8-bit multiplication
All interesting stuff, must book mark this thread :) Maths is my real weak point.
Author:  RichTW [ Sat Sep 19, 2009 5:23 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
OK, I wanted to try the next step which was to write a routine to multiply a 16-bit number by a fixed-point value (of this same format where +/-1.0 is represented by +/-127).

The results are on the disc image below!

It turned out that it's not really so difficult, and you can achieve it surprisingly accurately by extending the technique used above.

First thing: a bit of maths again!
Code:
X is a 16-bit value
Y is our fixed-point fractional value

X * Y
= (X.lsb + X.msb * 256) * Y
= (X.lsb * Y) + (X.msb * 256 * Y)

One thing to note here: the result of the second term (with X.msb) will be 16 bits long (because it is multiplied by 256), so we will need to introduce a multiplication table of LSBs which we previously omitted (because before we were discarding this part).

So, the technique will involve cutting the 16-bit value into two portions, multiplying the high portion by the fixed point number, and keeping the whole 16-bit result, and then multiplying the low portion by the fixed point number, discarding the least significant 8 bits, and adding this to the low byte of the result.

However, we really want to be able to handle the signedness of the numbers for free, so what if we were to chop the big multiplicand into 7-bit portions? This in fact is what I do, and it works really well!

So, we chop the number into two parts:
  • bits 7-14, which is a signed value
  • bits 0-6, which is an unsigned value
It turns out that regardless of the sign of this number, it's always true that:
Code:
value = value(7-14, signed) * 128 + value(0-6, unsigned)


So then, for the first operation, we multiply the signed value (bits 7-14) by the fixed point value. This yields a 16-bit result (8 bits 'integer' and 8 bits 'fraction'), but we have to shift it right one bit so that the 'integer' part occupies the same bits as the original multiplicand (i.e. bits 7-14).

Next, we multiply bits 0-6, as an unsigned value, by the fixed point value (for this we can use the original 8-bit multiply routine), and add this to the partial result we already have, and there's the final result!

I won't post the code here as it needs a little bit of commenting, optimising and tidying up, but it's there on the disc image with another test prog :)

Attachments:
Beeb3D.zip [5.22 KiB]
Downloaded 7 times
Author:  RichTW [ Sat Sep 19, 2009 7:12 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
ThomasHarte wrote:
My best Electron-oriented plan was essentially similar to that proposed by you on the other thread; 8bits for the fractional part, and a high byte with a single bit of integer precision and a separate sign bit (not two's comp, a separate bit). Then multiplication is xor the sign bits, copy the other low byte if either has the notional integer bit set, do a table multiply otherwise. Actually, I figured it'd probably be safer to do the low-byte table multiply then use the single integer bits as decision variables on adding single extra copies of the complete original low bytes, given that low precision often pushes lengths of things just a little above 1 if you're doing compound transforms ala Elite. Maybe I'm way off though.

Regarding this, this was also my first thought on an efficient storage mechanism - 8-bit fraction (non two's complement), 1 unit bit, 1 sign bit. I got as far as writing a multiply routine for it too, handing the 'unit bit' properly, but my heart sank when I had to write the addition/subtraction routines, and what might have been a straightforward 8 or 16-bit add/subtract was a horror! I figured that the extra cycles being used would be just as well spent doing the cheap "negate both inputs at start, negate result at end" technique in the multiply, allowing a regular add to be used.

So I threw it all away and went back to the drawing board, and I think the base-127 8-bit fixed point works much faster, though whether it has the required precision remains to be seen...
Author:  ThomasHarte [ Sat Sep 19, 2009 10:56 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
Conveniently, I can already answer the precision issue. Before beginning my recent splurge of Electron activity, I wrote a quick prototype C program on my Mac to see empirically how dropping the precision affects the quality of visuals.

Probably not too surprising, but base-127 provides slightly jumpy results in 256x256 when a unit-sized object is scaled to fill the entire screen. Base-255 or base-256 make even that scale decent. My feeling is that if you stick with unit objects, precision with base-127 numbers should be fine, probably at least comparable to the precision of Elite (which, at least for me, isn't as good as I remember it).

Anyway, I'm too tired to really digest the rest of this thread. I think the relevant questions are likely to be: (i) how would you add two of your numbers?; and (ii) am I right to think that a convert to int would rescale the numbers very very slightly? But possibly you've already answered one or both, or the answers are obvious...
Author:  RichTW [ Sun Sep 20, 2009 8:36 am ]
Post subject:  Re: Fixed-point 8-bit multiplication
Two of these fixed-point numbers can be added together via a simple ADC, as (a/127)+(b/127) is equivalent to (a+b)/127.

The first multiply routine can be used to multiply either s8*f127 (to yield a s8), or f127*f127 (to yield a f127). The second routine is used to multiply an s15*f127 (to yield an s15).

Regarding your last point, why would you want to convert an f127 to an integer? I can't really think of a point in the transformation or rendering pipeline where this is useful. Matrix composition works entirely with f127s, translation composition with s15*f127s, matrix application with s8*f127s + s15. Face normal direction is determined by (x1*y2)-(x2*y1), but we only care about the sign, not the magnitude, so this could equally be performed by treating the coordinates as s127s (scaled down a little bit if necessary, so that they fit in the right range). After that, there's just projection (division) and clipping (division), and by this stage we are dealing with s15s anyway - or at least, according to the method I have in my head!

Anyway, if you really wanted to do it, just a simple reinterpretation of meaning would lead to a magnitude loss of 1/128th as you said. Of course, an alternative would be to use the long multiplication routine to multiply 256 * f127, to yield an integer with 8-bits fraction (or similarly, to use the short multiplication routine to multiply by 64...).

Nice to know this kind of precision is just about on the side of acceptable, by the way!
Author:  ThomasHarte [ Sun Sep 20, 2009 2:42 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
RichTW wrote:
Two of these fixed-point numbers can be added together via a simple ADC, as (a/127)+(b/127) is equivalent to (a+b)/127.

But you've got bits 7-14 holding a signed value and bits 0-6 holding an unsigned value. What do you do about the carry between bits 6 and 7?
Quote:
Regarding your last point, why would you want to convert an f127 to an integer?

Because I intend to use it to plot to the screen, where the scale is pixels. Though a 127/128 scaling isn't an issue, since the numbers won't be read back and scaling clipped graphics so that they are smaller doesn't lead to any out-of-bounds accesses.
Author:  RichTW [ Sun Sep 20, 2009 2:59 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
Think we're talking about different things here!

The 15-bit value is a regular 2-byte number with a slightly more limited range, and can be manipulated like any other. Don't think of it as two components - this is just how the long multiply routine dissects it so that it can use the same table as the small multiply routine.

The 'fixed127' value (as I shall call it from now on) is not compatible with this, and is only used as an input to one of the multiply routines, where:

fixed127 * fixed127 = fixed127
s8 * fixed127 = s8
s15 * fixed127 = s15

Essentially, think of the fixed127 as a totally different type with a fixed-point value between -1.0 and +1.0.

Also, fixed127s can be added or subtracted just like any other 8-bit number, with the proviso that -128 is not a valid value:

fixed127 + fixed127 = fixed127
fixed127 - fixed127 = fixed127

Still not quite sure how you would use the fixed127 values to plot to the screen. In my mind, their purpose is solely as a parameter to the multiplication routine, which yields a regular s8 or s15 value.

So, (e.g.)

The composed matrix consists of 9 fixed127s.
The composed translation consists of 3 s15's (which itself is composed by multiplying s15 * fixed127)
Model space coordinates are s8's, and are transformed through the matrix to get more s8's, and then finally added to the translation to get s15s.

At this point, the model vertices are in camera space. Here, perhaps our methods differ - I would at this point do the perspective transform (probably by multiplying each s15 vertex by (1/z) which is of course another fixed127). Then I would clip to these coordinates to the viewport (i.e. clip 16-bit to 8-bit coordinates).

It may well be that we have rather different thought processes at this stage!
Author:  RichTW [ Sun Sep 20, 2009 3:04 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
Attached is a slightly tidied-up and optimised version of the fixed point multiply routines...

Attachments:
Beeb3D.zip [5.72 KiB]
Downloaded 13 times
Author:  ColinD [ Sun Sep 20, 2009 6:30 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
There is some intersting stuff on 3D maths on Jed Margolins website.... Think this was fixed point too iirc...

http://jedmargolin.com/uvmath/uvmath.htm

Maybe a little off topic here.... but a good read....

Cheers, Colin
Author:  ThomasHarte [ Sun Sep 20, 2009 8:15 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
Quote:
The 15-bit value is a regular 2-byte number with a slightly more limited range, and can be manipulated like any other. Don't think of it as two components - this is just how the long multiply routine dissects it so that it can use the same table as the small multiply routine.

I think I've figured out what I'm having issues with. I'm going to repeat a large number of things you've said to be sure I'm following generally.

You store integers in two's complement. These integers are the real (in both senses) numbers multiplied by 127. So:

127 = 1
-127 = -1

Build the lookup tables, and 8bit x 8bit multiplication is no real issue.

Then you get a 16bit number, and you suggest that you can just pass the two bytes separately through the same 8bit multiplication table and also add/subtract the results normally. But that doesn't quite work.

a = +1 = 7f
b = -128/127 = ff80

a * b = ((7f * ff)*127) + (7f*00) = (+1 * -1/127)*127 + (+1 * 00) = -127/127 = -1

(applying the split as described in your post; low 6 bits to one multiplication, 7 bits on top of those 6 bits to the other)

I guess the nub of the problem is: is &80 a valid 8bit number or not? If not then you've got a discontinuity in your mapping from integers to floating point numbers so adding integers can't work.

If so then multiplying by splitting bits doesn't quite work. Look at it this way: were you in a base 128 fixed point, the various bits would have these values:

bit 0: 0.0078125
bit 1: 0.015625
bit 2: 0.03125
bit 3: 0.0625
bit 4: 0.125
bit 5: 0.25
bit 6: 0.5
bit 7: -1

In your base 127 you've got (to the precision of my calculator):

bit 0: 0.007874015748031
bit 1: 0.015748031496063
bit 2: 0.031496062992126
bit 3: 0.062992125984252
bit 4: 0.125984251968504
bit 5: 0.251968503937008
bit 6: 0.503937007874016
bit 7: -1.007874015748031

By just chopping off the bits above bit 6, putting them through the table, then chucking them back on in a position from bit 6, you're scaling the portion of the value stored in those bits by 1.007874015748032. That's the price you pay for using bit division equivalent to a MOD operation in base-2 on a number space that is actually base-1.99776035.

Assuming that I've stumbled on a valid mathematical reason for my instinctive feeling that you're doing something wrong, using an alternative table for the top part multiplication that prescales results by 1/1.007874015748032 would fix things.

That said, I'm a human being and just as prone to confirmation bias as anyone else, so possibly I've led myself up a blind mathematical alley trying to reach the conclusion I already feel is right. Don't think it'll hurt my feelings if I've demonstrably made a massive error here...
Author:  RichTW [ Sun Sep 20, 2009 9:56 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
I think you're making it too complicated. The main thing here is not to think of a value of the bits of a fixed127 number at all... in fact, try to forget that it's even made out of bits at all!

Think of a fixed127 number as a 'thing' which has a value between -1.0 and +1.0, and that the integer representation of these values is -127 and +127 respectively. In order to multiply an integer by a fixed127, we multiply the integer by the integer representation of the fixed127, and divide by 127. Hopefully, this makes sense so far.

Now, the next thing is that we have rigged the multiplication table. Normally, the unrigged multiplication table works like this:

a * b = f(a+b) - f(a-b)

where f(x) = x*x / 4

Instead, my fixed point code uses a table like this:

f(x) = (x*x / 4) * 256 / 127

So now the formula is:

a * b * 256 / 127 = f(a+b) - f(a-b)

Let's take an example: a is the integer 57, and b is the fixed127 value 1.0, whose integer representation is 127. When we calculate f(a+b)-f(a-b) with a=57 and b=127, we calculate 57*127*256/127 = 14592.

If we take just the high byte of this result, we get 57, which is the right answer (57 * 1.0 = 57 ;))

The extension to 15-bit * fixed127 works on a similar principle. Let's say the value a is a 15-bit signed integer. In fact, let's say it's unsigned for the moment, as it makes it easier to think about.

a = a.low + a.high * 128

where a.low and a.high are both between 0 and 127, i.e. a 7-bit unsigned integer. We choose this range because this is also the range of values for which the multiplication table has a valid index (because we only have 256 entries, and so a+b can be no bigger than 255).

So now:

a * b * 256 / 127 = f(a+b) -f(a-b)

Substituting 'a' for this compound form gives:

(a.low + a.high * 128) * b * 256 / 127

= a.low * b * 256 / 127
+ a.high * 128 * b * 256 / 127

= f(a.low + b) - f(a.low - b)
+ [f(a.high + b) - f(a.high - b)] * 128

This is exactly what my routine does. First it calculates the second term (a.high * b * 256 / 127). This is a true fixed-point value with 8 bits integer and 8 bits fraction (this is the reason for the '* 256' in the function). It shifts it down 1 bit, and thus we have now essentially multiplied it by 128, as required. Next it calculates the first term (a.low * b * 256 / 127), and because we actually only want a.low * b / 127, we discard the low byte and take only the high byte. Finally we add these two results, and there is the final answer.

It's kinda late and perhaps I'm not explaining it well, but I'm confident that it's right. If in any doubt, try loading the TEST16 program on the disc image, and change lines 80 and 90 to be any value of your choosing, e.g. try it with A%=12345, and X%=127 (i.e. 1.0). You should get the right result every time.
Author:  RichTW [ Sun Sep 20, 2009 10:05 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
Maybe your point of confusion is that you believe all the values I'm dealing with to be in this crazy base 127 form? This isn't the case at all - only these fixed127s which represent -1.0...1.0 are in this form. Everything else is a regular signed 8-bit or 16-bit (actually 15-bit, due to limitations on the size of the multiply tables) integer. The multiplication routines expect that one of the parameters is a fixed127, which contains a factor of 127, and so the multiplication routines just divide the result by 127 automatically. That's all there is to it. Erm... I don't know if I'm making it any clearer really... it must be time for bed.... :)
Author:  ThomasHarte [ Sun Sep 20, 2009 10:56 pm ]
Post subject:  Re: Fixed-point 8-bit multiplication
If your one-byte table is designed to help multiply two fixed-127 numbers, then using it for a longer number by bit splitting will introduce scaling errors above and beyond those forced by the binary storage, which are not uniform across the digits.

If your one-byte multiplication helper table is designed to help one fixed-127 and one longer fixed-128 number then it's useless for matrix composition and applying matrices to modelspace vertices.

One table can't cover both possibilities, or you're saying that a * b/127 = a * b/128 for all values of b.
Author:  RichTW [ Mon Sep 21, 2009 7:18 am ]
Post subject:  Re: Fixed-point 8-bit multiplication
Nooo! Here lies the confusion I think.

The routine multiplies a regular integer by a fixed127. That's all. It effectively does:

result = a * b / 127

Suppose 'b' is the fixed127 value.

If 'a' is a signed 8-bit integer, then the result of this will also be a signed 8-bit integer.

If 'a' is a signed 15-bit integer, then the result will also be a signed 15-bit integer.

However, here's the tricky one - if 'a' is also a fixed127, then the result will also be a fixed127. The multiplication doesn't care about what 'a' actually means; it will just treat it as a signed integer, but this is fine. It will just return a signed integer which, when interpreted as a fixed127, still represents the value we mean. This works because the value of a fixed127 is proportional to its integer representation.

This makes the routine absolutely appropriate for matrix composition, as well as matrix/sine/cosine multiplication.

Think of the analogue with 8.8 fixed point. If we multiply 2 16-bit values, and then discard the bottom 8 bits, and take bits 8-23 as the result (i.e. x = a * b / 256), this works if either both the inputs were 8.8 fixed point, or if one was a 16-bit integer and the other was a 8.8 fixed point. The result will be either a 16-bit integer, or a 8.8 fixed point value. The routine doesn't work if both inputs were 16-bit integers, because of course we are dividing by 256 at the end, and losing half of the bits of the result.

Back to the fixed127 stuff, try the simple case: x = 1.0 * 1.0

We just feed 127 and 127 to the multiply routine, which yields
x = 127 * 127 / 127
= 127
= 1.0

The 15-bit multiply extends upon this idea. However in the case of this routine, obviously the 15-bit value must be a signed integer - it can't possibly be a fixed127 - and hence the result will also be a signed integer.

If you're still in any doubt, these multiply routines could never be used to multiply two regular integers. One of the values has to be a fixed127, because of the implicit divide by 127.

I'm kinda running out of ways to explain it, but I'm confident that it's correct (as ably demonstrated by my test programs).

In summary: fixed127s are just numbers between -1.0 and 1.0. Don't use them for anything other than multiplying an integer (or another fixed127) by a value between -1.0 and 1.0! This is why they are perfect for representing matrices :) Things like vertex coordinates should be regular signed 8-bit integers. Transform them by multiplying them by fixed127s to yield a new signed 8-bit value. Don't add fixed127s to regular integers - they're not compatible types, and this won't work. However, you can add one fixed127 to another - as indeed you would have to when composing a matrix.
Author:  RichTW [ Mon Sep 21, 2009 8:20 am ]
Post subject:  Re: Fixed-point 8-bit multiplication
Of course, at the end of all this, while fixed127s may look ok on paper, and can be multiplied pretty quickly, they may not be sufficient for decent transforms. There may be problems of accuracy, for example their inability to exactly represent +/-0.5. In which case the 10-bit approach would be better, but unfortunately just doubles the amount of memory required to represent each value (and hence slows down the code too).
Page 1 of 2 All times are UTC [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/