Forum
Faster Trigonometry - Printable Version

+- Forum (https://www.boriel.com/forum)
+-- Forum: Compilers and Computer Languages (https://www.boriel.com/forum/forumdisplay.php?fid=12)
+--- Forum: ZX Basic Compiler (https://www.boriel.com/forum/forumdisplay.php?fid=11)
+---- Forum: How-To & Tutorials (https://www.boriel.com/forum/forumdisplay.php?fid=13)
+---- Thread: Faster Trigonometry (/showthread.php?tid=163)

Faster Trigonometry - britlion - 02-20-2010

Sometimes we're willing to lose accuracy for speed. ZX BASIC uses the spectrum's ROM routines for many of its math functions, and as a result of them being general purpose routines that use 40 bit numbers, well, they can be a bit slow sometimes.

See my article on square roots, for a good example.

Here is a routine to produce SIN(angle) - where angle is in degrees. It uses a lookup table to calculate sin values, and it's a very quick and dirty method, in that it only actually knows 32 angles, and those to only 8 bit precision. It does linear interpolation between these known angles, however, so that does improve things somewhat.

I was actually surprised how precise it was - it's good for at least 2 decimal places, probably 3 as a rule of thumb. The average error is 0.002 That's probably good enough for games that need to calculate angles. It's about 4-5 times faster than the SIN(FLOAT) function, and not even written in native assembler.

If you need better accuracy, it would be fairly easy to change the method to use a bigger table - perhaps 2 bytes per entry, even.

Remember to work out COS and TAN can also use this function - COS is SIN(90+x) and TAN is SIN(x)/COS(x). It should be easy to write COSINE and TANGENT functions to do the adjustments and call the SINE function.

(And this one I didn't copy. It's all mine! Bugs and all. And now it's free for anyone to use.)

Code:
FUNCTION SINE(num as FIXED) as FIXED
DIM quad as byte
DIM est1,dif as uByte

while num>360
  num=num-360
end while

IF num>180 then
    quad=-1
    num=num-180
ELSE
    quad=1
END IF

IF num>90 then num=180-num: end if


num=((num*31)/90)
dif=num : rem Cast to byte loses decimal
num=num-dif : rem so this is just the decimal bit


est1=PEEK (@sinetable+dif)
dif=PEEK (@sinetable+dif+1)-est1 : REM this is just the difference to the next up number.

num=est1+(num*dif): REM base +interpolate to the next value.

return (num/255)*quad


sinetable:
asm
DEFB 000,013,026,038,051,064,076,088
DEFB 100,112,123,134,145,156,166,175
DEFB 184,193,201,209,216,223,229,234
DEFB 239,243,247,250,252,254,255,255
end asm
END FUNCTION


Re: Faster Trigonometry - boriel - 02-21-2010

britlion Wrote:Sometimes we're willing to lose accuracy for speed. ZX BASIC uses the spectrum's ROM routines for many of its math functions, and as a result of them being general purpose routines that use 40 bit numbers, well, they can be a bit slow sometimes.

See my article on square roots, for a good example.

Here is a routine to produce SIN(angle) - where angle is in degrees. It uses a lookup table to calculate sin values, and it's a very quick and dirty method, in that it only actually knows 32 angles, and those to only 8 bit precision. It does linear interpolation between these known angles, however, so that does improve things somewhat.

I was actually surprised how precise it was - it's good for at least 2 decimal places, probably 3 as a rule of thumb. The average error is 0.002 That's probably good enough for games that need to calculate angles. It's about 4-5 times faster than the SIN(FLOAT) function, and not even written in native assembler.

If you need better accuracy, it would be fairly easy to change the method to use a bigger table - perhaps 2 bytes per entry, even.

Remember to work out COS and TAN can also use this function - COS is SIN(90+x) and TAN is SIN(x)/COS(x). It should be easy to write COSINE and TANGENT functions to do the adjustments and call the SINE function.

(And this one I didn't copy. It's all mine! Bugs and all. And now it's free for anyone to use.)

Great :!: :!: :!: :o
I think this should go in the Library/ as Fsin, fcos, ftan, for example??? What do you think?
On the other hand, I think you must be included as a co-author of the ZX Basic framework. Tongue If you are reluctant, please tell me. But your contributions are really importants and you must appear as a coauthor, etc... both in documentation, Wiki, and so on.

Re: Faster Trigonometry - britlion - 02-21-2010

boriel Wrote:Great :!: :!: :!: :o
I think this should go in the Library/ as Fsin, fcos, ftan, for example??? What do you think?
On the other hand, I think you must be included as a co-author of the ZX Basic framework. Tongue If you are reluctant, please tell me. But your contributions are really importants and you must appear as a coauthor, etc... both in documentation, Wiki, and so on.

I think it would work there. The thing about this sort of function though is you can write a very fast very big and very accurate one - based on a lookup table, or a really tiny but very slow one (use the ROM) - or anything in between.

Right now I've thought of a way I might be able to speed it up AND make it more accurate, though.

As for the credit - you have done all the hard work. I've just broken it repeatedly :twisted:

But it would be nice for some thanks on there, yes. I really do appreciate the offer. Don't forget to mention LCD though :wink:


Now I've got my computer running again, I should be able to look at the new version. I had to reinstall the operating system!

Re: Faster Trigonometry - britlion - 02-28-2010

Here's a full set of functions, with a slightly higher accuracy (at a slightly larger cost - this one is tight to within 2 degrees, and interpolates anything in  between. As a result it needs 46 bytes for the table instead of the 33 used further up.) I figured that to use things like TAN - which divides one by the other - it might not hurt to tighten it a little; since that multiplies the error up!

It's now accurate to about 0.25% on average over a full circle. Slightly less for TAN values for the reasons listed above.


Code:
FUNCTION Fsin(num as FIXED) as FIXED
DIM quad as byte
DIM est1,dif as uByte

while num>360
  num=num-360
end while

while num<0
num=num+360
end while

IF num>180 then
  quad=-1
  num=num-180
ELSE
  quad=1
END IF

IF num>90 then num=180-num: end if

num=num/2
dif=num : rem Cast to byte loses decimal
num=num-dif : rem so this is just the decimal bit


est1=PEEK (@sinetable+dif)
dif=PEEK (@sinetable+dif+1)-est1 : REM this is just the difference to the next up number.

num=est1+(num*dif): REM base +interpolate to the next value.

return (num/255)*quad


sinetable:
asm
DEFB 000,009,018,027,035,044,053,062
DEFB 070,079,087,096,104,112,120,127
DEFB 135,143,150,157,164,171,177,183
DEFB 190,195,201,206,211,216,221,225
DEFB 229,233,236,240,243,245,247,249
DEFB 251,253,254,254,255,255
end asm
END FUNCTION

Code:
FUNCTION Fcos(num as FIXED) as FIXED
return Fsin(90-num)
END FUNCTION

Code:
FUNCTION Ftan(num as FIXED) as FIXED
return Fsin(num)/Fsin(90-num)
END FUNCTION