Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Long division/modulo with byte-size divisor
2021-06-13 12:42
Krill

Registered: Apr 2002
Posts: 2804
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 accu
This 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....
 
2021-06-14 10:10
Krill

Registered: Apr 2002
Posts: 2804
Quoting Oswald
a little writeup on the basic idea and how did you end up on the routine would help.
I started with a basic plain bitwise-division routine, expanded it for bignum dividends, then chipped away bits and pieces until i ended up with this. =) It was rather mechanical, really.
But a little later after posting, i noticed it's pretty much the same algorithm as Graham came up with for line slope divison (16 / 8 = 16): https://codebase64.org/doku.php?id=base:8bit_divide_8bit_product - filed somewhat wrongly or misleading there.
There are slight differences concerning the extra shift once per input byte, though.

Quoting Quiss
For 5 bits, there are only 32 possibilities. If you're willing to store a piece of code for each, some of them can be made faster.
(Powers of two, obviously. Also, in the first iteration of x, the "sbc" won't get executed until 2^(8-y) >= divisor, so you can do a preloop that just rols)
As i'm continuously extracting values, dividend and quotient are getting smaller and smaller. So the size of the byte array can be decreased whenever a most significant byte becomes zero. This should neatly halve overall execution time.
Prerolling for the first array byte comes with some additional cost, not sure when within those 8 bits that would amortise.

Quoting Quiss
That is, if you're doing this on the C64.
If this is some drive GCR thing (and the 5 bit provision makes me think it might be), then of course memory's too precious. But you might still be able to squeeze out a few cycles with a log2(x) lookup table, for x=0..31.

(EDIT: Actually, if memory's not an issue, you can have two 8kb lookup tables, for div and mod of 8 bit by 5 bit. You'll still have to shift, though.)
This is for C-64 itself, not the drive, not GCR. =)

It is "2 to 5 bits of divisor", actually. I'm extracting permutation indices from a large number, and the sets to permute have 3 to slightly over 16 items. Unranking the permutations can be done in O(n) as well, and in-place. :)

I'm rather size-constrained there, though, so cannot afford unrolling or big tables.
It's all not really time-critical, however, and i must strictly optimise for size.
2021-06-14 10:14
Krill

Registered: Apr 2002
Posts: 2804
Quoting NoobTracker
How would such a table improve speed? As far as I can tell, it could only be used for the first iteration.
Or the very last iteration? :) At least i don't see how this table would apply to larger arguments than a byte.
2021-06-14 10:27
Oswald

Registered: Apr 2002
Posts: 5007
Gunnar, "line slope divison" I'have discovered long ago that log/exp is accurate enough for that.
2021-06-14 10:27
NoobTracker
Account closed

Registered: Apr 2021
Posts: 14
Quote: Quoting NoobTracker
How would such a table improve speed? As far as I can tell, it could only be used for the first iteration.
Or the very last iteration? :) At least i don't see how this table would apply to larger arguments than a byte.


I actually mean the first one, the most significant byte, because that is the only byte where you have a clear accumulator. You store the division result and you load the modulo value into A. After that, you don't know how the previous byte influenced A and the lookup table only works for A=0, as far as I can tell. I might be wrong.
2021-06-14 10:31
Krill

Registered: Apr 2002
Posts: 2804
Quoting Oswald
Gunnar, "line slope divison" I'have discovered long ago that log/exp is accurate enough for that.
Try that on something similar, like slopes in a Gouraud shader. You'll find you really need the accuracy. And then there are line routines with subpixel accuracy, too. :) Anyways, different topic.
2021-06-14 11:37
ChristopherJam

Registered: Aug 2004
Posts: 1359
Nice work eliminating the 20 byte ROL present in the naive implementation :)

My first run looks like
div:
    ldy#160
iterl:
    clc
    ldx#20
:   rol acc,x
    dex
    bpl :-

    sec
    lda acc
    sbc den
    bcc nosub
    sta acc
    inc acc+20
nosub:
    dey
    bne iterl
    rts



and even then it feels like I should be able to lose the increment in favour of just shifting in the carry from the preceding comparison.
2021-06-14 16:26
Quiss

Registered: Nov 2016
Posts: 37
Quoting Krill

It is "2 to 5 bits of divisor", actually. I'm extracting permutation indices from a large number, and the sets to permute have 3 to slightly over 16 items. Unranking the permutations can be done in O(n) as well, and in-place. :)


Huh. I'll be curious to see what kind of 4k effect you need these kinds of cryptographic shenanigans for. :)

Quoting Krill

Or the very last iteration? :) At least i don't see how this table would apply to larger arguments than a byte.


It depends on the (number of bits in the) divisor. Take, for example, divisor = 3.

Let x = BIGNUM[0]. You look up divmod(x, 3), store the (temporary) result in RESULT[0]. That leaves you with a remainder in the range 0..2, so two bits. You read another 6 bits from BIGNUM[1] (so x is now mod << 6 | BIGNUM[1] >> 2). You look up divmod(x, 3) again for the new x. The div result of that you shift to the left by 2 and add it to RESULT[0]:RESULT[1]. Now you read another 6 bits from BIGNUM[1] and BIGNUM[2], and so on.

For all the shifting, it helps to have the usual shift-right-by-6, and-by-3-and-shift-left-by-4, shift-left-by-6 (etc.) lookup tables.
2021-06-14 19:09
Quiss

Registered: Nov 2016
Posts: 37
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)
2021-06-14 19:35
chatGPZ

Registered: Dec 2001
Posts: 11088
All of you should shut up and make a demo about it :)
2021-06-29 21:21
Fred

Registered: Feb 2003
Posts: 282
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
Previous - 1 | 2 | 3 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
t0m3000/ibex-crew
HCL/Booze Design
Airwolf/F4CG
Guests online: 341
Top Demos
1 Next Level  (9.8)
2 Mojo  (9.7)
3 Coma Light 13  (9.7)
4 Edge of Disgrace  (9.6)
5 No Bounds  (9.6)
6 Comaland 100%  (9.6)
7 Uncensored  (9.6)
8 The Ghost  (9.6)
9 Wonderland XIV  (9.6)
10 Bromance  (9.6)
Top onefile Demos
1 Party Elk 2  (9.7)
2 Cubic Dream  (9.6)
3 Copper Booze  (9.5)
4 Rainbow Connection  (9.5)
5 TRSAC, Gabber & Pebe..  (9.5)
6 Onscreen 5k  (9.5)
7 Dawnfall V1.1  (9.5)
8 Quadrants  (9.5)
9 Daah, Those Acid Pil..  (9.5)
10 Birth of a Flower  (9.5)
Top Groups
1 Booze Design  (9.3)
2 Nostalgia  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Crest  (9.3)
Top Coders
1 Axis  (9.8)
2 Graham  (9.8)
3 Lft  (9.8)
4 Crossbow  (9.8)
5 HCL  (9.8)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.069 sec.