Path: news1.icaen!news.uiowa.edu!news1.chicago.cic.net!iagnet.net!204.71.0.61!peerfeed!newsfeed.internetmci.com!arclight.uoregon.edu!platform.uoregon.edu!cie-2.uoregon.edu!nparker
From: nparker@cie-2.uoregon.edu (Neil Parker)
Newsgroups: comp.sys.apple2.programmer
Subject: Re: 32 bit mul & div
Date: 4 Sep 1997 07:10:08 GMT
Organization: University of Oregon Campus Information Exchange
Lines: 125
Message-ID: <5ulmsg$7d3@platform.uoregon.edu>
References: <19970904034300.XAA24485@ladder02.news.aol.com>
NNTP-Posting-Host: cie-2.uoregon.edu

In article <Pine.SOL.3.96.970824193831.22408C-100000@post.its.mcw.edu> Ronald
Kneusel <rkneusel@post.its.mcw.edu> writes:
>Subject says it all.  Specifically, I'm looking for 32-bit _signed_ 
>multiplication and division:
>
>32-bit * 32-bit = 64-bit (or 32-bit ignoring overflow)
>
>32-bit / 32-bit = 32-bit (plus remainder)
>
>I've found 16-bit routines but was wondering if anyone had 32-bit routines 
>in 6502 assembly handy.

Here's the 32-bit unsigned division routine.  It wants the dividend in
location Q1 (low byte) through Q4 (high byte), and the divisor in locations
D1 through D4.   The quotient comes out in locations Q1 through Q4
(replacing the dividend), and the remainder is in locations R1 through R4.
For maximum efficiency, all twelve locations should be on page 0, but this
is not required.

DIV32   LDA #0      ;Init remainder to 0
        STA R1
        STA R2
        STA R3
        STA R4
        LDX #32     ;Loop over 32 bits
LOOP    ASL Q1      ;Shift a bit off the dividend...
        ROL Q2
        ROL Q3
        ROL Q4
        ROL R1      ;...and catch it in the remainder
        ROL R2
        ROL R3
        ROL R4
        SEC         ;Try subtracting divisor from remainder
        LDA R1
        SBC D1
        PHA         ;(save result on stack)
        LDA R2
        SBC D2
        PHA
        LDA R3
        SBC D3
        PHA
        LDA R4
        SBC D4
        BCC DISCARD ;Did subtraction succeed?
        STA R4      ;If so, result becomes new remainder...
        PLA
        STA R3
        PLA
        STA R2
        PLA
        STA R1
        INC Q1      ;...and put a 1 bit in the quotient
        BCS NEXT    ;(branch always taken)
DISCARD PLA         ;Otherwise discard the subtraction
        PLA
        PLA         ;(there's already a 0 bit in the quotient)
NEXT    DEX         ;Done all 32 bits yet?
        BNE LOOP    ;If not, go do more
        RTS         ;Else we're done

And here's the wrapper for doing signed division.  This code *does* require
that your memory locations be on page 0.

        LDA Q4      ;Save sign of dividend
        PHP
        EOR D4      ;Compute sign of quotient
        PHP
        BIT Q4      ;If dividend<0, make it positive
        BPL TRYD
        LDX #$FC
        SEC
NEGQ1   LDA #0
        SBC Q4+1,X  ;(this only works if Q1..Q4 are on page 0)
        STA Q4+1,X
        INX
        BNE NEGQ1
TRYD    BIT D4      ;If divisor<0, make it positive
        BPL DODIV
        LDX #$FC
        SEC
NEGD1   LDA #0
        SBC D4+1,X  ;(this only works if D1..D4 are on page 0)
        STA D4+1,X
        INX
        BNE NEGD1
DODIV   JSR DIV32   ;Do the (unsigned) division
        PLP         ;If quotient should be <0, make it negative
        BPL TRYR
        LDX #$FC
        SEC
NEGQ2   LDA #0
        SBC Q4+1,X  ;(this only works if Q1..Q4 are on page 0)
        STA Q4+1,X
        INX
        BNE NEGQ2
TRYR    PLP         ;Transfer sign of dividend to remainder
        BPL DONE
        LDX #$FC
        SEC
NEGR1   LDA #0
        SBC R4+1,X  ;(this only works if R1..R4 are on page 0)
        STA R4+1,X
        INX
        BNE NEGR1
DONE    RTS

This wrapper implements "toward 0" rounding of signed quotients--that is,
when a negative quotient needs to be rounded, the result closer to 0 is
chosen.  The remainder has the sign of the dividend, which guarantees that
the usual division relationship holds:

     dividend = quotient*divisor + remainder.

The opposite choice, "floored" rounding (in which the more negative result
is chosen, like Applesoft's INT function), is similar, but requires
slightly different postprocessing of the unsigned result.

               - Neil Parker
-- 
Neil Parker, nparker@{cie-2,cie}.uoregon.edu, http://cie-2.uoregon.edu/~nparker
     "Evolution is vastly overrated."  -- Ambassador Delenn, _Babylon_5_

Unsolicited commercial e-mail to my address will be discarded unread.