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/cont...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!

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/show...2255#post92255

Have fun!!!