3. The Accumulator Pattern¶
Quick Overview of Day
Introduce the accumulator pattern with numbers.
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
Teacher note: A nice introduction to this lesson is to either demonstrate the process of multiplication by repeated addition on the whiteboard, or having the students work through a question on their own.
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
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.
What would happen if we put the assignment
running_total = 0 inside the for statement? Not sure? Try it and find out.
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
3.2.1. Check Your Understanding¶
Rearrange the code statements so that the program will add up the first n odd numbers where n is provided by the user.
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
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¶
3.4.1. Estimating Square Roots¶
Write a function called
my_sqrt that will approximate the square root of a number, call it n, by using Newton’s algorithm. Newton’s approach is an iterative guessing algorithm where the initial guess is n/2 and each subsequent guess is computed using the formula:
new_guess = (1/2) * (old_guess + (n/old_guess)).
To be sure you understand how this works, it is a good idea to try out Newton’s algorithm by hand at least once! Try estimating the square root of 9 by hand. You will see that it only takes a couple iterations to get really close to the actual value of the square root.
Be sure to test your square root function with a variety of numbers, and check with a calculator to see how well your function is performing!
3.4.2. Approximating Pi¶
Write a function called
my_pi() that will return an approximation of PI (3.14159…). Use the Leibniz approximation, which shows that you can approximate 1/4 of PI with the following series:
3.4.3. Finding A Natural Logarithm¶
Write a function called
ln2() that will return an approximation of ln(2). You can calculate an approximation of the natural logarithm of 2 with the following series: