Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: STxAxTIC on January 26, 2020, 09:02:44 pm

Title: Faster trig functions: tables and interpolation
Post by: STxAxTIC on January 26, 2020, 09:02:44 pm
I had to make good on what I was lecturing bplus about (even if the recent plasma program is speedier)...

So I create two things:

1) Trig tables, strictly 360 degrees. These are lightning fast, like by an order of 10 compared to the native trig functions.

Of course, sometimes you want fractional degrees, which brings me to the next thing:

2) Two functions, InterSin and InterCos - and these can completely (maybe need to convert them to radians first) replace the native SIN and COS. Without any optimization, they are 5% to 10% faster as-is pasted below. The reason they are quick is trigonometric interpolation. Fractional angles are inspired by a first-order approximation using the derivative.

Below is the whole package. Tables, functions, testing, etc. Enjoy. (By that I mean optimize away - I bet these functions can be made faster.)

Code: QB64: [Select]
  1. ' Constants.
  2. CONST PI = 3.141592654
  3. CONST PI2 = 2 * PI
  4. CONST PI180 = PI / 180
  5.  
  6. ' Define trig tables.
  7. DIM SHARED SinTable(0 TO 359) AS SINGLE
  8. DIM SHARED CosTable(0 TO 359) AS SINGLE
  9.  
  10. ' Create trig tables in degrees.
  11. FOR k = 0 TO 359 STEP 1
  12.     SinTable(k) = SIN(_D2R(k))
  13.     CosTable(k) = COS(_D2R(k))
  15.  
  16. '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  17. ' Accuracy and testing section (optional)
  18. '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  19.  
  20. ' Speed test native SIN and COS.
  21. t = TIMER
  22. FOR k = 1 TO 10 ^ 7
  23.     a = SIN(3)
  24.     b = COS(3)
  26. PRINT "Native:": PRINT TIMER - t: PRINT
  27.  
  28. ' Speed test table SIN and COS (integer arguments only).
  29. t = TIMER
  30. FOR k = 1 TO 10 ^ 7
  31.     a = SinTable(3)
  32.     b = CosTable(3)
  34. PRINT "Table only:": PRINT TIMER - t: PRINT
  35.  
  36. ' Speed test interpolated SIN and COS (any argument).
  37. t = TIMER
  38. FOR k = 1 TO 10 ^ 7
  39.     a = InterSin(3)
  40.     b = InterCos(3)
  42. PRINT "Interpolated:": PRINT TIMER - t: PRINT
  43.  
  44. ' Error test table at standard intervals:
  45. es = 0
  46. ec = 0
  47. FOR k = 0 TO 359 STEP 1
  48.     es = es + (SIN(_D2R(k)) - SinTable(k)) ^ 2
  49.     ec = ec + (COS(_D2R(k)) - CosTable(k)) ^ 2
  51. PRINT "Total error in table:": PRINT es: PRINT ec: PRINT
  52.  
  53. ' Error test table at smaller intervals:
  54. es = 0
  55. ec = 0
  56. FOR k = 0 TO 359 STEP .1
  57.     es = es + (SIN(_D2R(k)) - InterSin(k)) ^ 2
  58.     ec = ec + (COS(_D2R(k)) - InterCos(k)) ^ 2
  60. PRINT "Total error in interpolated functions:": PRINT es: PRINT ec: PRINT
  61.  
  62. ' Exampe:
  63. PRINT "Example use:"
  65. PRINT InterSin(25)
  67. PRINT InterCos(25)
  68.  
  70.  
  71. '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  72. ' Functions
  73. '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  74.  
  75. FUNCTION InterSin (arg AS SINGLE)
  76.     z = INT(arg)
  77.     x = arg - z
  78.     IF (x = 0) THEN
  79.         InterSin = SinTable(z)
  80.     ELSE
  81.         InterSin = SinTable(z) + x * (PI180) * CosTable(z)
  82.     END IF
  84.  
  85. FUNCTION InterCos (arg AS SINGLE)
  86.     z = INT(arg)
  87.     x = arg - z
  88.     IF (x = 0) THEN
  89.         InterCos = CosTable(z)
  90.     ELSE
  91.         InterCos = CosTable(z) - x * (PI180) * SinTable(z)
  92.     END IF
  94.  
Title: Re: Faster trig functions: tables and interpolation
Post by: david_uwi on February 04, 2020, 02:08:57 pm
Back when computers were slow this was the standard method to do trig functions (look-up tables).
I still use them these days when using 8-bit microprocessors with the added advantage that the lookup table can be written to program memory (plenty of that) rather than stored in RAM (not much of that).
There are still some legacy statements in BASIC that do this like CONST (program memory is being used rather than RAM).
As I've mentioned it let me give a plug to GCBasic a QB compatible programming language for microprocessors.
Text Only | Text with Attachments