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

Implementing Advanced Math Functions

spin.atomicobject.com

Post reply on HN
Print view View original

1–10 of 24 posts

Re: Implementing Advanced Math Functions

#4

Post by silentbicycle »

adrianN wrote: post #2

This article lacks a discussion about floating-point vs real arithmetic. Naively implementing these functions is bound to produce nasty rounding problems.

The previous post in this series is on fixed-point math: http://spin.atomicobject.com/2012/03/15/simple-fixed-point-m... .

Re: Implementing Advanced Math Functions

#5

Post by jensnockert »

adrianN wrote: post #2

This article lacks a discussion about floating-point vs real arithmetic. Naively implementing these functions is bound to produce nasty rounding problems.

The problem isn't in rounding or floating-point, these implementations won't be good enough to get even close to have to consider the issue of having to round correctly.

You really need to reduce the argument to a sane range, otherwise the `n' required even in infinite precision would be huge.

If someone is interested in how to do it, check out http://www.netlib.org/fdlibm/

Re: Implementing Advanced Math Functions

#6

Post by stephencanon »

Unfortunately, Taylor series are just about the worst choice possible for implementing transcendental math functions, due to the highly non-uniform error distribution. You end up doing far to much work to get good accuracy near the edges of the domain of interest. Much better choices of polynomial approximations for almost any such situation are (in increasing order of goodness and difficulty to work with): Chebyshev series, Cathedory-Fejer, and Minimax.

Re: Implementing Advanced Math Functions

#7

Post by zackzackzack »

davidkellis wrote: post #3

This is the type of stuff I come to HN for. This is so refreshing to see after days worth of press releases about Apple, new gadgets, and other mainstream news regurgitation.

If you want to see some crazy math stuff, look into axiom[0]. It's an open source computer algebra system programmed in Common Lisp. The manuals for the project add up to be ~10,000 pages[1]. It's all done in the literate programming style and it's being actively developed. I am probably going to write an idea up in a month or so, but if a computer programmer wants to learn some advanced Math beyond first year calculus quickly, downloading axiom and working through the first tutorial is the way to go.

[0]http://www.axiom-developer.org/ [1]http://www.axiom-developer.org/axiom-website/documentation.h...

Re: Implementing Advanced Math Functions

#8

Post by evincarofautumn »

I have the feeling that a naive polynomial approximation would give lower relative error than a naive Taylor series approximation—at least for the same number of clock cycles. Or am I just crazy?

    float sin(float const x) {
        float const y = (4 / pi) * x + (-4 / (pi * pi)) * x * abs(x);
        return y + 0.218 * (y * abs(y) - y);
    }

Re: Implementing Advanced Math Functions

#9

Post by jvranish »

stephencanon wrote: post #6

Unfortunately, Taylor series are just about the worst choice possible for implementing transcendental math functions, due to the highly non-uniform error distribution. You end up doing far to much work to get good accuracy near the edges of the domain of interest. Much better choices of polynomial approximations for almost any such situation are (in increasing order of goodness and difficulty to work with): Chebyshev…

If your goal is accuracy, you are absolutely correct. But in the instances where I've wanted to implement my own versions of transcendental math functions, accuracy was actually pretty low on my list of priorities. Often just a couple terms of a taylor series was accurate enough, fast, and easy to implement.

Re: Implementing Advanced Math Functions

#10

Post by stephencanon »

jvranish wrote: post #9
stephencanon wrote: post #6

Unfortunately, Taylor series are just about the worst choice possible for implementing transcendental math functions, due to the highly non-uniform error distribution. You end up doing far to much work to get good accuracy near the edges of the domain of interest. Much better choices of polynomial approximations for almost any such situation are (in increasing order of goodness and difficulty to work with): Chebyshev…

If your goal is accuracy, you are absolutely correct. But in the instances where I've wanted to implement my own versions of transcendental math functions, accuracy was actually pretty low on my list of priorities. Often just a couple terms of a taylor series was accurate enough, fast, and easy to implement.

It's true regardless of what your goal is (unless your goal is to play with Taylor series approximations). Even if you're going purely for speed, you can often replace a third-order Taylor series with a second-order minimax polynomial, and deliver the same or better accuracy with significantly fewer operations.
Post reply on HN