4 ms·
Let's unpack: > With the correct numeric type (rationals) precision is not fixed. Almost no problems can be represented exactly by rationals. Even the sqrt(2)
by ChrisLomont 6y ago
Let's unpack:
> With the correct numeric type (rationals) precision is not fixed.
Almost no problems can be represented exactly by rationals. Even the sqrt(2) you started with is not rational.
And rationals are unusable for almost any type of work, because they grow exponentially (in time and space) for most problems.
For example, if you tried to compute a simple mandelbrot set with rationals, you'd need more bytes than there are subatomic particles in the universe (~10^80).
Proof: Mandelbrot takes a complex number c = x + i y, which you want to represent as a rational, and iterates z <- z^2 + c. Squaring doubles the number of digits for each of the numerator and denominator, so each iteration requires ~2 times the storage of the previous iteration. Thus you'll need over 2^300 bytes for 300 iterations, which is > 10^90. A common mandelbrot uses over 1000 iterations.
So you see rationals are computationally unusable for even simple tasks.
> symbolic math libraries
These can be arbitrarily slow and use arbitrarily large memory for simple problems - which I stated above when I said "Such things are either incredibly inefficient or mathematically unsound." For example simple converging infinite sums that don't have closed forms known to your tools would never evaluate - the only solution is some fixed, finite representation if you want to use the value in later computations. The same thing for integrals, root finding, pdes, and thousands of other problems.
> deep learning libraries
Deep learning libraries have led to a reduction in precision specifically for the reasons I mentioned: lower memory requirements and higher speed. Hardware vendors from Intel to NVidia to AMD to ARM have introduced lower precision math, including the new bfloat16 (and some have a bfloat8) for these reasons. I think this is the opposite of what you claimed, but supports my claim.
Care to show me where deep learning libraries do perfect symbolic computation in the process of deep learning? I'm aware people try to train them to do symbolic computation, but the libraries themselves aren't using the types of reductions you posted.
> most optimizing compilers
Most compilers would reduce sqrt(2) * sqrt(2) to 2? List them. (Heck - list one!) It's simply not true (as can be checked trivially for all common C++ compilers on godbolt).
I've seen none, despite following optimizing compiler theory and practice for decades.
>Wolfram Alpha
Redundant with the symbolic stuff above - and I've used Mathematica since v1.0 in 1987 quite extensively. It most certainly is slower doing anything symbolically that can be done numerically, and there are lots of problems it cannot do symbolically without puking, but those same problems run instantly when approximated with floating point.
There's ample pages listing things symbolic engines get wrong or cannot do, but that can be done elsewhere.
>I don't understand your point about the Tablemaker's dilemma because it is a dilemma only if precision is fixed
????
The dilemma is not about fixed precision.
The problem is correctly rounding a function as if it had an infinite expansion first. For some functions this means arbitrarily large computations. Ahead of time mankind does not know how many digits are needed for many common uses. So the problem is not about fixed precision - it's about possibly unbounded computation, which is vastly different.
For example, no one has a bound on the number of digits needed to compute correctly rounded a^b for any two floating point values a and b.
And there exist computable numbers for which the rounded value can never be computed with any amount of digits [3].
So it's not about fixed precision. It's far more subtle.
If you're willing to run unbounded in time and space computations, then you can more and more precise answers, but at every point you still don't know if you've escaped the Tablemaker's dilemma. This is the point.
Here's a guy I've followed for decades, one of many researchers on the topic [1]. Note that his "hard to round cases" in 2013 took 1576 years of computer time to determine how many digits are needed for double precision values for some elementary functions, precisely because this is not the trivial problem you think it is.
Here's a 2016 paper doing some work on GPUs [2]: " For example, the Nesterenko and Waldschmidt [1996] bound for the exponential in double precision states that 7,290,678 bits of intermediate precision suffice to provide a correctly rounded result."
To get 64 bits of accuracy, correctly rounded, you need 1 megabyte and an incredible amount of computation. My point exactly. And these bounds tend to increase exponentially, not linearly, soon pushing such issues beyond currently computable (which is also why there are still research papers being published on getting results for 64 bit doubles in various ways and for various elementary functions).
Again you have the choice I presented: you either accept unbounded in time and space behavior, or you fix time and space to make things usable with approximations. Floating-point is an incredibly good solution to making numerics as good as possible under fixed space and time requirements.
[1] https://www.vinc17.net/research/index.en.html https://www.vinc17.net/research/index.en.html
[2] https://dl.acm.org/doi/pdf/10.1145/2935746 https://dl.acm.org/doi/pdf/10.1145/2935746
[3] https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma
- bjourne 6y ago> Almost no problems can be represented exactly by rationals. Even the sqrt(2) you started with is not rational. Almost all numerical problems software developers deal with can be represented exactly using rationals. Only a small fraction of all problems involve transcendentals. And those can't be represented exactly by floats either so I don't know what point you're making? > For example, if you tried to compute a simple mandelbrot set with rationals, you'd need more bytes than there are subatomic particles in the universe (~10^80). Well, yes. You'd run into the same problem if you tried to compute all the decimals of pi too. Using rationals does not mean that you can't round results. > So you see rationals are computationally unusable for even simple tasks. I see that rationals cannot represent all real numbers. > These can be arbitrarily slow and use arbitrarily large memory for simple problems - which I stated above when I said "Such things are either incredibly inefficient or mathematically unsound." For example simple converging infinite sums that don't have closed forms known to your tools would never evaluate - the only solution is some fixed, finite representation if you want to use the value in later computations. I wrote that in mainstream languages should be able to evaluate (2^(1/2))^2 == 2. How do you go from there to requiring them to be able to evaluate infinite sums?! > Care to show me where deep learning libraries do perfect symbolic computation in the process of deep learning? I didn't claim that. > Most compilers would reduce sqrt(2) * sqrt(2) to 2? List them. (Heck - list one!) It's simply not true (as can be checked trivially for all common C++ compilers on godbolt). I didn't claim that. Compilers are stuck with IEEE 754 fp semantics and therefore won't simplify (2^(1/2))^2. But there is no technical reason why they couldn't. To paraphrase your reply: "Rational arithmetic and symbolic computation can't solve every problem. Therefore they are useless/no better than floating point arithmetic." From a theoretical perspective that is perhaps true but in practice both are very useful tools.
- ChrisLomont 6y ago>Almost all numerical problems software developers deal with can be represented exactly using rationals. Only a small fraction of all problems involve transcendentals. There's more classes of real numbers than rationals and transcendentals. Hint: your example of sqrt(2) is neither. As to doing things exactly with rationals, anytime you take a sin, cos, exp, log of any non-zero rational number the result is not rational. Any time you take a root of a non-perfect power rational you don't get a rational number (you get an algebraic number, which is neither rational nor transcendental). So all you can do is simple arithmetic: + * / - (actually, that's from the definition of the field Q of rational numbers). And you still run into the problem that rational number arithmetic gets arbitrarily slow and runs out of memory. Each multiply on average results in requiring the sum of the storage sizes of the multiplicands, making more than about 40 multiplications infeasible before you're out of RAM. So your view of "almost all numerical problems software developers deal with" must be limited to only those using simple arithmetic and no more than around 40 operations. That's amazingly constraining. What problems do you call numerical problems that fit your constraints? Things that cannot be done exactly with rational numbers includes pretty much all of gaming (3D or otherwise), deep learning (probably every model has an exp in it), scientific computing, audio and video processing (cos and sin all over the place), and on and on. >Using rationals does not mean that you can't round results. Wait, you just claimed "...can be represented exactly using rationals. Now you want to round, throwing out the exactness? Which is it? And congrats - you just re-invented floating-point math which is simply approximating values using rational numbers in a clever manner to handle larger ranges than fixed point. But they're still always rational approximations to values. >I wrote that in mainstream languages should be able to evaluate (2^(1/2))^2 == 2. How do you go from there to requiring them to be able to evaluate infinite sums?! Ah, so you mean languages should be able to simply solve this one specific problem, not all relatively simple symbolic problems? That seems like an even bigger mess than using floating point, which is well-defined and covers a large class of problems. Does your mythical language know (A^(1/B))^B==A for all rationals A and B also representable in your language? Or are you limited to the value A=B=2 only? (Hint: if you claim it should hold, you're gonna hit problems again :)