Math: Writing a Sine function

[zeroth]

just for the fun of it.

problem is, I can't find anything on the net that explains how to get the sine of an angle. it just says that the sine of angle A is opposite/hypotenuse. that's all find and dandy if you have a triangle, but how do you get the sine of an Angle without that information? Calculators do this. pop in Sin(35) and you'll get the sine of angle 35. how does that work?

I've attempted to look up the Function definition in the standard C library, but all I can find is the function prototype in the header - where the heck is the function definition?

[GNU-Fan]

It is built in directly into the CPU since early 1990 on most platforms. So it's available directly as a assembler command. Look for FPU at Wikipedia.

But of course the C runtime must accommodate for CPUs lacking that feature. It is then provided by software emulation. (I think the kernel does this. Yes, it does http://git.kernel.org/?p=linux/kerne...0cdaa2be8076a7)

These low-level math functions are very system-dependent. This is how they ask the FPU. sourceware.org Git - glibc.git/blob - sysdeps/i386/fpu/s_sin.S


It boils down to a Taylor series of the sine function. You sum up as much terms as you need for a given accuracy. That is, the more terms you take into account, "the more decimal places" you get.
Trigonometric functions - Wikipedia, the free encyclopedia

[zeroth]

fwah! being built into the CPU or even a kernel-land asm definition, I guess I can thoroughly forget about writing my own as it would be a whole lot slower.

thanks for the links, I'll see if I can wrap my head around it.

[Rubberman]

Yeah. A Masters or PhD in math is helpful here. My friend Bruce Ravenel was the principal architect of the Intel 8087 math processor back in the 70's and he implemented the full IEEE standard for math functions on the chip - including all the standard transcendental (including trig) functions. That stuff is now baked into the Pentium processor family directly instead of a co-processor chip. He was an ABT (All But Thesis) PhD student at the University of Colorado (student of Niklaus Wirth of Pascal and Modula fame) when Intel came along with the job offer he couldn't refuse. His brother Douglas is one of the stellar mathmeticians in the world of field theory and abstract algebra. So, writing this stuff even in higher-level languages is not trivial. Imagine doing it in the hardware of logic gates!

FWIW, I have had some little experience implementing differential calculus in C/C++ software in order to implement risk analysis algorithms for the options trading industry. I don't bother to do stuff like implementing trig functions in software since the available library functions for that stuff is so well established and standardized, not to mention thoroughly vetted by some of the best minds for that stuff on the planet.

[zeroth]

wow. I wanted to write my own sine function both for the educational value as well as the niftyness of having sweet C++ libraries I've made all my own. I've got a handfull already, including Strings, linked lists, hash lists, and some basic trig (cartessian vectors and such).

I've hacked at Doom3's source for years (I'm lead/solo programmer on Hexen: Edge of Chaos (hexenmod.com), and as far as I can tell, John Carmack took the time to write all his own code, mostly ignoring the standard C++ library. he even rewrote malloc and claims his implementation to be many many times faster. I know the very basics of assembly, but imaginging writing that stuff is just like... wow.

[Rubberman]

I can readily believe that a hand-crafted malloc can be a LOT faster than the standard. I did R&D on reference-counted garbage collected allocators and was able to get much better performance than the standard tools for a lot of stuff. The math functions are another beast since they are hard-baked into the processor chips (at least on Intel and AMD ones) - not all ARM chips have onboard hardware math. So, there is absolutely no way that hand-crafted transcendental functions can be anywhere as fast as those that are run directly on the hardware in microcode, especially with todays' multi-core systems. You can run your math in its own thread(s) and take advantage of those extra cores to really speed up your calculations. Then, you can get some nVidia CUDA hardware and REALLY crank up your floating point math, since they use hundreds of cores that do pretty much nothing but math.

I guess my point is that for general floating point math functions, especially the transcendental ones (which include the trig functions), go hardware!

[Rubberman]

One final note. Yes, the visceral satisfaction on crafting a difficult set of functions on your own from the theoretical underpinnings cannot be underestimated - definitely a satisfying high! The reference-counted garbage collected allocator I mentioned was used as part of a C++ development framework I wrote which was the foundation for a 10+million line of code enterprise manufacturing suite that in all of those lines we never needed to manually call free/delete even once, yet we had zero memory leaks. That software is currently used to run about 80% of the semiconductor, disc drive, and flat-panel display factories in the world today. Some of the work I did on that project earned me a US Patent for adaptive systems.

[zeroth]

nice.

here's the snippet I was talking about:

/*
===============================================================================

	Memory Management

	This is a replacement for the compiler heap code (i.e. "C" malloc() and
	free() calls). On average 2.5-3.0 times faster than MSVC malloc()/free().
	Worst case performance is 1.65 times faster and best case > 70 times.
 
===============================================================================
*/

this is from the header file Heap.h in the Doom3 SDK. the header is about 900 lines, but the rest of the code for this particular thing is most likely not part of the SDK. I'd imagine John Carmack can outsmart any MS employee

[GNU-Fan]

I'd imagine John Carmack can outsmart any MS employee

Not that I'd doubt that,
but to be fair here we mustn't forget that game developers often can take advantage of only having to take a narrow application into account.

The OS and runtime developers must write general purpose code. With all the exceptions being dealt with and whatnot.