6502.org

Posted: **Sun Feb 25, 2024 5:37 pm**

BillG wrote:

BigDumbDinosaur wrote:

Proxy wrote:

honestly with how small the value range is (10 bit input, 8 bit output), i'd just use a table.

I second that. These days, memory is less valuable than time, so I’d go with the table approach for such a specific requirement.

Depending upon the application, a 1 KB table may be huge.

This.

Size and speed are subjective terms, and there will be a wide spectrum of possible solutions, many of which may not be suitable for the task at hand. Here's another ... 22 bytes + rts, 400ish clocks, lightly tested, and the remainder is a free bonus.

Code: Select all

; - - - - - - - - - - - - - - - - - - - - - - - - - - -
; 16-bit unsigned division by 3 routine
;   T /= 3, A = remainder, Y = low byte of quotient
;
div3:
        lda  #0         ; remainder
        ldy  #16        ; loop counter
div3b:
        asl  T          ; T is gradually replaced
        rol  T+1        ;   with the quotient
        rol             ; A is gradually replaced
                        ;   with the remainder
        cmp  #3         ; partial remainder >= 3?
        bcc  div3c
        sbc  #3         ;   yes: update partial
                        ;     remainder, set low bit
        inc  T          ;     in partial quotient
div3c:
        dey 
        bne  div3b      ; loop 16 times
        ldy  T          ; quotient:l
        rts

Posted: **Sun Feb 25, 2024 6:28 pm**

BigEd wrote:

Welcome, WynnSmith!

As your input is only barely over a byte in size, I wonder if we could start by comparing and subtracting 384 to get the top bit of the result, and then use the minimal bytesize version to get the rest.

(It's clever to use multiplication for division in the case that multiplication is fast but division is not, but I'm not sure it's always optimal when multiplication is also not fast. In general, a non-restoring division, perhaps with pre-calculated shifted divisors, might be a win.) ...

If there's somewhere between 512 bytes and 1KB available but not more, so 1KB in table is not an option, you could do a trial subtract of $180, and use the result to select from one of two 256 byte tables, one for $100-$17F dividends, and another for the $00-$FF dividends. I think it'd be about 25 clocks if it's an 8bit dividend (because if DIVHI is 0, you can skip the trial subtract), around 45 clocks if you do the trial subtract.

Edit: OK, because 3x$80 is $180, you don't need to do a trial subtract, you can just examine whether bit 1 of of DIVHI is set, or else both bit0 of DIVHI and bit7 of DIVLO. So given two 256 byte tables, RES8BIT if the tabled value is for a dividend of $00-$FF, and RES9BIT if the table value is for a dividend of $100-$17F, I think it is something along the following lines. 43 bytes, and if I am thinking correctly, the RES9BIT table only needs 128 bytes, so it might be possible to fit this in with under 512bytes total ... less if one or more useful routines can be fit in between the divide by three routine and the start of the RES9BIT table at START+$80.

Code: Select all

; Divide by 3, 10bit number guaranteed to have 8bit or lower result
; DIVLO - low 8bits of 10 bit dividend
; DIVHI -- high two bits of 10 bit dividend, bits2-7 clear
; RESULT -- stores result
; Put where you wish, I have a 12 byte "U" area at $34-$3F.
	RESULT = $3D
	DIVLO = $3E
	DIVHI = $3F
	DIVBY3 = $0400 ; 
	RES9BIT = DIVBY3 + $80
	RES8BIT = DIVBY3 + $100
* = DIVBY3
	LDY DIVHI
	LDA #0
	BNE +
	LDX DIVLO
-	ORA RES8BIT,X
	STA RESULT
	RTS
+	CPY #2
	BPL SUBTRACT_180
	LDX DIVLO
	BMI SUBTRACT_180
--	ORA RES9BIT,X
	STA RESULT
	RTS
SUBTRACT_180:
	LDA DIVLO
	SEC
	SBC $80
	TAX
	LDA #$80 ; bit7 is set if we are down here
	BCS + ; no borrow
	DEY ; borrow
+	DEY ; subtract $100
	BEQ - ; If Y=0, use RES8BIT
	BRA -- ; otherwise use RES9BIT

* = RES9BIT
	!byte $55,$55,$56,$56,$56,$57,$57,$57,$58,$58,$58,$59,$59,$59,$5A,$5A
	!byte $5A,$5B,$5B,$5B,$5C,$5C,$5C,$5D,$5D,$5D,$5E,$5E,$5E,$5F,$5F,$5F
	!byte $60,$60,$60,$61,$61,$61,$62,$62,$62,$63,$63,$63,$64,$64,$64,$65
	!byte $65,$65,$66,$66,$66,$67,$67,$67,$68,$68,$68,$69,$69,$69,$6A,$6A
	!byte $6A,$6B,$6B,$6B,$6C,$6C,$6C,$6D,$6D,$6D,$6E,$6E,$6E,$6F,$6F,$6F
	!byte $70,$70,$70,$71,$71,$71,$72,$72,$72,$73,$73,$73,$74,$74,$74,$75
	!byte $75,$75,$76,$76,$76,$77,$77,$77,$78,$78,$78,$79,$79,$79,$7A,$7A
	!byte $7A,$7B,$7B,$7B,$7C,$7C,$7C,$7D,$7D,$7D,$7E,$7E,$7E,$7F,$7F,$7F

* = RES8BIT
	!byte 0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5 ; ...
	!byte ; ...

Posted: **Mon Feb 26, 2024 9:14 pm**

I only worked out one random example by hand. Kind of a distributed division:

765 = 255 + 255 + 255

255 = 85 + 85 + 85

suppose x = 542 = %10 0001 1110
then x/3 = 180 (integer part only)

where x(hi) = %10 and x(lo) = 0001 1110
then x(hi) = 2 and x(lo) = 30
then x(lo)/3 = 10
then x(hi) means add 2 * 85
and the final answer is 10 + 170 = 180

so first cut:

; divide lo byte by 3

sta temp
lsr
adc #21
lsr
adc temp
ror
lsr
adc temp
ror
lsr
adc temp
ror
lsr

; adjust by hi byte

ldx dividend+1
clc
adc factor,x

factor:
.byte 0*85, 1*85, 2*85

Because I'm exceptionally lazy I stole some code from someone who worked it out earlier. Untested in full:

https://codebase64.org/doku.php?id=base ... bit_result

It's explained here (you'll have to scroll down a bit to find it):

https://retrocomputing.stackexchange.co ... y-instruct

Posted: **Tue Feb 27, 2024 12:12 am**

wow. Hey! What a great forum. Thank you all for your responses. I'm still working to digest some of it, but wanted to get back quickly and say thanks.

I should've mentioned my dividends are always multiples of 3, so there's no need to accomodate remainders or calculate/lookup non-multiples. To understand the algorithm, and those similar, get out a piece of paper and do the long-hand math we learned in grade school: First, 1/3 (%11 into 1), then %10 1111 1101 (765) x %0.01010101, and %11 x %0.01010101. You'll find this range barely keeps us within the boundaries where rounding-up in the last step works. If I had needed to calculate dividends larger than 765, more shifts, adds, and bits would've been needed.

This code is intended to become part of a larger library where the special case of division by 5 is also needed. The library would then be included with other code that efficiently encodes and decodes blocks of data. Therefore, code size and table size does matter.

What you've shown me is that this encoding and decoding challenge is possible on the 6502, which means higher-end features can be made available to lower-cost products. It was fun to touch 6502 code again.... such memories.

Posted: **Tue Feb 27, 2024 12:18 am**

I was wondering when you were going to come back.

I love how a question on this forum sometimes turns into an intense programming contest...

OK, it cannot be huge. Does it need to be fast?

WynnSmith wrote:

I should've mentioned my dividends are always multiples of 3

Oh, by the way, your code says 0 / 3 = 1

Posted: **Tue Feb 27, 2024 12:26 am**

Bill, Yes. We could call the general math library, but speed is the reason to investigate a special case algorithm.

P.S. good catch. Need a BEQ.

Posted: **Tue Feb 27, 2024 12:29 am**

Then I suggest that you look for ideas at the link provided by teamtempest in the post just above mine.

Posted: **Tue Feb 27, 2024 12:35 am**

BB8 wrote:

optimized a little:

I had a similar insight.

Subtracting by 255 is the same as subtracting 256 and adding 1.

The difference is that I chose not to add a loop to handle the upper byte. It is faster in some cases and slower in others.

Posted: **Tue Feb 27, 2024 12:50 am**

teamtempest wrote:

I only worked out one random example by hand. Kind of a distributed division:

<snip>

; adjust by hi byte

ldx dividend+1
clc
adc factor,x

factor:
.byte 0*85, 1*85, 2*85

$1FF aka 511 is a special case you will need to handle...

Posted: **Tue Feb 27, 2024 1:10 am**

This is my latest test program containing all of the code snippets. Each one is orged at a page boundary to make sizes obvious.

Code: Select all

                          00001          lib    FAKEFLEX.LIB
.                         00002 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.                         00003 ;
.                         00004 ; Fake FLEX environment for debugging in emulator
.                         00005 ;
.0000                     00481          .list
                          00482
 0002                     00483          org    ZeroPage
                          00484
                          00485 ;-----------------------------------------------------------------
                          00486 ; The dividend is stored in 00 and 01 before calling this routine.
                          00487 ; The resulting quotient will be accumulated in 03.
                          00488 ; Largest supported dividend is 765.  (add error checking?)
                          00489
 0002                     00490 DIVLO    rmb    1         ; Zero page locations of 10 bit dividend
 0003                     00491 DIVHI    rmb    1
 0004                     00492 QUOLO    rmb    1         ; low bits of accumulated sum
 0005                     00493 QUOHI    rmb    1         ; high bits of accumulated sum (Quotient)
                          00494
 0006                     00495 _DIVLO   rmb    1         ; Zero page locations of 10 bit dividend
 0007                     00496 _DIVHI   rmb    1
 0008                     00497 _QUOLO   rmb    1         ; low bits of accumulated sum
 0009                     00498 _QUOHI   rmb    1         ; high bits of accumulated sum (Quotient)
                          00499
 000A                     00500 __DIVLO  rmb    1         ; Zero page locations of 10 bit dividend
 000B                     00501 __DIVHI  rmb    1
 000C                     00502 __QUOLO  rmb    1         ; low bits of accumulated sum
 000D                     00503 __QUOHI  rmb    1         ; high bits of accumulated sum (Quotient)
                          00504
 000E                     00505 ___DivLo rmb    1         ; Zero page locations of 10 bit dividend
 000F                     00506 ___DivHi rmb    1
 0010                     00507 ___QuoLo rmb    1         ; low bits of accumulated sum
 0011                     00508 ___QuoHi rmb    1         ; high bits of accumulated sum (Quotient)
                          00509
 0012                     00510 lo_temp  rmb    1
 0013                     00511 hi_temp  rmb    1
 0014                     00512 lo_product rmb  1
 0015                     00513 Quotient rmb    1
                          00514
 0016                     00515 _res     rmb    1
 0017                     00516 _nl      rmb    1
 0018                     00517 _nh      rmb    1
                          00518
 0019                     00519 __res    rmb    1
 001A                     00520 __nl     rmb    1
 001B                     00521 __nh     rmb    1
                          00522
 001C                     00523 res      rmb    1
 001D                     00524 nl       rmb    1
 001E                     00525 nh       rmb    1
                          00526
 001F                     00527 T        rmb    2
                          00528
 0021                     00529 Ptr      rmb    2
 0023                     00530 Number   rmb    2
                          00531
 2000                     00532          org    FreeRAM
                          00533
 2000                     00534 DIVIDE_BY_THREE:
                          00535
                          00536 ; First, effectively multiply by 0.0000 0001
 2000 A5 02           [3] 00537          lda    DIVLO     ; low bits of dividend
 2002 85 04           [3] 00538          sta    QUOLO
 2004 A5 03           [3] 00539          lda    DIVHI     ; high bits of dividend
                          00540
                          00541 ; shift 6 times, add 3 times
 2006 A2 03           [2] 00542          ldx    #3        ; so, we'll loop 3 times
                          00543
                          00544 ; Then, effectively multiply by 0.0000 0101
                          00545 ; then by 0.0001 0101
                          00546 ; then by 0.0101 0101, which is 1/3
                          00547
 2008                     00548 LOOP:
                          00549
 2008 85 05           [3] 00550          sta    QUOHI
                          00551
 200A 06 04           [5] 00552          asl    QUOLO     ; first, shift left twice
 200C 26 05           [5] 00553          rol    QUOHI
 200E 06 04           [5] 00554          asl    QUOLO
 2010 26 05           [5] 00555          rol    QUOHI
 2012 18              [2] 00556          clc              ; Then, add the dividend
 2013 A5 04           [3] 00557          lda    QUOLO
 2015 65 02           [3] 00558          adc    DIVLO
 2017 85 04           [3] 00559          sta    QUOLO
 2019 A5 05           [3] 00560          lda    QUOHI
 201B 65 03           [3] 00561          adc    DIVHI
                          00562
 201D CA              [2] 00563          dex
 201E D0 E8 (2008)  [2/3] 00564          bne    LOOP
                          00565
 2020                     00566 FINISH:
                          00567
 2020 38              [2] 00568          sec
 2021 69 00           [2] 00569          adc    #0        ;  + 1 (round up)
 2023 85 05           [3] 00570          sta    QUOHI     ; The resulting Quotient is in the Accumulator
                          00571
 2025 60              [6] 00572          rts
                          00573
 2100                     00574          org    FreeRAM+$100
                          00575
                          00576 ; divide 16 bit number by 3 by multiplying by 1/3
                          00577 ; enter with
                          00578 ; A containing the hi byte of the number to be divided by 3
                          00579 ; Y containing the lo byte of the number to be divided by 3
                          00580 ; the hi byte of the partial product is kept in A or saved
                          00581 ; on the stack when neccessary
                          00582 ; the product (N/3 quotient) is returned hi byte in A,
                          00583 ; lo byte in Y
                          00584
 2100                     00585 div3_ay:
                          00586
                          00587  ; save the number in lo_temp, hi_temp
                          00588
 2100 84 12           [3] 00589          sty    lo_temp
 2102 84 14           [3] 00590          sty    lo_product
 2104 85 13           [3] 00591          sta    hi_temp
                          00592
 2106 A0 09           [2] 00593          ldy    #$09
 2108 18              [2] 00594          clc
 2109 90 0A (2115)  [2/3] 00595          bcc    ENTER
                          00596
                          00597  ; each pass through loop adds the number in
                          00598  ; lo_temp, hi_temp to the partial product and
                          00599  ; then divides the partial product by 4
                          00600
 210B                     00601 _LOOP:
 210B 48              [3] 00602          pha
 210C A5 14           [3] 00603          lda    lo_product
 210E 65 12           [3] 00604          adc    lo_temp
 2110 85 14           [3] 00605          sta    lo_product
 2112 68              [4] 00606          pla
 2113 65 13           [3] 00607          adc    hi_temp
 2115                     00608 ENTER:
 2115 6A              [2] 00609          ror    A
 2116 66 14           [5] 00610          ror    lo_product
 2118 4A              [2] 00611          lsr    A
 2119 66 14           [5] 00612          ror    lo_product
 211B 88              [2] 00613          dey
 211C D0 ED (210B)  [2/3] 00614          bne    _LOOP
 211E A4 14           [3] 00615          ldy    lo_product
 2120 60              [6] 00616          rts
                          00617
 2200                     00618          org    FreeRAM+$200
                          00619
                          00620 ;
                          00621 ; Observation: 765/3 fits within one byte!
                          00622 ;
                          00623 ;
                          00624 ; 1/3 = 1/4 + 1/12
                          00625 ;
                          00626 ; Look at the problem this way:
                          00627 ;
                          00628 ; 1 = 1/4 + 1/4 + 1/4 + 1/12 + 1/12 + 1/12
                          00629 ;
                          00630 ; Step 1:
                          00631 ;
                          00632 ;  Divide by 4 using two right shifts.  Store quotient.
                          00633 ;
                          00634 ; Step 2:
                          00635 ;
                          00636 ;  Add quotient to the remainder.  Divide this by 4.
                          00637 ;
                          00638 ; Step 3:
                          00639 ;
                          00640 ;  Add quotient to sum of partial quotients
                          00641 ;
                          00642 ; Step 4:
                          00643 ;
                          00644 ;  Repeat steps 2 and 3, summing quotients, until partial quotient is 0 and
                          00645 ;    remainder < 3
                          00646 ;
                          00647 ; Step 5:
                          00648 ;
                          00649 ;  If the remainder is 3, add 1 to the quotient
                          00650 ;
 2200                     00651 Mine:
 2200 A9 00           [2] 00652          lda    #0        ; Initially, result is zero
 2202 85 09           [3] 00653          sta    _QUOHI
                          00654
 2204 A5 06           [3] 00655          lda    _DIVLO    ; Get low byte of dividend
 2206 A8              [2] 00656          tay              ; Save to calculate remainder
                          00657
 2207 46 07           [5] 00658          lsr    _DIVHI    ; Divide by 4
 2209 6A              [2] 00659          ror    A
 220A 46 07           [5] 00660          lsr    _DIVHI    ; This uses up the upper byte
 220C 6A              [2] 00661          ror    A
                          00662
 220D 4C 2213         [3] 00663          jmp    EnterLoop
                          00664
 2210                     00665 MyLoop:
 2210 A8              [2] 00666          tay              ; Save to calculate remainder
                          00667
 2211 4A              [2] 00668          lsr    A         ; Divide by 4
 2212 4A              [2] 00669          lsr    A
                          00670
 2213                     00671 EnterLoop:
 2213 85 06           [3] 00672          sta    _DIVLO    ; Store partial quotient
 2215 F0 0C (2223)  [2/3] 00673          beq    ZeroDiv   ; Dividend has become zero
                          00674
 2217 18              [2] 00675          clc              ; Add to sum of partial quotients
 2218 65 09           [3] 00676          adc    _QUOHI
 221A 85 09           [3] 00677          sta    _QUOHI
                          00678
 221C 98              [2] 00679          tya              ; Add partial quotient to remainder
 221D 29 03           [2] 00680          and    #3        ; Carry still clear from above adc
 221F 65 06           [3] 00681          adc    _DIVLO    ; This is the new dividend
                          00682
 2221 D0 ED (2210)  [2/3] 00683          bne    MyLoop    ; Always branches
                          00684
 2223                     00685 ZeroDiv:
 2223 C0 03           [2] 00686          cpy    #3
 2225 90 02 (2229)  [2/3] 00687          blo    ImDone
                          00688
 2227 E6 09           [5] 00689          inc    _QUOHI    ; Add one third of three remaining
                          00690
 2229                     00691 ImDone:
 2229 60              [6] 00692          rts
                          00693
 2300                     00694          org    FreeRAM+$300
                          00695
 2300                     00696 BB8:
 2300 A9 00           [2] 00697          lda    #0
 2302 85 16           [3] 00698          sta    _res      ; result =0
 2304 A5 18           [3] 00699 _hv      lda    _nh       ; loads high byte
 2306 F0 14 (231C)  [2/3] 00700          beq    _lv       ; if zero then goes to low byte value
                          00701
 2308 18              [2] 00702          clc              ; will subtract 255
 2309 A9 55           [2] 00703          lda    #85       ; adds 85 to result
 230B 65 16           [3] 00704          adc    _res
 230D 85 16           [3] 00705          sta    _res
                          00706
 230F 38              [2] 00707          sec              ; subtracts from low byte
 2310 A5 17           [3] 00708          lda    _nl
 2312 E9 FF           [2] 00709          sbc    #255
 2314 85 17           [3] 00710          sta    _nl
 2316 B0 EC (2304)  [2/3] 00711          bcs    _hv       ; if no carry goes to next iteration
 2318 C6 18           [5] 00712          dec    _nh       ; adjusts high byte
 231A 90 E8 (2304)  [2/3] 00713 _jo      bcc    _hv
                          00714
                          00715 ;  **** value is <256 (only low byte)
 231C                     00716 _lv
 231C A5 17           [3] 00717          lda    _nl
 231E 4A              [2] 00718          lsr    A
 231F 4A              [2] 00719          lsr    A
 2320 65 17           [3] 00720          adc    _nl
 2322 6A              [2] 00721          ror    A
 2323 4A              [2] 00722          lsr    A
 2324 65 17           [3] 00723          adc    _nl
 2326 6A              [2] 00724          ror    A
 2327 4A              [2] 00725          lsr    A
 2328 65 17           [3] 00726          adc    _nl
 232A 6A              [2] 00727          ror    A
 232B 4A              [2] 00728          lsr    A
 232C 65 17           [3] 00729          adc    _nl
 232E 6A              [2] 00730          ror    A
 232F 4A              [2] 00731          lsr    A
 2330 18              [2] 00732          clc
 2331 65 16           [3] 00733          adc    _res
 2333 85 16           [3] 00734          sta    _res
 2335 60              [6] 00735          rts
                          00736
 2400                     00737          org    FreeRAM+$400
                          00738
 2400                     00739 OptimizedBB8:
 2400 A5 1B           [3] 00740          lda    __nh      ; loads high byte
 2402 F0 0D (2411)  [2/3] 00741          beq    __lv      ; if zero then goes to low byte value
                          00742
 2404 A9 00           [2] 00743          lda    #0
 2406 18              [2] 00744          clc
                          00745
 2407                     00746 __hv2:
 2407 69 55           [2] 00747          adc    #85       ; adds 85 to result
 2409 E6 1A           [5] 00748          inc    __nl      ; subtracts 255 from low byte
 240B F0 FA (2407)  [2/3] 00749          beq    __hv2
 240D C6 1B           [5] 00750          dec    __nh      ; adjusts high byte
 240F D0 F6 (2407)  [2/3] 00751          bne    __hv2
                          00752
                          00753 ;  **** value is <256 (only low byte)
 2411 85 19           [3] 00754 __lv     sta    __res
 2413 A5 1A           [3] 00755          lda    __nl
 2415 4A              [2] 00756          lsr    A
 2416 4A              [2] 00757          lsr    A
 2417 65 1A           [3] 00758          adc    __nl
 2419 6A              [2] 00759          ror    A
 241A 4A              [2] 00760          lsr    A
 241B 65 1A           [3] 00761          adc    __nl
 241D 6A              [2] 00762          ror    A
 241E 4A              [2] 00763          lsr    A
 241F 65 1A           [3] 00764          adc    __nl
 2421 6A              [2] 00765          ror    A
 2422 4A              [2] 00766          lsr    A
 2423 65 1A           [3] 00767          adc    __nl
 2425 6A              [2] 00768          ror    A
 2426 4A              [2] 00769          lsr    A
 2427 18              [2] 00770          clc
 2428 65 19           [3] 00771          adc    __res
 242A 85 19           [3] 00772          sta    __res
 242C 60              [6] 00773          rts
                          00774
 2500                     00775          org    FreeRAM+$500
                          00776
                          00777 ;
                          00778 ; Subtracting 255 is the same as subtracting 256 and adding 1...
                          00779 ;
 2500                     00780 ModifiedBB8:
 2500 A2 00           [2] 00781          ldx    #0        ; Start with result = 0
                          00782
 2502 A5 1E           [3] 00783          lda    nh        ; loads high byte
 2504 F0 15 (251B)  [2/3] 00784          beq    lv        ; if zero then goes to low byte value
                          00785
 2506 A2 55           [2] 00786          ldx    #85       ; add 85 to result
 2508 C9 01           [2] 00787          cmp    #1        ; Upper byte is 1?
 250A F0 02 (250E)  [2/3] 00788          beq    2f        ; Yes, but I wish 6502 carry is like the others...
                          00789
 250C A2 AA           [2] 00790          ldx    #2*85     ; It is 2, make that add 2*85
                          00791
 250E                     00792 2:
 250E 18              [2] 00793          clc              ; Add high byte to low
 250F 65 1D           [3] 00794          adc    nl
 2511 85 1D           [3] 00795          sta    nl
                          00796
 2513 90 06 (251B)  [2/3] 00797          bcc    lv
                          00798
 2515 8A              [2] 00799          txa              ; New low byte overflowed
 2516 69 54           [2] 00800          adc    #85-1     ; Add another 85 to result (carry set!)
 2518 AA              [2] 00801          tax              ; This is a special case for only $1FF
 2519 E6 1D           [5] 00802          inc    nl
                          00803
                          00804 ;  **** value is <256 (only low byte)
 251B                     00805 lv:
 251B 86 1C           [3] 00806          stx    res       ; Store partial result
 251D A5 1D           [3] 00807          lda    nl
 251F 4A              [2] 00808          lsr    A
 2520 4A              [2] 00809          lsr    A
 2521 65 1D           [3] 00810          adc    nl
 2523 6A              [2] 00811          ror    A
 2524 4A              [2] 00812          lsr    A
 2525 65 1D           [3] 00813          adc    nl
 2527 6A              [2] 00814          ror    A
 2528 4A              [2] 00815          lsr    A
 2529 65 1D           [3] 00816          adc    nl
 252B 6A              [2] 00817          ror    A
 252C 4A              [2] 00818          lsr    A
 252D 65 1D           [3] 00819          adc    nl
 252F 6A              [2] 00820          ror    A
 2530 4A              [2] 00821          lsr    A
 2531 18              [2] 00822          clc
 2532 65 1C           [3] 00823          adc    res
 2534 85 1C           [3] 00824          sta    res
 2536 60              [6] 00825          rts
                          00826
 2600                     00827          org    FreeRAM+$600
                          00828
 2600                     00829 MineTabled:
 2600 A9 00           [2] 00830          lda    #0        ; Initially, result is zero
 2602 85 0D           [3] 00831          sta    __QUOHI
                          00832
 2604 A5 0A           [3] 00833          lda    __DIVLO   ; Get low byte of dividend
 2606 A8              [2] 00834          tay              ; Save to calculate remainder
                          00835
 2607 46 0B           [5] 00836          lsr    __DIVHI   ; Divide by 4
 2609 6A              [2] 00837          ror    A
 260A 46 0B           [5] 00838          lsr    __DIVHI   ; This uses up the upper byte
 260C 6A              [2] 00839          ror    A
                          00840
 260D D0 05 (2614)  [2/3] 00841          bne    _EnterLoop
 260F F0 1D (262E)  [2/3] 00842          beq    _ZeroDiv
                          00843
 2611                     00844 _MyLoop:
 2611 A8              [2] 00845          tay              ; Save to calculate remainder
                          00846
 2612 4A              [2] 00847          lsr    A         ; Divide by 4
 2613 4A              [2] 00848          lsr    A
                          00849
 2614                     00850 _EnterLoop:
 2614 85 0A           [3] 00851          sta    __DIVLO   ; Store partial quotient
                          00852
 2616 18              [2] 00853          clc              ; Add to sum of partial quotients
 2617 65 0D           [3] 00854          adc    __QUOHI
 2619 85 0D           [3] 00855          sta    __QUOHI
                          00856
 261B 98              [2] 00857          tya              ; Add partial quotient to remainder
 261C 29 03           [2] 00858          and    #3        ; Carry still clear from above adc
 261E 65 0A           [3] 00859          adc    __DIVLO   ; This is the new dividend
                          00860
 2620 C9 14           [2] 00861          cmp    #16+3+1   ; Too big to use lookup table?
 2622 B0 ED (2611)  [2/3] 00862          bhs    _MyLoop   ; Make another trip around
                          00863
 2624 AA              [2] 00864          tax
 2625 A5 0D           [3] 00865          lda    __QUOHI
 2627 18              [2] 00866          clc
 2628 7D 2635       [4/5] 00867          adc    MyTable,X
 262B 85 0D           [3] 00868          sta    __QUOHI
                          00869
 262D 60              [6] 00870          rts
                          00871
 262E                     00872 _ZeroDiv:
 262E C0 03           [2] 00873          cpy    #3
 2630 90 02 (2634)  [2/3] 00874          blo    _ImDone
                          00875
 2632 E6 0D           [5] 00876          inc    __QUOHI   ; Add one third of three remaining
                          00877
 2634                     00878 _ImDone:
 2634 60              [6] 00879          rts
                          00880
 2635 00 00 00 01 01 01   00881 MyTable  fcb    0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6 ; 4 bits plus 3 remainder
 263B 02 02 02 03 03 03
 2641 04 04 04 05 05 05
 2647 06 06
                          00882
 2700                     00883          org    FreeRAM+$700
                          00884
                          00885 ; - - - - - - - - - - - - - - - - - - - - - - - - - - -
                          00886 ; 16-bit unsigned division by 3 routine
                          00887 ;   T /= 3, A = remainder, Y = low byte of quotient
                          00888 ;
 2700                     00889 div3:
 2700 A9 00           [2] 00890          lda    #0          ; remainder
 2702 A0 10           [2] 00891          ldy    #16         ; loop counter
 2704                     00892 div3b:
 2704 06 1F           [5] 00893          asl    T           ; T is gradually replaced
 2706 26 20           [5] 00894          rol    T+1         ;   with the quotient
 2708 2A              [2] 00895          rol    A           ; A is gradually replaced
                          00896                         ;   with the remainder
 2709 C9 03           [2] 00897          cmp    #3          ; partial remainder >= 3?
 270B 90 04 (2711)  [2/3] 00898          bcc    div3c
 270D E9 03           [2] 00899          sbc    #3          ;   yes: update partial
                          00900                         ;     remainder, set low bit
 270F E6 1F           [5] 00901          inc    T           ;     in partial quotient
 2711                     00902 div3c:
 2711 88              [2] 00903          dey
 2712 D0 F0 (2704)  [2/3] 00904          bne    div3b     ; loop 16 times
 2714 A4 1F           [3] 00905          ldy    T           ; quotient:l
 2716 60              [6] 00906          rts
                          00907
 2800                     00908          org    FreeRAM+$800
                          00909
                          00910 ;
                          00911 ; Divide number 0..765 by 3
                          00912 ;
                          00913 ; Use fast 8-bit divide by 3 for final byte remainder
                          00914 ;
                          00915 ; Subtracting 255 is the same as subtracting 256 and adding 1...
                          00916 ;
 2800                     00917 ModifiedBB8_plus_teamtempest:
 2800 A2 00           [2] 00918          ldx    #0        ; Start with result = 0
                          00919
 2802 A5 0F           [3] 00920          lda    ___DivHi  ; Load high byte
 2804 F0 15 (281B)  [2/3] 00921          beq    EightBit  ; If zero then do 8-bit division
                          00922
 2806 A2 55           [2] 00923          ldx    #85       ; Add 85 to result
 2808 C9 01           [2] 00924          cmp    #1        ; Upper byte is 1?
 280A F0 02 (280E)  [2/3] 00925          beq    2f        ; Yes
                          00926
 280C A2 AA           [2] 00927          ldx    #2*85     ; It is 2, make that add 2*85
                          00928
 280E                     00929 2:
 280E 18              [2] 00930          clc              ; Oh how I wish the 6502 carry flag is not backasswards
 280F 65 0E           [3] 00931          adc    ___DivLo  ; Add high byte to low
 2811 85 0E           [3] 00932          sta    ___DivLo
                          00933
 2813 90 06 (281B)  [2/3] 00934          bcc    EightBit
                          00935
 2815 8A              [2] 00936          txa              ; New low byte overflowed
 2816 69 54           [2] 00937          adc    #85-1     ; Add another 85 to result (carry set!)
 2818 AA              [2] 00938          tax              ; This is a special case for only $1FF
 2819 E6 0E           [5] 00939          inc    ___DivLo
                          00940
                          00941 ;  **** Value is < 256 (only low byte)
 281B                     00942 EightBit:
 281B 86 11           [3] 00943          stx    ___QuoHi  ; Store partial result
                          00944
                          00945 ;
                          00946 ; This code from
                          00947 ;
                          00948 ; https://codebase64.org/doku.php?id=base:8bitdivide_by_constant_8bit_result
                          00949 ;
 281D A5 0E           [3] 00950          lda    ___DivLo
 281F 4A              [2] 00951          lsr    A
 2820 69 15           [2] 00952          adc    #21
 2822 4A              [2] 00953          lsr    A
 2823 65 0E           [3] 00954          adc    ___DivLo
 2825 6A              [2] 00955          ror    A
 2826 4A              [2] 00956          lsr    A
 2827 65 0E           [3] 00957          adc    ___DivLo
 2829 6A              [2] 00958          ror    A
 282A 4A              [2] 00959          lsr    A
 282B 65 0E           [3] 00960          adc    ___DivLo
 282D 6A              [2] 00961          ror    A
 282E 4A              [2] 00962          lsr    A
                          00963
 282F 18              [2] 00964          clc              ; Combine with partial quotient
 2830 65 11           [3] 00965          adc    ___QuoHi
 2832 85 11           [3] 00966          sta    ___QuoHi
                          00967
 2834 60              [6] 00968          rts
                          00969
 2900                     00970          org    FreeRAM+$900
                          00971
                          00972 ;
                          00973 ; Test driver
                          00974 ;
 2900                     00975 Start:
 2900 A9 00           [2] 00976          lda    #>64
 2902 A2 40           [2] 00977          ldx    #<64
                          00978
 2904 85 03           [3] 00979          sta    DIVHI
 2906 85 07           [3] 00980          sta    _DIVHI
 2908 85 0B           [3] 00981          sta    __DIVHI
 290A 85 18           [3] 00982          sta    _nh
 290C 85 1B           [3] 00983          sta    __nh
 290E 85 1E           [3] 00984          sta    nh
 2910 85 20           [3] 00985          sta    T+1
 2912 85 0F           [3] 00986          sta    ___DivHi
                          00987
 2914 86 02           [3] 00988          stx    DIVLO
 2916 86 06           [3] 00989          stx    _DIVLO
 2918 86 0A           [3] 00990          stx    __DIVLO
 291A 86 17           [3] 00991          stx    _nl
 291C 86 1A           [3] 00992          stx    __nl
 291E 86 1D           [3] 00993          stx    nl
 2920 86 1F           [3] 00994          stx    T
 2922 86 0E           [3] 00995          stx    ___DivLo
                          00996
 2924 85 24           [3] 00997          sta    Number+1
 2926 86 23           [3] 00998          stx    Number
                          00999
 2928 20 2000         [6] 01000          jsr    DIVIDE_BY_THREE
                          01001
 292B A5 07           [3] 01002          lda    _DIVHI
 292D A4 06           [3] 01003          ldy    _DIVLO
 292F 20 2100         [6] 01004          jsr    div3_ay
 2932 84 15           [3] 01005          sty    Quotient
                          01006
 2934 20 2200         [6] 01007          jsr    Mine
                          01008
 2937 20 2300         [6] 01009          jsr    BB8
                          01010
 293A 20 2400         [6] 01011          jsr    OptimizedBB8
                          01012
 293D 20 2500         [6] 01013          jsr    ModifiedBB8
                          01014
 2940 20 2600         [6] 01015          jsr    MineTabled
                          01016
 2943 20 2700         [6] 01017          jsr    div3
                          01018
 2946 20 2800         [6] 01019          jsr    ModifiedBB8_plus_teamtempest
                          01020
 2949 A2 23           [2] 01021          ldx    #<Number
 294B A0 00           [2] 01022          ldy    #>Number
 294D A9 01           [2] 01023          lda    #1
 294F 20 02DB         [6] 01024          jsr    OUTDEC
                          01025
 2952 A2 23           [2] 01026          ldx    #<DividedBy
 2954 A0 2A           [2] 01027          ldy    #>DividedBy
 2956 20 2A10         [6] 01028          jsr    PSTR
                          01029
 2959 A9 00           [2] 01030          lda    #0
 295B 85 24           [3] 01031          sta    Number+1
                          01032
 295D A5 05           [3] 01033          lda    QUOHI
 295F 85 23           [3] 01034          sta    Number
 2961 A2 23           [2] 01035          ldx    #<Number
 2963 A0 00           [2] 01036          ldy    #>Number
 2965 A9 01           [2] 01037          lda    #1
 2967 20 02DB         [6] 01038          jsr    OUTDEC
                          01039
 296A A2 37           [2] 01040          ldx    #<NesDev
 296C A0 2A           [2] 01041          ldy    #>NesDev
 296E 20 2A10         [6] 01042          jsr    PSTR
                          01043
 2971 A5 15           [3] 01044          lda    Quotient
 2973 85 23           [3] 01045          sta    Number
 2975 A2 23           [2] 01046          ldx    #<Number
 2977 A0 00           [2] 01047          ldy    #>Number
 2979 A9 01           [2] 01048          lda    #1
 297B 20 02DB         [6] 01049          jsr    OUTDEC
                          01050
 297E A2 41           [2] 01051          ldx    #<Separator
 2980 A0 2A           [2] 01052          ldy    #>Separator
 2982 20 2A10         [6] 01053          jsr    PSTR
                          01054
 2985 A5 09           [3] 01055          lda    _QUOHI
 2987 85 23           [3] 01056          sta    Number
 2989 A2 23           [2] 01057          ldx    #<Number
 298B A0 00           [2] 01058          ldy    #>Number
 298D A9 01           [2] 01059          lda    #1
 298F 20 02DB         [6] 01060          jsr    OUTDEC
                          01061
 2992 A2 49           [2] 01062          ldx    #<_BB8
 2994 A0 2A           [2] 01063          ldy    #>_BB8
 2996 20 2A10         [6] 01064          jsr    PSTR
                          01065
 2999 A5 16           [3] 01066          lda    _res
 299B 85 23           [3] 01067          sta    Number
 299D A2 23           [2] 01068          ldx    #<Number
 299F A0 00           [2] 01069          ldy    #>Number
 29A1 A9 01           [2] 01070          lda    #1
 29A3 20 02DB         [6] 01071          jsr    OUTDEC
                          01072
 29A6 A2 59           [2] 01073          ldx    #<OptBB8
 29A8 A0 2A           [2] 01074          ldy    #>OptBB8
 29AA 20 2A10         [6] 01075          jsr    PSTR
                          01076
 29AD A5 19           [3] 01077          lda    __res
 29AF 85 23           [3] 01078          sta    Number
 29B1 A2 23           [2] 01079          ldx    #<Number
 29B3 A0 00           [2] 01080          ldy    #>Number
 29B5 A9 01           [2] 01081          lda    #1
 29B7 20 02DB         [6] 01082          jsr    OUTDEC
                          01083
 29BA A2 6A           [2] 01084          ldx    #<ModBB8
 29BC A0 2A           [2] 01085          ldy    #>ModBB8
 29BE 20 2A10         [6] 01086          jsr    PSTR
                          01087
 29C1 A5 1C           [3] 01088          lda    res
 29C3 85 23           [3] 01089          sta    Number
 29C5 A2 23           [2] 01090          ldx    #<Number
 29C7 A0 00           [2] 01091          ldy    #>Number
 29C9 A9 01           [2] 01092          lda    #1
 29CB 20 02DB         [6] 01093          jsr    OUTDEC
                          01094
 29CE A2 7A           [2] 01095          ldx    #<Tabled
 29D0 A0 2A           [2] 01096          ldy    #>Tabled
 29D2 20 2A10         [6] 01097          jsr    PSTR
                          01098
 29D5 A5 0D           [3] 01099          lda    __QUOHI
 29D7 85 23           [3] 01100          sta    Number
 29D9 A2 23           [2] 01101          ldx    #<Number
 29DB A0 00           [2] 01102          ldy    #>Number
 29DD A9 01           [2] 01103          lda    #1
 29DF 20 02DB         [6] 01104          jsr    OUTDEC
                          01105
 29E2 A2 99           [2] 01106          ldx    #<Barry
 29E4 A0 2A           [2] 01107          ldy    #>Barry
 29E6 20 2A10         [6] 01108          jsr    PSTR
                          01109
 29E9 A5 1F           [3] 01110          lda    T
 29EB 85 23           [3] 01111          sta    Number
 29ED A2 23           [2] 01112          ldx    #<Number
 29EF A0 00           [2] 01113          ldy    #>Number
 29F1 A9 01           [2] 01114          lda    #1
 29F3 20 02DB         [6] 01115          jsr    OUTDEC
                          01116
 29F6 A2 A2           [2] 01117          ldx    #<ModBB8PlusTT
 29F8 A0 2A           [2] 01118          ldy    #>ModBB8PlusTT
 29FA 20 2A10         [6] 01119          jsr    PSTR
                          01120
 29FD A5 11           [3] 01121          lda    ___QuoHi
 29FF 85 23           [3] 01122          sta    Number
 2A01 A2 23           [2] 01123          ldx    #<Number
 2A03 A0 00           [2] 01124          ldy    #>Number
 2A05 A9 01           [2] 01125          lda    #1
 2A07 20 02DB         [6] 01126          jsr    OUTDEC
                          01127
 2A0A 20 022E         [6] 01128          jsr    PCRLF
                          01129
 2A0D 4C 0200         [3] 01130          jmp    WARMS
                          01131
                          01132 ;
                          01133 ;
                          01134 ;
 2A10                     01135 PSTR:
 2A10 86 21           [3] 01136          stx    Ptr
 2A12 84 22           [3] 01137          sty    Ptr+1
 2A14 A0 00           [2] 01138          ldy    #0
                          01139
 2A16                     01140 2:
 2A16 B1 21         [5/6] 01141          lda    (Ptr),Y
 2A18 C9 04           [2] 01142          cmp    #4
 2A1A F0 06 (2A22)  [2/3] 01143          beq    3f
                          01144
 2A1C 20 0221         [6] 01145          jsr    PUTCHR
                          01146
 2A1F C8              [2] 01147          iny
                          01148
 2A20 D0 F4 (2A16)  [2/3] 01149          bne    2b        ; Always branches
                          01150
 2A22                     01151 3:
 2A22 60              [6] 01152          rts
                          01153
 2A23 202F203320657175    01154 DividedBy fcc   " / 3 equals: yours ",4
 2A2B 616C733A20796F75
 2A33 7273 20 04
 2A37 2C204E6573446576    01155 NesDev   fcc    ", NesDev ",4
 2A3F 20 04
 2A41 2C206D696E65 20 04          01156 Separator fcc   ", mine ",4
 2A49 0D0A202020202020    01157 _BB8     fcc    $D,$A,"         BB8 ",4
 2A51 202020424238 20 04
 2A59 2C206F7074696D69    01158 OptBB8   fcc    ", optimized BB8 ",4
 2A61 7A656420424238 20
 2A69 04
 2A6A 2C206D6F64696669    01159 ModBB8   fcc    ", modified BB8 ",4
 2A72 656420424238 20 04
 2A7A 0D0A202020202020    01160 Tabled   fcc    $D,$A,"         my code with table ",4
 2A82 2020206D7920636F
 2A8A 6465207769746820
 2A92 7461626C65 20 04
 2A99 2C204261727279 20   01161 Barry    fcc    ", Barry ",4
 2AA1 04
 2AA2 0D0A202020202020    01162 ModBB8PlusTT fcc $D,$A,"         modified BB8 plus teamtempest ",4
 2AAA 2020206D6F646966
 2AB2 6965642042423820
 2ABA 706C757320746561
 2AC2 6D74656D70657374
 2ACA 20 04
                          01163
 2900                     01164          end    Start

Posted: **Tue Feb 27, 2024 1:12 am**

And the scorecard of times for some selected dividend values.

765 / 3 = 255

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$AA 170 cycles for my code
$88 136 cycles for BB8 code
$64 100 cycles for optimized BB8 code
$54 84 cycles for modified BB8 code
$85 133 cycles for my code with table
$1A2 418 cycles for Mike Barry code
$4F 79 cycles for modified BB8 plus teamtempest code

726 / 3 = 242

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$AA 170 cycles for my code
$88 136 cycles for BB8 code
$64 100 cycles for optimized BB8 code
$54 84 cycles for modified BB8 code
$85 133 cycles for my code with table
$190 400 cycles for Mike Barry code
$4F 79 cycles for modified BB8 plus teamtempest code

666 / 3 = 222

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$AA 170 cycles for my code
$88 136 cycles for BB8 code
$64 100 cycles for optimized BB8 code
$54 84 cycles for modified BB8 code
$85 133 cycles for my code with table
$196 406 cycles for Mike Barry code
$4F 79 cycles for modified BB8 plus teamtempest code

513 / 3 = 171

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$AA 170 cycles for my code
$88 136 cycles for BB8 code
$64 100 cycles for optimized BB8 code
$54 84 cycles for modified BB8 code
$85 133 cycles for my code with table
$190 400 cycles for Mike Barry code
$4F 79 cycles for modified BB8 plus teamtempest code

512 / 3 = 170

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$A6 166 cycles for my code
$88 136 cycles for BB8 code
$64 100 cycles for optimized BB8 code
$54 84 cycles for modified BB8 code
$85 133 cycles for my code with table
$18A 394 cycles for Mike Barry code
$4F 79 cycles for modified BB8 plus teamtempest code

511 / 3 = 170

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$C3 195 cycles for my code
$81 129 cycles for BB8 code
$5D 93 cycles for optimized BB8 code
$5D 93 cycles for modified BB8 code
$85 133 cycles for my code with table
$18A 394 cycles for Mike Barry code
$58 88 cycles for modified BB8 plus teamtempest code

333 / 3 = 111

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$AA 170 cycles for my code
$65 101 cycles for BB8 code
$53 83 cycles for optimized BB8 code
$53 83 cycles for modified BB8 code
$85 133 cycles for my code with table
$196 406 cycles for Mike Barry code
$4E 78 cycles for modified BB8 plus teamtempest code

257 / 3 = 85

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$A6 166 cycles for my code
$65 101 cycles for BB8 code
$53 83 cycles for optimized BB8 code
$53 83 cycles for modified BB8 code
$68 104 cycles for my code with table
$18A 394 cycles for Mike Barry code
$4E 78 cycles for modified BB8 plus teamtempest code

256 / 3 = 85

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$A6 166 cycles for my code
$65 101 cycles for BB8 code
$53 83 cycles for optimized BB8 code
$53 83 cycles for modified BB8 code
$68 104 cycles for my code with table
$18A 394 cycles for Mike Barry code
$4E 78 cycles for modified BB8 plus teamtempest code

255 / 3 = 85

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$AA 170 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$68 104 cycles for my code with table
$18A 394 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

128 / 3 = 42

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$89 137 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$68 104 cycles for my code with table
$184 388 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

69 / 3 = 23

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$8D 141 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$18A 394 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

65 / 3 = 21

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$89 137 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$184 388 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

64 / 3 = 21

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$89 137 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$184 388 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

63 / 3 = 21

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$8D 141 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$184 388 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

47 / 3 = 15

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$89 137 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$18A 394 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

32 / 3 = 10

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$6C 108 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$17E 382 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

16 / 3 = 5

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$6C 108 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$17E 382 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

13 / 3 = 4

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$6C 108 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$178 376 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

4 / 3 = 1

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$4F 79 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$4B 75 cycles for my code with table
$178 376 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

3 / 3 = 1

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$36 54 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$32 50 cycles for my code with table
$178 376 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

0 / 3 = 0

$A4 164 cycles for your code
$161 353 cycles for NesDev code
$32 50 cycles for my code
$42 66 cycles for BB8 code
$40 64 cycles for optimized BB8 code
$42 66 cycles for modified BB8 code
$2E 46 cycles for my code with table
$172 370 cycles for Mike Barry code
$3D 61 cycles for modified BB8 plus teamtempest code

To be fair, note that the NesDev code is yielding a 16-bit result
and Mike Barry's is tiny.

Posted: **Tue Feb 27, 2024 2:48 am**

WynnSmith wrote:

... This code is intended to become part of a larger library where the special case of division by 5 is also needed. The library would then be included with other code that efficiently encodes and decodes blocks of data. Therefore, code size and table size does matter. ...

Yes, since $FFx5=$4FB, it would take two trial subtractions to get a table look-up down to one 256 byte table and one <128 byte table ($3Fx5=$13B), and at that point the game is likely not worth the candle.

A nybble multiplication table approach would only need 32 bytes for the products of each nybble with 0.10101010 and 0.00110011, with a iiii.ffff result, but efficient execution of nybble multiplications may entail some 256 byte tables for effective nybble operations.

Posted: **Tue Feb 27, 2024 2:07 pm**

WynnSmith wrote:

This code is intended to become part of a larger library where the special case of division by 5 is also needed.

I would base that on the divide by 3 code. This has not been tested very much.

Hmm... the divide by 3 code can be sped up by using a lookup table to handle the upper byte...

Code: Select all

                          00500 ;
                          00501 ; Divide number 0..1275 (255*5) by 5
                          00502 ;
                          00503 ; Use fast 8-bit divide by 5 for final byte remainder
                          00504 ;
                          00505 ; Subtracting 255 is the same as subtracting 256 and adding 1...
                          00506 ;
 2000                     00507 Div5:
 2000 A2 00           [2] 00508          ldx    #0        ; Start with result = 0
                          00509
 2002 A5 03           [3] 00510          lda    DivHi     ; Load high byte
 2004 F0 11 (2017)  [2/3] 00511          beq    EightBit  ; If zero then do 8-bit division
                          00512
 2006 A8              [2] 00513          tay
 2007 BE 2031       [4/5] 00514          ldx    Table,Y   ; Add upper byte * 255/5 to result
                          00515
 200A 18              [2] 00516          clc              ; Add high byte to low
 200B 65 02           [3] 00517          adc    DivLo
 200D 85 02           [3] 00518          sta    DivLo
                          00519
 200F 90 06 (2017)  [2/3] 00520          bcc    EightBit
                          00521
 2011 8A              [2] 00522          txa              ; New low byte overflowed
 2012 69 32           [2] 00523          adc    #255/5-1  ; Add another 255/5 to result (carry set!)
 2014 AA              [2] 00524          tax
 2015 E6 02           [5] 00525          inc    DivLo
                          00526
                          00527 ;  **** Value is < 256 (only low byte)
 2017                     00528 EightBit:
 2017 86 05           [3] 00529          stx    QuoHi     ; Store partial result
                          00530
                          00531 ;
                          00532 ; This code from
                          00533 ;
                          00534 ; https://codebase64.org/doku.php?id=base:8bitdivide_by_constant_8bit_result
                          00535 ;
 2019 A5 02           [3] 00536          lda    DivLo
 201B 4A              [2] 00537          lsr    A
 201C 69 0D           [2] 00538          adc    #13
 201E 65 02           [3] 00539          adc    DivLo
 2020 6A              [2] 00540          ror    A
 2021 4A              [2] 00541          lsr    A
 2022 4A              [2] 00542          lsr    A
 2023 65 02           [3] 00543          adc    DivLo
 2025 6A              [2] 00544          ror    A
 2026 65 02           [3] 00545          adc    DivLo
 2028 6A              [2] 00546          ror    A
 2029 4A              [2] 00547          lsr    A
 202A 4A              [2] 00548          lsr    A
                          00549
 202B 18              [2] 00550          clc              ; Combine with partial quotient
 202C 65 05           [3] 00551          adc    QuoHi
 202E 85 05           [3] 00552          sta    QuoHi
                          00553
 2030 60              [6] 00554          rts
                          00555
 2031 00 33 66 99 CC      00556 Table    fcb    0,255/5,2*255/5,3*255/5,4*255/5

Posted: **Tue Feb 27, 2024 4:06 pm**

I cannot help but ponder whether we can build a faster divide by 3 yielding a 16-bit result...

Yes, we can!

This has not been thoroughly tested.

Code: Select all

                          00502 ;
                          00503 ; Divide number by 3 yielding 16-bit quotient
                          00504 ;
                          00505 ; Subtracting 255 is the same as subtracting 256 and adding 1...
                          00506 ;
 2000                     00507 Div3_16:
 2000 A5 03           [3] 00508          lda    DivHi     ; Divide high byte by 3
 2002 20 2037         [6] 00509          jsr    Div3_8Bit
                          00510
 2005 85 05           [3] 00511          sta    QuoHi
                          00512
 2007 0A              [2] 00513          asl    A         ; Multiply by 3
 2008 18              [2] 00514          clc
 2009 65 05           [3] 00515          adc    QuoHi
 200B 85 06           [3] 00516          sta    Temp
                          00517
 200D A2 00           [2] 00518          ldx    #0        ; Start with low byte result = 0
                          00519
 200F A5 03           [3] 00520          lda    DivHi     ; Determine high byte of remainder
 2011 38              [2] 00521          sec
 2012 E5 06           [3] 00522          sbc    Temp
 2014 F0 11 (2027)  [2/3] 00523          beq    EightBit  ; If zero then do 8-bit division
                          00524
 2016 A8              [2] 00525          tay
 2017 BE 2034       [4/5] 00526          ldx    Table,Y   ; Add upper byte * 255/3 to result
                          00527
 201A 18              [2] 00528          clc              ; Add high byte to low
 201B 65 02           [3] 00529          adc    DivLo
 201D 85 02           [3] 00530          sta    DivLo
                          00531
 201F 90 06 (2027)  [2/3] 00532          bcc    EightBit
                          00533
 2021 8A              [2] 00534          txa              ; New low byte overflowed
 2022 69 54           [2] 00535          adc    #255/3-1  ; Add another 255/3 to result (carry set!)
 2024 AA              [2] 00536          tax              ; This is a special case for only $1FF
 2025 E6 02           [5] 00537          inc    DivLo
                          00538
                          00539 ;  **** Value is < 256 (only low byte)
 2027                     00540 EightBit:
 2027 86 04           [3] 00541          stx    QuoLo     ; Store partial result
                          00542
 2029 A5 02           [3] 00543          lda    DivLo
 202B 20 2037         [6] 00544          jsr    Div3_8Bit
                          00545
 202E 18              [2] 00546          clc              ; Combine with partial quotient
 202F 65 04           [3] 00547          adc    QuoLo
 2031 85 04           [3] 00548          sta    QuoLo
                          00549
 2033 60              [6] 00550          rts
                          00551
 2034 00 55 AA            00552 Table    fcb    0,255/3,2*255/3
                          00553
                          00554 ;
                          00555 ; 8-bit divide by 3
                          00556 ;
                          00557 ; This code from
                          00558 ;
                          00559 ; https://codebase64.org/doku.php?id=base:8bitdivide_by_constant_8bit_result
                          00560 ;
 2037                     00561 Div3_8Bit:
 2037 85 06           [3] 00562          sta    Temp
 2039 4A              [2] 00563          lsr    A
 203A 69 15           [2] 00564          adc    #21
 203C 4A              [2] 00565          lsr    A
 203D 65 06           [3] 00566          adc    Temp
 203F 6A              [2] 00567          ror    A
 2040 4A              [2] 00568          lsr    A
 2041 65 06           [3] 00569          adc    Temp
 2043 6A              [2] 00570          ror    A
 2044 4A              [2] 00571          lsr    A
 2045 65 06           [3] 00572          adc    Temp
 2047 6A              [2] 00573          ror    A
 2048 4A              [2] 00574          lsr    A
                          00575
 2049 60              [6] 00576          rts

Posted: **Tue Feb 27, 2024 5:28 pm**

Is the following significantly smaller than a 756 byte look-up table?

BillG wrote:

This is my latest test program containing all of the code snippets. Each one is orged at a page boundary to make sizes obvious.

Code: Select all

                          00001          lib    FAKEFLEX.LIB
.                         00002 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
.                         00003 ;
.                         00004 ; Fake FLEX environment for debugging in emulator
.                         00005 ;
.0000                     00481          .list
                          00482
 0002                     00483          org    ZeroPage
                          00484
                          00485 ;-----------------------------------------------------------------
                          00486 ; The dividend is stored in 00 and 01 before calling this routine.
                          00487 ; The resulting quotient will be accumulated in 03.
                          00488 ; Largest supported dividend is 765.  (add error checking?)
                          00489
 0002                     00490 DIVLO    rmb    1         ; Zero page locations of 10 bit dividend
 0003                     00491 DIVHI    rmb    1
 0004                     00492 QUOLO    rmb    1         ; low bits of accumulated sum
 0005                     00493 QUOHI    rmb    1         ; high bits of accumulated sum (Quotient)
                          00494
 0006                     00495 _DIVLO   rmb    1         ; Zero page locations of 10 bit dividend
 0007                     00496 _DIVHI   rmb    1
 0008                     00497 _QUOLO   rmb    1         ; low bits of accumulated sum
 0009                     00498 _QUOHI   rmb    1         ; high bits of accumulated sum (Quotient)
                          00499
 000A                     00500 __DIVLO  rmb    1         ; Zero page locations of 10 bit dividend
 000B                     00501 __DIVHI  rmb    1
 000C                     00502 __QUOLO  rmb    1         ; low bits of accumulated sum
 000D                     00503 __QUOHI  rmb    1         ; high bits of accumulated sum (Quotient)
                          00504
 000E                     00505 ___DivLo rmb    1         ; Zero page locations of 10 bit dividend
 000F                     00506 ___DivHi rmb    1
 0010                     00507 ___QuoLo rmb    1         ; low bits of accumulated sum
 0011                     00508 ___QuoHi rmb    1         ; high bits of accumulated sum (Quotient)
                          00509
 0012                     00510 lo_temp  rmb    1
 0013                     00511 hi_temp  rmb    1
 0014                     00512 lo_product rmb  1
 0015                     00513 Quotient rmb    1
                          00514
 0016                     00515 _res     rmb    1
 0017                     00516 _nl      rmb    1
 0018                     00517 _nh      rmb    1
                          00518
 0019                     00519 __res    rmb    1
 001A                     00520 __nl     rmb    1
 001B                     00521 __nh     rmb    1
                          00522
 001C                     00523 res      rmb    1
 001D                     00524 nl       rmb    1
 001E                     00525 nh       rmb    1
                          00526
 001F                     00527 T        rmb    2
                          00528
 0021                     00529 Ptr      rmb    2
 0023                     00530 Number   rmb    2
                          00531
 2000                     00532          org    FreeRAM
                          00533
 2000                     00534 DIVIDE_BY_THREE:
                          00535
                          00536 ; First, effectively multiply by 0.0000 0001
 2000 A5 02           [3] 00537          lda    DIVLO     ; low bits of dividend
 2002 85 04           [3] 00538          sta    QUOLO
 2004 A5 03           [3] 00539          lda    DIVHI     ; high bits of dividend
                          00540
                          00541 ; shift 6 times, add 3 times
 2006 A2 03           [2] 00542          ldx    #3        ; so, we'll loop 3 times
                          00543
                          00544 ; Then, effectively multiply by 0.0000 0101
                          00545 ; then by 0.0001 0101
                          00546 ; then by 0.0101 0101, which is 1/3
                          00547
 2008                     00548 LOOP:
                          00549
 2008 85 05           [3] 00550          sta    QUOHI
                          00551
 200A 06 04           [5] 00552          asl    QUOLO     ; first, shift left twice
 200C 26 05           [5] 00553          rol    QUOHI
 200E 06 04           [5] 00554          asl    QUOLO
 2010 26 05           [5] 00555          rol    QUOHI
 2012 18              [2] 00556          clc              ; Then, add the dividend
 2013 A5 04           [3] 00557          lda    QUOLO
 2015 65 02           [3] 00558          adc    DIVLO
 2017 85 04           [3] 00559          sta    QUOLO
 2019 A5 05           [3] 00560          lda    QUOHI
 201B 65 03           [3] 00561          adc    DIVHI
                          00562
 201D CA              [2] 00563          dex
 201E D0 E8 (2008)  [2/3] 00564          bne    LOOP
                          00565
 2020                     00566 FINISH:
                          00567
 2020 38              [2] 00568          sec
 2021 69 00           [2] 00569          adc    #0        ;  + 1 (round up)
 2023 85 05           [3] 00570          sta    QUOHI     ; The resulting Quotient is in the Accumulator
                          00571
 2025 60              [6] 00572          rts
                          00573
 2100                     00574          org    FreeRAM+$100
                          00575
                          00576 ; divide 16 bit number by 3 by multiplying by 1/3
                          00577 ; enter with
                          00578 ; A containing the hi byte of the number to be divided by 3
                          00579 ; Y containing the lo byte of the number to be divided by 3
                          00580 ; the hi byte of the partial product is kept in A or saved
                          00581 ; on the stack when neccessary
                          00582 ; the product (N/3 quotient) is returned hi byte in A,
                          00583 ; lo byte in Y
                          00584
 2100                     00585 div3_ay:
                          00586
                          00587  ; save the number in lo_temp, hi_temp
                          00588
 2100 84 12           [3] 00589          sty    lo_temp
 2102 84 14           [3] 00590          sty    lo_product
 2104 85 13           [3] 00591          sta    hi_temp
                          00592
 2106 A0 09           [2] 00593          ldy    #$09
 2108 18              [2] 00594          clc
 2109 90 0A (2115)  [2/3] 00595          bcc    ENTER
                          00596
                          00597  ; each pass through loop adds the number in
                          00598  ; lo_temp, hi_temp to the partial product and
                          00599  ; then divides the partial product by 4
                          00600
 210B                     00601 _LOOP:
 210B 48              [3] 00602          pha
 210C A5 14           [3] 00603          lda    lo_product
 210E 65 12           [3] 00604          adc    lo_temp
 2110 85 14           [3] 00605          sta    lo_product
 2112 68              [4] 00606          pla
 2113 65 13           [3] 00607          adc    hi_temp
 2115                     00608 ENTER:
 2115 6A              [2] 00609          ror    A
 2116 66 14           [5] 00610          ror    lo_product
 2118 4A              [2] 00611          lsr    A
 2119 66 14           [5] 00612          ror    lo_product
 211B 88              [2] 00613          dey
 211C D0 ED (210B)  [2/3] 00614          bne    _LOOP
 211E A4 14           [3] 00615          ldy    lo_product
 2120 60              [6] 00616          rts
                          00617
 2200                     00618          org    FreeRAM+$200
                          00619
                          00620 ;
                          00621 ; Observation: 765/3 fits within one byte!
                          00622 ;
                          00623 ;
                          00624 ; 1/3 = 1/4 + 1/12
                          00625 ;
                          00626 ; Look at the problem this way:
                          00627 ;
                          00628 ; 1 = 1/4 + 1/4 + 1/4 + 1/12 + 1/12 + 1/12
                          00629 ;
                          00630 ; Step 1:
                          00631 ;
                          00632 ;  Divide by 4 using two right shifts.  Store quotient.
                          00633 ;
                          00634 ; Step 2:
                          00635 ;
                          00636 ;  Add quotient to the remainder.  Divide this by 4.
                          00637 ;
                          00638 ; Step 3:
                          00639 ;
                          00640 ;  Add quotient to sum of partial quotients
                          00641 ;
                          00642 ; Step 4:
                          00643 ;
                          00644 ;  Repeat steps 2 and 3, summing quotients, until partial quotient is 0 and
                          00645 ;    remainder < 3
                          00646 ;
                          00647 ; Step 5:
                          00648 ;
                          00649 ;  If the remainder is 3, add 1 to the quotient
                          00650 ;
 2200                     00651 Mine:
 2200 A9 00           [2] 00652          lda    #0        ; Initially, result is zero
 2202 85 09           [3] 00653          sta    _QUOHI
                          00654
 2204 A5 06           [3] 00655          lda    _DIVLO    ; Get low byte of dividend
 2206 A8              [2] 00656          tay              ; Save to calculate remainder
                          00657
 2207 46 07           [5] 00658          lsr    _DIVHI    ; Divide by 4
 2209 6A              [2] 00659          ror    A
 220A 46 07           [5] 00660          lsr    _DIVHI    ; This uses up the upper byte
 220C 6A              [2] 00661          ror    A
                          00662
 220D 4C 2213         [3] 00663          jmp    EnterLoop
                          00664
 2210                     00665 MyLoop:
 2210 A8              [2] 00666          tay              ; Save to calculate remainder
                          00667
 2211 4A              [2] 00668          lsr    A         ; Divide by 4
 2212 4A              [2] 00669          lsr    A
                          00670
 2213                     00671 EnterLoop:
 2213 85 06           [3] 00672          sta    _DIVLO    ; Store partial quotient
 2215 F0 0C (2223)  [2/3] 00673          beq    ZeroDiv   ; Dividend has become zero
                          00674
 2217 18              [2] 00675          clc              ; Add to sum of partial quotients
 2218 65 09           [3] 00676          adc    _QUOHI
 221A 85 09           [3] 00677          sta    _QUOHI
                          00678
 221C 98              [2] 00679          tya              ; Add partial quotient to remainder
 221D 29 03           [2] 00680          and    #3        ; Carry still clear from above adc
 221F 65 06           [3] 00681          adc    _DIVLO    ; This is the new dividend
                          00682
 2221 D0 ED (2210)  [2/3] 00683          bne    MyLoop    ; Always branches
                          00684
 2223                     00685 ZeroDiv:
 2223 C0 03           [2] 00686          cpy    #3
 2225 90 02 (2229)  [2/3] 00687          blo    ImDone
                          00688
 2227 E6 09           [5] 00689          inc    _QUOHI    ; Add one third of three remaining
                          00690
 2229                     00691 ImDone:
 2229 60              [6] 00692          rts
                          00693
 2300                     00694          org    FreeRAM+$300
                          00695
 2300                     00696 BB8:
 2300 A9 00           [2] 00697          lda    #0
 2302 85 16           [3] 00698          sta    _res      ; result =0
 2304 A5 18           [3] 00699 _hv      lda    _nh       ; loads high byte
 2306 F0 14 (231C)  [2/3] 00700          beq    _lv       ; if zero then goes to low byte value
                          00701
 2308 18              [2] 00702          clc              ; will subtract 255
 2309 A9 55           [2] 00703          lda    #85       ; adds 85 to result
 230B 65 16           [3] 00704          adc    _res
 230D 85 16           [3] 00705          sta    _res
                          00706
 230F 38              [2] 00707          sec              ; subtracts from low byte
 2310 A5 17           [3] 00708          lda    _nl
 2312 E9 FF           [2] 00709          sbc    #255
 2314 85 17           [3] 00710          sta    _nl
 2316 B0 EC (2304)  [2/3] 00711          bcs    _hv       ; if no carry goes to next iteration
 2318 C6 18           [5] 00712          dec    _nh       ; adjusts high byte
 231A 90 E8 (2304)  [2/3] 00713 _jo      bcc    _hv
                          00714
                          00715 ;  **** value is <256 (only low byte)
 231C                     00716 _lv
 231C A5 17           [3] 00717          lda    _nl
 231E 4A              [2] 00718          lsr    A
 231F 4A              [2] 00719          lsr    A
 2320 65 17           [3] 00720          adc    _nl
 2322 6A              [2] 00721          ror    A
 2323 4A              [2] 00722          lsr    A
 2324 65 17           [3] 00723          adc    _nl
 2326 6A              [2] 00724          ror    A
 2327 4A              [2] 00725          lsr    A
 2328 65 17           [3] 00726          adc    _nl
 232A 6A              [2] 00727          ror    A
 232B 4A              [2] 00728          lsr    A
 232C 65 17           [3] 00729          adc    _nl
 232E 6A              [2] 00730          ror    A
 232F 4A              [2] 00731          lsr    A
 2330 18              [2] 00732          clc
 2331 65 16           [3] 00733          adc    _res
 2333 85 16           [3] 00734          sta    _res
 2335 60              [6] 00735          rts
                          00736
 2400                     00737          org    FreeRAM+$400
                          00738
 2400                     00739 OptimizedBB8:
 2400 A5 1B           [3] 00740          lda    __nh      ; loads high byte
 2402 F0 0D (2411)  [2/3] 00741          beq    __lv      ; if zero then goes to low byte value
                          00742
 2404 A9 00           [2] 00743          lda    #0
 2406 18              [2] 00744          clc
                          00745
 2407                     00746 __hv2:
 2407 69 55           [2] 00747          adc    #85       ; adds 85 to result
 2409 E6 1A           [5] 00748          inc    __nl      ; subtracts 255 from low byte
 240B F0 FA (2407)  [2/3] 00749          beq    __hv2
 240D C6 1B           [5] 00750          dec    __nh      ; adjusts high byte
 240F D0 F6 (2407)  [2/3] 00751          bne    __hv2
                          00752
                          00753 ;  **** value is <256 (only low byte)
 2411 85 19           [3] 00754 __lv     sta    __res
 2413 A5 1A           [3] 00755          lda    __nl
 2415 4A              [2] 00756          lsr    A
 2416 4A              [2] 00757          lsr    A
 2417 65 1A           [3] 00758          adc    __nl
 2419 6A              [2] 00759          ror    A
 241A 4A              [2] 00760          lsr    A
 241B 65 1A           [3] 00761          adc    __nl
 241D 6A              [2] 00762          ror    A
 241E 4A              [2] 00763          lsr    A
 241F 65 1A           [3] 00764          adc    __nl
 2421 6A              [2] 00765          ror    A
 2422 4A              [2] 00766          lsr    A
 2423 65 1A           [3] 00767          adc    __nl
 2425 6A              [2] 00768          ror    A
 2426 4A              [2] 00769          lsr    A
 2427 18              [2] 00770          clc
 2428 65 19           [3] 00771          adc    __res
 242A 85 19           [3] 00772          sta    __res
 242C 60              [6] 00773          rts
                          00774
 2500                     00775          org    FreeRAM+$500
                          00776
                          00777 ;
                          00778 ; Subtracting 255 is the same as subtracting 256 and adding 1...
                          00779 ;
 2500                     00780 ModifiedBB8:
 2500 A2 00           [2] 00781          ldx    #0        ; Start with result = 0
                          00782
 2502 A5 1E           [3] 00783          lda    nh        ; loads high byte
 2504 F0 15 (251B)  [2/3] 00784          beq    lv        ; if zero then goes to low byte value
                          00785
 2506 A2 55           [2] 00786          ldx    #85       ; add 85 to result
 2508 C9 01           [2] 00787          cmp    #1        ; Upper byte is 1?
 250A F0 02 (250E)  [2/3] 00788          beq    2f        ; Yes, but I wish 6502 carry is like the others...
                          00789
 250C A2 AA           [2] 00790          ldx    #2*85     ; It is 2, make that add 2*85
                          00791
 250E                     00792 2:
 250E 18              [2] 00793          clc              ; Add high byte to low
 250F 65 1D           [3] 00794          adc    nl
 2511 85 1D           [3] 00795          sta    nl
                          00796
 2513 90 06 (251B)  [2/3] 00797          bcc    lv
                          00798
 2515 8A              [2] 00799          txa              ; New low byte overflowed
 2516 69 54           [2] 00800          adc    #85-1     ; Add another 85 to result (carry set!)
 2518 AA              [2] 00801          tax              ; This is a special case for only $1FF
 2519 E6 1D           [5] 00802          inc    nl
                          00803
                          00804 ;  **** value is <256 (only low byte)
 251B                     00805 lv:
 251B 86 1C           [3] 00806          stx    res       ; Store partial result
 251D A5 1D           [3] 00807          lda    nl
 251F 4A              [2] 00808          lsr    A
 2520 4A              [2] 00809          lsr    A
 2521 65 1D           [3] 00810          adc    nl
 2523 6A              [2] 00811          ror    A
 2524 4A              [2] 00812          lsr    A
 2525 65 1D           [3] 00813          adc    nl
 2527 6A              [2] 00814          ror    A
 2528 4A              [2] 00815          lsr    A
 2529 65 1D           [3] 00816          adc    nl
 252B 6A              [2] 00817          ror    A
 252C 4A              [2] 00818          lsr    A
 252D 65 1D           [3] 00819          adc    nl
 252F 6A              [2] 00820          ror    A
 2530 4A              [2] 00821          lsr    A
 2531 18              [2] 00822          clc
 2532 65 1C           [3] 00823          adc    res
 2534 85 1C           [3] 00824          sta    res
 2536 60              [6] 00825          rts
                          00826
 2600                     00827          org    FreeRAM+$600
                          00828
 2600                     00829 MineTabled:
 2600 A9 00           [2] 00830          lda    #0        ; Initially, result is zero
 2602 85 0D           [3] 00831          sta    __QUOHI
                          00832
 2604 A5 0A           [3] 00833          lda    __DIVLO   ; Get low byte of dividend
 2606 A8              [2] 00834          tay              ; Save to calculate remainder
                          00835
 2607 46 0B           [5] 00836          lsr    __DIVHI   ; Divide by 4
 2609 6A              [2] 00837          ror    A
 260A 46 0B           [5] 00838          lsr    __DIVHI   ; This uses up the upper byte
 260C 6A              [2] 00839          ror    A
                          00840
 260D D0 05 (2614)  [2/3] 00841          bne    _EnterLoop
 260F F0 1D (262E)  [2/3] 00842          beq    _ZeroDiv
                          00843
 2611                     00844 _MyLoop:
 2611 A8              [2] 00845          tay              ; Save to calculate remainder
                          00846
 2612 4A              [2] 00847          lsr    A         ; Divide by 4
 2613 4A              [2] 00848          lsr    A
                          00849
 2614                     00850 _EnterLoop:
 2614 85 0A           [3] 00851          sta    __DIVLO   ; Store partial quotient
                          00852
 2616 18              [2] 00853          clc              ; Add to sum of partial quotients
 2617 65 0D           [3] 00854          adc    __QUOHI
 2619 85 0D           [3] 00855          sta    __QUOHI
                          00856
 261B 98              [2] 00857          tya              ; Add partial quotient to remainder
 261C 29 03           [2] 00858          and    #3        ; Carry still clear from above adc
 261E 65 0A           [3] 00859          adc    __DIVLO   ; This is the new dividend
                          00860
 2620 C9 14           [2] 00861          cmp    #16+3+1   ; Too big to use lookup table?
 2622 B0 ED (2611)  [2/3] 00862          bhs    _MyLoop   ; Make another trip around
                          00863
 2624 AA              [2] 00864          tax
 2625 A5 0D           [3] 00865          lda    __QUOHI
 2627 18              [2] 00866          clc
 2628 7D 2635       [4/5] 00867          adc    MyTable,X
 262B 85 0D           [3] 00868          sta    __QUOHI
                          00869
 262D 60              [6] 00870          rts
                          00871
 262E                     00872 _ZeroDiv:
 262E C0 03           [2] 00873          cpy    #3
 2630 90 02 (2634)  [2/3] 00874          blo    _ImDone
                          00875
 2632 E6 0D           [5] 00876          inc    __QUOHI   ; Add one third of three remaining
                          00877
 2634                     00878 _ImDone:
 2634 60              [6] 00879          rts
                          00880
 2635 00 00 00 01 01 01   00881 MyTable  fcb    0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6 ; 4 bits plus 3 remainder
 263B 02 02 02 03 03 03
 2641 04 04 04 05 05 05
 2647 06 06
                          00882
 2700                     00883          org    FreeRAM+$700
                          00884
                          00885 ; - - - - - - - - - - - - - - - - - - - - - - - - - - -
                          00886 ; 16-bit unsigned division by 3 routine
                          00887 ;   T /= 3, A = remainder, Y = low byte of quotient
                          00888 ;
 2700                     00889 div3:
 2700 A9 00           [2] 00890          lda    #0          ; remainder
 2702 A0 10           [2] 00891          ldy    #16         ; loop counter
 2704                     00892 div3b:
 2704 06 1F           [5] 00893          asl    T           ; T is gradually replaced
 2706 26 20           [5] 00894          rol    T+1         ;   with the quotient
 2708 2A              [2] 00895          rol    A           ; A is gradually replaced
                          00896                         ;   with the remainder
 2709 C9 03           [2] 00897          cmp    #3          ; partial remainder >= 3?
 270B 90 04 (2711)  [2/3] 00898          bcc    div3c
 270D E9 03           [2] 00899          sbc    #3          ;   yes: update partial
                          00900                         ;     remainder, set low bit
 270F E6 1F           [5] 00901          inc    T           ;     in partial quotient
 2711                     00902 div3c:
 2711 88              [2] 00903          dey
 2712 D0 F0 (2704)  [2/3] 00904          bne    div3b     ; loop 16 times
 2714 A4 1F           [3] 00905          ldy    T           ; quotient:l
 2716 60              [6] 00906          rts
                          00907
 2800                     00908          org    FreeRAM+$800
                          00909
                          00910 ;
                          00911 ; Divide number 0..765 by 3
                          00912 ;
                          00913 ; Use fast 8-bit divide by 3 for final byte remainder
                          00914 ;
                          00915 ; Subtracting 255 is the same as subtracting 256 and adding 1...
                          00916 ;
 2800                     00917 ModifiedBB8_plus_teamtempest:
 2800 A2 00           [2] 00918          ldx    #0        ; Start with result = 0
                          00919
 2802 A5 0F           [3] 00920          lda    ___DivHi  ; Load high byte
 2804 F0 15 (281B)  [2/3] 00921          beq    EightBit  ; If zero then do 8-bit division
                          00922
 2806 A2 55           [2] 00923          ldx    #85       ; Add 85 to result
 2808 C9 01           [2] 00924          cmp    #1        ; Upper byte is 1?
 280A F0 02 (280E)  [2/3] 00925          beq    2f        ; Yes
                          00926
 280C A2 AA           [2] 00927          ldx    #2*85     ; It is 2, make that add 2*85
                          00928
 280E                     00929 2:
 280E 18              [2] 00930          clc              ; Oh how I wish the 6502 carry flag is not backasswards
 280F 65 0E           [3] 00931          adc    ___DivLo  ; Add high byte to low
 2811 85 0E           [3] 00932          sta    ___DivLo
                          00933
 2813 90 06 (281B)  [2/3] 00934          bcc    EightBit
                          00935
 2815 8A              [2] 00936          txa              ; New low byte overflowed
 2816 69 54           [2] 00937          adc    #85-1     ; Add another 85 to result (carry set!)
 2818 AA              [2] 00938          tax              ; This is a special case for only $1FF
 2819 E6 0E           [5] 00939          inc    ___DivLo
                          00940
                          00941 ;  **** Value is < 256 (only low byte)
 281B                     00942 EightBit:
 281B 86 11           [3] 00943          stx    ___QuoHi  ; Store partial result
                          00944
                          00945 ;
                          00946 ; This code from
                          00947 ;
                          00948 ; https://codebase64.org/doku.php?id=base:8bitdivide_by_constant_8bit_result
                          00949 ;
 281D A5 0E           [3] 00950          lda    ___DivLo
 281F 4A              [2] 00951          lsr    A
 2820 69 15           [2] 00952          adc    #21
 2822 4A              [2] 00953          lsr    A
 2823 65 0E           [3] 00954          adc    ___DivLo
 2825 6A              [2] 00955          ror    A
 2826 4A              [2] 00956          lsr    A
 2827 65 0E           [3] 00957          adc    ___DivLo
 2829 6A              [2] 00958          ror    A
 282A 4A              [2] 00959          lsr    A
 282B 65 0E           [3] 00960          adc    ___DivLo
 282D 6A              [2] 00961          ror    A
 282E 4A              [2] 00962          lsr    A
                          00963
 282F 18              [2] 00964          clc              ; Combine with partial quotient
 2830 65 11           [3] 00965          adc    ___QuoHi
 2832 85 11           [3] 00966          sta    ___QuoHi
                          00967
 2834 60              [6] 00968          rts
                          00969
 2900                     00970          org    FreeRAM+$900
                          00971
                          00972 ;
                          00973 ; Test driver
                          00974 ;
 2900                     00975 Start:
 2900 A9 00           [2] 00976          lda    #>64
 2902 A2 40           [2] 00977          ldx    #<64
                          00978
 2904 85 03           [3] 00979          sta    DIVHI
 2906 85 07           [3] 00980          sta    _DIVHI
 2908 85 0B           [3] 00981          sta    __DIVHI
 290A 85 18           [3] 00982          sta    _nh
 290C 85 1B           [3] 00983          sta    __nh
 290E 85 1E           [3] 00984          sta    nh
 2910 85 20           [3] 00985          sta    T+1
 2912 85 0F           [3] 00986          sta    ___DivHi
                          00987
 2914 86 02           [3] 00988          stx    DIVLO
 2916 86 06           [3] 00989          stx    _DIVLO
 2918 86 0A           [3] 00990          stx    __DIVLO
 291A 86 17           [3] 00991          stx    _nl
 291C 86 1A           [3] 00992          stx    __nl
 291E 86 1D           [3] 00993          stx    nl
 2920 86 1F           [3] 00994          stx    T
 2922 86 0E           [3] 00995          stx    ___DivLo
                          00996
 2924 85 24           [3] 00997          sta    Number+1
 2926 86 23           [3] 00998          stx    Number
                          00999
 2928 20 2000         [6] 01000          jsr    DIVIDE_BY_THREE
                          01001
 292B A5 07           [3] 01002          lda    _DIVHI
 292D A4 06           [3] 01003          ldy    _DIVLO
 292F 20 2100         [6] 01004          jsr    div3_ay
 2932 84 15           [3] 01005          sty    Quotient
                          01006
 2934 20 2200         [6] 01007          jsr    Mine
                          01008
 2937 20 2300         [6] 01009          jsr    BB8
                          01010
 293A 20 2400         [6] 01011          jsr    OptimizedBB8
                          01012
 293D 20 2500         [6] 01013          jsr    ModifiedBB8
                          01014
 2940 20 2600         [6] 01015          jsr    MineTabled
                          01016
 2943 20 2700         [6] 01017          jsr    div3
                          01018
 2946 20 2800         [6] 01019          jsr    ModifiedBB8_plus_teamtempest
                          01020
 2949 A2 23           [2] 01021          ldx    #<Number
 294B A0 00           [2] 01022          ldy    #>Number
 294D A9 01           [2] 01023          lda    #1
 294F 20 02DB         [6] 01024          jsr    OUTDEC
                          01025
 2952 A2 23           [2] 01026          ldx    #<DividedBy
 2954 A0 2A           [2] 01027          ldy    #>DividedBy
 2956 20 2A10         [6] 01028          jsr    PSTR
                          01029
 2959 A9 00           [2] 01030          lda    #0
 295B 85 24           [3] 01031          sta    Number+1
                          01032
 295D A5 05           [3] 01033          lda    QUOHI
 295F 85 23           [3] 01034          sta    Number
 2961 A2 23           [2] 01035          ldx    #<Number
 2963 A0 00           [2] 01036          ldy    #>Number
 2965 A9 01           [2] 01037          lda    #1
 2967 20 02DB         [6] 01038          jsr    OUTDEC
                          01039
 296A A2 37           [2] 01040          ldx    #<NesDev
 296C A0 2A           [2] 01041          ldy    #>NesDev
 296E 20 2A10         [6] 01042          jsr    PSTR
                          01043
 2971 A5 15           [3] 01044          lda    Quotient
 2973 85 23           [3] 01045          sta    Number
 2975 A2 23           [2] 01046          ldx    #<Number
 2977 A0 00           [2] 01047          ldy    #>Number
 2979 A9 01           [2] 01048          lda    #1
 297B 20 02DB         [6] 01049          jsr    OUTDEC
                          01050
 297E A2 41           [2] 01051          ldx    #<Separator
 2980 A0 2A           [2] 01052          ldy    #>Separator
 2982 20 2A10         [6] 01053          jsr    PSTR
                          01054
 2985 A5 09           [3] 01055          lda    _QUOHI
 2987 85 23           [3] 01056          sta    Number
 2989 A2 23           [2] 01057          ldx    #<Number
 298B A0 00           [2] 01058          ldy    #>Number
 298D A9 01           [2] 01059          lda    #1
 298F 20 02DB         [6] 01060          jsr    OUTDEC
                          01061
 2992 A2 49           [2] 01062          ldx    #<_BB8
 2994 A0 2A           [2] 01063          ldy    #>_BB8
 2996 20 2A10         [6] 01064          jsr    PSTR
                          01065
 2999 A5 16           [3] 01066          lda    _res
 299B 85 23           [3] 01067          sta    Number
 299D A2 23           [2] 01068          ldx    #<Number
 299F A0 00           [2] 01069          ldy    #>Number
 29A1 A9 01           [2] 01070          lda    #1
 29A3 20 02DB         [6] 01071          jsr    OUTDEC
                          01072
 29A6 A2 59           [2] 01073          ldx    #<OptBB8
 29A8 A0 2A           [2] 01074          ldy    #>OptBB8
 29AA 20 2A10         [6] 01075          jsr    PSTR
                          01076
 29AD A5 19           [3] 01077          lda    __res
 29AF 85 23           [3] 01078          sta    Number
 29B1 A2 23           [2] 01079          ldx    #<Number
 29B3 A0 00           [2] 01080          ldy    #>Number
 29B5 A9 01           [2] 01081          lda    #1
 29B7 20 02DB         [6] 01082          jsr    OUTDEC
                          01083
 29BA A2 6A           [2] 01084          ldx    #<ModBB8
 29BC A0 2A           [2] 01085          ldy    #>ModBB8
 29BE 20 2A10         [6] 01086          jsr    PSTR
                          01087
 29C1 A5 1C           [3] 01088          lda    res
 29C3 85 23           [3] 01089          sta    Number
 29C5 A2 23           [2] 01090          ldx    #<Number
 29C7 A0 00           [2] 01091          ldy    #>Number
 29C9 A9 01           [2] 01092          lda    #1
 29CB 20 02DB         [6] 01093          jsr    OUTDEC
                          01094
 29CE A2 7A           [2] 01095          ldx    #<Tabled
 29D0 A0 2A           [2] 01096          ldy    #>Tabled
 29D2 20 2A10         [6] 01097          jsr    PSTR
                          01098
 29D5 A5 0D           [3] 01099          lda    __QUOHI
 29D7 85 23           [3] 01100          sta    Number
 29D9 A2 23           [2] 01101          ldx    #<Number
 29DB A0 00           [2] 01102          ldy    #>Number
 29DD A9 01           [2] 01103          lda    #1
 29DF 20 02DB         [6] 01104          jsr    OUTDEC
                          01105
 29E2 A2 99           [2] 01106          ldx    #<Barry
 29E4 A0 2A           [2] 01107          ldy    #>Barry
 29E6 20 2A10         [6] 01108          jsr    PSTR
                          01109
 29E9 A5 1F           [3] 01110          lda    T
 29EB 85 23           [3] 01111          sta    Number
 29ED A2 23           [2] 01112          ldx    #<Number
 29EF A0 00           [2] 01113          ldy    #>Number
 29F1 A9 01           [2] 01114          lda    #1
 29F3 20 02DB         [6] 01115          jsr    OUTDEC
                          01116
 29F6 A2 A2           [2] 01117          ldx    #<ModBB8PlusTT
 29F8 A0 2A           [2] 01118          ldy    #>ModBB8PlusTT
 29FA 20 2A10         [6] 01119          jsr    PSTR
                          01120
 29FD A5 11           [3] 01121          lda    ___QuoHi
 29FF 85 23           [3] 01122          sta    Number
 2A01 A2 23           [2] 01123          ldx    #<Number
 2A03 A0 00           [2] 01124          ldy    #>Number
 2A05 A9 01           [2] 01125          lda    #1
 2A07 20 02DB         [6] 01126          jsr    OUTDEC
                          01127
 2A0A 20 022E         [6] 01128          jsr    PCRLF
                          01129
 2A0D 4C 0200         [3] 01130          jmp    WARMS
                          01131
                          01132 ;
                          01133 ;
                          01134 ;
 2A10                     01135 PSTR:
 2A10 86 21           [3] 01136          stx    Ptr
 2A12 84 22           [3] 01137          sty    Ptr+1
 2A14 A0 00           [2] 01138          ldy    #0
                          01139
 2A16                     01140 2:
 2A16 B1 21         [5/6] 01141          lda    (Ptr),Y
 2A18 C9 04           [2] 01142          cmp    #4
 2A1A F0 06 (2A22)  [2/3] 01143          beq    3f
                          01144
 2A1C 20 0221         [6] 01145          jsr    PUTCHR
                          01146
 2A1F C8              [2] 01147          iny
                          01148
 2A20 D0 F4 (2A16)  [2/3] 01149          bne    2b        ; Always branches
                          01150
 2A22                     01151 3:
 2A22 60              [6] 01152          rts
                          01153
 2A23 202F203320657175    01154 DividedBy fcc   " / 3 equals: yours ",4
 2A2B 616C733A20796F75
 2A33 7273 20 04
 2A37 2C204E6573446576    01155 NesDev   fcc    ", NesDev ",4
 2A3F 20 04
 2A41 2C206D696E65 20 04          01156 Separator fcc   ", mine ",4
 2A49 0D0A202020202020    01157 _BB8     fcc    $D,$A,"         BB8 ",4
 2A51 202020424238 20 04
 2A59 2C206F7074696D69    01158 OptBB8   fcc    ", optimized BB8 ",4
 2A61 7A656420424238 20
 2A69 04
 2A6A 2C206D6F64696669    01159 ModBB8   fcc    ", modified BB8 ",4
 2A72 656420424238 20 04
 2A7A 0D0A202020202020    01160 Tabled   fcc    $D,$A,"         my code with table ",4
 2A82 2020206D7920636F
 2A8A 6465207769746820
 2A92 7461626C65 20 04
 2A99 2C204261727279 20   01161 Barry    fcc    ", Barry ",4
 2AA1 04
 2AA2 0D0A202020202020    01162 ModBB8PlusTT fcc $D,$A,"         modified BB8 plus teamtempest ",4
 2AAA 2020206D6F646966
 2AB2 6965642042423820
 2ABA 706C757320746561
 2AC2 6D74656D70657374
 2ACA 20 04
                          01163
 2900                     01164          end    Start

6502.org

Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three

Re: Old Guy with Special Case Need to Divide by Three