Coder Competition - Size Coding Sin Table Generator

[DanScott]

I was watching the LoveByte Demo Party, and loved seeing all these small intros & routines, but was surprised at the lack of Amiga entries there... there was only one small Amiga production (32bytes) by Blueberry, that although impressive (given the size), didn't really do a great deal.

This got me thinking about size coding, and about things that you might need in a small intro. One of these things is a sine (sin) table generator.

So here's the competition:

Generate a sine table with 1024 word entries with a range +16384 to -16384 of one full cycle a sine wave (0 to 2PI radians)

• Assume address register A0 on entry points to the start of 2048 bytes of sine table.
  
• Assume that those 2048 bytes are not cleared/zero
  
• Entries 0 and 512 in table must be zero
  
• Vanilla 68k only. RTS is not counted in code size. No calling of library functions (directly or indirectly).
  
• Maximum error for each entry must be under 5% (just to prevent people coding a simple triangle wave and claiming it's a sine wave ). Hoping people can get down to less than 1% error though in a small code size (I have). Error calculated for each entry in the table as: ( Difference / Correct Value ) * 100
  

Competition is for the smallest code size.




For reference, the following c# code was used to generate an accurate sine table rounded to nearest:

int[] SinTable = new int [1024];

for ( int i = 0; i < 1024; i++ )
{
	float t = Mathf.PI*2.0f;
	t = ( t / 1024.0f ) * (float)i;
	SinTable[i] = Mathf.RoundToInt( Mathf.Sin(t) * 16384.0f );
}

output as data:

     dc.w $0000,$0065,$00c9,$012e,$0192,$01f7,$025b,$02c0,$0324,$0388,$03ed,$0451,$04b5,$051a,$057e,$05e2
     dc.w $0646,$06aa,$070e,$0772,$07d6,$0839,$089d,$0901,$0964,$09c7,$0a2b,$0a8e,$0af1,$0b54,$0bb7,$0c1a
     dc.w $0c7c,$0cdf,$0d41,$0da4,$0e06,$0e68,$0eca,$0f2b,$0f8d,$0fee,$1050,$10b1,$1112,$1173,$11d3,$1234
     dc.w $1294,$12f4,$1354,$13b4,$1413,$1473,$14d2,$1531,$1590,$15ee,$164c,$16ab,$1709,$1766,$17c4,$1821
     dc.w $187e,$18db,$1937,$1993,$19ef,$1a4b,$1aa7,$1b02,$1b5d,$1bb8,$1c12,$1c6c,$1cc6,$1d20,$1d79,$1dd3
     dc.w $1e2b,$1e84,$1edc,$1f34,$1f8c,$1fe3,$203a,$2091,$20e7,$213d,$2193,$21e8,$223d,$2292,$22e7,$233b
     dc.w $238e,$23e2,$2435,$2488,$24da,$252c,$257e,$25cf,$2620,$2671,$26c1,$2711,$2760,$27af,$27fe,$284c
     dc.w $289a,$28e7,$2935,$2981,$29ce,$2a1a,$2a65,$2ab0,$2afb,$2b45,$2b8f,$2bd8,$2c21,$2c6a,$2cb2,$2cfa
     dc.w $2d41,$2d88,$2dcf,$2e15,$2e5a,$2e9f,$2ee4,$2f28,$2f6c,$2faf,$2ff2,$3034,$3076,$30b8,$30f9,$3139
     dc.w $3179,$31b9,$31f8,$3236,$3274,$32b2,$32ef,$332c,$3368,$33a3,$33df,$3419,$3453,$348d,$34c6,$34ff
     dc.w $3537,$356e,$35a5,$35dc,$3612,$3648,$367d,$36b1,$36e5,$3718,$374b,$377e,$37b0,$37e1,$3812,$3842
     dc.w $3871,$38a1,$38cf,$38fd,$392b,$3958,$3984,$39b0,$39db,$3a06,$3a30,$3a59,$3a82,$3aab,$3ad3,$3afa
     dc.w $3b21,$3b47,$3b6d,$3b92,$3bb6,$3bda,$3bfd,$3c20,$3c42,$3c64,$3c85,$3ca5,$3cc5,$3ce4,$3d03,$3d21
     dc.w $3d3f,$3d5b,$3d78,$3d93,$3daf,$3dc9,$3de3,$3dfc,$3e15,$3e2d,$3e45,$3e5c,$3e72,$3e88,$3e9d,$3eb1
     dc.w $3ec5,$3ed8,$3eeb,$3efd,$3f0f,$3f20,$3f30,$3f40,$3f4f,$3f5d,$3f6b,$3f78,$3f85,$3f91,$3f9c,$3fa7
     dc.w $3fb1,$3fbb,$3fc4,$3fcc,$3fd4,$3fdb,$3fe1,$3fe7,$3fec,$3ff1,$3ff5,$3ff8,$3ffb,$3ffd,$3fff,$4000
     dc.w $4000,$4000,$3fff,$3ffd,$3ffb,$3ff8,$3ff5,$3ff1,$3fec,$3fe7,$3fe1,$3fdb,$3fd4,$3fcc,$3fc4,$3fbb
     dc.w $3fb1,$3fa7,$3f9c,$3f91,$3f85,$3f78,$3f6b,$3f5d,$3f4f,$3f40,$3f30,$3f20,$3f0f,$3efd,$3eeb,$3ed8
     dc.w $3ec5,$3eb1,$3e9d,$3e88,$3e72,$3e5c,$3e45,$3e2d,$3e15,$3dfc,$3de3,$3dc9,$3daf,$3d93,$3d78,$3d5b
     dc.w $3d3f,$3d21,$3d03,$3ce4,$3cc5,$3ca5,$3c85,$3c64,$3c42,$3c20,$3bfd,$3bda,$3bb6,$3b92,$3b6d,$3b47
     dc.w $3b21,$3afa,$3ad3,$3aab,$3a82,$3a59,$3a30,$3a06,$39db,$39b0,$3984,$3958,$392b,$38fd,$38cf,$38a1
     dc.w $3871,$3842,$3812,$37e1,$37b0,$377e,$374b,$3718,$36e5,$36b1,$367d,$3648,$3612,$35dc,$35a5,$356e
     dc.w $3537,$34ff,$34c6,$348d,$3453,$3419,$33df,$33a3,$3368,$332c,$32ef,$32b2,$3274,$3236,$31f8,$31b9
     dc.w $3179,$3139,$30f8,$30b8,$3076,$3034,$2ff2,$2faf,$2f6c,$2f28,$2ee4,$2e9f,$2e5a,$2e15,$2dcf,$2d88
     dc.w $2d41,$2cfa,$2cb2,$2c6a,$2c21,$2bd8,$2b8f,$2b45,$2afb,$2ab0,$2a65,$2a1a,$29ce,$2981,$2935,$28e7
     dc.w $289a,$284c,$27fe,$27af,$2760,$2711,$26c1,$2670,$2620,$25cf,$257e,$252c,$24da,$2488,$2435,$23e2
     dc.w $238e,$233b,$22e7,$2292,$223d,$21e8,$2193,$213d,$20e7,$2091,$203a,$1fe3,$1f8c,$1f34,$1edc,$1e84
     dc.w $1e2b,$1dd3,$1d79,$1d20,$1cc6,$1c6c,$1c12,$1bb8,$1b5d,$1b02,$1aa7,$1a4b,$19ef,$1993,$1937,$18db
     dc.w $187e,$1821,$17c4,$1766,$1709,$16ab,$164c,$15ee,$1590,$1531,$14d2,$1473,$1413,$13b4,$1354,$12f4
     dc.w $1294,$1234,$11d3,$1173,$1112,$10b1,$1050,$0fee,$0f8d,$0f2b,$0eca,$0e68,$0e06,$0da4,$0d41,$0cdf
     dc.w $0c7c,$0c1a,$0bb7,$0b54,$0af1,$0a8e,$0a2b,$09c7,$0964,$0901,$089d,$0839,$07d6,$0772,$070e,$06aa
     dc.w $0646,$05e2,$057e,$051a,$04b5,$0451,$03ed,$0388,$0324,$02bf,$025b,$01f7,$0192,$012e,$00c9,$0065
     dc.w $0000,$ff9b,$ff37,$fed2,$fe6e,$fe09,$fda5,$fd41,$fcdc,$fc78,$fc13,$fbaf,$fb4b,$fae6,$fa82,$fa1e
     dc.w $f9ba,$f956,$f8f2,$f88e,$f82a,$f7c7,$f763,$f6ff,$f69c,$f639,$f5d5,$f572,$f50f,$f4ac,$f449,$f3e6
     dc.w $f384,$f321,$f2bf,$f25c,$f1fa,$f198,$f136,$f0d5,$f073,$f012,$efb0,$ef4f,$eeee,$ee8d,$ee2d,$edcc
     dc.w $ed6c,$ed0c,$ecac,$ec4c,$ebed,$eb8d,$eb2e,$eacf,$ea70,$ea12,$e9b4,$e955,$e8f7,$e89a,$e83c,$e7df
     dc.w $e782,$e725,$e6c9,$e66d,$e611,$e5b5,$e559,$e4fe,$e4a3,$e448,$e3ee,$e394,$e33a,$e2e0,$e287,$e22d
     dc.w $e1d5,$e17c,$e124,$e0cc,$e074,$e01d,$dfc6,$df6f,$df19,$dec3,$de6d,$de18,$ddc3,$dd6e,$dd19,$dcc5
     dc.w $dc72,$dc1e,$dbcb,$db78,$db26,$dad4,$da82,$da31,$d9e0,$d98f,$d93f,$d8ef,$d8a0,$d851,$d802,$d7b4
     dc.w $d766,$d719,$d6cb,$d67f,$d632,$d5e6,$d59b,$d550,$d505,$d4bb,$d471,$d428,$d3df,$d396,$d34e,$d306
     dc.w $d2bf,$d278,$d231,$d1eb,$d1a6,$d161,$d11c,$d0d8,$d094,$d051,$d00e,$cfcc,$cf8a,$cf48,$cf08,$cec7
     dc.w $ce87,$ce47,$ce08,$cdca,$cd8c,$cd4e,$cd11,$ccd4,$cc98,$cc5d,$cc21,$cbe7,$cbad,$cb73,$cb3a,$cb01
     dc.w $cac9,$ca92,$ca5b,$ca24,$c9ee,$c9b8,$c983,$c94f,$c91b,$c8e8,$c8b5,$c882,$c850,$c81f,$c7ee,$c7be
     dc.w $c78f,$c75f,$c731,$c703,$c6d5,$c6a8,$c67c,$c650,$c625,$c5fa,$c5d0,$c5a7,$c57e,$c555,$c52d,$c506
     dc.w $c4df,$c4b9,$c493,$c46e,$c44a,$c426,$c403,$c3e0,$c3be,$c39c,$c37b,$c35b,$c33b,$c31c,$c2fd,$c2df
     dc.w $c2c1,$c2a5,$c288,$c26d,$c251,$c237,$c21d,$c204,$c1eb,$c1d3,$c1bb,$c1a4,$c18e,$c178,$c163,$c14f
     dc.w $c13b,$c128,$c115,$c103,$c0f1,$c0e0,$c0d0,$c0c0,$c0b1,$c0a3,$c095,$c088,$c07b,$c06f,$c064,$c059
     dc.w $c04f,$c045,$c03c,$c034,$c02c,$c025,$c01f,$c019,$c014,$c00f,$c00b,$c008,$c005,$c003,$c001,$c000
     dc.w $c000,$c000,$c001,$c003,$c005,$c008,$c00b,$c00f,$c014,$c019,$c01f,$c025,$c02c,$c034,$c03c,$c045
     dc.w $c04f,$c059,$c064,$c06f,$c07b,$c088,$c095,$c0a3,$c0b1,$c0c0,$c0d0,$c0e0,$c0f1,$c103,$c115,$c128
     dc.w $c13b,$c14f,$c163,$c178,$c18e,$c1a4,$c1bb,$c1d3,$c1eb,$c204,$c21d,$c237,$c251,$c26d,$c288,$c2a5
     dc.w $c2c1,$c2df,$c2fd,$c31c,$c33b,$c35b,$c37b,$c39c,$c3be,$c3e0,$c403,$c426,$c44a,$c46e,$c493,$c4b9
     dc.w $c4df,$c506,$c52d,$c555,$c57e,$c5a7,$c5d0,$c5fa,$c625,$c650,$c67c,$c6a8,$c6d5,$c703,$c731,$c75f
     dc.w $c78f,$c7be,$c7ee,$c81f,$c850,$c882,$c8b5,$c8e8,$c91b,$c94f,$c983,$c9b8,$c9ee,$ca24,$ca5b,$ca92
     dc.w $cac9,$cb01,$cb3a,$cb73,$cbad,$cbe7,$cc21,$cc5d,$cc98,$ccd4,$cd11,$cd4e,$cd8c,$cdca,$ce08,$ce47
     dc.w $ce87,$cec7,$cf08,$cf48,$cf8a,$cfcc,$d00e,$d051,$d094,$d0d8,$d11c,$d161,$d1a6,$d1eb,$d231,$d278
     dc.w $d2bf,$d306,$d34e,$d396,$d3df,$d428,$d471,$d4bb,$d505,$d550,$d59b,$d5e6,$d632,$d67f,$d6cb,$d719
     dc.w $d766,$d7b4,$d802,$d851,$d8a0,$d8ef,$d93f,$d990,$d9e0,$da31,$da82,$dad4,$db26,$db78,$dbcb,$dc1e
     dc.w $dc72,$dcc5,$dd19,$dd6e,$ddc3,$de18,$de6d,$dec3,$df19,$df6f,$dfc6,$e01d,$e074,$e0cc,$e124,$e17c
     dc.w $e1d5,$e22d,$e287,$e2e0,$e33a,$e394,$e3ee,$e448,$e4a3,$e4fe,$e559,$e5b5,$e611,$e66d,$e6c9,$e725
     dc.w $e782,$e7df,$e83c,$e89a,$e8f7,$e955,$e9b4,$ea12,$ea70,$eacf,$eb2e,$eb8d,$ebed,$ec4c,$ecac,$ed0c
     dc.w $ed6c,$edcc,$ee2d,$ee8d,$eeee,$ef4f,$efb0,$f012,$f073,$f0d5,$f136,$f198,$f1fa,$f25c,$f2bf,$f321
     dc.w $f384,$f3e6,$f449,$f4ac,$f50f,$f572,$f5d5,$f639,$f69c,$f6ff,$f763,$f7c7,$f82a,$f88e,$f8f2,$f956
     dc.w $f9ba,$fa1e,$fa82,$fae6,$fb4b,$fbaf,$fc13,$fc78,$fcdc,$fd41,$fda5,$fe09,$fe6e,$fed2,$ff37,$ff9b

[ross]

Hi Dan, there is a problem here.

I've already published a 30 byte single quadrant generator for a 2.14 2048 points sine table.
It's not public but available...

EDIT
It generate:

0000  0000 002F 005F 008F 00BF 00EF 011F 014F
0010  017F 01AF 01DF 020F 023F 026F 029F 02CF
0020  02FF 032F 035F 038F 03BF 03EF 041F 044F
0030  047F 04AF 04DE 050E 053E 056E 059E 05CE
0040  05FE 062D 065D 068D 06BD 06EC 071C 074C
0050  077C 07AB 07DB 080B 083A 086A 089A 08C9
0060  08F9 0928 0958 0987 09B7 09E6 0A16 0A45
0070  0A75 0AA4 0AD4 0B03 0B32 0B62 0B91 0BC0
0080  0BF0 0C1F 0C4E 0C7D 0CAC 0CDB 0D0B 0D3A
0090  0D69 0D98 0DC7 0DF6 0E25 0E54 0E82 0EB1
00A0  0EE0 0F0F 0F3E 0F6D 0F9B 0FCA 0FF9 1027
00B0  1056 1084 10B3 10E1 1110 113E 116D 119B
00C0  11CA 11F8 1226 1254 1282 12B1 12DF 130D
00D0  133B 1369 1397 13C5 13F3 1420 144E 147C
00E0  14AA 14D7 1505 1533 1560 158E 15BB 15E9
00F0  1616 1643 1671 169E 16CB 16F8 1725 1752
0100  1780 17AC 17D9 1806 1833 1860 188D 18B9
0110  18E6 1912 193F 196C 1998 19C4 19F1 1A1D
0120  1A49 1A75 1AA1 1ACE 1AFA 1B26 1B51 1B7D
0130  1BA9 1BD5 1C00 1C2C 1C58 1C83 1CAF 1CDA
0140  1D06 1D31 1D5C 1D87 1DB2 1DDD 1E08 1E33
0150  1E5E 1E89 1EB4 1EDE 1F09 1F33 1F5E 1F88
0160  1FB3 1FDD 2007 2031 205C 2086 20AF 20D9
0170  2103 212D 2157 2180 21AA 21D3 21FD 2226
0180  2250 2279 22A2 22CB 22F4 231D 2346 236E
0190  2397 23C0 23E8 2411 2439 2462 248A 24B2
01A0  24DA 2502 252A 2552 257A 25A2 25C9 25F1
01B0  2618 2640 2667 268E 26B6 26DD 2704 272A
01C0  2752 2778 279F 27C5 27EC 2812 2839 285F
01D0  2885 28AB 28D1 28F7 291D 2943 2968 298E
01E0  29B4 29D9 29FE 2A24 2A49 2A6E 2A93 2AB8
01F0  2ADD 2B01 2B26 2B4A 2B6F 2B93 2BB7 2BDB
0200  2C00 2C23 2C47 2C6B 2C8F 2CB2 2CD6 2CF9
0210  2D1C 2D3F 2D63 2D86 2DA9 2DCB 2DEE 2E10
0220  2E33 2E55 2E78 2E9A 2EBC 2EDE 2F00 2F22
0230  2F44 2F65 2F87 2FA8 2FC9 2FEA 300B 302C
0240  304E 306E 308F 30AF 30D0 30F0 3110 3130
0250  3151 3170 3190 31B0 31D0 31EF 320E 322D
0260  324D 326B 328A 32A9 32C8 32E7 3305 3323
0270  3342 3360 337E 339C 33BA 33D7 33F5 3412
0280  3430 344C 346A 3487 34A4 34C0 34DD 34F9
0290  3516 3532 354E 356A 3586 35A2 35BD 35D9
02A0  35F4 360F 362A 3646 3661 367B 3696 36B0
02B0  36CB 36E5 36FF 3719 3733 374D 3766 3780
02C0  379A 37B2 37CC 37E5 37FE 3816 382F 3847
02D0  3860 3878 3890 38A8 38C0 38D7 38EF 3906
02E0  391E 3935 394C 3963 3979 3990 39A6 39BD
02F0  39D3 39E9 39FF 3A15 3A2A 3A40 3A55 3A6A
0300  3A80 3A94 3AA9 3ABE 3AD2 3AE7 3AFB 3B0F
0310  3B23 3B36 3B4A 3B5E 3B71 3B84 3B97 3BAA
0320  3BBD 3BD0 3BE2 3BF5 3C07 3C19 3C2B 3C3C
0330  3C4E 3C5F 3C71 3C82 3C93 3CA4 3CB4 3CC5
0340  3CD6 3CE5 3CF6 3D06 3D16 3D25 3D34 3D44
0350  3D53 3D62 3D71 3D7F 3D8E 3D9C 3DAA 3DB8
0360  3DC7 3DD4 3DE2 3DEF 3DFD 3E0A 3E17 3E23
0370  3E30 3E3C 3E49 3E55 3E61 3E6D 3E78 3E84
0380  3E90 3E9A 3EA5 3EB0 3EBB 3EC5 3ED0 3EDA
0390  3EE4 3EEE 3EF7 3F01 3F0B 3F14 3F1C 3F25
03A0  3F2E 3F36 3F3F 3F47 3F4F 3F57 3F5E 3F66
03B0  3F6D 3F74 3F7B 3F82 3F89 3F8F 3F95 3F9B
03C0  3FA2 3FA7 3FAC 3FB2 3FB7 3FBC 3FC1 3FC5
03D0  3FCA 3FCE 3FD2 3FD7 3FDA 3FDE 3FE1 3FE4
03E0  3FE8 3FEA 3FED 3FF0 3FF2 3FF4 3FF6 3FF7
03F0  3FFA 3FFA 3FFC 3FFD 3FFE 3FFE 3FFF 3FFF

Perhaps the problem does not arise, and can be disqualified.
Apart that it is with double the points (but that is not a problem because it is enough to generate half of them ), maybe it is not within the tolerance of 5%.
Someone check it out, please

[DanScott]

I am currently at 58 bytes, to generate full wave @ 0.4% max error

0.4009164% max error to be precise

[ross]

Originally Posted by DanScott

I am currently at 58 bytes, to generate full wave @ 0.4% max error

0.4009164% max error to be precise

Great.

I've only two mulu, no div.

[DanScott]

I have 2 divu, no mul

[DanScott]

Anyway, this is why I though it would make a good coder competition, as there's so many different ways to do it (my algorithm I have not seen anywhere else, derived it myself, but maybe it is a derivative of something else already done...)

[ross]

Same here, in theory is original code/idea, but surely it was also thought by someone else, let alone.
But I challenge anyone to do it in 30 bytes.
Never seen similar in any Amiga intro/demo (hmm, a slightly modified version was actually used, but it comes from this )

[mr.spiv]

Down to 42 bytes, no muls or divs. Though, 512 word entries (old code).
Edit: the inner loop is 22 bytes.

[ross]

Perhaps code are based on the same idea?
The fact that we used only two multiplying factors (you directly the divisors, me the reciprocals) it makes me think..

[ross]

Originally Posted by mr.spiv

Down to 42 bytes, no muls or divs. Though, 512 word entries (old code).

Interesting

[DanScott]

So.. rules still stand... 1024 word entries 2.14 fixed point Sine.. smallest code wins

[mr.spiv]

Originally Posted by ross

Interesting

Variation it this old HAKMEM(149) circle algorithm from 70s.
NEW X = OLD X - epsilon * OLD Y
NEW Y = OLD Y + epsilon * NEW(!) X

[DanScott]

Originally Posted by mr.spiv

Variation it this old HAKMEM(149) circle algorithm from 70s.
NEW X = OLD X - epsilon * OLD Y
NEW Y = OLD Y + epsilon * NEW(!) X

That's funny.. my method is based on something that someone showed me in around 1991 (that I totally forgot about until recently), and is essentially the same thing

I presume you are using shifts ?

Anyway.. competition is on... rules are in place... let's see what people come up with

And remember, accuracy is very important

[ross]

Mine on an approximated 3rd degree Taylor series..

[mr.spiv]

Originally Posted by DanScott

I presume you are using shifts ?

Yeh, if epsilon is power of two then a shift can be used.

[Antiriad_UK]

Originally Posted by ross

Mine on an approximated 3rd degree Taylor series..

Is that the one you did for me last year? I’m using it for everything, vector rotating and general sine stuff . It’s great.

[ross]

Originally Posted by Antiriad_UK

Is that the one you did for me last year? I’m using it for everything, vector rotating and general sine stuff . It’s great.

Yep

But I think that these two alternative approaches based on the Minsky circle algorithm are really excellent competitors!

[DanScott]

I can't see (or work out) how using a shift can give both a period and an amplitude that is a power of 2 though :/

[a/b]

Currently at 32 bytes, but have a problem with #512 ;\ (max error is ~1.27%):
- Entries 0 and 512 in table must be zero

Bring the brain pain!

[Jobbo]

I'm at 24 bytes, max error 5.6%.

I'm calling that 5% Dan

How does this work, when do we post code?