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

Finding the best sine function for Nintendo 64 [video]

youtube.com

Post reply on HN
Print view View original

41–47 of 47 posts

Re: Finding the best sine function for Nintendo 64 [video]

#41

Post by boywitharupee »

Sesse__ wrote: post #34
thebooktocome wrote: post #22

Earlier quoted context omitted.

By itself, Remez is not usually helpful for these kinds of low-accuracy polynomial approximations, because getting the minmax error beneath the quantization threshold is too strong a constraint. Usually one ends up doing some brute force polishing at the end to try and reduce the polynomial degree and/or the bits necessary to represent coefficients.

FWIW, Sollya's Remez algorithm takes intermediate floating-point accuracy into account. At the very least, one should start by such a polynomial and then try to tweak it by hand, not just drag coefficients around from scratch. Numerics isn't “just messing around with numbers” as he claims; it's a large field with lots of cleverness. As a quick example (using Maple, though, not Sollya): f(x) = x * (1.020875931 + x * (…

How are you computing the max error here? What would be the max error for taylor series?

Re: Finding the best sine function for Nintendo 64 [video]

#42

Post by nsajko »

boywitharupee wrote: post #41
Sesse__ wrote: post #34

Earlier quoted context omitted.

FWIW, Sollya's Remez algorithm takes intermediate floating-point accuracy into account. At the very least, one should start by such a polynomial and then try to tweak it by hand, not just drag coefficients around from scratch. Numerics isn't “just messing around with numbers” as he claims; it's a large field with lots of cleverness. As a quick example (using Maple, though, not Sollya): f(x) = x * (1.020875931 + x * (…

How are you computing the max error here? What would be the max error for taylor series?

Take an interval, for sine it might be, for example [0,π/4], I think it was [0,π] in the video (a mistake, most probably). You're interested in the maximum approximation error over the interval, so you could, for example, sample ten thousand points from the interval uniformly, evaluate the error over all of them, and take the maximum.

Technically, what you're really looking for is the supremum, not the maximum. The former is the limit of the latter.

Sollya does something smarter than just sampling uniformly, though, it knows about the derivatives of all the functions it works with (and derivatives of the derivatives, etc), and uses that information to compute an arbitrarily small interval that is guaranteed to contain the supremum: https://www.sollya.org/sollya-weekly/help.php#supnorm

My package also does something more complicated than just sampling uniformly, however it doesn't know anything about the derivatives of the relevant functions, so the maximum it finds is just approximate.

Re: Finding the best sine function for Nintendo 64 [video]

#43

Post by Sesse__ »

nsajko wrote: post #42
boywitharupee wrote: post #41

Earlier quoted context omitted.

How are you computing the max error here? What would be the max error for taylor series?

Take an interval, for sine it might be, for example [0,π/4], I think it was [0,π] in the video (a mistake, most probably). You're interested in the maximum approximation error over the interval, so you could, for example, sample ten thousand points from the interval uniformly, evaluate the error over all of them, and take the maximum. Technically, what you're really looking for is the supremum, not the maximum. The f…

In this case, you know the input is one out of 16384 distinct values (originally 65536, but due to range-reduction and symmetries, you only need to consider one of them). So you can simply test them all.

But in the case of the minimax polynomial, I just got it out of Maple (it can tell you as part of computing it). That's not accounting for floating-point inaccuracies, though.

Re: Finding the best sine function for Nintendo 64 [video]

#44

Post by nsajko »

sosodev wrote: post #40
nsajko wrote: post #38

Earlier quoted context omitted.

I'm not claiming anything extraordinary, though, most or all of what I said is well known in the field.

The burden of proof is on you though. If you think you can do it better then do it. It's ridiculous to post a dismissal without even watching the full video.

A good reference is the Handbook of Floating-Point Arithmetic. If you can be more specific about what is it that's not clear, I'll give more specific "proof". Even though you're being a bit "sealion"-y.

> It's ridiculous to post a dismissal without even watching the full video.

The video is jarring to watch. It's well-produced, engaging, etc.; but also pretentious and overconfident. It seems to be chock-full with irrelevant "developments". So it's not reasonable to expect me to watch it end-to-end.

Re: Finding the best sine function for Nintendo 64 [video]

#45

Post by Sesse__ »

Sesse__ wrote: post #34
thebooktocome wrote: post #22

Earlier quoted context omitted.

By itself, Remez is not usually helpful for these kinds of low-accuracy polynomial approximations, because getting the minmax error beneath the quantization threshold is too strong a constraint. Usually one ends up doing some brute force polishing at the end to try and reduce the polynomial degree and/or the bits necessary to represent coefficients.

FWIW, Sollya's Remez algorithm takes intermediate floating-point accuracy into account. At the very least, one should start by such a polynomial and then try to tweak it by hand, not just drag coefficients around from scratch. Numerics isn't “just messing around with numbers” as he claims; it's a large field with lots of cleverness. As a quick example (using Maple, though, not Sollya): f(x) = x * (1.020875931 + x * (…

I looked at the video a bit more closely, and it seems he requires the symmetry around 0 (he doesn't explicitly do range reduction to positive values), so you want only odd-numbered coefficients. If so, you can do a formula of the type x * (c + x*x*(b + x*x*a)) (aka: ax⁵ + bx³ + cx; this is essentially the same as his formula with c=1 and prescaling x by a constant), which Sollya readily gives for single precision:

  > fpminimax(sin(x*2*Pi/65536.0),[|x,x^3,x^5|],[|SG...|],[0;16384]);
  Warning: For at least 2 of the constants displayed in decimal, rounding has happened.
  x * (9.58634263952262699604034423828125e-5 + x^2 * (-1.46252571143166976153082714517950080335140228271484e-13 + x^2 * 6.1585575698811928868593794069233315902067715796875e-23))
This has a maximum error of 0.000108 over that range. This is pretty close to optimal, but you can squeeze it ever so slightly lower (just below 0.0001) if you're willing to spend a lot of CPU time. :-)

Re: Finding the best sine function for Nintendo 64 [video]

#46

Post by rasz »

dietrichepp wrote: post #21
phire wrote: post #20

Earlier quoted context omitted.

In one of Kaze's older videos [1] , he tracks both CPU and RCP time over various optimisations. The numbers make it pretty apparent that you can get significant RDP performance gains by reducing the amount of CPU bandwidth and/or improving it's access locality. The N64 is a unified memory system, and memory stalls triggered by the CPU will slow RDP down. The N64's memory controller appears to be very simple. As I und…

The bank organization is relatively well-known, so maybe you put the framebuffer in one bank, you put the zbuffer in another bank, and you have two banks left over without touching expansion memory. I mentioned World Driver Championship specifically because it runs at 640x480, and runs well, without the expansion pack. Yes, memory access by the CPU will slow the RDP down. But the RDP is plenty slow even when the CPU…

Isnt World Driver Championship fast because it doesnt use Zbuffer in the first place freeing half of memory BW normally used by gpu? Afair their custom RDP code sorted triangles back to front and just hoped you wouldnt notice glitches.

Re: Finding the best sine function for Nintendo 64 [video]

#47

Post by Sesse__ »

nsajko wrote: post #44
sosodev wrote: post #40

Earlier quoted context omitted.

The burden of proof is on you though. If you think you can do it better then do it. It's ridiculous to post a dismissal without even watching the full video.

A good reference is the Handbook of Floating-Point Arithmetic. If you can be more specific about what is it that's not clear, I'll give more specific "proof". Even though you're being a bit "sealion"-y. > It's ridiculous to post a dismissal without even watching the full video. The video is jarring to watch. It's well-produced, engaging, etc.; but also pretentious and overconfident. It seems to be chock-full with irr…

> The video is jarring to watch. It's well-produced, engaging, etc.; but also pretentious and overconfident. It seems to be chock-full with irrelevant "developments".

Don't even try to read the YouTube comments :-) “Kaze has to be the best assembly programmer of all time”, “this is the greatest genius since the inverse square root trick”, “this SM64 hack is the most optimized Nintendo 64 game of all time”, etc…

Post reply on HN