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

Chebyshev approximation and how it can help (2012)

embeddedrelated.com

Post reply on HN
Print view View original

11–20 of 20 posts

Re: Chebyshev approximation and how it can help (2012)

#11

Post by AlotOfReading »

inamberclad wrote: post #9

Once more, this is _exactly_ why Ada has arbitrary precision decimal arithmetic. One merely needs to specify type Result is range -100 .. 100 delta 0.0001; and the compiler will figure out how to give you fast math with only the accuracy and resolution that you need!

How does that feature work without a solution to the tablemaker's dilemma? Does the compiler just give up and give you arbitrary precision every time you use transcendentals or does it give up and use lower precision if the estimate exceeds some arbitrary bound?

Re: Chebyshev approximation and how it can help (2012)

#12

Post by alexcnwy »

programjames wrote: post #7

Some other useful things about Chebyshev approximations: 1. You can use a Fourier transform to get the coefficients in O(n log n) time. 2. So, multiplying two approximations only takes O(n log n) time. 3. Also, adding, integrating, or taking the derivative only take O(n) time. This is why chebfun/chebpy can run so fast while magically finding roots/derivatives/etc. A couple other interesting facts: 1. Remember the do…

I’m gonna give this to my gpt system prompt as an example of how I want everything explained :)

Re: Chebyshev approximation and how it can help (2012)

#13

Post by LegionMammal978 »

AlotOfReading wrote: post #11
inamberclad wrote: post #9

Once more, this is _exactly_ why Ada has arbitrary precision decimal arithmetic. One merely needs to specify type Result is range -100 .. 100 delta 0.0001; and the compiler will figure out how to give you fast math with only the accuracy and resolution that you need!

How does that feature work without a solution to the tablemaker's dilemma? Does the compiler just give up and give you arbitrary precision every time you use transcendentals or does it give up and use lower precision if the estimate exceeds some arbitrary bound?

Looking at the spec [0], it only demands 1 ULP of precision for the elementary operations, and 2, 4, or 8 ULPs for special functions. So there's no magic 1/2-ULP guarantee.

[0] http://ada-auth.org/standards/22rm/html/RM-G-2-3.html

Re: Chebyshev approximation and how it can help (2012)

#14

Post by kragen »

inamberclad wrote: post #9

Once more, this is _exactly_ why Ada has arbitrary precision decimal arithmetic. One merely needs to specify type Result is range -100 .. 100 delta 0.0001; and the compiler will figure out how to give you fast math with only the accuracy and resolution that you need!

have you tested this? how fast and accurate were the results? or are you simply assuming that all compilers are perfect?

my experience outside of ada is that decimal arithmetic is never fast on binary computers

Re: Chebyshev approximation and how it can help (2012)

#15

Post by guyomes »

If you are ready to spend some precomputation time to compute a good approximation, you can use the Remez algorithm [1]. It is implemented in the Sollya library for machine precision [2,3]. It has notably been used to implement the Core Math library [4] to provide correct rounding for the math functions in the libc library.

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

[2] : https://www.sollya.org/

[3]: https://www.sollya.org/sollya-weekly/sollya.php

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

Re: Chebyshev approximation and how it can help (2012)

#16

Post by abecedarius »

kragen wrote: post #14
inamberclad wrote: post #9

Once more, this is _exactly_ why Ada has arbitrary precision decimal arithmetic. One merely needs to specify type Result is range -100 .. 100 delta 0.0001; and the compiler will figure out how to give you fast math with only the accuracy and resolution that you need!

have you tested this? how fast and accurate were the results? or are you simply assuming that all compilers are perfect? my experience outside of ada is that decimal arithmetic is never fast on binary computers

aaui that Ada line would declare a fixed-point type, so decimal/binary shouldn't really come up except for overflow handling, here. (Haven't tried it though.)

Re: Chebyshev approximation and how it can help (2012)

#17

Post by mhh__ »

alexcnwy wrote: post #12
programjames wrote: post #7

Some other useful things about Chebyshev approximations: 1. You can use a Fourier transform to get the coefficients in O(n log n) time. 2. So, multiplying two approximations only takes O(n log n) time. 3. Also, adding, integrating, or taking the derivative only take O(n) time. This is why chebfun/chebpy can run so fast while magically finding roots/derivatives/etc. A couple other interesting facts: 1. Remember the do…

I’m gonna give this to my gpt system prompt as an example of how I want everything explained :)

Good luck. It uses to be this clear (modulo "reasoning" abilities) but it gets dumber and more waffly with every update

Re: Chebyshev approximation and how it can help (2012)

#18

Post by herodotus »

This is so strange: a few days ago I commented on an HN post (https://news.ycombinator.com/item?id=40582712) about when "programmer" became an acknowledged job title, and, in my comment, mentioned how I used a Chebyshev approximation followed by two iterations of Newton's method to compute sqrt, and then today this article shows up with exactly that use case!

I wrote that code (to compute sqrt 2) in 1974 or 1975 in IBM 360 Assembler. I used a conditional macro constant that increased the number of iterations of Newton's from 2 to 3 just in case the client wanted double precision.

Re: Chebyshev approximation and how it can help (2012)

#19

Post by skyde »

richrichie wrote: post #10

As Boyd says in his book on Chebyshev Methods: when in doubt use Chebyshev polynomials. I use Chebyshev polynomials extensively in finance and have tried problems like MNIST with Chebyshev and they get close to CNNs in accuracy. ApproxFun Julia package pretty cool for Chebyshev work: https://juliaapproximation.github.io/ApproxFun.jl/latest/

What do you mean by close to CNN?

What is your architecture? Is it just a fully connected layer of chebyshev?

Re: Chebyshev approximation and how it can help (2012)

#20

Post by getlawgdon »

mhh__ wrote: post #17
alexcnwy wrote: post #12

Earlier quoted context omitted.

I’m gonna give this to my gpt system prompt as an example of how I want everything explained :)

Good luck. It uses to be this clear (modulo "reasoning" abilities) but it gets dumber and more waffly with every update

Agreed.
Post reply on HN