Lesson 03-07: Accumulator Algorithms¶

An Example of an Accumulator Algorithm¶

Accumulator comes from the word accumulate, which means “gradually gather or acquire”. In programming, we use accumulator algorithms for the same purpose. For example, if we wanted to use loops to add up all positive integers up to 10, how would we do that?

Here is that same code, except with added print statements to detail the process:

Breaking Down the Accumulator Algorithm¶

The accumulator algorithm can be broken down into three parts:

1. Variable Initialization - You will have to have a variable that keeps track of your running total. This variable has to be initialized outside the loop. If you initialize it inside the loop, you will be repeatedly setting it to 0.
2. The Iterator - You need to figure out what iterator (in these cases, a range) will work best for your loop. Need to look at all the even numbers between 2 and 100? Better use a range(2,101,2). Later on, we’ll learn how to iterate over strings and lists as well.
3. The Update Statement - Since this is an accumulator algorithm, you should probably be accumulating something! This statement is for updating your running total with the new total. This doesn’t have to happen every time the loop runs, for example, if it’s inside of an if statement.

Let’s do an example: Let’s get the product (multiplication) all the numbers that end in “4” from 1 to 100.

We start with our variable initialization - I’m gonna call mine total and set it to 1. I don’t want to set it to zero because I know I’m going to be multiplying, and if I multiply anything by zero, it will always be zero!

1

total = 1

Next, I have to think about what I want to look at - in this case, what numbers do I need to look at? I could look at every number between 1 and 100, and that would be a waste - but I’m going to do it anyway to illustrate a point. Our range will therefore be range(1,101), since we want to include 100.

1
2

total = 1
for n in range(1,101):

Next is the update statement. I know my update statement is multiplication, and that statement would look like total = total * num. However, I only want to do that when the number ends in 4. How do we know if a number ends in 4? Well, it’s a bit tricky, but we can do this:

n % 10 == 4

This will take the remainder of dividing the number by 10, which drops everything except for the last digit 10, 100, 100, etc are all divisible by 10, so they all go away). This boolean expression will tell us if a number ends in 4 or not.

1
2
3
4

total = 1
for n in range(1,101):
    if n % 10 == 4:
        total = total * num

Finally, I want to make sure I’m correct, so I print out the number and run it!.

Although I don’t know what the actual answer is, so I will just punch the following into wolframalpha:

4 * 14 * 24 * 34 * 44 * 54 * 64 * 74 * 84 * 94

And I get 4060162871525376 as my answer. It matches!

What I did was the inefficient way as well - a clever programmer may have figured out that I could simply make a better range and come to the same conclusion:

(This code will loop 10 times, whereas the other loops 100 times)

Checks For Understanding¶