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: 2871		 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.
 
... 20 posts hidden. Click here to view all posts....
 
2021-07-02 10:57
Fred

Registered: Feb 2003
Posts: 285		 Quote: 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.

Correct. I now see the beauty of your version :-)

Some correction on your routine, I see that the BIGNUMBYTES isn't taken into account correctly. If you set it to e.g. 20, the number of bytes processed is 19. See my correction below.

To speed up the algorithm, I think it is best to skip zeros before going into the loop in case the number of bytes is always fixed and the value is low.

Replace:

            ldx #BIGNUMBYTES


with:

            ldx #BIGNUMBYTES + 1

-           ldy BIGNUM - 1,x
            bne longdivmod
            dex
            bne -
2021-07-02 13:50
Krill

Registered: Apr 2002
Posts: 2871		 Quoting Fred
Some correction on your routine
With BIGNUMBYTES = 1
            ldx #2; BIGNUMBYTES + 1

-           ldy BIGNUM - 1,x; BIGNUM + 1, BIGNUM + 0
            bne longdivmod
            dex
            bne -
this now iterates over 2 bignum-bytes. Likewise one to many for all other settings.

So, no, i think my code was okay.

Quoting Fred
To speed up the algorithm, I think it is best to skip zeros before going into the loop in case the number of bytes is always fixed and the value is low.
Yes. =)
Quoting Krill
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.
But i didn't add this optimisation, as i need the bytes elsewhere and it's already quick enough for my purposes. :)
2021-07-02 14:43
Fred

Registered: Feb 2003
Posts: 285		 Quote: Quoting Fred
Some correction on your routine
With BIGNUMBYTES = 1
            ldx #2; BIGNUMBYTES + 1

-           ldy BIGNUM - 1,x; BIGNUM + 1, BIGNUM + 0
            bne longdivmod
            dex
            bne -
this now iterates over 2 bignum-bytes. Likewise one to many for all other settings.

So, no, i think my code was okay.

Quoting Fred
To speed up the algorithm, I think it is best to skip zeros before going into the loop in case the number of bytes is always fixed and the value is low.
Yes. =)
Quoting Krill
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.
But i didn't add this optimisation, as i need the bytes elsewhere and it's already quick enough for my purposes. :)

ok, my conclusion was too fast, sorry about that. I retested it and you're right, it works okay.
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
Mason/Unicess
doctorfargo/Binary L..
Guests online: 65
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.7)
5 Edge of Disgrace  (9.6)
6 Uncensored  (9.6)
7 Comaland 100%  (9.6)
8 No Bounds  (9.6)
9 Aliens in Wonderland  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 Layers  (9.6)
2 Cubic Dream  (9.6)
3 Party Elk 2  (9.6)
4 Copper Booze  (9.6)
5 Rainbow Connection  (9.5)
6 It's More Fun to Com..  (9.5)
7 Dawnfall V1.1  (9.5)
8 Birth of a Flower  (9.5)
9 Daah, Those Acid Pil..  (9.5)
10 Morph  (9.5)
Top Groups
1 Nostalgia  (9.4)
2 Oxyron  (9.3)
3 Booze Design  (9.3)
4 Censor Design  (9.3)
5 Offence  (9.3)
Top Musicians
1 Rob Hubbard  (9.7)
2 Stinsen  (9.7)
3 Jeroen Tel  (9.6)
4 Linus  (9.6)
5 MacMagix  (9.6)

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