# Most optimized algorithm for incrementing squares [closed]

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


The entries will be judged on the most efficient algorithm.

• Oh, come on. Code challenge to write a loop or comprehend a list. Whoop dee doo! – dmckee --- ex-moderator kitten May 5 '11 at 16:53
• This was the dumbest question I've ever asked. – Mateen Ulhaq Jun 7 '17 at 7:00

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();
}
}

• +1 Technically, the fastest...the multiply will be optimized by the compiler to a single shift operation. so zero Multiplication (unlike the other answers) – st0le May 5 '11 at 7:09
• Actually that's a good point - I was aiming to avoid multiplication, so I may as well be explicit about the shift. – Peter Taylor May 5 '11 at 7:20
• 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 ;-) – Joey May 5 '11 at 7:56
• @Joey, it gets complicated with Java. javac would emit an imul and leave it to the JIT to turn it into a shift. – Peter Taylor May 5 '11 at 8:01
• @Peter, why don't you throw in a sq += (min << 1) | 1 – st0le May 5 '11 at 8:24

Python

print ", ".join(x*x for x in range(int(raw_input()), int(raw_input())+1))


## 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;
}


## Ruby

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


# 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!

• Jelly can do this in 2 bytes: r². Now I know this isn't code golf, but I do wonder how/why your program is more efficient than that. – steenbergh Jun 6 '17 at 15:02
(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.

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