How It Works

Software that graphs explicit functions has it pretty easy. Set the x-value equal to the left hand window coordinate. Calculate the y-value for this x-value, add an increment to the x-value and calculate the next y-value. Then connect these two points with a short segment. Add another small increment to x, and so on, until you get all the way across the screen.

For example, suppose y = x2 - 2. If x = -5 is the left edge of the screen, the y-value that corresponds is y = (-5)2 - 2 = 23. The graph starts at the point (-5, 23). Add 0.1 to x, so x = -4.9, with the corresponding y = (-4.9)2 - 2 = 22.01. Draw a segment connecting the points (-5, 23) and (-4.9, 22.01). Now proceed for x = -4.8.

This is a relatively fast and efficient algorithm, and the program is designed to do this when it recognizes an explicit function (perhaps you noticed a difference in the speed when graphing y = 1/x and xy = 1, for instance), but it won't work for an implicit function, like x2 - xy2 + sin y = y, since setting x to a particular value leaves an equation of arbitrary difficulty that mist be solved to find the value (or values) of y (if any).

Here's how this program works. Suppose X-Scan is checked. The program first sets y equal to the y-value at the top line of pixels on the graph, so suppose y = 5. Substituting gives x2 - x(5)2 + sin 5 = 5, or x2 - 25x - 0.9589 = 5. Now this particular example is a quadratic in x, so we know that there are either 2 real roots or no real roots, and there are straightforward algorithmic methods to find the roots (ala quadratic formula), but in general, you get an equation in x of arbitrary complexity at this stage.

What the program does is first set x equal to the x-value of the leftmost pixel on the graph, and substitutes this value into the left and right sides of the equation, separately. Suppose x = -5. In our example, the left side would be (-5)2 - 25(-5) - 0.9589 = 149.05, and the right side is 5. The program notes that the left side of the equation has a larger value than the right side.

The program then proceeds to the next pixel in the row, suppose it has an x value of -4.95, for which the left side of the equation above becomes (-4.95)2 - 25(-4.95) - 0.9589 = 147.29. The program continues to scan the x-values in this row (hence the name X-Scan...) until it finds an x-value for which the left side of the equation is not greater than the right side. If such an x-value is found, the program colors the corresponding pixel on the graph. When the current line of pixels is scanned, the program sets y equal to the y-value of the second line of pixels and scans again, etc. Y-Scan works similarly.

That's why the program is SO SLOW!!! It has to calculate the value of the function for each pixel on the graph. If both X-Scan and Y-Scan are checked, it has to do it twice!

This algorithm is not original. I first saw it in a magazine article back in my TRS-80 days. I don't remember the author's name, or the article's title, or even the magazine from that long ago, but, whoever you are - Thanks!

last update October 20, 2006 by JL Stanbrough