What does the following C function compute? You may assume the input argument is a positive integer.
int function (int x)
{
int y = 1;
int z = 0;
int i = 0;
while (x > 0) {
z += 6;
y += z;
x -= y;
++i;
}
return i;
}
Remember the algorithm that computes integer square roots by
subtracting successive odd numbers from the input value? This function extends
that concept to computing integer cube roots.
— ADVERTISMENT—
—Advertise Here—
The reason this works is that taking the differences between
successive values is the discrete equivalent of taking a derivative in the
continuous world. The derivative of a cubic curve is a quadratic, and the
derivative of a quadratic is a straight line. To generate a “straight line” in
the discrete world, you just add a constant to a variable.
When you look at successive squares—0, 1, 4, 9, 16, 25, etc.—the
differences are 1, 3, 5, 7, 9, etc. This is why the algorithm that subtracts
odd numbers works for computing square roots.
When you look at the successive cubes—0, 1, 8, 27, 64, 125, etc.—the first set of differences is the sequence 1, 7, 19, 37, 61, etc. This doesn’t look very useful until you take the differences between those numbers, which are: 6, 12, 18, 24, etc., which is obviously another straight line.
| Keep up-to-date with our FREE Weekly Newsletter! | Don't miss out on upcoming issues of Circuit Cellar. Note: We’ve made the May 2020 issue of Circuit Cellar available as a free sample issue. In it, you’ll find a rich variety of the kinds of articles and information that exemplify a typical issue of the current magazine. |
| Would you like to write for Circuit Cellar? We are always accepting articles/posts from the technical community. Get in touch with us and let's discuss your ideas. |
