×   Main Menu ALL The 8BS News Manuals (New menu) Links Worth a Look Tools Disc and Basic Webring Site Map 8BS Guestbook Old Guest Book Me The Barnsley Rovers   
8-Bit Software

The BBC and Master Computer Public Domain Library

Integer Division

Submitted by Steve Fewell

Routine: Integer Division
Name: Integer Division
Starting Address: &80F9
Entry criteria: Either the IWA or FWA contain the Dividend (Integer A), The BASIC Expression pointed to by BASICs second text pointer (&19, &1A) evaluates to the Divisor value (Integer B).
Exit: The routine evaluates the expression Integer A / Integer B. Addresses &39 to &3C & the Carry-flag [so that odd-numbers are handled correctly] contain half of the quotient (result) value. Addresses &3D to &40 contain the remainder.

Description:
Check the current variable type (A), and if the current value is Floating-Point, convert the Floating-Point value to an Integer (IWA).
Next, prepare the Dividend value by pushing its sign-byte (&2D) to the 6502 stack, and making the dividend positive (so that we only need to deal with positive numbers).

Next call BASICs Integer expression handler &A00F to push the current integer to the BASIC stack, read the BASIC expression from the second Text Pointer (&19, &1A), evaluate it and return a numeric result. Check the variable type (A) of the numeric result, and if the current value is Floating-Point, convert the Floating-Point value to an Integer (IWA).

Retrieve the sign-byte for the Dividend (from the 6502 stack), Store it in &38 - This is the sign of the Remainder. EOR the Dividend's sign-byte with the sign-byte of the Divisor to obtain the sign of the result, store this in &37.

Next, as we already have determined the signs of our remainder and result, prepare the Divisor value by making it positive (so that we only need to deal with division of positive numbers).

Retrieve the Dividend from the BASIC stack to locations &39, &3A, &3B and &3C and clear locations &3D, &3E, &3F and &40 (the remainder). So that the IWA contains the Divisor, &39-&3C contain the Dividend/result and &3D-&40 contain the remainder.

If all bytes of the Divisor are zero (indicating a zero value), then give a Division by zero error and exit.

Set Y to 32 (this is the number of Dividend digits that we need to process, assume a 32-bit Integer). 

&812D-&8139 keep decrementing Y and shifting the Dividend value left (towards the Most significant byte &3C), until we find a bit that is not zero. Now we know exactly how many bits in the Dividend we need to process (as we have removed the leading zeros).

This is the main loop, which performs binary long division on the two numbers:

*1) Shift the Result left 1 place. &813A-8141. (This is the same as the shift in step *2), but is specified here for clarity, as a different value is affected).

*2) Shift the Dividend left 1 place, loosing the top-most bit and shift the bit that was just lost from the Dividend into the lower-end of the Remainder (moving the remainders other bits left a place). &813A-&8149.

*3) Subtract the Divisor from the Remainder (least significant byte first), storing the 32-bit result in these 4 locations: 6502 stack (2 bytes), in X (1 byte) and in A (1 byte). &814A-&815D.

*4) If a borrow did not occur (the Divisor was successfully subtracted), then [&815E-&816B] store the result as the new remainder (&3D to &40). The next time step *2) is executed, shift 1 into the upper-end [right] of the Dividend, this will form the next bit of the result, when the Dividends bits are shifted left. BASIC cleverly uses the same 4-bytes to store the result, and the bits which are still left to be processed of the Dividend. Note: as the values are Binary, only 1 subtraction is required.

*5) Decrement Y

Keep looping until Y has reached zero. This indicates that no digits of the Dividend remain to be processed, and that locations &39-&3C contain the result. Note: The result has not been updated with the number of times the Divisor could be subtracted from the Remainder (in step *4)), so it is up to the calling routine to shift the carry-flag value into the bottom-end of the Result, shifting its other bits left a place. The calling routine also needs to convert the result (using &37) and/or Remainder (using &38) to the correct sign.

To simplify what this division routine is dong, here is the same routine using Base-10 Integer numbers:

ResultAdd = 0
Result = 0
Remainder = 0
Base = 10
Y = Len(Dividend)
Repeat
    *1) Result = (Result * Base) + ResultAdd
    *2) Remainder = (Remainder * Base) + Next-Digit-of-Dividend
    *3a) Temp = Remainder
    *3b) ResultAdd = 0
    *3c) For Counter = 1 to Base-1
    *3d)    Temp = Temp - Divisor
    *3e)     if Temp > 0 then Remainder = Temp : ResultAdd = ResultAdd + 1
    *3f) Next Counter
    *4) Rem Not required
    *5) Y = Y - 1
Until Y = 0

E.g. 324 / 5 would produce the following workings:
Y = 3
Divisor = 5
Dividend = 324
*1) Result = (0 * 10) + 0  = 0
*2) Remainder = (0 * 10) + 3 = 3
*4) Remainder = 3; ResultAdd = 0
*5) Y = 2
*1) Result = (0 * 10) + 0  = 0
*2) Remainder = (3 * 10) + 2 = 32
*4) Remainder = 2; ResultAdd = 6
*5) Y = 1
*1) Result = (0 * 10) + 6  = 6
*2) Remainder = (2 * 10) + 4 = 24
*4) Remainder = 4; ResultAdd = 4
*5) Y = 0

Now to get the correct Result we need to do step *1) again :

*1) Result = (6 * 10) + 4 = 64

So, the result of 324/5 is 64, and the remainder is 4.

Disassembly for the Integer Division routine

80F9   032 190 150 20 BE 96 JSR &96BE   Check if Integer and Convert if Float
80FC - 165 045 A5 2D LDA &2D
80FE H 072 48 PHA
80FF   032 190 172 20 BE AC JSR &ACBE   Integer Positive
8102   032 015 160 20 0F A0 JSR &A00F   Push Integer to Stack and Get result of expression
8105 ' 134 039 86 27 STX &27
8107   032 190 150 20 BE 96 JSR &96BE   Check if Integer and Convert if Float
810A h 104 68 PLA
810B 8 133 056 85 38 STA &38
810D E- 069 045 45 2D EOR &2D
810F 7 133 055 85 37 STA &37
8111   032 190 172 20 BE AC JSR &ACBE   Integer Positive
8114 9 162 057 A2 39 LDX#&39
8116   032 008 189 20 08 BD JSR &BD08   Pop Integer from BASIC Stack Zero-page
8119 d= 100 061 64 3D STZ &3D
811B d> 100 062 64 3E STZ &3E
811D d? 100 063 64 3F STZ &3F
811F d@ 100 064 64 40 STZ &40
8121 - 165 045 A5 2D LDA &2D
8123 * 005 042 05 2A ORA &2A
8125 + 005 043 05 2B ORA &2B
8127 , 005 044 05 2C ORA &2C
8129 G 240 071 F0 47 BEQ 71 --> &8172   Division by zero error
812B   160 032 A0 20 LDY#&20
812D   136 88 DEY
812E A 240 065 F0 41 BEQ 65 --> &8171
8130 9 006 057 06 39 ASL &39
8132 &: 038 058 26 3A ROL &3A
8134 &; 038 059 26 3B ROL &3B
8136 &< 038 060 26 3C ROL &3C
8138   016 243 10 F3 BPL -13 --> &812D
813A &9 038 057 26 39 ROL &39
813C &: 038 058 26 3A ROL &3A
813E &; 038 059 26 3B ROL &3B
8140 &< 038 060 26 3C ROL &3C
8142 &= 038 061 26 3D ROL &3D
8144 &> 038 062 26 3E ROL &3E
8146 &? 038 063 26 3F ROL &3F
8148 &@ 038 064 26 40 ROL &40
814A 8 056 38 SEC
814B = 165 061 A5 3D LDA &3D
814D * 229 042 E5 2A SBC &2A
814F H 072 48 PHA
8150 > 165 062 A5 3E LDA &3E
8152 + 229 043 E5 2B SBC &2B
8154 H 072 48 PHA
8155 ? 165 063 A5 3F LDA &3F
8157 , 229 044 E5 2C SBC &2C
8159   170 AA TAX
815A @ 165 064 A5 40 LDA &40
815C - 229 045 E5 2D SBC &2D
815E   144 012 90 0C BCC 12 --> &816C
8160 @ 133 064 85 40 STA &40
8162 ? 134 063 86 3F STX &3F
8164 h 104 68 PLA
8165 > 133 062 85 3E STA &3E
8167 h 104 68 PLA
8168 = 133 061 85 3D STA &3D
816A   176 002 B0 02 BCS 2 --> &816E
816C h 104 68 PLA
816D h 104 68 PLA
816E   136 88 DEY
816F   208 201 D0 C9 BNE -55 --> &813A
8171 ` 096 60 RTS

 


 Back to 8BS
Or