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

0 Members and 1 Guest are viewing this topic.

#### Streetwalrus

• LV12 Extreme Poster (Next: 5000)
• Posts: 3820
• Rating: +80/-8
##### [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.
« Last Edit: April 10, 2013, 03:59:10 pm by Streetwalker »
send it

#### Streetwalrus

• LV12 Extreme Poster (Next: 5000)
• Posts: 3820
• Rating: +80/-8
##### 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 ?
send it

#### Matrefeytontias

• Axe roxxor (kinda)
• LV10 31337 u53r (Next: 2000)
• Posts: 1982
• Rating: +310/-12
• Axe roxxor
##### 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 ), so you would do 32 loops I think. But I can't really help.

#### Hayleia

• Programming Absol
• Coder Of Tomorrow
• LV12 Extreme Poster (Next: 5000)
• Posts: 3367
• Rating: +393/-7
##### 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
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.

#### Runer112

• Moderator
• LV11 Super Veteran (Next: 3000)
• Posts: 2289
• Rating: +639/-31
##### 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 »

#### Streetwalrus

• LV12 Extreme Poster (Next: 5000)
• Posts: 3820
• Rating: +80/-8
##### 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. 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.

« Last Edit: April 11, 2013, 01:02:21 pm by Streetwalker »
send it

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4607
• Rating: +716/-6
• Calc-u-lator, do doo doo do do do.
##### 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 Or were you talking about the BASIC code/trial division stuff?

#### Streetwalrus

• LV12 Extreme Poster (Next: 5000)
• Posts: 3820
• Rating: +80/-8
##### 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...
send it

#### Streetwalrus

• LV12 Extreme Poster (Next: 5000)
• Posts: 3820
• Rating: +80/-8
##### 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]

#### Streetwalrus

• LV12 Extreme Poster (Next: 5000)
• Posts: 3820
• Rating: +80/-8
##### 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.
« Last Edit: April 12, 2013, 12:09:23 pm by Streetwalker »
send it

#### fghsgh

• LV1 Newcomer (Next: 20)
• Posts: 10
• Rating: +2/-0
##### 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 ; 7div32_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 ; 10cansub: ex de,hl ; 4 dec a ; 4 jr nz,div32_16loop ; 12/7 ret ; 10I'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.

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4607
• Rating: +716/-6
• Calc-u-lator, do doo doo do do do.
##### 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!