From njackiw@mail.keypress.com Sun Feb 2 21:29 EST 1997
Aarnout,
Thanks for taking the time to put together HTML pages describing your technical problems with Sketchpad, which Shari Horne brought to my attention. Both of them describe complex subjects with no easy answers, but I'll try to explain them as best as I can.
Cycloids
As far as I can tell, there's no problem with the construction here, and you are indeed running into a precision/accuracy error in the internal numeric representation of the construction. Sketchpad is forced to represent things numerically, instead of symbolically, so that it can compute the updated figures that one sees while dragging a point in real time. (In other words, while one could write a program which modeled the construction symbolically, and therefore could solve problems and answer mathematical questions >exactly<, it wouldn't be fast enough to allow dynamic dragging---at least not on today's desktop machines!)
Referring to my original construction (which you can access by clicking here )Nic wrote:
However, Sketchpad's numeric resolution is "pretty good"--there's a fair amount of internal code that attempts to limit loss of precision. This made me wonder why the cycloid.gsp sketch was demonstrating such gross inaccuracies, which are visible both in the 8/3 animation and by numerically comparing the radii of the two circles. (In the 8/3 configuration, the small circle has radius ~58.50021 pixels, instead of 58.5 exactly.) Examining the construction revealed that the entire cycloid is built on a very unstable numericall foundation. In other words, it's surprising that the 8/3 configuration is the only place you're finding problems--I would expect them to show up in most of the configurations!
In order to understand why this is so, it's necessary to delve into the mechanics by which computers represent real (and possibly irrational) numbers. This form of representation that Sketchpad uses is called "floating point," which means that a fixed number of binary digits are used to represent each number, combined with an exponent that indicates the magnitude. (In Sketchpad's case, there are about 56 binary digits of mantissa and 8 of exponent.) This is like scientific notation, except in binary.
There are two immediate ramifications of such a numeric model. The first is that many numbers, both rational and irrational, cannot be represented exactly. 1/3, for instance, can not be represented as a binary fraction precisely, so we must settle for the nearest representable approximation (..which should be within plus or minus 1 x 2^(-56), if you're following the math...). The second implication is that, as always when we represent things in scientific notation, performing arithmetic on our numbers causes them to lose precision over time. As an example, let's grossly exaggerate and say that computers can't represent the number 3 exactly, and instead use the nearest representable approximation of 4. At this point, we're off by one, or by about 33% of the number we're trying to represent. Now let's use a computer to solve 3-squared. That's 4x4 (because computers use 4 to represent 3), which is 16. Mathematically, we know the answer is 9, so our computer is off by 7, which is almost 78% error. Our precision has decreased dramatically as the result of a single multiplication! As it turns out, addition and subtraction introduce little if any precision error, multiplication and division decrease precision fairly dramatically, and square roots, sines, and various derived trigonometric and transcendental functions have the worst effect on the net accuracy of the results.
Now let's look at what's going on in your cycloid sketch. Basically, the fixed large circle has an exactly representable radius of 156 pixels. (We know it's exact, because it was drawn with the freehand tools, which are registered to the integer grid imposed by pixels on the screen...you can't draw a circle centered 1/3 of the way between two pixels!) The various action buttons on the right control the radius of the smaller circle, by moving (hidden) point '**' to various subdivisions along a hidden segment. These subdivisions are located by Euclid's parallel partioning method. So far so good. But to what object are each of these parallels being constructed as parallel? Segment ab, which is drawn through point AM. And what is AM? AM is the intersection of something with a circle which is determined by another intersection of something with a circle which is determined by another intersection of something with a circle which etc. etc. etc. Ultimately, there are 24 circle intersections occurring between the accurate, exactly-representable points of the construction and the segment which governs the calculation of all of the ratios on the right side of the screen. Recall that to solve the intersection of a circle with a line or another circle requires a square root, which (by the previous paragraph) involves a dramatic loss in precision. In essence, this construction chops the available accuracy of the computer in half not once, not twice, but twenty-four times before going on to make any calculations of ratios!
So while from a compass and straight-edge perspective, this construction is entirely accurate, from Sketchpad's feeble numerical model, it's surprising we don't see greater error! Of course, the fault is entirely Sketchpad's--and I have, at various times, looked into ways that Sketchpad could interact with a more powerful symbolic engine (like Maple or Mathematica) to see if an apparent numeric result actually resulted from the construction, or merely from the inaccuracies that occur whenever you represent and computer numbers using "floating point" arithmetic.
Meanwhile, however, I should point out it's possible to get much better performance out of Sketchpad (especially once you understand how mathematical error can be introduced and expanded in a construction!). Generally speaking, the best way to preserve accuracy is to have as few computational steps between the original numbers and the desired results as possible. In Sketchpad, this corresponds to as few intermediate objects as possible. (A side benefit of this approach is that your sketch will respond more rapidly to freehand dragging and to animation as well.) Following this philosophy, I constructed a cycloid in which I used dilation by a scale factor of 8/3 to calculate the ratio necessary between the radii of the two wheels. When I animate >that< much simpler construction, the animation closes exactly, and the small spoke traces out an accurate stellation of eight points after three revolutions around the larger wheel.
Sadly, however, the construction using dilation still has similar errors. Another method of overcoming the errors described is to adjust the size of the large circle for each case and I have found that we can find (in each case) particular settings that avoid the problem BUT the setting will not work in all cases.