Recently, I overheard some programmers talking about creating a simple starfield simulation for a screen saver module. You probably have seen one of these before. The stars begin clustered in the center of the screen and move out toward the edges, producing an effect similar to what you might see while looking out of a spaceship window.
The programmers were talking about the best way to plot the path of the stars, and the general consensus was that it should be done using trigonometry and would require a great deal of floating-point calculation. Each star would occupy a given point and traverse a course which would be defined by triangulation using trigonometric functions.
These programmers knew something about trigonometry and immediately understood how it could be applied to their particular problem. Trigonometry was the tool and their manner of thinking was dictated by it.
While this was not entirely unreasonable, and the general method which they proposed will work, there is an even simpler way to solve this which involves no floating point and is much faster. But if you are stuck on the idea that the problem involves trigonometry, you may never discover an easier way. This was a case in which the tool needed to be abandoned and a new one selected.
INTEGERS SCALE THE SLOPE
It is possible to use integers for each star’s location and slope. The speed and direction of each star’s motion can be expressed by the slope. For example, a slope of 2/4 would have the same direction as a slope of 1/2, but it would have a greater speed.
The problem with integers is that they are imprecise. What if you needed a slope of 1.4/2.125? Another significant reason why they felt it was important to use floating point was to avoid round-off errors. In a repeating series of equations, such as would be involved in plotting the path of a moving object or calculating an amortization table, round-off errors would accumulate in integers and produce results that would become more invalid with each iteration until they were completely useless.
Does this mean we have to rule out using integers? No, but we have to be intelligent about it. The right idea is to use scaled integers. Instead of working on a scale of one counting unit per pixel, use something larger. In this month’s program, I use 1,000 units per pixel (see the SCALE constant in the source). This gives me the precision I need while avoiding round-off problems. So, a slope of 1.4/2.125 becomes 1,400/2,125. A scale of 1,000 is not perfectly precise, but it is certainly adequate for my needs.
A slope of 3.54821/2.94516 would become 3,548/2,945 and a little precision would be lost, but this is so small that we can easily ignore it. Remember, too, that floating-point numbers are also integers at heart and represent only an approximation of the true number.
You may have seen this technique before. It is common in financial programs to keep track of money using integers by counting in units of cents or even tenths of cents.
If the precision of fractional numbers is vitally important, the most accurate way to represent them would be as rational integer pairs–one for the numerator and another for the denominator. In this way, you can represent any rational number with great accuracy. For example, there is no way to adequately represent 1/3 as a decimal number.
Somewhere, you have to truncate the repeating 3’s in 0.3333333, so you will be left with only a close approximation. However, if you use an integer pair, you can represent it as 1 (the numerator) and 3 (the denominator). Any additional number can be represented in this way. This is, in fact, the definition for rational numbers. Irrational numbers, such as pi, cannot be represented as integer pairs, but you will still get a more accurate approximation.
The rest of the Stars program is pretty straightforward. The main() function sits in a loop waiting for a keypress. As long as there is no keypress ready, it animates the stars. When a key is received, it takes the appropriate action: + increments the speed multiplier in g.Speed; – decrements it; and the Escape key exits the program.
The MoveStars() function loops through each star. First the star is drawn in black (to erase it). The position is then updated by the slope times the speed. Lastly, the star is redrawn at the new location.
The NewStar() function assigns a star to a position close to the center of the screen. To improve the visual effect, a little randomness is thrown in so that all stars will not begin at the same point. The slope is then selected at random, with care taken so that a slope of 0/0 never occurs. Should that happen, the program would eventually wind up with all its stars in the center of the screen and not moving.
The star’s size is selected at random. Ninety percent of the time, it is 1×1 pixel, and 10 percent of the time, it is 2×2 pixels. Finally, the color is selected with 90 percent of the stars as white and the remaining 10 percent as red, gray, blue, or yellow.
That’s all there is to it. All integer arithmetic. No rocket science (if you’ll pardon the pun). You might turn this program into a screen saver or even make it into a backdrop for a space shoot-’em-up game.
THE N-QUEENS AND OTHER PROBLEMS SOLVED
On to old business. I am pleased to announce that we have a winner for the N-queens problem. As you may recall, the N-queens problem is to find a way to place N queens on an NxN chessboard in such a way that no two queens attack each other. The traditional approach involves time-consuming generation and testing of many possible arrangements to find a solution.
Last June, I presented an N-queens solving program and received quite a bit of mail from the readers. Many of you noticed that the solutions frequently contained predictable patterns and tried to design some general pattern-based solution to the problem.
Jeffrey Phelps of Falls Church, Va., has written a program that solves the problem through patterns. His program is available in the library of the ZiffNet Computer Shopper Forum. A detailed description of his method is too large for this column, but it is very nicely documented in his program. Congratulations, Jeff!
Michael Davis of Sumter, S.C., has a question about the November Column, DiskPack. He writes, “I don’t understand what’s wrong with the ‘greedy’ algorithm. Optimum may show me the fewest files to fill up a given disk, but that’s not what I want to do. I want to use the fewest number of disks with the number and sizes of files that I have. Could you go into a little more detail about why the ‘optimum’ algorithm is better?”
For the benefit of readers who are just joining us, I will describe how a “greedy” algorithm works. A greedy algorithm is very simple-minded. It makes no attempt at being clever and just takes the next largest item that will fit. In the case of organizing files to fit on disks, a greedy algorithm would just take the next largest file that will fit on the current disk. If no file will fit in the remaining space on the current disk, it would go on to another disk and put the largest file on it.
In the case of making change, a greedy algorithm would just take the next largest coin denomination and use it. For example, to make change for 23 cents, a greedy algorithm would take two dimes and three pennies.
Five coins is the optimum solution, and the greedy algorithm works. However, our coin denominations were designed (long before there ever were computers!) especially to accommodate the greedy algorithm. It works because each denomination is worth at least twice as much as the next lowest denomination. If that weren’t the case, the greedy algorithm would often fail. Try this example: Imagine a 14-cent coin. Provide 29 cents in change. Greedy Optimum
1 quarter 2 14-cent coins 4 pennies 1 penny 5 coins 3 coins
The same goes with organizing files to fit on disks. Imagine that you want to organize these five files to fit on the fewest number of diskettes. The diskette size is 100K and file sizes are in kilobytes.
READ.ME 40 COMPRESS.COM 40 INSTALL.EXE 30 OPTIMIZE.BAT 30 SORT.COM 30 MERGE.EXE 30
The greedy algorithm would select READ.ME and COMPRESS.COM to go on disk one. This totals 80K; with no space left for further files, it could put INSTALL.EXE, OPTIMIZE.BAT, and SORT.COM would have to go on a third disk by itself.
An optimizing algorithm would put READ.ME, INSTALL, EXE, and OPTIMIZE.BAT on disk one. This totals 100K and there is no waste. COMPRESS.COM, SORT.COM, and MERGE.EXE would go on disk two (also totaling 100K). A third disk would be unnecessary. The optimizing algorithm “looks ahead” and uses fewer disks.
These examples are pretty simple and easily solved by hand, but real-life problems tend to be much more difficult and often require a great deal of calculation (time) to solve. Imagine having to optimize for hundreds of files of widely varying sizes. While practically impossible for a human, this is an ideal job for a computer.
SOLUTION TO THE CHECKERBOARD PROBLEM
A checkerboard alternates squares of light and dark color. Therefore, each domino must cover both a light square and a dark square. Squares in diagonally opposite corners are of the same color, so if you remove them, you will have 30 squares of one color and 32 squares of the other color. It is impossible to cover the board. Seems easy now, doesn’t it? Try this one on your friends.