from Hacker News

How do computers calculate sine?

by vegesm on 3/7/24, 6:59 PM with 163 comments

• by staplung on 3/8/24, 12:20 AM

  I recently learned how Doom was ported to the SNES. It's quite impressive. The SNES hardware was nowhere near fast enough to do all the trig calculations needed for the game but cartridge based games had a trick up their sleeve: they could include actual hardware inside the cart that the game code could make use of. It was more expensive but if you expected to sell a boatload of copies, it could be worth it. However, even using extra hardware wasn't enough in this case. So they pre-calculated lookup tables for sine, cosine, tangent etc. for every angle at the necessary precision. They were helped by the fact that the game resolution in this case was fairly low.

  If you're interested, you can peruse the C code that was used to generate the tables. Here's the file for sine/cosine:

  https://github.com/RandalLinden/DOOM-FX/blob/master/source/m...

• by warpech on 3/7/24, 7:30 PM

  This made me realize that trigonometric functions are not deterministic across different CPU architectures, OS, and programming languages (floating point precision aside).

  E.g. I would assume that Math.sin(x) returns the same thing in NodeJS on Windows and Mac/M1, but it turns out it is necessarily so. https://stackoverflow.com/questions/74074312/standard-math-f...

• by jxy on 3/7/24, 8:05 PM

  It's much clearer if you read one of the source code of the libm.

  Plan 9: https://9p.io/sources/plan9/sys/src/libc/port/sin.c

  Freebsd: https://cgit.freebsd.org/src/tree/lib/msun/src/k_sin.c

• by microtherion on 3/7/24, 7:34 PM

  P.J. Plauger's _The Standard C Library_ provides an implementation for all functions in the (then) C standard: https://www.amazon.com/Standard-Library-P-J-Plauger/dp/01383...

• by toolslive on 3/7/24, 11:18 PM

  After reducing the interval, you don't want to use the Taylor series as you're building an approximation that's really good in 0 but not so good moving away from 0. It's better to use an interpolating polynomial (Chebychev comes to mind) over the whole target interval.

• by tails4e on 3/7/24, 7:22 PM

  I've seen the third order Taylor series used, but with the coefficients calculated at various offsets for a quarter wave. So you lookuo where you are in the quarter wave, then look up the 3 or 4 cofficients. This keeps the error somewhat bounded as the size of X is a small so the series does not diverge too much.

• by eska on 3/7/24, 7:46 PM

  You might also find this video interesting:

  "Finding the BEST sine function for Nintendo 64"

  https://www.youtube.com/watch?v=xFKFoGiGlXQ

• by eh_why_not on 3/8/24, 12:11 AM

  Anyone experienced with the Remez algorithm mentioned at the end of the article?

  The degree-9 polynomial, said to be a thousand times better than the original Taylor approximation in maximum error, also appears to be very close to the Taylor series in the first place.

  Rounding the Taylor coefficients to 6 digits after the decimal:

  1/3! = 0.166667

  1/5! = 0.008333

  1/7! = 0.000198

  1/9! = 0.000027(56)

  The first 2 are exact, the third is 5 digits only (so 0.000190), and the fourth is more different starting from the 6th digit (0.000026019).

  The delta in the 9-th order is expected if you were to truncate the Taylor series starting from the 11th order to infinity (+ x^11 / 11! - x^13/13! ...).

• by azhenley on 3/7/24, 8:51 PM

  I blogged my adventure of implementing cosine from scratch and how others have done it:

  https://austinhenley.com/blog/cosine.html

• by dboreham on 3/7/24, 7:38 PM

  This was my first use of open source, around 1978. I wondered how calculators and computers did trig functions, and was also using Unix V7. We had a large disk and kept the source on line. So I was able to find this: https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libm/s... and from there this book: https://www.biblio.com/book/computer-approximations-john-f-h...

• by duped on 3/7/24, 7:12 PM

  1 - cos^2(x), obviously

• by convolvatron on 3/7/24, 7:24 PM

  http://steve.hollasch.net/cgindex/math/inccos.html is a great technique if you need a fast integer approximation for some some arbitrary sampling interval (i.e. motor control)

• by aidenn0 on 3/8/24, 11:12 PM

  Just using the 32 entry LUT and the small-angle approximations (sin(x) = x, cos(x) = 1-x^2/2) lets you calculate sin(x) within +/- 0.00015, which is rather impressive for something that can be done quickly by hand.

  If you use cos(x) = 1 then you are still accurate to within 1%

  [edit]

  I think I also found an error in TFA? It seems like picking the "best" N would allow r to be in the range -pi/32 < r < pi/32, which makes the 3rd order Taylor series have an error of 4e-12, significantly better than the error range for 0 < r < pi/16

• by vardump on 3/7/24, 7:39 PM

  CORDIC is how it's usually done in hardware (and FPGAs).

  https://en.wikipedia.org/wiki/CORDIC

• by Tade0 on 3/8/24, 9:23 AM

  I was truly amazed when my high school computer science teacher expanded the sine function into a Taylor series for us to implement in class.

  Couldn't wrap my head around the concept until the topic was revisited in college, but idea was there and helped me understand the tradeoffs brought by "fast math" libraries I was using during high school.

• by t-3 on 3/7/24, 7:21 PM

  Link doesn't appear to be valid, but aren't these usually precalculated and stored in a lookup table?

• by mettamage on 3/8/24, 2:16 AM

  What’s the best way to calculate it by hand?

  I’m brushing up my math basics (I graduated CS while dodging the math requirements) and it frustrates me that in trig I need to remember values at all. The values such as sqrt(2)/2 make sense but how hard is it to calculate sin(5 degrees) by hand?

• by sema4hacker on 3/8/24, 4:55 AM

  I remember seeing the source code for a version of SpaceWar! running on an Adage Graphics Terminal (a one's complement machine) around 1970 that used a precomputed sine table.

  I wonder what the first program was that ever used a precomputed trig table.

• by simonblack on 3/8/24, 1:35 AM

  The same way you can eat an elephant: one byte at a time.

  Any calculating job can be undertaken by a proper Turing machine. You just have to keep in mind the old triangle of usage: Cost, capability and speed.

  If a human can calculate a sine, so can any full-blown computer.

• by demondemidi on 3/8/24, 12:02 AM

  I thought modern CPUs since the late 1980's used a lookup table for trig/transcendental functions. Is the LUT just an expansion of the polynomial? I never really understood how FPUs worked...

• by perihelions on 3/7/24, 8:00 PM

  Is this still current? The paper has a publication year of 1999.

• by deepthaw on 3/7/24, 8:38 PM

  Ignorant question:

  Given the ridiculous number of transistors and so on we can use in CPUs and GPUs nowadays how feasible is a relatively huge trig lookup table burned into rom?

• by Solvency on 3/8/24, 12:32 AM

  Why isn't this just done with an industry standard lookup table these days?

• by paulpauper on 3/7/24, 7:05 PM

  sine is easy because the series is globally convergent and fast converging

• by amelius on 3/7/24, 7:23 PM

  And arcsin?