This page is a mirror of Tepples' nesdev forum mirror (URL TBD).

# Divide by three

I have the PPMCK code to divide by two, for selecting the octave. This is good, and I also added a #CUSTOM-TUNING command to make music other than 12-TET. But I also want to add the code to divide by three (which code is selected depends on macro), so that Bohlen-Pierce musics can also be written using PPMCK.
You could make a look up table (LUT), though that'd be 256 bytes. Effectively, you'd calculate everything out by hand and have a table that'd look like this:

.db 0,0,0,1,1,1,2,2,2 ...

I have a division by 3 routine for my game, though I just use it to get boss health milestones. May or may not be suitable for what you're doing...

Code:
DivisionBy3Routine:
LDA #0
LDX #8
ASL <temp + 6
.L1:
ROL A
CMP #3
BCC .L2
SBC #3
.L2:
ROL <temp + 6
DEX
BNE .L1
RTS

The result is stored in a variable called temp + 6. The remainder is in X. temp + 6 gets loaded with whatever number you want to divide by before calling this routine.
It is a sixteen bit number I need to divide, and some registers are already in use. But I can learn from the examples. (It is being used in PPMCK, like I said I already have divide by two working, because it is just right shift. Do you know what PPMCK is?)
Quote:
some registers are already in use

Save them when entering the function. Restore them when exiting. Problem solved!

Quote:
It is a sixteen bit number I need to divide

I think the solution should be obvious here. You take his routine and modify it to use 16-bit variables. It's not that much work
OK thanks I can try
Well I'll recommend to read this wiki article : http://wiki.nesdev.com/w/index.php/Division_by_a_constant_integer

It is possible (and easy) to divide by 3 using only the accumulator, if the result don't exceed 8-bit that is. (the example code is for 4-bit, therefore there is 4 comparaisons, but if you need more bits in the result you need to do more comparaisons). If the result is 16-bit then you'd have to complicate the example code, splitting it into low and high 8-bits.
Well I'll recommend to read this wiki article : http://wiki.nesdev.com/w/index.php/Division_by_a_constant_integer

It is possible (and easy) to divide by 3 using only the accumulator, if the result don't exceed 8-bit that is. (the example code is for 4-bit, therefore there is 4 comparaisons, but if you need more bits in the result you need to do more comparaisons). If the result is 16-bit then you'd have to complicate the example code, splitting it into low and high 8-bits.

Caveat: none of this code is tested.

An alternative is to multiply by the reciprocal.

The reciprocal of 14 is (in binary) .0001001001001...
Since 14 has non power of 2 factors the reciprocal
is a repeating decimal which can be useful.

You need enough partial products to get your desired
accuracy, that is, if you want it accurate to the nearest
integer and the number you're dividing is a single byte
(max value ~256) your smallest partial product needs to be
<1/256 so that that partial product is less than 1
because you want it accurate to the nearest 1
So in that case (one byte divided by 14 accurate to the
nearest integer) you need to multiply by .0001001001

Defer the division of the partial products so that you
retain as much accuracy as possible.

Code:
sta temp
lsr
lsr
lsr       ; A = number x .001

; don't clear the carry to get some rounding

adc temp  ; C,A now contain 1.001 x number

ror       ; ror not lsr, gotta keep C
lsr
lsr
adc temp  ; C,A now contain 1.001001 x number
ror
lsr
lsr
lsr       ; A= .0001001001 x number = number/14

Because it'a a repeating decimal you could roll
it up into a loop.
not so useful for a single byte divided by 14
but might be for 16 bits divided by 3
Also since it's a repeating decimal you can
Accumulate a partial product and save some adding.

1/3 (decimal) = .010101010101... (binary)

And in the case of 1/3 it repeats bytewise so you
can accumulate a byte's worth of partial product
and then shift by bytes.

so you might eg do a loop that accumulates four
of the partial products from the reciprocal and then
add the high byte of that in, shifted one byte,

you'd generate number x .10101010
then shift that by a byte and add it in to get
Code:
.10101010
+ .000000001010101

= .101010101010101

and if you're only doing 16 bits accuracy, you only need
to add in the high byte (shifted by one byte)

some code (like I said, untested)

Code:
; A contains the number to be divided

; enter with
; A containing the hi byte of the number to be divided by 3
; Y containing the lo byte of the number to be divided by 3

; the hi byte of the partial product is kept in A or saved
; on the stack when neccessary

; save the number in lo_temp, hi_temp

sty lo_temp
sty lo_product
sta hi_temp

ldy #\$03
clc

; each pass of the loop divides the partial product by 4
; and then adds number in lo_temp, hi_temp to that

LOOP
ror
ror lo_product
lsr
ror lo_product
pha
lda lo_product
sta lo_product
pla
dey
bne LOOP

; C,A and lo_product should now contain 1.010101 x number

ror               ; get the high bit of the partial product
ror lo_product    ; from C in to A so that A, lo_product now
; contain .1010101 x number
pha               ; save the hi byte of the partial product
adc lo_product    ; and add it back in shifted by one byte
sta lo_product
pla
adc #\$00          ; propagate the carry from the lo byte
; A, lo_product now contain
; .101010101010101 x number
lsr
ror lo_product

edit: fixed the wrong way shifts jeez what a mistake to make!

edit: too many passes through the loop
After you multiply by the reciprocal, you'll need to multiply the result by 3 to make sure that the remainder is 0, 1, or 2. Both multiplying by \$55/\$100 and multiplying by \$56/\$100 produce results that aren't exactly equal to x/3 in some cases. But luckily, multiplying by 3 to check one's work is easy (x + (x << 1)), so an exact division would look like this Python code:
Code:
def divide_by_3(dividend):
quotient = dividend * 0x55 // 0x100
product = quotient + (quotient << 1)
if dividend - product >= 3:
quotient += 1
return quotient

I did the same routine of multiply by reciprocal, multiply, and correct when dividing by 10 in a text formatting routine on the Game Boy Advance, which has hardware mul but lacks hardware div.
tepples wrote:
After you multiply by the reciprocal, you'll need to multiply the result by 3 to make sure that the remainder is 0, 1, or 2. Both multiplying by \$55/\$100 and multiplying by \$56/\$100 produce

That was my point about keeping enough accuracy in the partial product.
And maybe I confused things by using the term "partial product"
inconsistently.

Also I was a bit glib especially considering that the code does rounding
in the midst of the computations.

To put it in your terms (if I understand you) I was saying you need do
at least \$155/\$400 but you should be able to do it with single byte math
by defering the divsion as long as possible and keeping as much accuracy
in the partial products as possible (and the rounding should help )

And speaking of the remainder, if you need the remainder, maybe
using division by reciprocal multiplication wont be the best way.

edit: fixed the fraction after I goofed the conversion really good
ie \$CC/\$400 should have been \$155/\$400 Here's some code that seems to work.
You don't get a remainder.

Code:
; divide 16 bit number by 3 by multiplying by 1/3
; enter with
; A containing the hi byte of the number to be divided by 3
; Y containing the lo byte of the number to be divided by 3
; the hi byte of the partial product is kept in A or saved
; on the stack when neccessary
; the product (N/3 quotient) is returned hi byte in A,
; lo byte in Y

; save the number in lo_temp, hi_temp

sty lo_temp
sty lo_product
sta hi_temp

ldy #\$09
clc
bcc ENTER

; each pass through loop adds the number in
; lo_temp, hi_temp to the partial product and
; then divides the partial product by 4

LOOP
pha
lda lo_product
sta lo_product
pla
ENTER
ror
ror lo_product
lsr
ror lo_product
dey
bne LOOP
ldy lo_product
rts

Here's a couple that do 8 bits one looped, one unrolled.

Code:
; enter with number to be divided in A

sta temp
ldx #\$04
lsr
lsr
LOOP
ror
lsr
dex
bne LOOP
rts

Code:
; enter with number to be divided in A

sta temp
lsr
lsr