How do computers calculate sine?

https://androidcalculator.com/how-do-calculators-compute-sine/

by vegesm • 2 years ago

227 163 2 years ago

paulpauper4• 2 years ago

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

ot• 2 years ago

Did you read the article? It is specifically about how the series looks simple, but the error is actually very bad if you do things naively.

paulpauper4• 2 years ago

That still makes it easier compared to computing constants in which the series are not globally convergent, like inverse trig functions. Obviously, you would have to break it apart to speed convergence.

zgs• 2 years ago

It would also be extremely inaccurate. The x^n numerators grow very quickly and digits get lost because unlimited precision isn't available. Likewise, the n! denominators also grow rapidly. Then the series is alternating which means cancellation is happening for every added term.

If you don't believe me try for x=10.

planede3• 2 years ago

You need around 26 terms for x=10 if you do it without reduction and you want an accuratish result for double precision.

You wouldn't evaluate the terms naively from left-to-right.

x - x^3/3! + x^5/5! - ... = x * (1 - x^2/(2*3) * (1 - x^2/(4*5) * ... ) )

I just checked in python and you get a result that is around 1000*machine epsilon off. Not great, not terrible.

duped• 2 years ago

1 - cos^2(x), obviously

nh23423fefe• 2 years ago

instead, you could just double negate to optimize away the square root

    -(-(sin(x))

ChainOfFools• 2 years ago

clear, but too verbose. 1/csc is what you want.

or for style points just -cos'

t-3• 2 years ago

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

lupire• 2 years ago

Think about how big that lookup table would be for an 64bit double float.

They use a lookup table for nπ/16, and then a polynomial to approximate the difference to other values.

Etherlord87• 2 years ago

That would be quite a big lookup table... Half of float numbers are in -1…+1 range. You don't need the negative part, so that's a quarter of float numbers, over one billion numbers. And then some to get from 1 to π/2.

And that's only float32!

tails4e• 2 years ago

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.

amelius• 2 years ago

And arcsin?

paulpauper4• 2 years ago

harder due to convergence issues

convolvatron• 2 years ago

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)

phkahler• 2 years ago

I've been doing FoC motor control for a long time and I've settled on a neat little fixed point approximation for sin/cos. I haven't been able to find the blog I got the idea from. It's accurate to 9 bits, but is very symmetric and hits 1,0,-1 exactly. It's also smooth which usually makes it better than lookup tables.

warpech• 2 years ago

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...

adgjlsfhk15• 2 years ago

some languages (e.g. Julia) provide their own math library do that you get the same results across across operating systems.

TylerE5• 2 years ago

Safer to assume that floats are never deterministic.

jacobolus5• 2 years ago

Floats follow a clear specification which determines precisely how basic arithmetic should work. They should work the same on all popular modern platforms. (Whether specific software libraries are the same is a separate question.)

aardvark1793• 2 years ago

Floats are well defined, and it is perfectly possible to reason about how algorithms based on them should behave. Few languages specify the accuracy of things like trig functions, so relying on them can be tricky, and JavaScript is particularly bad in that respect.

saagarjha4• 2 years ago

This is not always a safe assumption (in certain scenarios floating point results being nondeterministic has the possibility to introduce bugs and security issues) and is also a kind of sad way to look at the world. The response to "I don't understand how this works" should not be to adopt an incorrect viewpoint, but to know the limitations of your understanding.

mhh__• 2 years ago

They're always deterministic in some sense (and as long as your OS respects the rounding mode after a context switch properly). This might sound pedantic but it determines how we think about floats — the behaviour is specified quite exactly.

contravariant• 2 years ago

I don't think that's safe at all. Catastrophic cancellation would be quite a lot less catastrophic if rounding errors were random but accurate on average.

throwway120385• 2 years ago

It depends. If you're constrained to one chip and one platform you can characterize or you can estimate the characteristics of a float that matter in your application. In some applications like embedded that's actually totally fine, and modern embedded chips can often do floating point as fast or faster than they can emulate fixed point to work around floating point's drawbacks. On one project I worked on they originally wrote everything fixed point out of fear that floating point would introduce some deleterious effect. But in the end they rewrote parts of the project using floating point to no ill effect and great performance improvement. And there were features of the product that they had to strike because the rewrite needed to support them couldn't touch certain sensitive areas of the code that had been tested extensively in the 2 or 3 years of development. It would have been much better to evaluate the assumption that floats are bad early on in the project and make the decision based on real information. The heuristic they were applying ended up costing part of the product that was strategically important.

charlieyu1• 2 years ago

But why? We all know 0.1+0.2 won’t give 0.3 with floats but at least we should expect deterministic result for same numbers and same operations and same order, no?

cogman104• 2 years ago

Well, what's fun is that (AFAIK) trigonometric functions tend not to be implemented in the newer floating point instructions, such as AVX or SSE.

So while what you say is true about the x87 implementation of those functions, for anything targeting a machine built in the last 20 years it's likely the code will run consistently regardless the architecture (barring architecture floating point bugs, which aren't terribly uncommon in the less significant bits and when overclocking comes into play).

x86 compilers won't use x87 instructions when SSE2 and later are available. x87 is just a really weird and funky instruction set that's best left in the gutter of history.

bnprks• 2 years ago

Sadly even SSE vs. AVX is enough to often give different results, as SSE doesn't have support for fused multiply-add instructions which allow calculation of a*b + c with guaranteed correct rounding. Even though this should allow CPUs from 2013 and later to all use FMA, gcc/clang don't enable AVX by default for the x86-64 targets. And even if they did, results are only guaranteed identical if implementations have chosen the exact same polynomial approximation method and no compiler optimizations alter the instruction sequence.

Unfortunately, floating point results will probably continue to differ across platforms for the foreseeable future.

bee_rider• 2 years ago

They do, however, have some intrinsics for trig functions in AVX in their compilers. Not as good as having an instruction of course.

enriquto2• 2 years ago

x87 is just a really weird and funky instruction set that's best left in the gutter of history

hmmm, can you use the long doubles in sse or avx? They are glorious, and as far as I see from playing with godbolt, they still require dirtying your hands with the x87 stack.

fulafel• 2 years ago

What about GPU ISAs?

aardvark1793• 2 years ago

Somewhat annoyingly the ascribe standard only specifies that various math functions return an approximation but does not set any bounds on that approximation. So for many functions you could just return NaN and still be compliant.

layer82• 2 years ago

Isn’t NaN the one value that can’t possibly count as an approximation, because it’s not a number and unordered? ;)

retrac• 2 years ago

Rounding transcendentals correctly has unknown time and space complexity. [1] Sort of brushes up against the halting problem. With limited precision, the upper limit becomes calculable but it's rather large - packages that offer correct rounding on 64-bit floating point use potentially hundreds of bytes to deal with a single floating point value. Dedicated circuitry to implement it fast would be big and complicated even by today's standards.

https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma

lifthrasiir4• 2 years ago

True in general, almost false for binary64. Important univariate functions have been thoroughly mapped for known hard-to-round cases, which resulted in the fact that we only need at most triple-double format to do the correct rounding. (Bivariate functions like `pow` are much harder, and not yet fully mapped as of this writing.) As a result we now have a mathematical library that almost ensures correct rounding [1], and a further optimization is currently in progress.

[1] https://core-math.gitlabpages.inria.fr/

throwawaymaths• 2 years ago

unknown time and space complexity

True in general but for the basic datatypes sent through hardware regusters your processor architecture has fixed precision. So the time and space complexity is O(1)

ImHereToVote3• 2 years ago

We should just use analog circuit for this sort of thing where the exact precision doesn't matter.

quickthrower2• 2 years ago

So you can use sin(x) for various x to tell what you are running on. Maybe even in the browser?

lifthrasiir4• 2 years ago

V8 and SpiderMonkey have converged to the same underlying library (fdlibm), partly for the interoperability, so you generally can't.

Karliss• 2 years ago

There is a shader which uses similar idea to detect what kind of GPU you have https://www.shadertoy.com/view/slySWV

Arelius• 2 years ago

Yeah, but you'd be surprised at how frequently they appear to be the same. I once worked on a HTML5 game that that relied on deterministic simulation for networking. And it wasn't untill pretty late in development that a build of Chrome shipped on some platform that finally triggered a desync in our extensive cross-platform test suite.

We implemented a deterministic approximation, and moved on. But I learned something important about trig functions that day.

paulddraper• 2 years ago

deterministic

I would use the word "consistent."

Non-determinism implies randomness.

microtherion• 2 years ago

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...

dboreham• 2 years ago

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...

vardump4• 2 years ago

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

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

adgjlsfhk15• 2 years ago

no it's not. cordic has awful convergence of 1 bit per iteration. pretty much everyone uses power series.

f1shy2• 2 years ago

That is 64 iterations for a double, that is nothing!

ajross• 2 years ago

Actually pretty much everyone implements double precision sin/cos using the same (IIRC) pair of 6th order polynomials. The same SunPro code exists unchnaged in essentially every C library everywehre. It's just a fitted curve, no fancy series definition beyond what appears in the output coefficients. One for the "mostly linear" segment where the line crosses the origin and another for the "mostly parabolic" peak of the curve.

perihelions3• 2 years ago

CORDIC is pretty obsolete, AFAIK. Its advantage is that its hardware requirements are absolutely tiny: two (?) accumulator registers, and hardware adders and shift-ers—I think that's all. No multiplication needed, in particular. Very convenient if you're building things from discrete transistors, like the some of those earlier scientific calculators!

(Also has a nice property, apparently, that CORDIC-like routines exist for a bunch of special functions and they're very similar to each other. Does anyone have a good resource for learning the details of those algorithms? They sound elegant).

pclmulqdq• 2 years ago

CORDIC still is used in tiny microcontrollers (smaller than Cortex-M0) and in FPGAs when you are very resource-constrained. Restricting the domain and using Chebyshev/Remez is the way to go pretty much everywhere.

f1shy2• 2 years ago

Multiplication is pretty much needed in cordic! And is far from obsolete! It works perfectly fine, and dont have any of the problems said in the article.

dilyevsky• 2 years ago

I think still used out of necessity when hw floating point not available (like fpgas)

rcxdude3• 2 years ago

CORDIC doesn't make sense if multiplies have a similar cost to adds. If you have cheap multiplications then a successive approximation is faster. If multiplications are expensive relative to adds then CORDIC can still generally win. Basically this is only the case nowadays if you are doing ASICs or FPGAs.

derf_• 2 years ago

I have used CORDIC to compute fixed-point log/exp with 64 bits of precision, mostly because I wanted to avoid having to implement (portable) 64x64->128 bit integer multiplication in C. It is probably still slower than doing that, but the code was really simple, and very accurate.

idatum• 2 years ago

I just recently came across CORDIC in a fun read I just finished, 'Empire of the Sum', by Keith Houston. It's a history of calculators, and there's a chapter on the HP-35 which used CORDIC. The author goes into some details how it was used by that constrained device.

There are a lot of references given in the book including more details on CORDIC.

bigbillheck4• 2 years ago

Why would you ever use CORDIC if you had any other option?

vardump4• 2 years ago

It's great for hardware implementations, because it's simple and you get good/excellent accuracy. I wouldn't be surprised if that's still how modern x86-64 CPUs compute sin, cos, etc.

That said, last time I had to do that in software, I used Taylor series. Might not have been an optimal solution.

EDIT:

AMD's Zen 4 takes 50-200 cycles (latency) to compute sine. I think that strongly suggests AMD uses CORDIC. https://www.agner.org/optimize/instruction_tables.pdf page 130.

Same for Intel, Tiger Lake (Intel gen 11) has 60-120 cycles of latency. Page 353.

I'd guess usually ~50 cycles for Zen 4 (and ~60 for Intel) for float32, float64/float80 datatype. Denormals might also cost more cycles.

eska• 2 years ago

You might also find this video interesting:

"Finding the BEST sine function for Nintendo 64"

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

perihelions3• 2 years ago

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

jxy3• 2 years ago

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

lifthrasiir4• 2 years ago

FreeBSD code is missing the range reduction step (it's named a "kernel" for the reason): https://cgit.freebsd.org/src/tree/lib/msun/src/e_rem_pio2.c

planede3• 2 years ago

Ah, I always referred to the musl implmenetation, but I just now realized that they copied the Freebsd one.

jxy3• 2 years ago

and the directory name is literally: `msun`

anthk• 2 years ago

Does 9front keep the same sin.c implementation?

jxy3• 2 years ago

http://git.9front.org/plan9front/plan9front/HEAD/sys/src/lib...

deepthaw• 2 years ago

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?

bigbillheck4• 2 years ago

Seems like a terrible idea on latency grounds alone.

zokier7• 2 years ago

There is huge number of 64bit floats and huge portion of those are between 0..pi/2.

aidenn04• 2 years ago

A lookup table (for any function) that covered all values between 0 and 1 in single precision, would be ~4GB; there are approximately 1B values between 0 and 1, and the result of each value is 4 bytes.

Such a table for double-precision would be much, much larger.

azhenley• 2 years ago

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

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

toolslive• 2 years ago

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.

paulpauper4• 2 years ago

There are many ways to do this. It's not a difficult problem unless memory is constrained.

demondemidi2• 2 years ago

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...

Someone• 2 years ago

That would take way too much room. A full lookup table would have 2^64 entries of 64 bits each, at 2^70 bits of ROM.

For comparison:

- Apple’s M2 Ultra has about 134 billion transistors. That’s about 2^38.

- Avogadro’s number is about 2^79.

Reducing the argument to a small range around zero decreases that a lot, but not enough by a far stretch. There are 2^52 doubles in [0.5, 1.0), 2^52 more in [0.25, 0.5], 2^52 more in [0.125, 0.25], etc. so you’d still easily need 2^52 entries or 2^58 bits (likely way, way more)

demondemidi2• 2 years ago

They DO use a lookup table because that’s what the FDIV but came from:

https://en.m.wikipedia.org/wiki/Pentium_FDIV_bug

“It is implemented using a programmable logic array with 2,048 cells, of which 1,066 cells should have been populated with one of five values: −2, −1, 0, +1, +2.”

Not sure what you’re trying to demonstrate, they wouldn’t store every single float!! I hope don’t program. ;)

lifthrasiir4• 2 years ago

Older CPUs generally have used CORDIC (which does use LUT but that's only a part of the algorithm) due to its simplicity and compactness, while later CPUs with extensive microcode support would do the same thing as software implementations.

aidenn04• 2 years ago

TFA says they use a 32 entry LUT, then do some math on the result.

eh_why_not2• 2 years ago

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! ...).

stephencanon• 2 years ago

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

It’s a very simple iterative algorithm, essentially the dumbest thing that could possibly work (like most good algorithms). It fails to converge for functions that have poles nearby unless you have a very good initial guess (the Chebyshev or Carathéodory-Fejér approximants are ~always good starting points and easily computed). In practice you want to optimize a weighted L-inf norm rather than absolute, because floating-point errors are measured in a relative norm.

olooney• 2 years ago

I don't think the polynomial given in the article was calculated via Remez. Perhaps the author merely meant it as an illustration. Here is Wolfram Alpha plotting the error of equation from the article:

https://www.wolframalpha.com/input?i=plot+sin%28x%29+-+P%28x....

You'll note that the error is small near zero, and large near pi/4, which is characteristic of a Taylor series around zero, and not the characteristic "level" oscillation characteristic of Remez approximations[1]. Note also that the polynomial only includes odd terms, which is not something I would expect from Remez unless it was run on the symmetric interval [-pi/4, pi/4].

I ran Remez for the problem and after 4 iterations obtained a degree 8 polynomial with error less than 1e-9, but it didn't look anything like the polynomial given in the article.

    1.7209863008943345e-05x^8 -0.00024575124459624625x^7 +7.194649190849227e-05x^6 +0.008268794893899754x^5 +3.425379759410762e-05x^4 -0.16667692317020713x^3 +1.5422400957890642e-06x^2 +0.9999999106213322x +8.526477071446453e-10

Although of course the first few digits of the low-order matching terms will be very similar - any polynomial approximation method will agree there because they are fitting the same function, after all. But by the time we reach x^5 or x^7 the agreement is very loose, really only the first couple digits are the same.

[1] https://en.wikipedia.org/wiki/Approximation_theory

eh_why_not2• 2 years ago

Perhaps the author merely meant it as an illustration.

Yes I too was expecting oscillations (since I saw Chebyshev polynomials mentioned on the wiki page). I'm beginning to think that the word "might" in their statement "One way to calculate is Remez’s algorithm. The results might look like this:" is doing a lot of heavy lifting.

A couple of notes about your results:

- The interval only needs to be [0, pi/16] and not [0, pi/4]; adjusting that in your wolframalpha query yields a similar bound to what the author lists: 3.5 e-9. (Although same observation about the change of behavior at the bounds as you made).

- The polynomial you obtained actually looks pretty close to the Taylor one: the even coefficients are small, and rounding to 5 or 6 digits might yield a close one, maybe if we look for a degree 9 polynomial instead of degree 8. (I don't have an implementation of Remez handy right now to try it myself).

Although of course the first few digits of the low-order matching terms will be very similar

Makes sense.

djmips• 2 years ago

Robin Green goes into this in this GDC 2002 article.

https://basesandframes.files.wordpress.com/2016/05/rgreenfas...

staplung• 2 years ago

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...

pillusmany• 2 years ago

Games targetting pre-Pentium PCs also used precomputed trig tables.

Pentium was fast enough that it didn't matter as much.

Just a few years later it was slower to read a trig precomputed table.

xarope• 2 years ago

in other words, for those of us who remember, they used the equivalent of a slide rule

BD103• 2 years ago

Yup, I remember watching a video about how the RAM bus is the bottleneck when running Super Mario 64 on the N64. The original implementation used trig lookup tables, but the person optimized it by instead using Taylor series (I think) and some negation / shifting.

Dwedit• 2 years ago

It turns out that SNES DOOM missed out on a big optimization that people figured out later on. If you use the SNES's Mosaic feature combined with scrolling tricks, you can nearly double the fill rate. Rather than outputting two pixels, you let the SNES's mosaic hardware do the pixel doubling.

mads• 2 years ago

Back in the 80's, when I made demos on the C64, we also used pre-calculated sines. I remember going to the library to get a book with the values.

nwellnhof• 2 years ago

I just wrote a BASIC program generating values using the SIN function [1] and poked them into memory.

[1] https://www.c64-wiki.com/wiki/SIN

albrewer2• 2 years ago

Abramowitz and Stegun's Handbook of Mathematical Functions[0] - I still use it to test whenever I need to implement any kind of fundamental math function that's not built into whatever environment I'm using. Haven't used it in some time but it comes in handy.

[0]https://en.wikipedia.org/wiki/Abramowitz_and_Stegun

inkyoto• 2 years ago

[…] pre-calculated lookup tables […]

The approach is older than that. I remember my grandfather's engineering books from 1950's – nearly each of them had a large addendum with the said pre-calculated sine, cosine, tangent and logarithm lookup tables. And there was at least one book that only had such tables and no other information.

That is how engineers used to calculate before the advent of computers.

aoanla• 2 years ago

The classic of this field of books is Abramowitz and Stegun's "Handbook of Mathematical Functions" - although the two listed names are merely those of the compilation editors, as the calculations of the numerous tables of values (and sheets of mathematical identities) required hundreds of human computers operating for years. Ironically, on publication in 1964 it was just in time to see the dawn of the electronic computer age that would supplant it.

hakuseki• 2 years ago

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.

Is this really the order of events? I imagine the pre-calculated route is what you'd try first, and only go for extra hardware if that failed somehow.

shzhdbi09gv8ioi• 2 years ago

Lookup tables were commonplace in 80s-90s graphics programming. It should have been used before any consideration of custom hardware solutions.

tdudhhu2• 2 years ago

Once I tested lookup tables for a path tracer (ray tracer).

It is interesting that you can get very decent results even with low quality tables. Of course there will be artifacts but due to the randomness of a path tracer this is not always very noticeable.

ImHereToVote3• 2 years ago

I always wonder when hearing about these old optimizations why they aren't used in contemporary code. Wouldn't you want to squeeze every bit of performance even on modern hardware?

pengaru• 2 years ago

imagine thinking lookup tables are innovative

Solvency• 2 years ago

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

simonblack• 2 years ago

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.

mettamage• 2 years ago

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?

HenryPrickett• 2 years ago

Use a Taylor series with a four function calculator.

0 is a decent approximation of sin near 0.

x is a better one.

x - x^3/6 is an even better one.

x - x^3/6 + x^5/120 ...

Note that x here is in radians rather than degrees so convert (degrees * pi/180) first. Repeat until you're satisfied with how many stable digits you get

empath-nirvana• 2 years ago

https://www.youtube.com/watch?v=3d6DsjIBzJ4

_v7gu• 2 years ago

Five is small enough that you can get away with sin(5 deg) = 5pi/180

sema4hacker• 2 years ago

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.

Tade0• 2 years ago

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.

aidenn04• 2 years ago

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

How do computers calculate sine?

Related Stories