3. The Accumulator Pattern¶

3.1. Squaring a Number with the Accumulator Pattern¶

In a previous example, we wrote a function that computes the square of a number. The algorithm we used in the function was simple: multiply the number by itself. In this section we will re-implement the square function and use a different algorithm, one that relies on addition instead of multiplication.

If you want to multiply two numbers together, the most basic approach is to think of it as repeating the process of adding one number to itself. The number of repetitions is where the second number comes into play. For example, if we wanted to multiply three and five, we could think about it as adding three to itself five times. Three plus three is six, plus three is nine, plus three is 12, and finally plus three is 15. Generalizing this, if we want to implement the idea of squaring a number, call it n, we would add n to itself n times.

Do this by hand first and try to isolate exactly what steps you take. You’ll find you need to keep some “running total” of the sum so far, either on a piece of paper, or in your head. Remembering things from one step to the next is precisely why we have variables in a program. This means that we will need some variable to remember the “running total”. It should be initialized with a value of zero. Then, we need to update the “running total” the correct number of times. For each repetition, we’ll want to update the running total by adding the number to it.

In words we could say it this way. To square the value of n, we will repeat the process of updating a running total n times. To update the running total, we take the old value of the “running total” and add n. That sum becomes the new value of the “running total”.

Here is the program in Python. Note that the heading of the function definition is the same as it was before. All that has changed is the details of how the squaring is done. This is a great example of “black box” design. We can change out the details inside of the box and still use the function exactly as we did before.

In the program above, notice that the variable running_total starts out with a value of 0. Next, the iteration is performed original_number times. Inside the for loop, the update occurs. running_total is reassigned a new value which is the old value plus the value of original_number.

This pattern of iterating the updating of a variable is commonly referred to as the accumulator pattern. We refer to the variable as the accumulator. This pattern will come up over and over again. Remember that the key to making it work successfully is to be sure to initialize the variable before you start the iteration. Once inside the iteration, it is required that you update the accumulator.

Here is the same program in codelens. Step through the function and watch the “running total” accumulate the result.

3.2. The General Accumulator Pattern¶

initialize the accumulator variable
repeat:
    modify the accumulator variable

# when the loop terminates the accumulator has the correct value

        n = int(input('How many odd numbers would
you like to add together?'))
the_sum = 0
odd_number = 1
---
for counter in range(n):
---
   the_sum = the_sum + odd_number
   odd_number = odd_number + 2
---
print(the_sum)
        

3.3. Applying the Accumulator Pattern¶

Use the accumulator pattern to write a fruitful function sum_to(n) that returns the sum of all integer numbers up to and including n. So sum_to(10) would be 1+2+3...+10 which would return the value 55.

Now that you have written a solution for the sum_to(n) function, let’s test it a bit. You might want to do the following in Thonny, rather than your browser, as it will cause your browser to become unresponsive while the program is working.

Although our accumulator pattern worked just fine when we passed in a number like 10, let’s see what happens if we crank that number up a bit. Try 100. How about 1000? Let’s keep going, and try 10000. Continue to add on one more zero, then running the code again. Depending on the speed of your computer, there will come a point where you begin to notice a distinct pause before your program prints an answer. Why is this? By looking at your code, you should realize that the loop must repeat by the number you pass into the function, so when we pass in 100, the loop repeats 100 times. Is there any way we can write a better sum_to(n) function?

There’s a famous story (no one really knows if it’s true) about the mathematician Carl Friedrich Gauss, from when the mathematician was only in grade school (in the late 18th century). Gauss’ teacher wanted a break from dealing with his students, so he assigned them a simple, but tedious problem; find the sum of the integers from 1 to 100. The teacher expected to have a few minutes of peace and quiet, but Gauss thought briefly, and astonished his teacher by correctly answering the question without doing the tedious task of summing all the values together.

How did he do it? He noticed a pattern, as follows:

the_sum = 1 + 2 + 3 + 4 + ... + 98 + 99 + 100

Writing the terms in the opposite order will still provide the same result:

the_sum = 100 + 99 + 98 + ... + 4 + 3 + 2 + 1

If we combine the two ideas together, you get the following:

the_sum = 1   + 2  + 3  + 4  + ... + 98 + 99 + 100
the_sum = 100 + 99 + 98 + 97 + ... + 3  + 2  + 1

If you add each of the values vertically, you notice that what you get is the sum of 101 added 100 times:

the_sum * 2 = 101 + 101 + 101 + ... + 101

This can be written as:

the_sum * 2 = 100 * 101

Dividing by 2:

the_sum = (100 * 101) / 2

Writing this more generically to work for any number, the formula becomes:

Now that you understand Gauss’ pattern for finding the sum of a series, rewrite the sum_to(n) function you created above, this time using the formula!

To be sure you understand why we bothered to learn another way to create the sum_to(n) function, test out the function with ridiculously large numbers. Notice that with this version of the function, the solution can be calculated dramatically faster. This is another example of why black-box function design is helpful: if an optimized version of the function is found, it can be implemented without affecting any of the code that calls that function.

3.4. Practice Problems¶