Test Your EQ (Engineering Quotient)

EQ #23

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.

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.

Supporting Companies

Slider

Upcoming Events

Copyright © 2021 KCK Media Corp.

EQ #23

by Circuit Cellar Staff time to read: 1 min