Author Topic: 24 bit multiplication  (Read 17686 times)

0 Members and 1 Guest are viewing this topic.

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
24 bit multiplication
« on: December 07, 2011, 08:13:26 am »
I have been looking for two days now to find a z80 ASM routine that multiplies two 24 bit numbers to get a 48 bit result.

I need it because I want to try and make a Mandelbrot set generator for the Ti84+ using Q2.21 Fixed Point numbers.

Now I would try to come up with one myself but if anyone knows of an existing one I'd like to know!

Thanks

Offline jacobly

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 205
  • Rating: +161/-1
    • View Profile
Re: 24 bit multiplication
« Reply #1 on: December 07, 2011, 11:05:18 pm »
I do have a 24-bit floating-point multiplication routine ;D

Anyway, for normal 24-bit multiplication, it might just barely be possible without using memory, iy, or shadow registers...
Code: [Select]
; hldebc = hla * cde, a = 0
ld b,0
push hl
ld l,b
ld h,a
ld ix,0
ld a,24
Loop:
add ix,ix
adc hl,hl
ex (sp),hl
adc hl,hl
ex (sp),hl
jr nc,Next
add ix,de
adc hl,bc
jr nc,Next
ex (sp),hl
inc hl
ex (sp),hl
Next:
dec a
jr nz,Loop
pop de
ex de,hl
push ix ; ld c,ixl
pop bc ; ld b,ixh
...cool, I was right!

saved 2 bytes, 1149 cycles saved by using iy too (and in a way compatible with TIOS, imagine that)
Code: [Select]
; hldebc = hlc * bde
ld (iy+asm_Flag1),b
xor a
ld ix,0
ld b,24
Loop:
add ix,ix
rla
rl c
adc hl,hl
jr nc,Next
add ix,de
adc a,(iy+asm_Flag1)
rl c
jr nc,Next
inc hl
Next:
djnz Loop
ld e,a
ld d,c
push ix ; ld c,ixl
pop bc ; ld b,ixh

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit multiplication
« Reply #2 on: December 08, 2011, 10:01:41 am »
Thanks a lot jacobly for your reply!

So, those 2 routines, are they for floating point numbers or for integers? I assume the latter, but just to be sure :)
Any idea how long they take to complete on average? I could count myself but seeing you talking about saving 1149 cycles makes me think you have an idea yourself ;)

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: 24 bit multiplication
« Reply #3 on: December 08, 2011, 10:11:48 am »
And, I'm assuming the result is in bc?

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: 24 bit multiplication
« Reply #4 on: December 08, 2011, 10:12:35 am »
hldebc, actually, according to the note in the first code (I am assuming)

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit multiplication
« Reply #5 on: December 08, 2011, 10:27:12 am »
That's right, because the a 24 bit times 24 bit multiplication can have a result of at most 48 bits or 6 bytes, hence it should be stored in 'hldebc' and not just 'bc'.

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: 24 bit multiplication
« Reply #6 on: December 08, 2011, 10:38:11 am »
Ok, this is a bit of a stretch, but how about square-rooting a 24-bit number. Because I need to do the distance formula with a three-byte inputs for x1, x2, y1, y2, z1, and z2.

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit multiplication
« Reply #7 on: December 08, 2011, 10:53:11 am »
Quote
Ok, this is a bit of a stretch, but how about square-rooting a 24-bit number

Interesting question. I have thought about this myself since I would need to square as well for the Mandelbrot formula. I would just multiplicate normally, but I bet there could be some optimization when both the multiplier and multiplicator are the same. Perhaps you could try something with just 8 bits first to keep it simple and then if it works, work up to 24 bits.

EDIT: Sorry, read you question wrong.. thought you meant squaring. Square-rooting would be a little harder I suppose...
« Last Edit: December 08, 2011, 10:55:35 am by cerzus69 »

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: 24 bit multiplication
« Reply #8 on: December 08, 2011, 10:55:41 am »
Hmm, that is an interesting question... I know of a simple algorithm that I have ported to 8-bit and 16-bit z80 code, but I haven't tried 24-bit or 32-bit...

EDIT: @cerzus69: he meant sqrt(x) as opposed to x2 I believe

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: 24 bit multiplication
« Reply #9 on: December 08, 2011, 11:12:03 am »
Yes. Basically, here's what I'm trying to do:

1. (x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2  --> Ans , where all x,y,and z coords are 3 bytes large
2. √Ans

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit multiplication
« Reply #10 on: December 08, 2011, 11:19:11 am »
If all the coords are 3 bytes large wouldn't that mean that Ans could possibly be 6 bytes large?
« Last Edit: December 08, 2011, 11:19:36 am by cerzus69 »

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: 24 bit multiplication
« Reply #11 on: December 08, 2011, 11:20:31 am »
So you really need 48-bit square root...
This could be fun x.x :D

Offline ACagliano

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 919
  • Rating: +32/-2
    • View Profile
    • ClrHome Productions
Re: 24 bit multiplication
« Reply #12 on: December 08, 2011, 11:31:05 am »
Ideas? Anyone willing to have "fun" with this?

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: 24 bit multiplication
« Reply #13 on: December 08, 2011, 11:36:34 am »
Well I am almost positive that using my algorithm would require the use of RAM, even if you used all the shadow registers, too.

Offline cerzus69

  • LV2 Member (Next: 40)
  • **
  • Posts: 27
  • Rating: +6/-0
    • View Profile
Re: 24 bit multiplication
« Reply #14 on: December 08, 2011, 11:36:52 am »
I wouldn't know where to start, I'm having problems enough with 24bit multiplication... :(