Flaky: datatypes for real world quantities
dimaborzov.com
dimaborzov.com
x=1
for(i=0;i<n;++i)
x=0.01+sqrt(x)
Most equations that aren't trivial cannot be simplified. This datatype would only be useful for spoon-fed high school math problems. Furthermore, it costs so much CPU to perform you might as well just use an arbitrary precision library, which will probably be faster and be just as effective at preventing edge cases.
https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
I have learned to be careful about making such claims.
The quadratic equation case he shows is pretty good. Say you want to solve ax^2 + bx + c = 0. In C you might write "(-b + sqrt(b * b - 4 * a * c))/(2 * a)" which has all the precision problems he described. However, in his library that code would be converted to an AST, then symbolically simplified given the variable values, and _then_ evaluted numerically. The intermediate symbolic step would be able to automatically account for the edge cases, eg if c was 0, so that the numeric step wouldn't fail. In this case, the symbolic solver would recognize that (+, (sqrt, (-, ( *, b, b), 0)), b) is exactly zero before the floating point computation occurs.
I often write scientific programs with the issues he describes, and I have also wished for something along these lines but kind of suspect it is impossible. I usually have to play in mathematica/on paper a bit before finding an algorithm that takes care of the numeric issues (yes, even when using multiprecision), and while it would be nice for it to happen automatically, my impression is that the algorithms I find on paper are nontrivial for a computer to come up with. In some cases, however, the computer could have done it for me. But I have a feeling that in the case precision becomes an issue, even if this library gets me 90% of the way, I would still want total manual control of how the calculations occur. But I still want him to try in case it works!
Your critique really boils down to:
Most equations that aren't trivial cannot be simplified.
but this is not true, just take a look at what Wolfram Alpha or Mathematica can do.
If you want to write a library to do it for you, great! But don't advertise it as a replacement for floating point number representations, because it isn't.
Compilers aren't able to do similar optimizations, first of all the flow of data that finally leads to some computation might be non-trivial and I think most compilers deal well only with reasonably local (in space and in time) optimizations. Besides, compilers typically don't know much mathematics. If I have a function for taking a square root and a function for squaring the compiler most likely wont rewrite sqr(sqrt(x)) to just x. Certainly it wont rearrange a quadratic equation to minimize round-off.
You are basically totally dismissing an idea on very little evidence, which is typical of HN lately. It certainly isn't completely hopeless and trying it out will shed much more light on the problem than your know-it-all-in-advance comments not substantiated by any evidence (like the claim about not being able to simplify most expressions and now the claim of 99.9%).
And, he clearly isn't marketing it as a replacement for floating point. He says: "It is important to note, however, that the goal of the project is to make tools for symbolic calculations, not to create a viable alternative to the floating point." and he talks a lot about estimating numerical error and precision.
This may actually not be a problem in most instances, however. It really depends on the use case, but outside of scientific computing/engineering design we're not usually doing computations to find roots of degree >= 5 polynomials.
OTOH, as pointed out by GP, it is easy to construct 'unsimplifiable' operations which after some time may grow too large.
My conclusions are, this certainly cannot be implemented on practical systems without some care -- it's not as straightforward as it looks at first -- and certainly not a better default as is right now.
Is there any bank which uses floating point for accounting?
Most banking systems predate standardized FP and use fixed decimal representations.
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html...
Exercise 2.14 and onwards point out that two expressions that are algebraically equivalent for perfectly accurate values stop being equivalent once we introduce uncertainty. This is only for a toy example expression with 2 variables. Suppose we want to solve a linear system of equations in 100s of thousands of variables. Is it tractable to track the uncertainty for all of those variables at once? Will their uncertainties be dependent? ...
- go back and improve if necessary, or otherwise - express the uncertainty of a comparison
thanks for the link :)
Note however, that solutions to many problems may in a sense 'non-analytic', there may be no finite set of elementary functions on a given rational number which yields the solution.
Also, iterative answers are usually the only viable way to reach solutions, they're usually much faster than the exact solution (or the floating point precision limited solution), and you can always control how good your solution is.
Observation: So in a sense what is practically used may indeed very close to the Kolmogorov complexity of the solutions - the representation as R=IterativeProblemSolve(Problem,ClosestSolution), where we publish the problem and the desired solution! (assumig we are efficiently describing the problem)
The first rule of numerics is not to compare variables of very different magnitude. His first example has coefficients that differ by almost 200 orders. This example is totally outrageous, but still, what any reasonable person would do is introduce some scaling into the equation.
Yes, you have to think about scales, but you already do that. You never write programs with meters and seconds, you choose scaled dimensionless quantities. And unless you choose the scales very badly, you won't get any problems from floats.
Richard Schroeppel and Bill Gosper explored continued fractions in the '70s:
You may also be interested in the open source "sage mathematics", which is a frontend/interface to many different open-source symbolic solvers such as sympy, maxima, GAP, PARI, Singular, and octave.
They are not as good as mathematica currently, but can already do quite a lot.
1) Mathics 2) SAGE 3) Sympy 4) Maxima
Add one of the pattern matching and term rewriting packages and you'll be very close to the foundation of the core of Mathematica. It will be a SMOP and adding to the library of facts enabling recognition of reducible terms.
The numbers, in the billions, of course weren't there, but my guess is that the proportions are applicable.
Edit: After reading the article, I strongly disagree this approach is "better" in any sense of the word. More along the lines of using whale oil for the automobile instead of gasoline. Gasoline isn't perfect, but it works. Until we have something better (I.E. Electric), I'll stick to that.
The only place where the shoe doesn't fit is where you need a minimum accuracy. In that case what you should be doing is using integers to represent your minimum quantifiable unit.
For example, you could represent currency in millicents to give you respectably accurate rounding. Not accurate enough? Microcents then. Now you don't have enough range? Good, you're thinking about your requirements now, floating point DEFINITELY wouldn't of worked.
Microcents with signed long long (64bit) means a maximum value of 263 / 100 / (106) = 92233720368. In words "92 billion", which might not be enough.
4 billion. eak.