Subscribe to RSS

Some rights reserved

Except where otherwise noted, content on this site is licensed under a Creative Commons License


blog‎ > ‎

Squares

posted Nov 24, 2009 6:31 AM by Davide Angelocola   [ updated Dec 26, 2009 4:40 PM ]

Today I need a way to quickly generate the n-th square, iteratively. I'm wondering about several naive approaches, all involving at least one multiplication. Maybe we can try an alternative approach based on these results:

1 = 1 (the square of 1)

1 + 3 = 4 (the square of 2)

1 +  3 + 5 = 4 + 5 = 9 (the square of 3)

1 + 3 + 5 + 7 = 9 + 7 = 16 (the square of 4)

It is clear now that the sum of the first n odd itegers is n2. The proof is left to thes an exercise for the reader. I used this simple observation to write an iterator that uses no multiplications, only additions:

public class SquaresIterator implements Iterator<Integer>, Iterable<Integer> {

    private int square = 0;
    private int nextOdd = 1;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public Integer next() {
        square += nextOdd;
        nextOdd += 2;
        return square;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public Iterator<Integer> iterator() {
        return this;
    }
}

the testcase:

for (int square : new SquaresIterator()) {
    System.out.println(square);

print:

1
4
9
16
25
36
49
64
81
100
121