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