How do computers calculate sine? • Hacker News Board

Re: How do computers calculate sine?

#161

Post by saagarjha » Fri, Mar 08, 2024, 6:41 PM UTC

otabdeveloper4 wrote: post #130

saagarjha wrote: post #43

Earlier quoted context omitted.

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.

Irrational numbers cannot have an exact representation in digital bits. (Computers use rational numbers with modular arithmetic under the hood.)

Yes I am aware of this fact

Re: How do computers calculate sine?

#162

Post by Const-me » Fri, Mar 08, 2024, 8:59 PM UTC

ImHereToVote wrote: post #133

tdudhhu wrote: post #132

Earlier quoted context omitted.

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.

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?

Some of these old optimizations are now deprecated. For example, there’s a famous trick for inverse square root: https://en.wikipedia.org/wiki/Fast_inverse_square_root Modern processors have a special instruction for that. The hardware instruction is several times faster, and couple orders of magnitude more precise: https://www.felixcloutier.com/x86/rsqrtps

Other optimizations are now applied automatically by compilers. For example, all modern compilers optimize integer division by compile-time constants, here’s an example: https://godbolt.org/z/1b8r5c5MG

Squeezing performance out of modern hardware requires doing very different things.

Here’s an example about numerical computations. On paper, each core of my CPU can do 64 single-precision FLOPs each cycle. In reality, to achieve that performance a program needs to spam _mm256_fmadd_ps instructions while only loading at most 1 AVX vector per FMA, and only storing at most 1 AVX vector per two FMAs.

Re: How do computers calculate sine?

#163

Post by aidenn0 » Fri, Mar 08, 2024, 11:12 PM UTC

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

Re: How do computers calculate sine?

#164

Post by adgjlsfhk1 » Sat, Mar 09, 2024, 1:31 AM UTC

jacobolus wrote: post #158

dzaima wrote: post #98

Earlier quoted context omitted.

Software implementations can and do differ (even dynamically) based on the hardware though - e.g. glibc's sin(x) function, what C code will end up using (if not other languages relying on the C stdlib), uses FMA instructions on my CPU, and thus the exact same binary on the exact same OS with the exact same glibc should behave differently on a very old CPU without FMA where it should have a different implementation (a…

Yeah, the lack of FMA in some contexts is a serious bummer. It would be great if every popular CPU platform would figure out a way to get FMA implemented, and if programming languages would figure out better ways to help programmers use it explicitly without making their code too ugly.

at this point, Intel, AMD, Arm, and RiscV all do and have for a while. The only one that is at all relevant that doesn't is Apple m-series under rosetta.

Re: How do computers calculate sine?

#165

Post by pests » Sat, Mar 09, 2024, 3:23 AM UTC

BD103 wrote: post #115

pillusmany wrote: post #107

Earlier quoted context omitted.

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.

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.

Also enjoy his discovery that, while the game got flak online for years due to the release build have files that were not optimized, it turns out most of the optimizations that were done were actually for the worse due the low instruction cache/ram (I forget the exact details.) Things like unrolling loops just increased the code size and required more slow code paging.

Re: How do computers calculate sine?

#166

Post by djmips » Sat, Mar 09, 2024, 1:14 PM UTC

eh_why_not wrote: post #90

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 exa…

Robin Green goes into this in this GDC 2002 article.

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

Re: How do computers calculate sine?

#167

Post by Etherlord87 » Sat, Mar 09, 2024, 10:46 PM UTC

t-3 wrote: post #5

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

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!