Divide by three

[zzo38]

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.

[Sivak]

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: Select all

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.

[zzo38]

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?)

[mic_]

some registers are already in use

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

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

[zzo38]

OK thanks I can try

[Bregalad]

Well I'll recommend to read this wiki article : http://wiki.nesdev.com/w/index.php/Divi ... nt_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.

[bogax]

Well I'll recommend to read this wiki article : http://wiki.nesdev.com/w/index.php/Divi ... nt_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: Select all

 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,
to get the answer.

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

Code: Select all

   .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: Select all

 ; 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
 adc lo_temp
 sta lo_product
 pla
 adc hi_temp
 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

[tepples]

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: Select all

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.

[bogax]

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

[bogax]

Here's some code that seems to work.
You don't get a remainder.

Code: Select all

 ; 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 
 adc lo_temp 
 sta lo_product 
 pla 
 adc hi_temp 
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: Select all

 ; enter with number to be divided in A
 ; answer returned in A

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

Code: Select all

 ; enter with number to be divided in A
 ; answer returned in A

 sta temp
 lsr
 lsr
 adc temp
 ror
 lsr
 adc temp
 ror
 lsr
 adc temp
 ror
 lsr
 adc temp
 ror
 lsr
 rts

[clueless]

Awesome. I don't need this right now, but I might in the future. May I kindly suggest adding this to the wiki (or ask Tepples to do it)?