Author Topic: [z80] 32 bit by 16 bits division and 32 bit square root  (Read 22074 times)

0 Members and 1 Guest are viewing this topic.

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
[z80] 32 bit by 16 bits division and 32 bit square root
« on: April 10, 2013, 03:50:37 pm »
I need a 32 bit by 16 bit division routine but I have absolutely no idea how to do this. I specifically need to check if the modulus is non zero. Can you give me some tips ? Asm in 28 days has 32/8 which is not enough for me.

Same for a 32 bit square root routine. I need the result as a 16 bit integer.

Note that I'm not asking for code but some help to create them myself and then optimization because I'm not Runer/ThePenguin/Calc84maniac and I want to learn. :P
« Last Edit: April 10, 2013, 03:59:10 pm by Streetwalker »

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #1 on: April 11, 2013, 07:21:25 am »
Is anyone willing to help ?

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #2 on: April 11, 2013, 10:52:16 am »
I don't really know how to do that, but I think it's the same way as a 16 by 16 division. I know that in the process you loop as much times as bits that are in the first operand (idk if that's English :P), so you would do 32 loops I think. But I can't really help.

Offline Hayleia

  • Programming Absol
  • Coder Of Tomorrow
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3367
  • Rating: +393/-7
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #3 on: April 11, 2013, 11:38:56 am »
I am not really sure that people trying to win the TI Planet contest will be willing to help you before the deadline :P
I own: 83+ ; 84+SE ; 76.fr ; CX CAS ; Prizm ; 84+CSE
Sorry if I answer with something that seems unrelated, English is not my primary language and I might not have understood well. Sorry if I make English mistakes too.

click here to know where you got your last +1s

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #4 on: April 11, 2013, 11:47:07 am »
I think Z80 Bits is where everybody learned how bitwise math routines worked. It has code for multiplication, division, and square root routines of varying bit-width inputs, and pretty good explanations of the algorithms behind them. Unfortunately none of the routines go up to bit widths quite as high as you're looking for, probably because at that point you start running out of registers. I figure you can get 32-bit/16-bit by just using one of the existing routines and throwing in the use of ix to fit all the necessary bits. As for the restoring square root algorithm... that algorithm is a little mind-boggling. But I figure you'd need 16 bits to store the result instead of 8, the comparison step would have to compare 24 bits instead of 16, and you'd need to find a way to feed in 24 bits of the input (I think 8 bits always start in the "accumulator"). By the looks of it, you might be short one register, even if you use ix. Perhaps make sure interrupts are turned off and use shadow registers?

But as Hayleia said, since I'm pretty sure this is for the TI-Planet contest, I don't think anybody should really write your routines for you. But hopefully I've given you some good guidance to being able to take a stab at it yourself. :)
« Last Edit: April 11, 2013, 11:48:00 am by Runer112 »

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #5 on: April 11, 2013, 11:48:14 am »
Xeda helped me optimize my primality checker a bit. I think I have an idea for arbitrary precision division though and jacobly linked me an arbitrary precision sqrt routine. I will see what I can do with that. And everyone is not in the contest. :P Also :
Note that I'm not asking for code but some help to create them myself and then optimization because I'm not Runer/ThePenguin/Calc84maniac and I want to learn. :P

Thanks for the link Runer.
« Last Edit: April 11, 2013, 01:02:21 pm by Streetwalker »

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: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #6 on: April 11, 2013, 05:27:21 pm »
I did? I don't remember that D: Or were you talking about the BASIC code/trial division stuff?

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #7 on: April 12, 2013, 02:01:54 am »
Yeah that's what I was talking about but since I use the exact same thing in Axe... :P

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #8 on: April 12, 2013, 07:36:40 am »
I can't get the 24/16 routine from z80 bits to work. :s
Here's what I'm running :
Code: [Select]
    di
    ld a, 244      ;dividend high byte
    ld bc, 9216   ;dividend low word (244*2^16+9216=16000000)
    ld de, 47288 ;divisor
    ld hl, 0
    exx
    ld b, 24
LOOP:
    exx
    slia c ; unroll 24 times
    rl b ; ...
    rla ; ...
    adc hl,hl ; ...
    sbc hl,de ; ...
    jr nc,$+4 ; ...
    add hl,de ; ...
    dec c ; ...
    exx
    djnz LOOP
    exx
    ;load the values of a, bc and hl to the first five bytes of appBackupScreen
    ei
What am I doing wrong ? ??? I tried it several times and I always get wrong results.
« Last Edit: April 12, 2013, 08:01:56 am by Streetwalker »

Offline jacobly

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 205
  • Rating: +161/-1
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #9 on: April 12, 2013, 07:52:33 am »
You only have one exx in the loop, so every time through the loop uses different registers.  It should work if you add an exx at the beginning of the loop.
« Last Edit: April 12, 2013, 07:53:12 am by jacobly »

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #10 on: April 12, 2013, 07:58:03 am »
You only have one exx in the loop, so every time through the loop uses different registers.  It should work if you add an exx at the beginning of the loop.
I forgot to copy it but I actually have it.

Offline jacobly

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 205
  • Rating: +161/-1
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #11 on: April 12, 2013, 08:07:44 am »
In that case you probably have an overflow problem.  Try either using a 48-bit temp value or putting
Code: [Select]
jr nc,$+7
or a
sbc hl,de
jr $+7
after adc hl,hl.

Offline Streetwalrus

  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3821
  • Rating: +80/-8
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #12 on: April 12, 2013, 08:18:20 am »
Should I leave the extra sbc hl,de ?

Edit : It doesn't fix anything...
Edit 2 : My code actually worked I was just displaying without the small r in axe. :P
« Last Edit: April 12, 2013, 12:09:23 pm by Streetwalker »

Offline fghsgh

  • LV1 Newcomer (Next: 20)
  • *
  • Posts: 11
  • Rating: +2/-0
    • View Profile
Re: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #13 on: March 17, 2019, 09:53:03 am »
I know this is old (and I'm sorry for sending you all a notification), but I happened to need a 32 div 16 routine today, so I made one:
This divides HLIX by BC
The result is stored in HLIX, the remainder in DE
BC is unmodified
A is 0
it doesn't use any other registers or RAM
Code: [Select]
div32_16:
 ld de,0 ; 10
 ld a,32 ; 7
div32_16loop:
 add ix,ix ; 15
 adc hl,hl ; 15
 ex de,hl ; 4
 adc hl,hl ; 15
 or a ; 4
 sbc hl,bc ; 15
 inc ix ; 10
 jr nc,cansub ; 12/7
  add hl,bc ; 11
  dec ix ; 10
cansub:
 ex de,hl ; 4
 dec a ; 4
 jr nz,div32_16loop ; 12/7
 ret ; 10
I'm not saying this is the fastest possible, but at least it does the job. This takes 4094 T-States in the worst case, 3582 in the best case, which is between .6 and .7 ms at 6 MHz.
I could add some comments to this, but it's more difficult to explain what is going on than to just program it.
Also, note that this doesn't check if BC is 0 so you will get junk as an answer in that case.
I might also write a 32-bit square root routine if it is still needed.

EDIT: an optimized version can be found further in this topic.
« Last Edit: March 17, 2019, 12:39:08 pm by fghsgh »
English is not my native language. If I make any mistakes, please correct me so I can learn.

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: [z80] 32 bit by 16 bits division and 32 bit square root
« Reply #14 on: March 17, 2019, 10:40:19 am »
Thanks! I am on mobile, so not much help, but a few quick optimizations I see are changing those Inc/dec ix to use ixl instead (the bottom bit is 0 and 1 at those points, so no worry of overflow) and you don't need the `or a` before the sbc since the add before it is always pushing out a 0 bit (so leaving carry reset).

Do you prefer speed optimizations or size optimizations, btw?

Thanks for the work, I actually visit this thread semi-frequently!