64-bit division

[Manfred]

I'm developing a hobby project involving a 16F886 and a DDS, and for this I need to divide a 64-bit number by a 32-bit number to get a 32-bit result. The problem is that I seem to be too mathematically challenged to come up with a way to do this!

The division I need is unsigned.

The 64 bit number is actually a 32 bit number shifted left, so that the right 32 bits are always zero.

The actual numbers I will have for the dividend are in the range from 500,000 to 35,000,000 for the 32 MSBs (26 truly valid bits. The 6 MSBs stay at zero). That would be about 2*10^15 to 1.5*10^17 for the full 64 bit dividend, making it actually a 58 bit number.

The divisor will be between 150,000,000 and 500,000,000, so this is actually a 29 bit number.

The result I need to get will range from zero to about 1.5*10^9, so it's actually a 31 bit number.

How can I do this, using the 16 bit divide function of PBP?

[Bruce]

Have a look at this thread by Darell: http://www.picbasic.co.uk/forum/showthread.php?t=12433

[Manfred]

Bruce,
that assembly library should indeed solve my problem - if I ever manage to understand how to use it from PBP!

I would prefer to do this with PBP's math functions, to keep the program nice and readable.

[mackrackit]

If you figure out how to do it with straight PBP I doubt if it would be any more readable than
INCLUDE "N-Bit_MATH.pbp"
with a few lines of ASM added to your main code.

[Manfred]

Well, I'm trying to get that n-bit math to work for me. I downloaded and installed MPASMWIN (I hope that's the right one?), included the math library in my program, defined the three 64 bit variables, etc. So far I haven't been able to get it working, I'm still sorting through the learning curve.
At this time I'm a bit stuck because MPASMWIN shows up, says it has found one error, has one warning, and 262 messages. When I press "OK", I have to quickly stop the stream to be able to even see the beginning, where the error is! The error is:

Unable to exceute mpasmwin.

The warning does not show up, and the messages are all about the code crossing page boundaries.

I don't understand this. How is it that it can't execute mpasmwin, when mpasmwin is reporting that error??? Isn't this like the question of the hen and the egg?

[mackrackit]

To start with you probably need to use the MPASWIN that came with your PBP CD.
Install MPLAB from the CD to the default place and MPASMWIN will be there. Sometimes the one downloaded will not work.

Then I will guess that you are using Micro Code Studio as a code editor. Go to Tool on the tool bar and select compiler options then under the Assembler tab select MPASM.

Then give it a try.

[Manfred]

I'm so antiquated that I still use Notepad to edit my PBP programs! Also I use Notepad to edit programs in several other languages. It doesn't have any bells and whistles, but is quick and practical.

About installing MPLAB to the default place, that isn't possible, because for starters I run the whole PIC stuff on drive E:. Perhaps this is the reason why MPASM won't work. I do have the paths properly set up, but who knows what they do with them!

This whole thing is getting too problematic. I had hoped that someone could propose a simple PBP routine, using the 16-bit math provided in PBP, to do this 64-bit division. I will better continue in that line, rather than setting up a new programming environment, learning to use it, perhaps reformat and repartition my hard disk, to be able to use that assembly library!

The worst case is that I have to implement bitwise division in PBP, which would be rather slow and inelegant. Surely somebody has a better idea!

[ScaleRobotics]

This whole thing is getting too problematic. I had hoped that someone could propose a simple PBP routine, using the 16-bit math provided in PBP, to do this 64-bit division. I will better continue in that line, rather than setting up a new programming environment, learning to use it, perhaps reformat and repartition my hard disk, to be able to use that assembly library!

Darrel's N-Bit math is the only simple PBP routine I know of. 64 bits on an 8 bit device is not so simple. Most program examples and includes on this site, all require mpasm, so you will probably eventually want to go there anyway. Why not install PBP as the manual suggests (on page 5) and put PBP in a folder on the C drive. Make your life easier, not harder.

If you want a routine, you can follow the links on Darrel's http://www.picbasic.co.uk/forum/content.php?r=153-N-Bit_MATH and retrieve assembly code to your liking. http://avtanski.net/projects/math/

Here is the bare assembly 64 bit division:


#include
; remove this if not necessary

#define PRECISION 64 ; byte size for registers

M_STOR_STATUS macro WHERE
movf STATUS,w
movwf WHERE
endm

M_RETR_STATUS macro WHERE
movf WHERE,w
movwf STATUS
endm

cblock 0x20
REG_X:PRECISION
REG_Y:PRECISION
REG_Z:PRECISION
REG_COUNTER
REG_STATUS
REG_T1
REG_T2
REG_ROT_COUNTER
endc


org 0x00
goto M_TEST
org 0x04
goto M_TEST


org 0x0c
M_TEST ; Test subroutine
movlw REG_X
call M_CLR ; clear register X

movlw REG_Y
call M_CLR ; clear register Y

movlw REG_Z
call M_CLR ; clear register Z

movlw 0x8A
movwf REG_X ; set register X (lowest byte)

movlw 0xFC
movwf REG_Z ; set register Z (lowest byte)

call M_ADD ; adds X and Z, result in Z

movlw 0x05 ; set regiester X (lowest byte)
movwf REG_X

call M_DIV ; divide Z by X, result in Y, remainder in Z
sleep ; end of test


M_CLR ; clear a register
movwf FSR
movlw PRECISION
movwf REG_COUNTER
M_CLR_loop
clrf INDF
incf FSR,f
decf REG_COUNTER,f
btfss STATUS,Z
goto M_CLR_loop
return

M_INC ; increment a register
movwf FSR
movlw PRECISION
movwf REG_COUNTER
M_INC_loop
incf INDF,f
btfss STATUS,Z
return
incf FSR,f
decf REG_COUNTER,f
btfss STATUS,Z
goto M_INC_loop
return


M_DEC ; decrement a register
movwf FSR
movlw PRECISION
movwf REG_COUNTER
M_DEC_loop
decf INDF,f
movlw 0xFF
subwf INDF,w
btfss STATUS,Z
return
incf FSR,f
decf REG_COUNTER,f
btfss STATUS,Z
goto M_DEC_loop
return


M_ROL ; rotate a register to the left
movwf FSR
M_STOR_STATUS REG_STATUS
clrf REG_COUNTER
M_ROL_loop
M_RETR_STATUS REG_STATUS
rlf INDF,f
M_STOR_STATUS REG_STATUS
incf FSR,f
incf REG_COUNTER,f
movlw PRECISION
subwf REG_COUNTER,w
btfss STATUS,Z
goto M_ROL_loop
return


M_ROR ; rotates a register to the right
movwf FSR
movlw PRECISION-1
addwf FSR,f
M_STOR_STATUS REG_STATUS
clrf REG_COUNTER
M_ROR_loop
M_RETR_STATUS REG_STATUS
rrf INDF,f
M_STOR_STATUS REG_STATUS
decf FSR,f
incf REG_COUNTER,f
movlw PRECISION
subwf REG_COUNTER,w
btfss STATUS,Z
goto M_ROR_loop
return


M_CMP ; Z <=> X -> STATUS(C,Z)
; STATUS,C set if Z => X;
; STATUS,Z set if Z == X
clrf REG_COUNTER
M_CMP_loop
movf REG_COUNTER,w
sublw REG_Z+PRECISION-1
movwf FSR
movf INDF,w
movwf REG_T1
movf REG_COUNTER,w
sublw REG_X+PRECISION-1
movwf FSR
movf INDF,w
subwf REG_T1,f
btfss STATUS,Z
return
incf REG_COUNTER,f
movlw PRECISION
subwf REG_COUNTER,w
btfss STATUS,Z
goto M_CMP_loop
return


M_ADD ; Z + X -> Z
bcf STATUS,C
clrf REG_STATUS
clrf REG_COUNTER
M_ADD_loop
clrf REG_T1
btfsc REG_STATUS,C
incf REG_T1,f
clrf REG_STATUS
movlw REG_X
addwf REG_COUNTER,w
movwf FSR
movf INDF,w
addwf REG_T1,f
btfsc STATUS,C
bsf REG_STATUS,C
movlw REG_Z
addwf REG_COUNTER,w
movwf FSR
movf INDF,w
addwf REG_T1,f
btfsc STATUS,C
bsf REG_STATUS,C
movf REG_T1,w
movwf INDF
incf REG_COUNTER,f
movlw PRECISION
subwf REG_COUNTER,w
btfss STATUS,Z
goto M_ADD_loop
return


M_SUB ; Z - X -> Z
clrf REG_COUNTER
bsf REG_STATUS,C
M_SUB_loop
bsf REG_T2,C
movlw REG_Z
addwf REG_COUNTER,w
movwf FSR
movf INDF,w
movwf REG_T1
movlw REG_X
addwf REG_COUNTER,w
movwf FSR
movf INDF,w
subwf REG_T1,f
btfss STATUS,C
bcf REG_T2,C
btfsc REG_STATUS,C
goto M_SUB_no_carry
movlw 0x01
subwf REG_T1,f
btfss STATUS,C
bcf REG_T2,C
M_SUB_no_carry
movlw REG_Z
addwf REG_COUNTER,w
movwf FSR
movf REG_T1,w
movwf INDF
bsf REG_STATUS,C
btfss REG_T2,C
bcf REG_STATUS,C
incf REG_COUNTER,f
movlw PRECISION
subwf REG_COUNTER,w
btfss STATUS,Z
goto M_SUB_loop
btfss REG_STATUS,C
bcf STATUS,C
return


M_MUL ; X * Y -> Z
movlw REG_Z
call M_CLR
movlw PRECISION*8+1
movwf REG_ROT_COUNTER
M_MUL_loop
decf REG_ROT_COUNTER,f
btfsc STATUS,Z
return
btfsc REG_Y,0
call M_ADD
bcf STATUS,C
movlw REG_Y
call M_ROR
bcf STATUS,C
movlw REG_X
call M_ROL
goto M_MUL_loop


M_DIV ; Z / X -> Y; remainder -> Z
movlw REG_Y
call M_CLR
movlw PRECISION*8
movwf REG_ROT_COUNTER
M_DIV_rot_loop
btfsc REG_X+PRECISION-1,7
goto M_DIV_loop
movlw REG_X
bcf STATUS,C
call M_ROL
decf REG_ROT_COUNTER,f
btfss STATUS,Z
goto M_DIV_rot_loop
bsf STATUS,Z
return
M_DIV_loop
call M_CMP
M_STOR_STATUS REG_T2
movlw REG_Y
call M_ROL
M_RETR_STATUS REG_T2
btfsc STATUS,C
call M_SUB
bcf STATUS,Z
bcf STATUS,C
movlw REG_X
call M_ROR
incf REG_ROT_COUNTER,f
movlw PRECISION*8+1
subwf REG_ROT_COUNTER,w
btfss STATUS,Z
goto M_DIV_loop
return

END
But I still think installing PBP right, and using Mpasm with Darrels N Bit Math is the way to go. Especially if you want easy. Once you get your program set up right, you will be able to easily add different include files.

[Manfred]

Well, I'm getting old, and as you surely know, we old guys tend be get used to our own ways of doing things! http://www.picbasic.co.uk/forum/images/smilies/wink.gif

Thank you a lot for all your help, but it simply seems too complicate to have all that looooong assembly code put in, just to do one single division! Reconfiguring my PC to be able to install PBP in the default configuration, and then learning to use the new programs, and so on, would simply take FAR too long. I want to get my project going soon, instead of embarking in a new project of PC reconfiguration, learning to use a new programming environment, and who knows what else.

So I have totally turned around the way I calculate the value I need. Instead of the routine that required the 64 bit division to arrive at the final 32 bit tuning value I need for my DDS, I prepare the data in 16 bit chunks and calculate the 32 bit tuning value as the last step in the process, using PBP's "*" and "**" operators. In doing so, I loose some tuning range, and some tuning resolution, compared to the method that needs the 64 bit division. But both of these losses are acceptable for this particular project, so I will keep this for now.

In the future I will probably do more demanding projects using a DDS, and at that point I will get back to needing multibit division... But based on the newly acquired experience, I will then use an 18-series PIC, so I can use PBP's 32 bit math, which should allow enough tuning range and resolution for even quite high requirements, using the same algorithm I implemented a while ago.

By the way, the configuration of my PC has evolved from the very first PC I owned, almost 30 years ago, and that's why it doesn't conform to modern Windows practice. I use a large quantity of specific programs , many of them written by myself. Over the years, I have added to this setup, and transferred it from each PC to the next more modern one.

Any attempts I have done to set up a new system on a new PC, and getting everything to work there, have proven to take so much time that I threw the towel before getting anywhere close to finishing. That's why I still use my old configuration.

Thanks again. I have learned that apparently there is no simple way to use PBP's 16 bit math to create 32 or 64 bit math, and so it's better for me to use a workaround.

[mackrackit]

Using note pad is cool. And to talk about non standard setups I mostly run on Linux and either use Emacs or gEdit for code writing.
I just figured you were a newb that is why I assumed you were using Micro Code Studio ... Sorry.

When you do start using 18F's MPASM will be required. It cam be evoked from the command line from just about anyplace. When you get to that point and maybe need some help we will be here.

[Manfred]

I should not have much trouble using MPASM. I just tried it with the present version of my program, and it works well. It only reported that strange error when there was the n-bit math code present.
Without that code, it assembles my program well, but still reports over 200 messages about crossing page boundaries. I hope these messages can be disabled somehow, because they make any real error messages scroll out of the window AND out of the screen buffer!

I guess that with enough time, things will fall into place.

[mackrackit]

This should help
http://www.picbasic.co.uk/forum/showthread.php?t=40

[Manfred]

Yes, it helps! Now the hundreds of useless messages are gone!

But one problem leads to the next: With PM, I edited the include file for the specific PIC to get the configuration word I need, without having to edit it in the PIC programmer every time. But with MPASM, I get the default config word, and have to edit it! I tried adding directives for the assembler to use the config word I need, but so far this has only led to errors.

Other than that, MPASM is giving the exact same output as PM. So, as long as I still use only 16F devices, I don't see a good reason to use MPASM at all! Is there any?

[mackrackit]

In the same inc file that you set the configs for PM is where you set them for MPASM . Second set of configs.

If you are using 16Fs and straight PBP then PM is fine.

[Manfred]

Oh, stupid me! It even SAYS in the file that the first set is for PM and the other is for MPASM! I didn't notice that... Now it works fine.

Let's blame it to my old age!

Thanks again!

[mackrackit]

Oh, stupid me!
:D
If only I could figure out how to get paid for my stupid mistakes I would have it made.
http://www.picbasic.co.uk/forum/showthread.php?t=13557&p=92255#post92255

Have fun!!!