3
\$\begingroup\$

Write the "fastest" program to print an incrementing series of squares from a given input to a given input.

Example input:

-2
7

Example output:

4, 1, 0, 1, 4, 9, 16, 25, 36, 49

When using a "cryptic" language, please post the pseudocode, in addition to your program.

The entries will be judged on the most efficient algorithm.

\$\endgroup\$
2
  • 6
    \$\begingroup\$ Oh, come on. Code challenge to write a loop or comprehend a list. Whoop dee doo! \$\endgroup\$ May 5, 2011 at 16:53
  • \$\begingroup\$ This was the dumbest question I've ever asked. \$\endgroup\$ Jun 7, 2017 at 7:00

6 Answers 6

9
\$\begingroup\$

The tag says "code-challenge", but I don't see any challenge. Just some mathematics we studied when I was about 12.

import java.util.*;

public class IncSquares
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int min = in.nextInt();
        int max = in.nextInt();

        int sq = min * min;
        System.out.print(sq);
        while (min < max) {
            sq += (min << 1) + 1;
            min++;
            System.out.print(", " + sq);
        }
        System.out.println();
    }
}
\$\endgroup\$
8
  • 1
    \$\begingroup\$ +1 Technically, the fastest...the multiply will be optimized by the compiler to a single shift operation. so zero Multiplication (unlike the other answers) \$\endgroup\$
    – st0le
    May 5, 2011 at 7:09
  • \$\begingroup\$ Actually that's a good point - I was aiming to avoid multiplication, so I may as well be explicit about the shift. \$\endgroup\$ May 5, 2011 at 7:20
  • \$\begingroup\$ If in doubt, the compiler probably knows best whether to represent a multiplication by 2 by a shift, a multiply or an add. The usual rule is to state your intent and let those optimize who do that for a living ;-) \$\endgroup\$
    – Joey
    May 5, 2011 at 7:56
  • \$\begingroup\$ @Joey, it gets complicated with Java. javac would emit an imul and leave it to the JIT to turn it into a shift. \$\endgroup\$ May 5, 2011 at 8:01
  • 2
    \$\begingroup\$ @Peter, why don't you throw in a sq += (min << 1) | 1 \$\endgroup\$
    – st0le
    May 5, 2011 at 8:24
1
\$\begingroup\$

Python

print ", ".join(`x*x` for x in range(int(raw_input()), int(raw_input())+1))
\$\endgroup\$
1
\$\begingroup\$

C

Since my usual language interpreter has a one-second startup time already, I chose not to use it here.

#include <stdio.h>

int main(void) {
    int start, end, i;
    scanf("%d\n%d", &start, &end);
    for (i = start; i <= end; i++) {
        printf("%d", i*i);
        if (i != end)
            printf(", ");
    }
    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

Ruby

a,b=*$<.map(&:to_i)
p (a+1..b).reduce([a**2]){|m,x|m<<m[-1]+x+x-1;m}*?,
\$\endgroup\$
0
\$\begingroup\$

Jelly 12 bytes

+³’µ²
_N‘RÇ€

Explanation

+³’µ²
 ³’    -Decrement the first argument
+      -Sum it
   µ   -Groups the functions prior to this
    ²  -Square the result

_N‘RÇ€
_      -Subtract the two arguments
 N     -Negate the difference
  ‘    -Increment the difference
   R   -Generate Range from Difference
    ǀ -Map range with above function

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Jelly can do this in 2 bytes: . Now I know this isn't code golf, but I do wonder how/why your program is more efficient than that. \$\endgroup\$
    – steenbergh
    Jun 6, 2017 at 15:02
-1
\$\begingroup\$
(z + 1)^2 = z^2 + (2z + 1)

We already know z^2, and 2z is simply z<<1.

(z + 1)^2 = (z^2) + (z << 2 + 1)

Now just memorize this trick if you want to list squares in your head.

If you've got an arbitrary [two-digit] square (to do in your head), z^2, do this:

z^2 = (z-n)*(z+n) + n^2

Or:

23^2 = (23-3)*(23+3) + 3^2
23^2 = 20*26 + 9
23^2 = 520 + 9
23^2 = 529

Works even "faster" with larger numbers, relative to you doing 97*97 in your head. Have fun showing off.

\$\endgroup\$
3
  • \$\begingroup\$ So basically it's the same as mine but with added bugs? \$\endgroup\$ May 5, 2011 at 20:08
  • \$\begingroup\$ @Peter Oh yes. :) \$\endgroup\$ May 5, 2011 at 22:46
  • \$\begingroup\$ 2z != z << 2. 2z = z << 1, always. \$\endgroup\$
    – Ry-
    May 9, 2011 at 0:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.