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.
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.
— ADVERTISMENT—
—Advertise Here—
Keep up-to-date with our FREE Weekly Newsletter!
Don't miss out on upcoming issues of Circuit Cellar.
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.
