Incremental Java
Example of while: Summing from 1 to num

Summing from 1 to num

In this example, we're going to implement: 
public void sum( int num ) ;
which sums from 1 up to num. We're going to implement this with, surprise, a while loop.

Let's think about what we've done so far. We can print from 1 to num. We can print from from 0 to num - 1. If you can print a range, you can use the numbers in that range.

But what should we do? We want to sum 1 to 2 to 3 and so forth. Suppose someone asked you to sum 100 different numbers. This person says a number, then the next and so forth. How would you sum it up?

You'd probably remember the first number. Then, when you heard the second, you'd add it. Then, when you heard the third number, you'd add that. After 100 numbers, you'd have the total sum. In the process, you don't have to remember all 100 numbers. You keep adding to a running sum.

We're going to take the same approach here. First, we'll have a sum. What's a good value to initialize it to? We should initialize sum to 0. 

// Getting started
public int sum( int num )
{
   int total = 0 ;
}
Then, we should set up a loop that goes from 1 to num. We've done this in the first example: 
// Adding the loop
public int sum( int num )
{
   int sum = 0 ;
 
   int count = 1 ;
   while ( count <= num )
   {
      count++ ;
   }
}
The only difference in this loop is removing the println().

All we have to do is to add count to the sum. Should this be done before count++ 

// VERSION 1
public int sum( int num )
{
   int sum = 0 ;
 
   int count = 1 ;
   while ( count <= num )
   {
      sum += count ; // Does it go here?
      count++ ;
   }
}
or after the increment 
// VERSION 2
public int sum( int num )
{
   int sum = 0 ;
 
   int count = 1 ;
   while ( count <= num )
   {
      count++ ;
      sum += count ; // Or maybe here?
   }
}
The best way to check this is to trace an example. Let's try it out on a small example. Assume num is 2.

Woops! There's already an error. We've incremented to 2, and haven't even added 1. So this one is wrong.

If you trace the VERSION 1, you'll see it's correct.

A Solution Without Loops 

// Quick solution without loops
public int sum( int num )
{
    return ( num * ( num + 1 ) ) / 2 ;
}
This solution is attribute to Gauss. A teacher is said to have asked the class to sum numbers from 1 to 100. Gauss answered in only a few seconds, and the teacher assumed he was lying.

Gauss noticed that adding the first and last number (1 and 100) was 101. Adding the second and next to last (2 and 99) was also 101. Adding the third and third to last was 101 (3 and 98).

This pattern holds up. You just pair the nth and nth from last number and it sums to num + 1. There are num / 2 such pairs.

So (num + 1) * (num / 2) is the total (it doesn't look like the code above, but they are equivalent).

Amazingly, this formula works even if num is odd (and the number of pairs has a leftover). The reason is works is that you basically add the middle number to itself, so it gets added twice (but then divided out, as well).