I have been going over the first few days of HMH trying to get them in my head, and the TODO about implementing the sine catches my eye everytime I pass that section again. Did he implement the sine at some point in the future (maybe I have missed it if it happened in the first 100 or so episodes)?
Also, I went and googled how to do it from scratch and found some scary looking stuff. So apparently, its not as simple as just using some taylor series expansion and the way to do it is by an algorithm called the CORDIC explained here: https://www.allaboutcircuits.com/technical-articles/an-introduction-to-the-cordic-algorithm/
There also seems to be an x86 instruction which will compute the sine of a value referenced here: https://mudongliang.github.io/x86/html/file_module_x86_id_114.html
From the first article, I see that the basic idea is to rotate a unit vector aligned to the x-axis by the angle whose sine or cosine is needed and then read off the value of the rotated x or y coordinate. And this is fast because one can break down the angle of rotation into smaller angles such that those smaller angles always satisfy tan(x) = 2^(-i)
. Then, the problem reduces to division by powers of 2 which is just bit shifting. This leaves out a scaling factor which supposedly can be proved to be some fixed value within some error-bounds if we specify how many smaller angles we break our initial angle into.
Now, its unclear to me how that angle breaking part is done (even though the article provides a listing of one run with the values involved).
But I get the basic idea, i.e. implement this algorithm which takes out a fixed scaling factor (I'm definitely missing something here) that has the error inside it and the rest can be done using bit-shifts that are fast and don't have any error.
Does anyone know if
- the x86 instruction referenced in the second link just implements this algorithm?
- if the c runtime uses an implementation of this algorithm or just call the instruction in the hardware
- and whether his plan was to implement this algorithm on stream... man that math-hole would have been something to look at (or if it exists in some future episode tell me the episode number)