Battlefront3.net

[Arosenivai]

I'm running into trouble with the sine and cosine, asine and acosine methods offered by cmath. I mean they're stable and efficient memory-wise, but is a bit lacking when it comes to the speed department. I mean running the function 2 million times takes up 44 milliseconds (as opposed to a simple cross product method in C code is 5 milliseconds, and in assembly is 3 milliseconds ), so running the sin and cos function roughly 90,000 times per second with that kind of slowness is out of the question. I'm only familiar with Taylor series, and exponential approximations ( quadratic, cubic, et cetera ), and I'm looking for more stable approximations for sin and cosine along with asine and acos. Any ideas?

[Sam]

What problem are you trying to solve with the trig functions?

and how accurate do you need the calculations to be?

[Arosenivai]

I would prefer them to be relatively stable, but I'm going to have to run a stabilization method anyway at least once a second. It's for my physics engine, and the speed of the basic trig functions (offered by cmath) isn't covering it ( part of the reasons is exception throwing. ). Mainly the trigonometry is used for establishing rotational Unit Quaternions. (and extensions thereof). I would prefer accuracy to be < .01% but I know that's going to be hard. I'm more interested in the error of the formula sinapprox( angle )^2 + cosapprox( angle) ^2 ==1, than I'm worried about sinapprox( angle ) == sin(angle).

[Matthew]

I'm not sure of the fastest ways to calculate sine values but the standard c functions should certainly be the fastest way to create accurate (Limited by computer storage) values for trigonometric functions. If the method uses a series, you could copy the method and reduce the number of terms, for speed traded for accuracy.

I once made my own sine generator in python. The series for sine (backwards) I have as this:

x^25/15511210043330985984000000-x^23/25852016738884976640000+x^21/51090942171709440000-x^19/121645100408832000+x^17/355687428096000-x^15/1307674368000+x^13/6227020800-x^11/39916800+x^9/362880-x^7/5040+x^5/120-x^3/6+x

The denominator, is factorial based, while the power is linear. The denominator becomes large fast. The number of terms in that example is large enough to create an accurate answer for 90 degrees. I mirrored other values.

You can simply cut a few terms to increase speed but I'm sure the c functions would use a much more complex algorithm to solve sine values. The functions will surely also be optimised in assembly.

If anyone is interested here's my full python program:

Code: Select all

#!/usr/bin/env python2.3
#
#  Sine Generator for accurate Sine, Cosine and Tangent functions
#
#  Created by Matthew Mitchell on 13/09/2009.
#  Copyright (c) 2009 Matthew Mitchell. All rights reserved.
#
def sin0tohalfpi(x):
	#Works out with only enough accuracy for the 13dps, the sine wave from 0 to pi/2 in radians. Symmetry can be used to work out any value. It's the first few terms in a series that generates the sine wave with x added. A term is x^(4r+1)/(4r+1)!-x^(4r-1)/(4r-1)!, that goes from 1 to infinity. The more terms, the more accurate. 6 terms is used here.
	return x**25/15511210043330985984000000-x**23/25852016738884976640000+x**21/51090942171709440000-x**19/121645100408832000+x**17/355687428096000-x**15/1307674368000+x**13/6227020800-x**11/39916800+x**9/362880-x**7/5040+x**5/120-x**3/6+x
def sin(x,d=False):
	if d:
		#Convert to radians
		x = x*3.1415926535897931/180
	if int(x/1.570796326794897) % 2: #True if on the second part of the curver
		a = sin0tohalfpi(3.1415926535897931 - (x % 3.1415926535897931))
	else:
		a = sin0tohalfpi(x % 3.1415926535897931)
	if int(x/3.1415926535897931) % 2: #True if the value is negative.
		a = - a
	return round(a,13) #A decimal to 13dp is more than adequate and gives 100% accuracy to this precision.
def cos(x,d = False):
	#Quite simply call the sin function with 90 degrees or pi/2 radians added to x
	if d:
		return sin(x + 90,d)
	else:
		return sin(x + 1.570796326794897,d)
def tan(x,d = False):
	#sin(x)/cos(x) = tan(x). Knowing this, it's simply done. Remember if cos(x) is 0, it's impossible.
	cosine = cos(x,d)
	if cosine == 0:
		return float("nan")
	return sin(x,d)/cosine
if __name__ == "__main__":
	print "Sine, Cosine and Tangent Function Demo."
	print
	import math as maths
	import time
	import psyco
	psyco.bind(sin0tohalfpi)
	psyco.bind(sin)
	start = time.time()
	for x in xrange(1000):
		maths.tan(x)
	print time.time() - start
	for x in xrange(1000):
		tan(x)
	print time.time() - start
	print
	print "Enter S, C or T to switch between the sine, cosine and tangent functions"
	print "Enter R or D at any time to switch between the radians and degrees modes."
	print "The current mode is radians. The current function is sine."
	degrees = False
	function = 0
	while 1:
		input = raw_input("Enter number: ")
		if input == "R":
			degrees = False
		elif input == "D":
			degrees = True
		elif input == "S":
			function = 0
		elif input == "C":
			function = 1
		elif input == "T":
			function = 2
		if input in ("R","D","S","C","T"):
			print "The current mode is " + ("degrees" if degrees else "radians") + ". The current function is " + ("sine", "cosine", "tangent")[function] +  "."
		else:
			try:
				if function == 0:
					print sin(float(input),degrees)
				elif function == 1:
					print cos(float(input),degrees)
				else:
					print tan(float(input),degrees)
			except ValueError:
				print "You have not entered a valid number."
	

[Arosenivai]

Assembly, won't be too much of an issue. The problem is the Taylor series convergence takes a long time, along with the CORDIC method which works well, but not with long floating point types. (I need one for both doubles and floats ) So if you have any other Ideas, please let me know.

[Arosenivai]

So as it turns out I was being an idiot. My compiler was using exception throws that I didn't want it to make (such as checking for -1 inside a sqrt function. ). That I forcibly disabled. (I'd like to note that normally I would say this is a horrible idea, but since dealing with exceptions is so time intensive, and I'm doing a real time program and all the uses are safe [such as taking magnitude of a vector] )