CS211 Project 1
Due Monday, October 30
Computers are generally fast at math, but some operations are slower than others. One which can cause performance problems in real-time physics simulations (as in, computer games) is trig functions, such as sin, cos, and tan. One strategy to improve performance is to precompute a table of values for each function, turning a complicated calculation into a memory access. A memory access itself is slower than an integer operation, but may be faster than calculating the value of a trig function.
For this project, develop a pair of functions, fast_sin and fast_cos, which use a precomputed array of values. Working in degrees, cos(x) = sin(x + 90), so both of these functions should share a table. The array will have to be computed before either function can be used, and should be allocated on the heap rather than the stack.
Precision and Table Size
Generally, float is preferred for 3D graphics because it is half the size of a double. This makes transfer of a large number of twice as fast as a large number of doubles, allows CPU operations to finish more quickly, etc. Graphics cards are generally optimized for float at the expense of double as well. Your table should contain floats rather than doubles.
An array has a fixed number of items, and as such, the exact values asked for may not be in the array. This will reduce the precision of this solution. Retrieve a value close to what the user asked for. For example, if the array contains 1000 values per degree (360,000 values total), the resolution will be 0.001 degrees, and the function would return the same value if asked for 142.00001 as 142.00002. You can make a conversion from degrees to array index with a formula like (int)(degrees * table_resolution), where the conversion to int will throw away any decimal part remaining. A table of 360,000 floats will be 360,000 * 4 bytes in size or 1,440,000 bytes, or about 1.4 megabyes. Since computers these days have multiple gigabytes of RAM, this isn't a large amount, and could be considered a reasonable price to pay for faster trig functions.
init and cleanup functions
Besides fast_sin and fast_cos, you should write two more functions. fastmath_init will allocate space on the heap, and compute the values for the array. Note that the array should be global, or at least available to all 4 functions. fastmath_cleanup will deallocate the array.
Starting Point for This Project
There is a program, p1start.cpp, available to start from. I've tested it on isoptera and online GDB, so I hope it works for you! I think the timing code should work on all platforms, but if it doesn't, let me know. Replace the call to sinf in the benchmark with fast_sin once you've got fast_sin working, and see if the running time improves.