Coder Competition - Size Coding Sin Table Generator

[Jobbo]

I ran both my code and Dan's and printed out the results and stuffed those in the spreadsheet.

Anyone should be able to add their own column to the spreadsheet or tweak how it calculates error.

I'm going to setup a little project where I can add any code and run it, I can put that on github when I'm done and then repopulate the spreadsheet.

[DanScott]

I'm surprised mine worked, I just typed it out of my head straight into the forum here

[Jobbo]

Here's code that'll output the results for my code and Dan's. Anyone should be able to add their own.

You can use Bartman's VSCode plugin to compile this. I'm sure many will moan about the %%d0 syntax.

But it was quick to setup and the output can be copied into a spreadsheet easily enough.

https://github.com/rjobling/SmallSin

[Edit] Also added A/B's code to github and the spreadsheet.

https://docs.google.com/spreadsheets...it?usp=sharing

[a/b]

Did some analysis of indices/data:

a=0 b=512 a*b=0 sum=0 diff=0
a=1 b=511 a*b=511 sum=511 diff=511
a=2 b=510 a*b=1020 sum=1020 diff=509
a=3 b=509 a*b=1527 sum=1527 diff=507
a=4 b=508 a*b=2032 sum=2032 diff=505
a=5 b=507 a*b=2535 sum=2535 diff=501
a=7 b=505 a*b=3535 sum=3535 diff=499
a=8 b=504 a*b=4032 sum=4032 diff=497
a=9 b=503 a*b=4527 sum=4527 diff=495
a=10 b=502 a*b=5020 sum=5020 diff=493
a=11 b=501 a*b=5511 sum=5511 diff=491
a=12 b=500 a*b=6000 sum=6000 diff=489
a=13 b=499 a*b=6487 sum=6487 diff=487
a=14 b=498 a*b=6972 sum=6972 diff=485

Update, 24 bytes and no muls (same accuracy, though):

	moveq	#0,d0
	lea	(511+2).w,a1
Loop4	subq.l	#2,a1
	move.l	d0,d2
	asr.l	#2,d2
	move.w	d2,(a0)+
	neg.w	d2
	move.w	d2,(1024-2,a0)
	add.l	a1,d0
	bne.b	Loop4

[Jobbo]

That is very cool!

[DanScott]

lea (511+2).w,a1

Nice trick.. sign extends to clear the top word. Never considered that before

[ross]

Originally Posted by DanScott

lea (511+2).w,a1

Nice trick.. sign extends to clear the top word. Never considered that before

I usually write this as:

movea.w #511+2,a1

It reminds to me that I am using a constant with a sign extension.

[Jobbo]

Ross, I added your output. Can you post byte count and code?

[DanScott]

Love the error graphs... we are plotting boobs

I need to work more on my accurate version, there's a few things I can do there to bring down the code size a bit

Hopefully will have something in the next 24 hours...obviously 24bytes is not going to be beatable (I doubt I'll get below 50 to be honest)

[ross]

Originally Posted by DanScott

Love the error graphs... we are plotting boobs

Check this:
exp(-((x-4)^2+(y-4)^2)^2/1000) + exp(-((x+4)^2+(y+4)^2)^2/1000) + 0.1exp(-((x+4)^2+(y+4)^2)^2)+0.1exp(-((x-4)^2+(y- 4)^2)^2)

Well, you can paste it in google..

[ross]

Originally Posted by Jobbo

Ross, I added your output. Can you post byte count and code?

46 byte
I'll post the code when Dan gives the green light to everyone

But just noticed one small thing and I call the referee if he lets me do it.
Since it is the extended version of the 30 bytes one for single quadrant, I usually add some code to generate 5 (to allow quick access to cos too).
So for various reasons I need the vector to be 1025 and not 1024.
I can do it?

EDIT:
Ok, I'll could do it for 1024 values but 48 byte of code.
I need to trade the two bytes losing 2000 CPU cycles (45776 vs 47826), very annoying
I would never do that in real code.

I can't wait to publish it, surely someone would be able to optimize it further.
I usually manage to optimize the main algorithm and miss the trivial optimization because I get tired of looking at it (there are several examples in the forum )

[a/b]

Originally Posted by ross

I usually write this as:

movea.w #511+2,a1

It reminds to me that I am using a constant with a sign extension.

a*

Yeah, forgot to u(pdate) the source (in case "a*" doesn't ring any bells, in asm-one it indicates modified source). Why is this relevant? Because I actually changed lea to move in this case because it's data.

[DanScott]

Originally Posted by ross

46 byte
I'll post the code when Dan gives the green light to everyone

But just noticed one small thing and I call the referee if he lets me do it.
Since it is the extended version of the 30 bytes one for single quadrant, I usually add some code to generate 5 (to allow quick access to cos too).
So for various reasons I need the vector to be 1025 and not 1024.
I can do it?

I think it would be good to keep the rules fixed as they are... I am sure your code size is going to beat mine anyway

I will be posting something tomorrow evening, I need to rework mine to save a few instructions (I'm calculating one quadrant, where I can potentially calculate all, but error might accumulate along the way doing that)

[malko]

Originally Posted by ross

Check this:
exp(-((x-4)^2+(y-4)^2)^2/1000) + exp(-((x+4)^2+(y+4)^2)^2/1000) + 0.1exp(-((x+4)^2+(y+4)^2)^2)+0.1exp(-((x-4)^2+(y- 4)^2)^2)

Well, you can paste it in google..

[ Show youtube player ]

[ross]

Originally Posted by DanScott

(I'm calculating one quadrant, where I can potentially calculate all, but error might accumulate along the way doing that)

How many byte you lose from one quadrant to four?
I have a feeling i could improve my code at this, but i can't figure out how.
My code could calculate 2 quadrants in the loop, but in order not to lose precision I maximize 16-bit operations and unfortunately I would have a part of the table with overflows, so I preferred to make only one and then derive the others.
However in my code there is not even a shift opcode, everything fits magically

[DanScott]

Originally Posted by ross

How many byte you lose from one quadrant to four?

Trying to work that out in my head here (don't have the code on this PC)...

I *think* around 14 minimum ..

[DanScott]

Loving that 24 byte version too... it's got the 5.6% inaccuracy, but perhaps that would not be noticeable in most applications... but I am a stickler for having accuracy too

[ross]

Originally Posted by DanScott

I *think* around 14 minimum ..

Well, I want these 14 bytes, I would stay to 44 bytes

Yes, the 24-byte version is awesome!

[DanScott]

Super accurate 1 quadrant version

58 bytes.. perhaps I've missed some *obvious* optimisation here

                        ; Entry a0 = Beginning of 2048 byte sine table buffer

                        lea     512(a0),a0  ; a0 = 2nd Quadrant Start
	                lea     2(a0),a1    ; a1 = 1st Quadrant End + 2
	                moveq	#11,d0      ; d0.l = x = 11
                        moveq   #1,d1
                        ror.w   #2,d1       ; d1.l = y = 16384 
	                move.w  #163,d2     ; d2 = Q = magic division value = 512/PI (162.97466)
	                move.w  #256-1,d7   ; 256 values in quadrant
.Loop
	                move.l  d1,d3	
	                divu    d2,d3
	                add.w	d3,d0       ; x = x + (y / Q)
	                move.l  d0,d3
	                divu    d2,d3
	                sub.w	d3,d1       ; y = y - (x / Q)
	                move.w  d1,d3
	                neg.w   d3
	                move.w  d3,1024(a0) ; write 4th Quadrant
                        move.w  d3,1022(a1) ; write 3rd Quadrant
                        move.w  d1,(a0)+    ; Write 2nd Quadrant
                        move.w  d1,-(a1)    ; Write 1st Quadrant
	                dbra    d7,.Loop
                        clr.w   -(a1)       ; Set SinTable index 0 to 0 
                        clr.w   (a0)        ; Set SinTable index 512 to 0
.End

Working on the smaller version, but having issues currently with the accuracy rolling into other quadrants

[ross]

Quasi-accurate 1+3 quadrant version.

48 bytes.. perhaps me too missed some optimisation here.

    lea SinEntries*2(a0),a1
    moveq   #3,d0
    ror.l   #2,d0
    moveq   #0,d1
.l  move.l  d0,d3
    move.l  d1,d2
    mulu.w  d2,d2
    sub.l   d2,d3
    swap    d3
    mulu.w  d1,d3
    swap    d3
    move.w  d3,(a0)+
    move.w  d3,-2-SinEntries(a1)
    neg.w   d3
    beq.b   .2
    move.w  d3,-(a1)
.2  move.w  d3,-2+SinEntries(a0)
    addi.w  #1<<7,d1
    bpl.b   .l
    bvs.b   .l

Initial d0 could probably be bruteforced to artificially improve precision (even if mathematically it would not be correct).
Bias now follow the sine on the lower part but using a bigger value it oscillate better near the perfect sinus.