Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How do computers calculate sine?

androidcalculator.com

Post reply on HN
Print view View original

131–140 of 167 posts

Re: How do computers calculate sine?

#131

Post by aoanla »

inkyoto wrote: post #123
staplung wrote: post #94

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

> […] 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.

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.

Re: How do computers calculate sine?

#132

Post by tdudhhu »

staplung wrote: post #94

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

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.

Re: How do computers calculate sine?

#133

Post by ImHereToVote »

tdudhhu wrote: post #132
staplung wrote: post #94

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

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?

Re: How do computers calculate sine?

#134

Post by ImHereToVote »

retrac wrote: post #56
warpech wrote: post #10

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

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

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

Re: How do computers calculate sine?

#135

Post by lkschubert8 »

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?

Doing so costs time/wage dollars.

Re: How do computers calculate sine?

#136

Post by csande17 »

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?

The "processor-memory performance gap" is a big reason why lookup tables aren't as clear of a win on modern hardware as they were on the SNES.

If it takes two CPU cycles to read from RAM, a lookup table will basically always be faster than doing the math at runtime. If it takes fifty cycles (because, while your RAM may be faster, your CPU is a lot faster), and your processor has more advanced hardware that can do more math per cycle, maybe just doing the math is faster.

Re: How do computers calculate sine?

#137

Post by Tade0 »

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.

Re: How do computers calculate sine?

#138

Post by lambdas »

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?

A lot get antiquated by instruction additions, like the infamous inverse square root

Re: How do computers calculate sine?

#139

Post by tdudhhu »

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?

Artifacts are ugly. So why force it on modern hardware when GPUs are extremely fast?

For reference: I was doing a path tracer in PHP :) so yeah, that renders like ancient hardware.

(The browser requested different buckets of an image. A PHP script then rendered and returned that bucket. So it was a kind of multi-threading but still very slow.)

Re: How do computers calculate sine?

#140

Post by rcxdude »

adgjlsfhk1 wrote: post #99
rcxdude wrote: post #84

Earlier quoted context omitted.

yeah, but 52 adds can be a lot cheaper than a few multiplies, if you're making them out of shift registers and logic gates (or LUT). in a CPU or GPU, who cares, moving around the data is 100x more expensive than the ALU operation.

> moving around the data is 100x more expensive than the ALU operation. This is exactly the problem with CORDIC. 52 dependent adds requires moving data from a register to the ALU and back 52 times.

It's the problem with CORDIC in that context, yes!
Post reply on HN