| |
Krill
Registered: Apr 2002
Posts: 2940 |
Long division/modulo with byte-size divisor
So i needed something to divide a large integer (160 or more bits) by a small integer (5 bits) while also performing a modulo operation.
After a few rounds of optimisation, turns out the 6502 implementation is surprisingly compact and fast: ; dividend is in BIGNUM, little-endian
; divisor is in accu
sta DIVISOR
lda #0
ldx #BIGNUMBYTES
longdivmod ldy #8
asl BIGNUM - 1,x
- rol
cmp DIVISOR
bcc +
sbc DIVISOR
+ rol BIGNUM - 1,x
dey
bne -
dex
bne longdivmod
; quotient is in BIGNUM, little-endian
; remainder is in accuThis runs in O(n) linear time. The routine can be executed continuously on the dividend/quotient to extract modulo values.
It's also possible to have a big-endian long integer argument/result by simply iterating over the byte array in reverse order.
Of course, can slightly optimise performance (2 cycles per output bit) by sacrificing a few bytes to self-modify the two DIVISOR arguments with immediate operands. Or unroll the entire thing.
This shall go to Codebase64 at some point, of course, but there might be some more optimisation opportunities.
Also i think there are some requirements on the arguments, such that their MSB must be clear or so. |
|
... 13 posts hidden. Click here to view all posts....
|
| |
Quiss
Registered: Nov 2016
Posts: 41 |
Actually, for small divisors like 3, you could invest a full 2kb and have a (here) 10 bit lookup for div and mod, since that brings it down to
# [init zp_{mod,div} to point to {mod,div}_lookup]
loop:
ldy BIGNUM, x
lda (zp_div), y
sta RESULT, x
lda (zp_mod), y
ora #(>div_lookup)
sta zp_div+1
eor #(>div_lookup) ^ (>mod_lookup)
sta zp_mod+1
inx
cpx #BIGNUMBYTES
bne loop
(Several optimizations are possible, of course. Like having the mod_lookup table already to the ora) |
| |
chatGPZ
Registered: Dec 2001
Posts: 11293 |
All of you should shut up and make a demo about it :) |
| |
Fred
Registered: Feb 2003
Posts: 285 |
Here's another division routine with byte-size divisor. It has one loop less compared to Krill's routine and is a few bytes shorter:
; div16
; input:
; - 16-bit number in dividend, little-endian
; - 8-bit in divisor
; output:
; - 16-bit number in dividend
; - AC: remainder
; - XR: 0
; - YR: unchanged
div16 ldx #16
lda #0
- asl dividend
rol dividend+1
rol a
cmp divisor
bcc +
sbc divisor
inc dividend
+ dex
bne -
rts
divisor .byte 0
dividend .byte 0, 0
|
| |
Krill
Registered: Apr 2002
Posts: 2940 |
Yeah cool, but the point was having arbitrarily large dividends to divide by an 8-bit divisor. =) |
| |
Fred
Registered: Feb 2003
Posts: 285 |
Right, the routine I provided is 16 bits dividend only. |
| |
Fred
Registered: Feb 2003
Posts: 285 |
Here is my version of a long division, specified in bytes in DIV_IN_BYTES:
; div
; input:
; - n-bytes dividend, little-endian
; - 8-bit divisor
; output:
; - n-bytes result stored in dividend
; - AC: remainder
; - XR: 0
; - YR: 0
DIV_IN_BYTES = 20
div ldy #DIV_IN_BYTES * 8
lda #0
- clc
ldx #-DIV_IN_BYTES & $ff
- rol dividend + DIV_IN_BYTES - $100,x
inx
bmi -
rol
cmp divisor
bcc +
sbc divisor
inc dividend
+ dey
bne --
rts
divisor .byte $00
dividend .byte $00, $00, $00, $00, $00, $00, $00, $00
.byte $00, $00, $00, $00, $00, $00, $00, $00
.byte $00, $00, $00, $00
|
| |
Krill
Registered: Apr 2002
Posts: 2940 |
At a quick glance, this seems to run in O(n^2) quadratic time rather than O(n) linear.
With a growing input dividend, both the inner and the outer loops take more iterations.
So i guess this will run slower. |
| |
Monte Carlos
Registered: Jun 2004
Posts: 355 |
Using both cmp as well as sbc seems subject to possible optimization. |
| |
Krill
Registered: Apr 2002
Posts: 2940 |
Quoting Monte CarlosUsing both cmp as well as sbc seems subject to possible optimization. If the X register can be spared, replacing cmp DIVISOR
bcc +
sbc DIVISOR
+with something like tax
sbx #DIVISOR
bcc +
txa
+might be possible, but this hardly looks like it would save cycles on average. =) |
| |
Krill
Registered: Apr 2002
Posts: 2940 |
That said, the long division as in the OP is quite swift, but the long multiplication i also need in the same context turned out to be considerably slower. :) (I guess mostly because it's executed a lot more often, though.) |
| Previous - 1 | 2 | 3 - Next |
