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).

In reply to (Slightly) OT: Re: Nested Loops: A cautionary tale about exponential growth (long, rambly anecdote) by roboticus
in thread Nested Loops: A cautionary tale about exponential growth by Lady_Aleena

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.