Trig Lookup Tables

BlitzMax Forums/BlitzMax Programming/Trig Lookup Tables

Czar Flavius(Posted 2010) [#1]
Here are some fast trig lookup tables. The tables are populated using MAPM, but you could easily replace this with the built-in trig functions if you want. The results are not entirely accurate, but (I hope) accurate enough for a game and very fast.

Decimals are handled in an unusual way using integers. For example, 3600 is 360 degrees. 450 is 45 degrees. 705 is 70.5 degrees. For results, 1000 is 1.000. 743 is 0.743 5829 is 5.829. The factors for this are stored in constants. I haven't tested with other factors so I can't say that will work.

On my computer it takes 2 seconds to load all three tables, which isn't bad! To calculate every 0.1th angle from 0 to 360 degrees took 0 milliseconds for the fast trig and 2 milliseconds for built-in trig.

Strict

Import bah.mapm

Const trig_factor = 3, trig_ten = 10 ^ trig_factor

Const angle_factor = 1, angle_ten = 10 ^ 1, angle_360 = 360 * angle_ten

Function fix_angle:Int(angle:Int)
	If angle >= 0
		Return angle Mod angle_360
	Else
		Return angle - (angle_360 * (angle/angle_360 - 1))
	End If
End Function

Global temp:TMAPM = New TMAPM

Global sin_table:Int[]
Function load_sin_table()
	If sin_table.Length = 0
		sin_table = New Int[angle_360]
		For Local i = 0 Until angle_360
			temp.SetDouble(i/Float(angle_ten))
			Local result:TMAPM = temp.Sin(trig_factor)
			temp.SetInt(trig_ten)
			result = result.Multiply(temp)
			sin_table[i] = Int(result.ToIntString())
		Next
	End If
End Function

Function fast_sin:Int(a)
	Return sin_table[fix_angle(a)]
End Function

Global cos_table:Int[]
Function load_cos_table()
	If cos_table.Length = 0
		cos_table = New Int[angle_360]
		For Local i = 0 Until angle_360
			temp.SetDouble(i/Float(angle_ten))
			Local result:TMAPM = temp.cos(trig_factor)
			temp.SetInt(trig_ten)
			result = result.Multiply(temp)
			cos_table[i] = Int(result.ToIntString())
		Next
	End If
End Function

Function fast_cos:Int(a)
	Return cos_table[fix_angle(a)]
End Function

Global tan_table:Int[]
Function load_tan_table()
	If tan_table.Length = 0
		tan_table = New Int[angle_360]
		For Local i = 0 Until angle_360
			temp.SetDouble(i/Float(angle_ten))
			Local result:TMAPM = temp.tan(trig_factor)
			temp.SetInt(trig_ten)
			result = result.Multiply(temp)
			tan_table[i] = Int(result.ToIntString())
		Next
	End If
End Function

Function fast_tan:Int(a)
	Return tan_table[fix_angle(a)]
End Function

Function load_trig()
	load_sin_table()
	load_cos_table()
	load_tan_table()
End Function



Local time

time = MilliSecs()
load_trig()
Print "It took " + String(MilliSecs()-time) + " milliseconds to load the tables."

time = MilliSecs()
For Local i = 0 To 3600
	fast_sin(i)
	fast_cos(i)
	fast_tan(i)
Next
Print "It took " + String(MilliSecs()-time) + " milliseconds for fast trig."

time = MilliSecs()
For Local i:Float = 0 To 360 Step 0.1
	Sin(i)
	Cos(i)
	Tan(i)
Next
Print "It took " + String(MilliSecs()-time) + " milliseconds for normal trig."



Czar Flavius(Posted 2010) [#2]
I've made an ATan look up table which was a challenge. I know that there is a way to improve the find function (using binary search for example) but it's fast enough for me to leave as it is just now.

Const small_arc_tan_results = 20000
Const big_arc_tan_results = 60
Const small_range = 20
Const big_range = 60

Global arc_tan_table:Int[][]

Function load_arc_tan_table()
	If arc_tan_table.Length = 0
		arc_tan_table = New Int[][2]
		Local small:Int[] = New Int[small_arc_tan_results*2]
		Local big:Int[] = New Int[big_arc_tan_results*2]
		arc_tan_table[0] = small
		arc_tan_table[1] = big
		
		For Local i = 0 Until small_range * 1000
			small[i+small_arc_tan_results] = find_tan(i)
			small[-i+small_arc_tan_results] = find_tan(-i)
		Next
		
		For Local i = small_range Until big_range
			big[i+big_arc_tan_results] = find_tan(i*1000)
			big[-i+big_arc_tan_results] = find_tan(-i*1000)
		Next
	End If
End Function

Function fast_arc_tan:Int(a)
	Local b = a/tan_ten
	If Abs(b) >= 60 Then Return 90 * angle_ten
	If Abs(b) >= 20 'above 20
		Return arc_tan_table[1][b+big_arc_tan_results]
	Else 'below 20
		Return arc_tan_table[0][a+small_arc_tan_results]
	End If
End Function

Function find_tan:Int(a)
	'note improve
	For Local i = 901 Until 1800
		Local t = fast_tan(i)
		If t >= a
			Return i-1800
		End If
	Next
	For Local i = 0 Until 900
		Local t = fast_tan(i)
		If t >= a
			Return i
		End If
	Next
	Return 900
End Function