[CSDb] - User Forums - sets of add/sub

Welcome to our latest new user maak ! (Registered 2024-04-18)

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > sets of add/sub

2017-03-18 12:02

Repose

Registered: Oct 2010
Posts: 222

sets of add/sub

I want to do a-b+c-d+e-f. I wonder if you can save some cycles somewhere? I looked at the stats of the actual numbers, no hopes there, any pair can carry/borrow with about 50% chance.

First I'll look at adding 3x 16bit adds and generalizing

Standard version
-----------------
We will keep the running sum in a register
n1,n2,n3 - numbers to add
r, r+1,... - the sum

;assume n1 stored in r
2 clc
3 lda r
3 adc n2
2 tax;n2+n1 save low byte in X
2 lda #0;small optimization first time when you know r+1 is 0.
2 adc #0; basically convert carry to 1
2 tay;16c save high byte in Y
;-- repeat for n>=3 (n is number of numbers to add)
;clc not needed
2 txa
3 adc n3
3 sta r;r+n3=n1+n2+n3 or tax until final add
2 tya
2 adc #0
3 sta r+1;16+15=31 or tay until final add
rts

In general,
Time is 16+(n-2)*13+2=18+(n-2)*13

n time, cycles
2 18 =18
3 18+13 =31
4 18+13+13 =44

Fast Version 1
--------------

2 clc

3 lda n2
3 adc r;n2+n1
2 bcs s1;2+9=11 if taken
3 adc n3
3 sta r
2 lda #0
2 adc #0
3 sta r+1;2+8+13=23 if no carry in n1+n2
rts;or bcc s2 =26
;11c
2 s1 clc;there was a carry in first add, A=n1+n2
3 adc n3
3 sta r
2 lda #1;representing the carry from n1+n2>255
2 adc #0
3 sta r+1;11+15=26 if carry in n1+n2
s2 rts;23/26, average 24.5, saving 6.5 cycles from standard (31c)
realistically always 26 or saving 5 cycles

Conclusions
Adding 3 numbers, I went from 31 to 26 cycles.

The statistics of adding 3 numbers drawn from multiplies
--------------------------------------------------------

In a partial sums routine, only some bytes of the product are added

case carries % total
l l h 2908442244 67.7 4294967296
h h l 2044355014 47.6 4294967296

Conclusions
High bytes of products are always less likely to create a carry when added to other numbers. The differences are so little that it hardly makes any difference.

ps took a while to simulate 4 billion multiplies and gather stats. I'd hate to figure out stats for larger mults, would have to actually think through it instead. But I can tell you they change quite a bit, in some cases there's hardly two carries in a row for example.

... 45 posts hidden. Click here to view all posts....

2017-03-21 14:49

ChristopherJam

Registered: Aug 2004
Posts: 1370

Quoting JackAsser

Indeed, but special care has to be taken after 256 potential overflows. That would of course imply a >16-bit result in the end.

I wonder if you could just get away with checking the Y value every N potential overflows, and just see if it has decreased since the last test... it'd be quicker than doing a branch every time.

N may well be as high as 255; I'd have to think a bit harder to be sure of that.

2017-03-21 20:08

lft

Registered: Jul 2007
Posts: 369

Quoting ChristopherJam

We're all terrible at reading each other's comments.

Whoops, you're quite right. Sorry!

2017-03-22 00:50

Fresh

Registered: Jan 2005
Posts: 101

While thinking about this topic I've come up with a completely different approach which is not ideal for this case but may be useful if we need to add more numbers. Hope this is not too off-topic.
Beware, I haven't checked if this needs some kind of CIA version fix: this works fine with old CIAs.
BTW, I'm not using the carry.

.const  zp0=$fb
.const  zp1=$fc
.const  zp2=$fd

.pc=$1000
start:
        sei
!:	bit $d011
	bpl !-   // No BLs!
	lda zp1
	sta b+1
	lda zp2
	sta c+1	
	lda #$00
	sta $dd0f
	sta $dd06
	lda #$01
	sta $dd07
	sta $dd0f		
	
	ldy zp0		// 3
b:
	ldx tab,y	// 4/5
c:
	ldy tab,x	// 4/5
	
	// Here we could add more ldx/ldy
lo:		
	ldx $dd06	// 4 => Wait=15/17	
	lda carrytab,x
	// HI/LO in A/Y
	sty $63
	sta $62
        cli
	jmp $bdd1	

	
.align $0100
tab:
.fill 512,i&$ff
carrytab:
.fill 256,[$f3-i]&$ff

2017-03-22 05:32

Repose

Registered: Oct 2010
Posts: 222

I can't follow your code yet, but an idea just came to me (which probably you used), that any addition crossing a page boundary takes one more cycle and you can simply difference the cycles to find the number of carries. Very clever!

My own idea which just came to mind based on this concept, is

addtab is a 510 byte table, starting at a page boundary (very important!), that is just a count (0,1,1...255,0..)

ldx n1
lda n2
sta sm1+1
lda n3
sta sm2+1;or just imagine the numbers are already stored there

;initialize and start the timer to a high value
lda TimerA_Low
sta start

sm1 lda addtab,x; if addtab+x crosses page, add 1 cycle
tax; transfer running sum (n1+n2) to X
sm2 lda addtab,x;add n3 to running sum
...
sta r0;the low byte of sum
lda start
sec
sbc timerAlo
sbc #some constant
sta r1;the high byte of sum

It's not fast but, it's an interesting concept that could be applied to optimized code somehow.

If I store n2,n3... directly in sm1+1, sm2+1..., then it optimizes out to:

ldx n1
sm1 lda addtab,x;n1+n2
tax
sm2 lda addtab,x;n3+ (n1+n2)
tax
sm3 lda addtab,x;n4+ (n1+n2+n3)
...
carries are time of code minus the constant 6*n (the number of values added)

This is also quite faster so it's actually practical!

I just invented the missing add instruction. The indexed addressing is doing the adds, and the timer is doing the carries, in parallel.

2017-03-22 06:33

ChristopherJam

Registered: Aug 2004
Posts: 1370

Quoting Repose

The indexed addressing is doing the adds, and the timer is doing the carries, in parallel.

which is exactly what Fresh is proposing \O/

@lft - all good, I missed that Repose was tracking the carry count in X in post #4

2017-03-22 06:41

Repose

Registered: Oct 2010
Posts: 222

Even better:

clc
lda n1
adc n2
bcs *+2;basically do nothing as quickly as possible to make carry consume one more cycle
adc n3
bcs *+2
...
sta sum
;diff timer
sta sum+1

My first method was 6/7, this one is 5/6. The probability of a carry is just under half, so basically approaches 5.5 cycles per number added.

I love to see someone's face try to decode that though, confuse the @#@ out of them :)

2017-03-22 07:18

Repose

Registered: Oct 2010
Posts: 222

You can even add/sub in the same sequence

;now do subtractions
sec
sbc n5
bcs *+2; 'subtract' one cycle from timing if there's a borrow
sbc n6
bcs *+2
...

2017-03-22 07:21

Repose

Registered: Oct 2010
Posts: 222

Why stop there?

lda n
ror
bcs *+2
x8
;diff timer
sta popcnt

Population count in 4.5 cycles per bit. Of course a table would be much faster. What else useful could you do?

2017-03-22 08:29

Repose

Registered: Oct 2010
Posts: 222

bcs/bcc, bmi/bpl, bvc can all be used in this technique to accumulate the times those flags were in a certain state. By extension, you can accumulate times a certain bit was set or value was reached, like cmp #$40:bcc *+2:
So think of the timer as an extra register that you can increment or decrement (by using the opposite branch), using branches or page crossings, that is only fast to use over a longish sequence. It can do corrections after the fact or count things. There is also a free divide, IIRC you can set the speed the timer counts? Or is it fixed to decrement each clock cycle? No matter, use the SID voice 3 output and set the frequency for a free division.

Question, what use can this be put to? And can you use the flags as part of a calculation ,while using the accumulation of times the flags happened for a parallel computation using the timer (which has no sideeffects) to do double the work? (I mean, use the branch to do one thing, then at the end do another thing with the timer value).

In another direction, can you do some computation unrolled then interrupt it at a certain time to see the value and that's your result?

example,
rol
bcs +2
inx
... x8
interrupt after 24 cycles
X will be 4-(popcnt(A and $#f)/6) or something (the full formula is kinda long)

Another idea I've used to to make 'infinite' loops that can only be stopped by an interrupt
lda #0
sta $4000
sta $4001
..
decide which area of the bitmap you want to fill
jump into the code
stop it with an interrupt
of course you can 'plot' an RTS into the middle as well, then restore it.
Interrupt idea might turn out faster

This is getting off topic though.

2017-03-22 08:42

ChristopherJam

Registered: Aug 2004
Posts: 1370

I've definitely considered using an interrupt to terminate an unrolled fill loop, but yes, plotting an RTS seemed like a saner option at the time.

Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 - Next

Refresh

Subscribe 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

Kickback
Guests online: 59

Top Demos

1 Next Level  (9.8)
2 Mojo  (9.7)
3 Coma Light 13  (9.7)
4 Edge of Disgrace  (9.6)
5 Comaland 100%  (9.6)
6 No Bounds  (9.6)
7 Uncensored  (9.6)
8 Wonderland XIV  (9.6)
9 The Ghost  (9.6)
10 Bromance  (9.6)

Top onefile Demos

1 It's More Fun to Com..  (9.9)
2 Party Elk 2  (9.7)
3 Cubic Dream  (9.6)
4 Copper Booze  (9.5)
5 Rainbow Connection  (9.5)
6 TRSAC, Gabber & Pebe..  (9.5)
7 Onscreen 5k  (9.5)
8 Dawnfall V1.1  (9.5)
9 Quadrants  (9.5)
10 Daah, Those Acid Pil..  (9.5)

Top Groups

1 Oxyron  (9.3)
2 Nostalgia  (9.3)
3 Booze Design  (9.3)
4 Censor Design  (9.3)
5 Crest  (9.3)

Top NTSC-Fixers

1 Pudwerx  (10)
2 Booze  (9.7)
3 Stormbringer  (9.7)
4 Fungus  (9.6)
5 Grim Reaper  (9.3)

Page generated in: 0.042 sec.