Dividing by seven

[chitselb]

barrym95838 wrote:

CH,

Just for S&Gs, maybe you could try plugging this one into your test bench: it's two bytes shorter and slightly faster, on average (upper 300s, still not nearly as fast as Omegamatrix's code)

Replaced the 40/MOD word with your new code and tested it on all inputs (0..65535). It returned the correct results in each case, and was 2 bytes smaller (7%) and 116 jiffies faster (4%) than the prior version. Thank you, I'll take it!

[bogax]

I'll have a go

Code: Select all

mod_40
 lda hi
 asl
 asl
 asl
 asl
 clc
 adc lo
 bcc *+4
 adc #$0F
 sta tmp
 lda hi
 and #$F0
 adc tmp
 bcc *+4
 adc #$0F
 sec
div_loop
 sbc #$28
 bcs div_loop
 adc #$28
 rts 

[barrym95838]

Can you explain to us how it works, bogax? It would appear that you're from the same "school of commenting" as dclxvi

Do you have a rough cycle count estimate for typical inputs?

Mike B.

[BigDumbDinosaur]

bogax wrote:

I'll have a go

Code: Select all

mod_40
 lda hi
 asl
 asl
 asl
 asl
 clc
 adc lo
 bcc *+4
 adc #$0F
 sta tmp
 lda hi
 and #$F0
 adc tmp
 bcc *+4
 adc #$0F
 sec
div_loop
 sbc #$28
 bcs div_loop
 adc #$28
 rts 

A comment would die of loneliness in that code.

[bogax]

barrym95838 wrote:

Can you explain to us how it works, bogax? It would appear that you're from the same "school of commenting" as dclxvi

Do you have a rough cycle count estimate for typical inputs?

Mike B.

actually I tend to think of the code as sort of
incidental to the comments else we'd all be coding
in hex (or something)

that's not to say I do a great job of commenting

code is easy
comments are hard

but I hate to spoil these little puzzles





256 % 40 = 16
256 = 6 * 40 + 16
so if I subtract some mutiple x * 256 from the
remainder and then add back in x * 16 I've reduced
the remainder by some multiple of 40, 6 * x
the most the result (the partial remainder) can
be with a nibble is
15 * 16 + 255 = 495 = 256 + 239
so if the carry is set and I add 15 back in
I've done it again except in this case x is 1
and the most the answer can be is 239 + 16 = 255
and the carry will be clear when you do the high
nibble which is similar in that 4096 % 40 = 16
except that 4096 is already mutiplied by 16 so
no shifting

then it just repeatedly subtracts 40 in a tight
loop


I think worst case is 73 cycles

[barrym95838]

I haven't tried it out yet, and it looks like it may have potential as a fast MOD ... but CH needs the quotient too, so your routine won't be able to do what he has in mind for unpacking three chars from a cell.

Mike B.

[bogax]

barrym95838 wrote:

I haven't tried it out yet, and it looks like it may have potential as a fast MOD ... but CH needs the quotient too, so your routine won't be able to do what he has in mind for unpacking three chars from a cell.

Mike B.

yes, perhaps I should have made that more explicit

but he's already got his reciprocal multiplication for that

[Omegamatrix]

Bogax, you can save a byte by eliminating the CLC this way. I tested it against all input values.

Code: Select all

  lda dividendHigh
  and #$F0
  sta temp
  eor dividendHigh
  asl
  asl
  asl
  asl
  adc dividendLow
  bcc .skipAdd16A
  adc #$0F
.skipAdd16A:
  adc temp
  bcc .skipAdd16B
  adc #$0F
.skipAdd16B:
  sec
div_loopMod:
  sbc #40
  bcs div_loopMod
  adc #40
  rts