Inexact is Good Enough
Oh, my God! It has a little mark for pi!
I personally have a very difficult time understanding how anyone ever got by using just a slide rule, yet the Apollo astronauts took them to the moon to make any calculations there that they needed to. I sit there and think that it requires someone to examine the distance between two marks on the rule and estimate several decimal places. Visual estimation? By a human being? On a mission-critical calculation? Inconceivable! And, of course, any complicated calculation performed before say, 1945, were most certainly done by hand using a slide-rule or a table of logarithms. For example, the designers of the Eiffel Tower or the Brooklyn Bridge didn’t have the benefit of any type of exact calculation except what they could do by hand.
I think the reason I find this so disconcerting is that those of us in the digital generation (especially those of us who took too many discrete math classes in college, i.e. computer science majors, such as myself), have a lot of philosophical trouble with inexact results. We studied the natural numbers and the integers, number theory as it relates to Gödel’s Incompleteness Theorem and Alan Turing and the Entscheidungsproblem (I love saying “Entscheidungsproblem”). All of these theorems and results are about discrete, countable sets (the natural numbers, mostly). The reals are left as kind of a messy exercise for the reader or the IEEE.
Most of our programming languages also hide the fact that floating-point division and integer division are very different operations, internally. It can be very disorienting when one first uses a functional language like Haskell that has different syntactic forms for integer and floating-point division:
Hugs> 10 / 3
3.33333333333333
Hugs> div 10 3
3
That’s Haskell, but OCaml, Scheme and probably other functional languages have similar operators. And Haskell’s type-inference system will brutally punish you if you use the wrong one in a function, until you get it right. This is, perhaps, taking the divide between pure, beautiful, discrete exact integers and profane, disgusting, inexact real numbers a bit too far.
But in Java, C, C++, C# and lots of other languages, we have nearly the opposite problem, as numeric operations have an implicit widening conversion so that an integer divided or multiplied by a floating-point value gives a floating point value. This yields the familiar round-off error inherent in these types of conversions and calculations, which is why we should probably avoid using them for financial calculations. It also hides from the programmer that they just descended from the heaven of perfect precision into the hell of inexactness. Perhaps I’m being a bit too dramatic.
The fact is, there’s a whole world of calculation where “Inexact is Good Enough.” For example, in a post on Better Explained that I already linked to above, we find out that 40 digits of pi is enough to calculate the number of atoms needed to form a circle around the entire universe. So, like 640K of RAM, 40 digits of pi is enough for any conceivable real-world calculation. Computer Science courses, with the exception of scientific computing classes, generally shy away from discussing these sloppy, inexact real-world scenarios, but that is to the detriment of our growth as programmers, I think.
There are algorithms that only work because Inexact is Good Enough. For example, video and audio compression algorithms (”lossy” compression algorithms, at least) are based around discarding information that people have a difficult time perceiving psychologically.
The world is sloppy and inexact, and as developers, we may need to check ourselves before we try too hard to make it fit into a perfect and exact representation inside the machine.
P.S. A reader on reddit also pointed out that NP-Complete problems can be approximately “solved” in polynomial time, as shown here for the travelling-salesman problem, if you can handle an inexact result.
August 29th, 2008 at 12:01 pm
However, I prefer $33.3333 over $33.33 myself.
August 29th, 2008 at 7:14 pm
Hm sorry for the criticism here, but, my ghci sez:
Prelude> 1/3.0
0.3333333333333333
And my C++ says that 1/3 is 0.
It was Pascal that had the mathematically sense of division IIRC. Python has it, too, with “from __future__ import division”.
Additionaly, there *are* some NP-complete problems that ***cannot*** be approximated, i.e. http://en.wikipedia.org/wiki/Maximum_independent_set_problem.
However, heuristics yield “good enough” results on real-world instances.
Maybe research better next time?
August 29th, 2008 at 11:36 pm
That’s because Haskell can infer that you are using 1 as a Franctional. Force it to a non-Fractional type to see what he’s talking about.
Prelude> (1::Integer)/3.0
:1:0:
No instance for (Fractional Integer)
arising from a use of `/’ at :1:0-15
Possible fix: add an instance declaration for (Fractional Integer)
In the expression: (1 :: Integer) / 3.0
In the definition of `it’: it = (1 :: Integer) / 3.0
Maybe research better next time?
(sorry, couldn’t help myself…)
August 30th, 2008 at 2:44 am
Good thought, good article.
I want to comment on comp sci a bit though. This is a field that’s been badly watered down lately in all but a few schools. The way I was thought, everything is a trade-off. The trade-off between time and space is the most discussed. Programming something like the Atari 2600 is interesting, where you have very little CPU power but even less space — 128 bytes of RAM — and so are forced to optimize for space. Good comp sci curriculums teach about NP-complete problems and algorithms, where a perfect solution for even a normal set of data in unfeasible, and the approximate (”pretty good”) solutions that are workable. Students learn — or should learn — that various constraints are wins. The more you know about your data or the problem space, the more you can optimize. Closed polygons versus open ones; directed versus undirected graphs; and so on. These are approximations in that a less generalized algorithm is an approximation of the more generalized algorithm. Kind of.
Just looking at the history of computer gaming, the break throughs usually came about when someone was able to do something in an approximate fashion. Flight sims started on 8 bit machines with cos/sin tables with 256 entries of 8 bits each, which is terrible precision, but some clever chap at Sublogic thought it might just be good enough to make something kind of fly. And he was right. 8 bits isn’t many, but most 8 bit games somewhere have tables where the bytes are broken down further, assigning 4 bits to the whole part and 4 bits to the fractal part of a number, and similar things. The programmers spend a lot of time thinking about how much precision they really need to eek by. Early interesting enemy AIs were finite state machines. The ghosts in Pac Man have simple personalities. I’ve been playing a bit of Blaster Master on the NES lately and the little routines the various types of baddies go through is quite impressive. Doom used a terrible simplification of the 3D model called “raycasting” which is piled full of constraints and trade-offs.
If you’re a smart guy playing, trying to see if something unlikely is in fact feasible, you’re coming at all of this very different from a work-a-day grunt. The smart guy playing is going after what’s barely possible; the grunt uses inherent difficulty in problems to excuse himself from being expected to exceed, or even take the assignment seriously.
To say that people used to use slide rules to do amazing things is a bit of a simplification. The interesting things that were done were done with slide rules. But most people were using mechanical adding machines which required less imagination to use and had even less precision, besides nothing resembling logs. Most people were doing very mundane things with tried and true technologies that were simple to operate and quite limited in potential. And that hasn’t changed. I don’t expect it will.
Cheers,
-scott
August 30th, 2008 at 2:45 am
This is something I have to teach to every new graduate in engineering, the moment they start their post-academic career. “Close enough” is a valid phrase in the engineering of most things - partly because we cannot know for certain much of the input data we are using to design roads, bridges, buildings, etc. The input data isn’t perfect, so stop carrying excessive significant figures. Sometimes 3*3=10 is acceptable.
August 30th, 2008 at 9:34 am
Thanks for the feedback, everyone.
Although, I see I made that classic mistake of bringing up Haskell, and I brought out all the Haskell experts. Next time, I’ll stick to Scheme.
What I was getting at with Haskell’s division operators is something like this:
collatz :: Int -> [Int] collatz 1 = [1] collatz n = if (odd n) then n : collatz (3 * n + 1) else n : collatz (n / 2)This generates an error because you’re using the wrong division operator. It’s not really on the topic of the post, so I left it out. It’s not a criticism of the language, so much as a “feature” that you either take advantage of or don’t.
August 30th, 2008 at 3:33 pm
Common Lisp has precise integer division:
CL-USER> (/ 10 3)
10/3
CL-USER> (+ 7/6 5/6)
2
August 30th, 2008 at 3:53 pm
I wish numerical methods were more emphasized in the CS education I got.
I did take one class which covered interval arithmetic, which is basically a way to measure the error in your calculations, which leads to a clean analysis of floating point error accumulation.
For example, you mention that pi to 40 decimal places is sufficient for any needs, but that really depends on what else you are doing with the result - maybe you’re using it to compute the volume of a pipe, and adding many such computations together. With interval arithmetic you can figure out whether you still have enough precision for your needs, given your inputs. Most CPUs also allow you to modify the rounding method, so you get guaranteed intervals.
September 9th, 2008 at 10:03 pm
Even integers can be vague in their fit to the real world — and still useful.
It makes sense to say “There are more than 10 peaks in the Rocky Mountains”, and true for all practical planning.
It makes sense to say “There are fewer than 100,000,000,000 peaks in the Rocky Mountains”, and true for all practical planning (fractal landscape models have their own problems).
It makes no sense to say “The number of peaks in the Rocky Mountains is odd”, or “The number of peaks in the Rocky Mountains is even”, so neither statement is true. We cannot define “peak” closely enough.
So “The number of peaks in the Rocky Mountains” is a ‘number’ for which some but not all arithmetical statements have a truth value.