Lady Aleena:

That reminds me of a problem we had to solve in a programming contest we had in High School. We were submitting the jobs in a time-share system, and the code had to (1) print the correct answer, and (2) execute within the CPU time limit. The problem was trivial: Find the cube root of some large number (say 13000) that happened to have an integer for a cube root. My code went roughly^[1] like this:

FOR I = 1 to 13000
   FOR J = 1 TO 13000
      FOR K = 1 TO 13000
         IF 13000 = I*J*K THEN PRINT "CUBE ROOT IS ", I
      NEXT K
   NEXT J
NEXT I
[download]

(Obviously, this is when I was young and stupid.) They would only give us the error messages from the run, nothing else. This code kept blowing the CPU time limit. (We didn't know that until after the contest, because it didn't generate any output. They just told us "Your program didn't print anything".)

After the contest, I thought to myself: "Oh, obviously I, J and K can't be any larger than the cube root of the number: We were blowing the time limit because we had 13000^3 or 2.197x10^12 loops^[2]. We should've looked up log(13000) from our CRC book^[4], divided by three and reverse-lookup to get 27.5. Then we would've had less than 22000 loops if we changed the code to^[3]:

FOR I = 1 to 28
   FOR J = 1 TO 28
      FOR K = 1 TO 28
         IF 13000 = I*J*K THEN PRINT "CUBE ROOT IS ", I
      NEXT K
   NEXT J
NEXT I
[download]

...roboticus

NOTES:

[1] As accurate as I can recall over several decades...

[2] On the GE-635 processor we were using, a multiply was between 5 and 10 uS, so looking only at the multiplications, it would've taken 127+ days to complete... assuming the jumps, additions, and comparisons were free. Also assuming no-one else was using the computer.

[3] It wasn't for several months before I realized the code should've been:

FOR I = 1 to 28
   IF 13000 = I*I*I THEN PRINT "CUBE ROOT IS ", I
NEXT I
[download]

Oh, well, I was a wee cog back then.

[4] I had just received a "four-banger" calculator (a calculator with addition, subtraction, multiplication and division) for Christmas -- rather expensive back then. I don't recall if scientific calculators were available at the time or not. I barely missed having to use a "slipstick" (slide rule).