Hacker News new | ask | show | jobs
by ChrisFoster 1898 days ago
Yes, well put. I'd take it further - in numerical code there is no real distinction /at all/ between closed form vs iterative solutions. Every type of numerical code is subject to truncation error; an iterative method with few moving parts may systematically converge to a more accurate result than the direct expression of a closed-form solution.

It's quite interesting to delve into how special functions like `sin` and the like are actually implemented and the lengths people go to to make them "correctly rounded" (see, for example, crlibm). Even something as simple as linear interpolation between two floating point endpoints can be quite subtle if you want an implementation that is exactly correctly rounded and also fast.

1 comments

> I'd take it further - in numerical code there is no real distinction /at all/ between closed form vs iterative solutions.

This assertion is however wrong. Closed form solutions at worse accumulate rounding errors of a single expression, while iterative solutions not only pile on rounding errors throughout the iterations but they also have to stop by truncating the rest of the solution, leading to results which not only is approximate but also amplifies rounding errors.

This is false, and your description of how to analyze/compare errors of iterative algorithms is also wrong. In short, if you have an algorithm with error n*eps compared to m*eps+tol, there's no a priori reason why one would be greater/equal to/smaller than another, it's just an overgeneralization (because you don't know yet what m,n,tol are). Focussing on truncating the rest of the solution is also wrong because that makes you think of only some specific types of iterative algorithms, as if they all converge linearly/sublinearly or something. In this particular paper the closed form is given as a ratio of two integrals, and both integrals are evaluated approximately using a perfectly reasonable quadrature rule, suitably chosen, and that quadrature rule has a truncation error, and that error is small enough not to matter.