In this Campus Cast, Jordan and Tina talk to Sun Campus Ambassador, Yevgeniya Kovalchuk. Yevgeniya is a PhD Student in the School of Computer Science and Electrical Engineering at the University of Essex. Listen in and learn how Yevgeniya's passion for genetic programming, computer science, and dance lead her towards interesting projects and an active OSUM Club.

In a new segment called "What do you do?", Jordan interviews a Sun employee and learns what they do for the company. In the first installment, he interviews Kevin Roebuck, Business Development Manager for Sun eLearning. Kevin's main focus is helping students connect, collaborate, and learn online.

» Download Audio and Play

Campus Cast 7 Riddle

The technical lead for my project comes up to me and says, "Jordan, could you please write me a method that prints out all of the perfect squares between 1 and 1000?" A perfect square, of course, is a number which is the product of the same number. For example, 4 is a perfect square because it is 2 times 2. 9 is the next perfect square because it is 3 times 3. I say, "Piece of cake, I'll just write a loop between 1 and 1000 and during each iteration multiplies the number by itself to get the perfect square." So I hand the code my my technical lead, and he looks at my with a scowl. "Humph" he says, "I think multiplying the two numbers will take too long. I bet you can do this with at most a few additions during each iteration of the loop."

What solution does my project lead have in mind?

Answer:

We can easily write a program that computes and prints the perfect squares that looks something like this:

    for (int x = 1; x <= 1000; x++) {
        int square = x * x;
        System.out.println("The next perfect square is " + square);
    }

However, that does a multiplication each iteration of the loop. We realize that if we know the perfect square for 'x', then the perfect square for (x + 1) is (x + 1) * (x + 1). When we expand this, we get x^2 + 2x + 1. So if we already know x^2 from the previous iteration of the loop, we can compute the perfect squares much quicker as follows:

    int square = 1;
    System.out.println("The next perfect square is 1");
    for (int x = 1; x < 1000; x++) {
        square = square + x + x + 1;
        System.out.println("The next perfect square is " + square);
    }