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

Even faster asin() was staring right at me

16bpp.net

Post reply on HN
Print view View original

51–60 of 68 posts

Re: Even faster asin() was staring right at me

#51

Post by coldcity_again »

srean wrote: post #36
coldcity_again wrote: post #34

Earlier quoted context omitted.

If you just see the conclusion I think it's hard to immediately grok how rotation can arise from this. This is a great technique for cheaply doing 3D starfields etc on 8-bit machines. Look ma, no sine table!

A related interesting fact is that small angular motions compose almost like vectors, order does not matter (i.e. they are commutative). This makes differential kinematics easier to deal with when dealing with polar or cylindrical coordinate systems. Large angular deflections while being linear transforms, do not in general commute. It will spoil the linear relation in your elegant expression, but a slightly better a…

Great point, thanks.

Re: Even faster asin() was staring right at me

#52

Post by [deleted] »

fatih-erikli-cg wrote: post #48
BigTTYGothGF wrote: post #44

Earlier quoted context omitted.

> In what way do you think a sin function is computed? In some way vaguely like this: https://github.com/jeremybarnes/cephes/blob/master/cmath/sin... > I think it is stored like sintable[deg]. The degree is index. I can think of a few reasons why this is a bad idea. 1. Why would you use degrees? Pretty much everybody uses and wants radians. 2. What are you going to do about fractional degrees? Some sort of interpreta…

It isnt good idea to store such values in code. I think it is something that computed when a programming environment is booting up. E.g. when you run "python", or install "python". I try to understand how Math.sin works. There is Math.cos. It is sin +90 degrees. So not all of them is something that completes a big puzzle.

[deleted]

Re: Even faster asin() was staring right at me

#53

Post by LegionMammal978 »

LegionMammal978 wrote: post #45

The coefficients given are indeed a near-optimal cubic minimax approximation for (π/2 - arcsin(x))/sqrt(1-x) on [0,1]. But those coefficients aren't actually optimal for approximating arcsin(x) itself. For reference, the coefficients given are [1.5707288, -0.2121144, 0.0742610, -0.0187293]: if we optimize P(x) = (π/2 - arcsin(x))/sqrt(1-x) ourselves, we can extend them to double precision as [1.5707288189560218, -0.2…

Actually, we can improve this a bit further, by also adjusting the "π/2" constant in arcsin(x) = π/2 - P(x)*sqrt(1-x). We take coefficients [1.5707256467180715, -0.21298179775496026, 0.07727939759417458, -0.02132102849918157] for P(x), then take arcsin(x) = 1.570760986756484 - P(x)*sqrt(1-x). This reduces the max error by 6.97%, from 3.80e-5 to 3.53e-5.

Adjusting the "1" upward in sqrt(1-x) does not seem to help at all.

Re: Even faster asin() was staring right at me

#54

Post by anon-3988 »

srean wrote: post #20

A notable approximation of ~650 AD vintage, by Bhaskara is ArcCos(x)= Π √((1-x)/(4+x)). The search for better and better approximations led Indian mathematicians to independently develop branches of differential and integral calculus. This tradition came to its own as Madhava school of mathematics from Kerala. https://en.wikipedia.org/wiki/Kerala_school_of_astronomy_and... Note the approximation is for 0 If I remembe…

Clearly India history has a lot to say about mathematics but I don't think they get enough attention. Or am I just ignorant and living in my own bubble? Indian philosophy is also very intriguing.

Re: Even faster asin() was staring right at me

#55

Post by mcraiha »

anon-3988 wrote: post #54
srean wrote: post #20

A notable approximation of ~650 AD vintage, by Bhaskara is ArcCos(x)= Π √((1-x)/(4+x)). The search for better and better approximations led Indian mathematicians to independently develop branches of differential and integral calculus. This tradition came to its own as Madhava school of mathematics from Kerala. https://en.wikipedia.org/wiki/Kerala_school_of_astronomy_and... Note the approximation is for 0 If I remembe…

Clearly India history has a lot to say about mathematics but I don't think they get enough attention. Or am I just ignorant and living in my own bubble? Indian philosophy is also very intriguing.

At least Srinivasa Ramanujan has gotten some attention.

Re: Even faster asin() was staring right at me

#56

Post by Lockal »

It makes zero sense to measure performance without measuring correctness. Especially, when you use LLM. Here is even faster asin(): `return 0;`

This precisions should be measured in avg and worst ULP, not in "charts". A good approximation should also give exact results in critical points (-1/0/-1 in this case).

The "faster" version gives this:

  asin(0) = 6.75268e-05 (double precision)
Which gives around 5e+15 ULPs, while common libc math implementations targets 19 ULPs (but will be 0 for asin(0)).

Re: Even faster asin() was staring right at me

#57

Post by kzrdude »

LegionMammal978 wrote: post #45

The coefficients given are indeed a near-optimal cubic minimax approximation for (π/2 - arcsin(x))/sqrt(1-x) on [0,1]. But those coefficients aren't actually optimal for approximating arcsin(x) itself. For reference, the coefficients given are [1.5707288, -0.2121144, 0.0742610, -0.0187293]: if we optimize P(x) = (π/2 - arcsin(x))/sqrt(1-x) ourselves, we can extend them to double precision as [1.5707288189560218, -0.2…

How did you find out that his optimization was done for a different equation, just by trial?

Re: Even faster asin() was staring right at me

#58

Post by srean »

anon-3988 wrote: post #54
srean wrote: post #20

A notable approximation of ~650 AD vintage, by Bhaskara is ArcCos(x)= Π √((1-x)/(4+x)). The search for better and better approximations led Indian mathematicians to independently develop branches of differential and integral calculus. This tradition came to its own as Madhava school of mathematics from Kerala. https://en.wikipedia.org/wiki/Kerala_school_of_astronomy_and... Note the approximation is for 0 If I remembe…

Clearly India history has a lot to say about mathematics but I don't think they get enough attention. Or am I just ignorant and living in my own bubble? Indian philosophy is also very intriguing.

Regarding attention, anything that does not draw directly from the Greek mainline, does not get much attention in the mainstream.

Lot of interesting mathematics was done by Indians, Persians, Arabs, Mayans.

Indian mathematics has an additional layer of obscurity. Very little was written down and when it was it was written down in picturesque and poetic verses (as a mnemonic device) that used a lot of symbolism and imagery. For the number one they will mention the Sun, for two the moon and so on, these mappings would also change from work to work, chapter to chapter. So one needs a lot of context to understand what a document is saying.

For example the source of the approximation above is described as follows (literal translation) [1]

The degree of the arc, subtracted from the total degrees of half a circle, multiplied by the remainder from that [subtraction], are put down twice. [In one place] they are subtracted from sky-cloud-arrow-sky-ocean [40500]; [in] the second place, [divided] by one-fourth of [that] remainder [and] multiplied by the final result [i.e., the trigonometric radius].

[1] Kim Plofker, Mathematics in India.

Re: Even faster asin() was staring right at me

#59

Post by BigTTYGothGF »

fatih-erikli-cg wrote: post #48
BigTTYGothGF wrote: post #44

Earlier quoted context omitted.

> In what way do you think a sin function is computed? In some way vaguely like this: https://github.com/jeremybarnes/cephes/blob/master/cmath/sin... > I think it is stored like sintable[deg]. The degree is index. I can think of a few reasons why this is a bad idea. 1. Why would you use degrees? Pretty much everybody uses and wants radians. 2. What are you going to do about fractional degrees? Some sort of interpreta…

It isnt good idea to store such values in code. I think it is something that computed when a programming environment is booting up. E.g. when you run "python", or install "python". I try to understand how Math.sin works. There is Math.cos. It is sin +90 degrees. So not all of them is something that completes a big puzzle.

There's no nice way of saying this, and I mean no malice here, but I think you're exceptionally confused or ignorant, and I don't think it would be rewarding for either of us to continue this conversation.

Re: Even faster asin() was staring right at me

#60

Post by LegionMammal978 »

kzrdude wrote: post #57
LegionMammal978 wrote: post #45

The coefficients given are indeed a near-optimal cubic minimax approximation for (π/2 - arcsin(x))/sqrt(1-x) on [0,1]. But those coefficients aren't actually optimal for approximating arcsin(x) itself. For reference, the coefficients given are [1.5707288, -0.2121144, 0.0742610, -0.0187293]: if we optimize P(x) = (π/2 - arcsin(x))/sqrt(1-x) ourselves, we can extend them to double precision as [1.5707288189560218, -0.2…

How did you find out that his optimization was done for a different equation, just by trial?

Just looking at the formula in the code (and the book it came from), we see that the approximation is of form arcsin(x) = π/2 - P(x)*sqrt(1-x). It is called a minimax solution in both, and the simplest form of minimax optimization is for polynomials. So we look at P(x) = (π/2 - arcsin(x))/sqrt(1-x): plotting out its error function with the original coefficients, it has the clear equioscillations that you'd expect from an optimized polynomial, i.e., each local peak has the exact same height, which is the max error. But if we look at the error curve in terms of arcsin(x), then its oscillations no longer have the same height, which indicates that the approximation can be improved.
Post reply on HN