Lab 4
Identifying and Exploiting Repeating Patterns
Introduction
============
In lab 3, we explored how to make decisions. Decision making allows
us to write much more interesting programs because we have programs
with multiple paths of execution. This week we will be looking at
loops and patterns. Looping is the control structure which allows
us to write programs which are far more useful. Unfortunately, loop
behavior can be a bit difficult to comprehend. In this lab, we will
explore using loops to create repeating patterns. In both the
guided and self labs, we will explore problems which have
non-obvious solutions, and they will seem a little complicated. The
key to solving these problems will be in spotting the underlying
pattern in them.
Part I (Guided) - Fun With Etruscan Sheep
=========================================
In the land of Tuscany, before the birth of Romulus and Remus, there
lived two shepherds named Reg and Stan. One morning, Reg noticed
that something was amiss. "Stan, does it seem like we have fewer
sheep today than we did yesterday?", he asked. Stan replied, "I
don't know. Tell you what. Let's take this bone and cut a notch
into it for each sheep, then we can recount it in the morning and
see if there may be a wolf in our midst." That day, they set out
doing just that. They took a lamb bone and carved notches:
||||
The next day, they repeated the same task:
|||
"Aha!", exclaimed Reg, "We are down by one. Let's stay up tonight
and see what's happening to the sheep." That night they found a
wolf prowling their fields. They killed the wolf by pelting it with
rocks, thus preserving the number of their flock. Now, Reg and
Stan became the most successful shepherds in all of Tuscany, and
they had also made one of the first steps for building a mechanical
computer. Their success, however, turned to dismay after a
particularly successful lambing season. Reg returned with the
following notches:
|||||||||||||||||||||
Stan took one look and said "I just can't handle that many notches!
It's hard to read at a glance. We'll spend all our time counting
notches!" Reg thought it over and then said, "What if we change
every 5th mark?" He then carved a new bone:
||||/\||||/\||||/\||||/\|
Stan took one look and said, "Ah! So every fifth mark is /\. Now
we can count by fives. What if we extend it further, and made
every tenth mark be overlapping 5's like this." Stan took the bone
and carved:
||||/\||||X||||/\||||X|
Reg took one look and liked what he saw. "Now we can see at a
glance, that we have 2 10's and 1 left over notch. That's bloody
brilliant!" (All 7th century BC Etruscans used British slang. Just
roll with it!). They then decided to expand this just a little
further. They made a symbol for every 5th X and for every 2nd 50.
Thus the Etruscan counting bone system was:
Number Symbol
------ ------
1 |
5 /\
10 X
/|\
50 |
100 >|<
They didn't go above 100, because that was more sheep than they had
ever seen in their lives. It's easy to see that this is a method
that can be used for counting large numbers efficiently. Thus the
Etruscan counting bone became one of the world's first manual
computers!
In time, Reg and Stan decided they wanted to chart their business
over long periods of time. Now that they had over 50 sheep, they
were going through a lot of bones. One day as Stan was recording a
year's worth of sheep he started to get tired. He had carved:
/|\
||||/\||||X||||/\||||X||||/\||||X||||/\||||/\||||X||||/\|||||
As Stan was massaging his swollen wrist it hit him. "Oy! These
notches are brilliant for adding, but they are rubbish for recording
data." After a little thinking he said, "I have it! We can just
take everything prior to the largest symbol as read, so I could just
carve:
/|\
|
"and we'll know that those exhausting marks came before it. I could
also just do groups of those, for instance, I could do XX for 20
sheep." Reg liked the idea, but there was just one small problem.
"What about when you have one less than the big one?" "Oh yeah..."
Almost at the same instant, a bolt of genius hit them. "What if we
put the notch just before the big group. Like |X would mean 9 and
we'd just understand that the 3 others are there. You know, they'd
have to build up to it anyway." So they practiced and found that
this worked well. |X for 9, |/\ for 4... and all was well.
Then came the rise of Populous Romanus. They liked Reg and Stan's
counting method. They especially liked how it work for both
counting and recording, but they thought the symbols looked like
something that a shepherd would come up with. So, they decided to
use letters. | became I, /\ became V, and so on. This made it easy
for Roman stone carvers to carve numbers into Roman walls. They
also extended the system a bit, so the total table of symbols
became:
Decimal Symbol
------- ------
1 I
5 V
10 X
50 L
100 C
500 D
1000 M
They also decided to call these things "Roman Numerals." Our
Etruscan friends were none too pleased by this. "Bloody Romans!"
they muttered, "What have they ever done for us?"
Problem
-------
We want to create a program which will convert any decimal number
to Roman Numerals. At first glance, this seems like a monumental
task. Up to 10 is easy, but I want to be able to do the following:
1024 - MXXIV
3900 - MMMCM
249 - CCXLIX
A sample run of the program which you are going to write is:
-- Begin Sample Run --
Enter Number: 597
DXCVII
-- End Sample Run --
Developing a Solution
---------------------
In order to solve this problem, we need to identify a repeating
pattern. Using the standard set of Roman numerals would allow us to
count to 3,999 before the pattern will break. A later addition used
the drawing of bars over the letters to multiply them by 1000. So
_
M
Would become 1,000,000. This is a bit too much for us to handle at
the present state of our knowledge of C++, however, so we are going
to make 3,999 our maximum number. You could solve every single
Roman numeral and then have a 4,000 element switch statement, but
that would be very tiring. Instead, we want to work smarter, not
harder! Take a look at the story above, especially the tables and
the notches. Can you see a pattern to what they are doing? Ponder
it a bit before you read the next paragraph.
They are using an ordinal counting system, where the total value of
the numbers accumulate from left to right. The largest amount of
the values is always at the left. For instance, X would be
preceded by 9 marks prior to the X. That's how they came up with
the short form |X (or IX for the Romans). So if we want to convert
numbers to Roman numerals, we are going to start by subtracting out
the larger parts and record their symbols. For instance, let's say
we look at 2013. We can see that the highest part of the number is
in the thousands. So we record as many thousands as we can:
MM
This leaves us with 13. 13 is less than 500, 100, and 50. Now we
record as many 10's as we can:
MMX
this leaves us with 3. There can be no 5's, but there can be ones.
We record the remaining 1's.
MMXIII
So pseudocode at the first attempt at this would work as follows:
For each letter in {M, D, C, L, X, V, I}
if num >= value of letter
print num / value of that letter
num = num % value (the remainder)
end if
end for
There is, of course one problem with this. Can you see what it is?
Try a hand trace of the above for the number 40. You'll end up with
"XXXX" which is invalid. So we have to think about this some more.
We know that the base symbols are {M, D, C, L, X, V, and I}. Just
like Reg and Stan, we are faced with the problem of boundaries
between these symbols. So we could augment the above algorithm with
these boundaries:
For each letter in {M, D, CD, C, XC, L, XL, X, IX, V, IV, I}
if num >= value of letter
print num / value of that letter
num = num % value (the remainder)
end if
end for
This algorithm will work. But how can we implement it? After all,
how will the computer know the value of the numbers? In order to
implement this, we are going to use an iterative design and
implementation process. This is a technique which allows us to go
back and forth between pseudocode and C++ code in an effort to
develop the program over time. The first detail we will look at is
the issue of the values of these separations. Observe the following
table of symbols (including the boundaries):
Decimal Symbol
------- ------
1000 M
900 CM
500 D
400 CD
100 C
90 XC
50 L
40 XL
10 X
9 IX
5 V
4 IV
1 I
Now, if we look closely at this, we can see an underlying pattern.
Notice how we keep repeating 9,5,4,1? We do this once at each
multiple of 10. That is, we have 900, 500, 400, 100; and we also
have 90, 50, 40, 10. So we could iterate over these values by
keeping track of where we are in the sequence. We will need a
counter for each of the positions. There are 4 states in the
sequence:
for counter=3 to 0
case 3
value = 9
case 2
value = 5
case 1
value = 4
case 0
value = 1
print value
end for
This will, of course, handle our sequence 9,5,4,1 but not the full
counting that we want. The full counting needs to loop through each
decade, starting at 1000 and decreasing to 1. We will stay in each
decade for a count of 4. We can combine all this into one large
loop by observing that we decrease the decade only once the counter
reaches 0. The pseudocode for all this is:
counter=0
decade=1000
while decade > 0
switch(counter)
case 3
value = 9 * decade
case 2
value = 5 * decade
case 1
value = 4 * decade
case 0
value = decade
decade = decade / 10
counter = 4
end switch
counter = counter - 1
display the value
end while
As you can see, we are getting close to C++ code, so let's go
ahead and write some C++. Create a file called "roman.cpp" and
enter the following code:
-- Begin roman.cpp --
/*
* File: roman.cpp
* Purpose: A little program to compute the roman numeral sequence.
*/
#include <iostream>
using namespace std;
int main(void)
{
int counter=0;
int decade=1000;
int val=1000;
// run through all decades
while(decade) {
//update the value
switch(counter) {
case 3:
val = 9 * decade;
break;
case 2:
val = 5 * decade;
break;
case 1:
val = 4 * decade;
break;
case 0:
val = decade;
decade /= 10; //new decade!
counter=4;
break;
}
//update the counter
counter --;
//output the value
cout << val << endl;
}
return 0;
}
-- End roman.cpp --
Run this code and verify that it prints:
1000
900
500
400
100
90
50
40
10
9
5
4
1
Now we can iterate over the correct values, we want to add to it
iteration over the correct symbols. Of course, this is pretty
simple in that we can just add in the following switch statement.
Instead of
//output the value
cout << val << endl;
What we really want is:
//output the correct symbol
switch(val) {
case 1000:
cout << "M" << endl;
break;
case 900:
cout << "CM" << endl;
break;
case 500:
cout << "D" << endl;
break;
case 400:
cout << "CD" << endl;
break;
case 100:
cout << "C" << endl;
break;
case 90:
cout << "XC" << endl;
break;
case 50:
cout << "L" << endl;
break;
case 40:
cout << "XL" << endl;
break;
case 10:
cout << "X" << endl;
break;
case 9:
cout << "IX" << endl;
break;
case 5:
cout << "V" << endl;
break;
case 4:
cout << "IV" << endl;
break;
case 1:
cout << "I" << endl;
break;
}
Make that change and run the program. Verify that it runs through
the correct symbols. Now we can implement the technique for
conversion we discussed above. First, we need to make new variables
for the number we want to convert, and also counters for the number
of each symbol. Let's create the variables first. Add the
following to the appropriate place in code:
int i, n, num;
Before we enter the loop, we want to get the number we are going to
convert. Add the following before the loop:
//get the number
cout << "Number: ";
cin >> num;
Now we want to surround the printing of symbols in the following
around the switch case which prints out the letters
n=num / val;
for(i=0; i<n; i++) {
/* the switch case from above goes here. */
}
num = num % val;
Now run the program. It almost works! Though it would be nice if
we printed all the symbols on one line, wouldn't it? Go through the
switch statement and remove all the endl parts. Add 1 end of line
just before we return 0 at the end. The end of the main function
should end with:
cout << endl;
return 0;
Run the program and you'll see that it works beautifully! Well done!
Try out some of the harder test cases for roman numerals. Look back
over the code and make sure you understand all the reasoning we used
to get there. Fully understanding what you are to do, identifying
patterns, and then implementing those patterns is a very powerful
technique in computer science. Mastering this type of thinking is
not easy, but once you do you'll be able to tackle any coding
challenge anyone throws at you!
As a final step, create a script file which contains a listing of
your code and a few sample runs. Submit this using the turnin script.
Part II (Self) Realizing a Misanthropic Dream
=============================================
Another long day at the Analytical Society in Cambridge has passed.
The foolish men I must surround myself with have been particularly
tiring of late, and far less than helpful in the design of complex
machines. I seldom think that many men are up to the task of
reasoning as I can. "Mr. Babbage" this, and "Mr. Babbage" that, Why
do they call after me all the time? And now, I must walk home amid
the mob. How I detest the mob.
It's not that we could do without them. Oh no, we need their labour,
and we need their taxes to fund our higher purposes. What we do not
need is their tendency to break my plate glass windows. Oh yes, I
know it is they that do it. I have outlined a table of the ways
they break and destroy, and yet I have to walk home among them. I
have to pass through their parks, with their infernal offspring
grabbing at my coat tails. I have to see their "musicians", if one
uses the term loosely, playing on the street corners. I know the
organ grinder will be there. I hate organ grinder music. It
distracts and infuriates me! The suffering and pecuniary effects of
these half rated vagabonds astounds the mind. At least I am almost
at my door. I turn back and realize that the one thing I cannot
stomach is the mob's noise. All the noise, noise, NOISE!
At least my chamber is quiet. I think I will turn to my
computations, and find solace in my math. Ah, computation, how
wonderfully exact, obedient, and ready to serve. Wait. What's
this? My table tells me the log of 1231 is 3.0901?! Outrageous,
even a fool knows that log(1231) is 3.0903 if rounded at 4 places.
They will not get away with this! These tables affect every aspect
of computations, and they have the gall to make an error. No, this
will not do. This cannot be trusted to the minds of men, for the
computers* will make error upon error and their error will grow to
catastrophe. I shall build a machine, for it is to the machine we
should entrust all that is important. I shall build a difference
engine!
* NOTE: Prior to 1947, the term "Computer" referred exclusively to a
professional person who's sole task was to carry out
mathematical computation. This is why ENIAC was called an
"Electronic Computer." By the 1960's, the term came to be
used almost exclusively for electrical and mechanical
devices. The computer profession is dead. No one you will
meet will claim to be a computer. (At least not the sane ones.)
Problem
-------
The above rant is my attempt to think like Charles Babbage, a truly
embittered man (though he had a few friends with whom he was
tender.) He set out to build a table of logarithms via machine, and
to this end he designed the difference engine. The difference
engine would have been the world's first general purpose mechanical
computer. However, his designed proved to be far more involved and
expensive than originally anticipated. Also, he had started the
design of the analytic engine which would have been more powerful.
His parliamentary backers decided to fund the analytic engine
instead. The analytic engine also proved too expensive and so it
was ultimately abandoned. He did succeed in building parts of both
engines, and it has been shown that his machines would have worked.
Modern engineers have built his designs, showing that Babbage really
did know his stuff!
As another side note, the analytic engine was programmable. A woman
by the name of Ada Lovelace, a long time friend of Babbage, wrote
programs for the analytic engine. This has lead to the wonderful
bit of trivia that the world's first computer programmer was a
woman, even though it is now a male dominated field.
The task which the difference engine was originally designed for was
the computation of logarithms. Logarithms were much more important
to day to day computation during Babbage's time as they were used to
multiply numbers efficiently. This follows from the definition of
the log:
x
b = y
log y = x
Suppose we multiply two exponentials of a common base. By the laws
of exponents:
x y x + y
b * b = b
So if you want to multiply two numbers, you find the log of both
numbers, then add them, and then take the antilog using your log
table. For instance
123 * 412
becomes
log(123) + log(412)
e
4.8121 + 6.0210
e
10.8331
e
50670
Which is close to the answer. A skilled log table user would be
able to extract the last digit, which is 6. 50676 is the exact
answer. Note that everything except the addition step is just a
table lookup in a book. Thus the more accurate and precise your log
tables, the more accurate and precise your multiplications. Also
note that here, when I write "log" I mean natural log. Up until the
advent of the pocket calculator, log always referred to natural log,
and in most engineering circles, it still does.
So now, here's your problem. You are going to realize Charles
Babbage's dream, and you are going to construct a program which
generates a nice and neat log table. The table will be in four
columns, and it will allow for the user to select the number of
lines per page, and the number of pages to print. For example, here
is a sample run of my program:
-- Begin Sample Run --
Welcome to the Babbage Log Engine
Lines Per Page: 5
Pages: 3
0.1 2.0
-----------------------------------------------------------------------
0.1 -2.3026 0.6 -0.5108 1.1 0.0953 1.6 0.4700
0.2 -1.6094 0.7 -0.3567 1.2 0.1823 1.7 0.5306
0.3 -1.2040 0.8 -0.2231 1.3 0.2624 1.8 0.5878
0.4 -0.9163 0.9 -0.1054 1.4 0.3365 1.9 0.6419
0.5 -0.6931 1.0 0.0000 1.5 0.4055 2.0 0.6931
-----------------------------------------------------------------------
2.1 4.0
-----------------------------------------------------------------------
2.1 0.7419 2.6 0.9555 3.1 1.1314 3.6 1.2809
2.2 0.7885 2.7 0.9933 3.2 1.1632 3.7 1.3083
2.3 0.8329 2.8 1.0296 3.3 1.1939 3.8 1.3350
2.4 0.8755 2.9 1.0647 3.4 1.2238 3.9 1.3610
2.5 0.9163 3.0 1.0986 3.5 1.2528 4.0 1.3863
-----------------------------------------------------------------------
4.1 6.0
-----------------------------------------------------------------------
4.1 1.4110 4.6 1.5261 5.1 1.6292 5.6 1.7228
4.2 1.4351 4.7 1.5476 5.2 1.6487 5.7 1.7405
4.3 1.4586 4.8 1.5686 5.3 1.6677 5.8 1.7579
4.4 1.4816 4.9 1.5892 5.4 1.6864 5.9 1.7750
4.5 1.5041 5.0 1.6094 5.5 1.7047 6.0 1.7918
-----------------------------------------------------------------------
-- End Sample Run --
Note how each "page" begins with a header showing the first and last
logarithms on the page. Also note that everything is neatly
aligned. There is a lot of iomanip action going on in this
program. I want you to reproduce this output exactly as it appears
here.
Clearly, hand computing test cases here will be highly impractical.
Instead, what we should do is just spot check a few of the
logarithms.
Hints & Observations
--------------------
1. You've probably realized that cout lets you do line output, but
you can't come back up to a line. This means that each line has
to be printed all at once. You'll be doing 4 logarithms per
loop iteration. The key here is knowing the starting point of
each column.
2. Look at the cmath documentation on cplusplus.com to see how to
compute logarithms.
3. Try to identify patterns in how to determine the first and last
log on a page as well as the start of each column.
4. Try using setw and setfill to do most of your formatting. You
shouldn't have to write a loop to do the "---" separator lines!
5. You may want to discuss the design with your peers. Bouncing
ideas off of each other can be a big help with problems like this.
Extra Credit (20 points)
------------------------
Charles Babbage did publish a logarithm table. It wasn't
mechanically computed, but it was more accurate than the ones he
started with. Head over to
http://archive.org/details/tableoflogarithm00char to see Babbage's
log table. If you can make your program output a table formatted like
Babbage's original table, I will give you 20 points. Yes, you can
score a 120 on the lab! Good luck!
