| |
Dr. Jay
Account closed
Registered: Jan 2003
Posts: 32 |
fixed point multiplication
Okay, so a newbie, lamer question again. I did the Google searches, etc, but came up with (a) a MACRO that doesn't compile with the assemblers I'm using, and (b) some excerpts of code that weren't well documented. The best I could come up with for a 16-bit integer multiply that does NOT handle overflow is this:
mult16 lda #$00
sta $fb
sta $fc
ldx #$10
multloop asl $fb
rol $fc
asl $f7
rol $f8
bcc multnext
clc
lda $f9
adc $fb
sta $fb
lda $fa
adc $fc
sta $fc
multnext dex
bpl multloop
rts
Unfortunately, this code does NOT work .. I'm assuming there's something I need to shift right, etc, but I'm banging my head. Anyone wanna help a newbie out?
|
|
| |
Dr. Jay
Account closed
Registered: Jan 2003
Posts: 32 |
P.S. The "intention" was to have integer one in low-high format ($f7, $f8) x ($f9, $fa) into ($fb, $fc)
|
| |
CyberBrain
Administrator
Posts: 392 |
i made a similiar routine once. Just checked the source and the only diffence (unless there's something i didn't spot) is that you write:
asl $fb
rol $fc
asl $f7
rol $f8
where i wrote:
lsr $fc
ror $fb
ror $f8
ror $f7
i'm too tired to relearn the theory right now, so just try it and see if it works.
I can see in my source that you can make the result 32-bit without changing the source at all!! Something about that i re-used one of the product-words as a result-word (or whatever). TOO TIRED!!
|
| |
Dr. Jay
Account closed
Registered: Jan 2003
Posts: 32 |
I got it ... finally. http://www.6502.org/ had source for a 32-bit multiply with a 64-bit result, so I knocked it down to 16-bit with 32-bit results:
;16-bit multiply with 32-bit product
multiplier = $f7
multiplicand = $f9
product = $fb
mult16 lda #$00
sta product+2 ; clear upper bits of product
sta product+3
ldx #$10 ; set binary count to 16
shift_r lsr multiplier+1 ; divide multiplier by 2
ror multiplier
bcc rotate_r
lda product+2 ; get upper half of product and add multiplicand
clc
adc multiplicand
sta product+2
lda product+3
adc multiplicand+1
rotate_r ror ; rotate partial product
sta product+3
ror product+2
ror product+1
ror product
dex
bne shift_r
rts
Thanks for the help. Now I just got to figure out how to reverse the byte order for fixed point multiplication of decimals (i.e. back fraction part in low order byte, multiply, etc) and then I should be well on my way to coding my first routine. Coolio.
|
| |
White Flame
Registered: Sep 2002
Posts: 136 |
Here's a really short 8bit x 8bit multiply routine, works with signed and unsigned: http://www.geocities.com/white-flame/multiply.txt |
| |
Dr. Jay
Account closed
Registered: Jan 2003
Posts: 32 |
White Flame - thanks for that, it *is* a great algorithm. I was able to use it to perform fixed point math to approximately 3 decimal places and plot a bifurcation diagram ( x[n+1] = r * x[n] * (1.0 - x[n]) ) in less than a minute in hi-res bitmap mode! So thanks!
Dr. Jay
|
| |
raven
Account closed
Registered: Jan 2002
Posts: 137 |
well that algorithm is still very slow..
if you need mult for real-time code, you better use the following formulae:
a*b = f(a+b) - f(a-b), f(x) = x^2/4.
you can find more info on it in C=Hacking magazine issue #16 ( www.ffd2.com/fridge ).
For something even faster (but less accurate) you can always use logs.
good luck :)
Raven/64ever |
| |
White Flame
Registered: Sep 2002
Posts: 136 |
Yeah, but the quarter-square method requires at least a 512-byte table, and doesn't scale as easily to larger numbers (eg. 16/32-bit operands) which Dr. Jay needs.
The one I came up with was written to be as tiny as possible. It's the smallest shift-add routine that I've seen (11 bytes for multiply-accumulate), and does have the early-end optimization which really helps the speed.
Once I have time to get into 65816 code, it'd be nice to extend this to use 16-bit registers. :) |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
Hmm... time to re-publish the rest of my maths tuts in English. |
| |
Dr. Jay
Account closed
Registered: Jan 2003
Posts: 32 |
Krill, I found your math assembly tuts 1 & 2 ... are the other ones published in English as well? I could only find the two diskmags (Attitude #4 and Domination #17) ....
Thanks,
Your humble fan,
-Doc |
