(Problem 1) In class, we defined a machine language and showed its instruction set. We were then
able to write programs for a few Simple tasks. In this problem, you are asked to make some
modifications to those programs.
a) Create a machine language program that will add the N numbers starting at the number K. These
would be the numbers K, K+1, K+2, ... K+N-1.
Answer:
10: Load R1 <--- K (K)
11: Load R2 <--- 0000 (running total)
12: Load R3 <--- N (N)
13: Load R4 <--- 0001 (always 1)
14: Add R2 <--- R2 + R1 (add K to the running total)
15: Add R1 <--- R1 + R4 (K = K + 1)
16: Subtract R3 <--- R3 - R4 (N = N - 1)
17: Jump to 14 if (R3 > 0) (if N isn't 0 yet, continue to add)
18: Halt (N is now 0, and R2 = K + (K+1) + ... + (K+N-1) )
Or, if you prefer to use "Jump & Count", here is a solution:
10: Load R1 <--- K (K)
11: Load R2 <--- 0000 (running total)
12: Load R3 <--- N (N)
13: Load R4 <--- 0001 (always 1)
14: Subtract R3 <--- R3 - R4 (N = N - 1)
15: Add R2 <--- R2 + R1 (add K to the running total)
16: Add R1 <--- R1 + R4 (K = K + 1)
17: Jump to 15 and decrease R3 if (R3 > 0)
(if N isn't 0 yet, decrease R3 by 1 and continue to add)
18: Halt (N is now 0, and R2 = K + (K+1) + ... + (K+N-1) )
Note: without line 14, you'll end up doing one more addition than needed
(i.e. the final result will be R2 = K + (K+1) + ... + (K+N-1) + (K+N) )
b) Create a machine language program that will compute 6! (that is, 6 factorial which is defined as
1 x 2 x 3 x 4 x 5 x 6).
Answer:
10: Load R1 <--- 0006 (N)
11: Load R2 <--- 0001 (running product)
12: Load R3 <--- 0001 (always 1)
13: Multiply R2 <--- R2 x R1 (multiply N to the running product)
14: Subtract R1 <--- R1 - R3 (N = N - 1)
15: Jump to 13 if (R1 > 0) (if N isn't 0 yet, continue to multiply)
16: Halt (N is now 0, and R2 = 1 x 2 x 3 x 4 x 5 x 6)
c) Create a machine language program that will let you put a value N in a register and then compute
N! (N factorial which is the product of the first N integers). (Hint: this will be a modification of one
of the programs for adding the first N integers.
Answer:
10: Load R1 <--- N (N)
11: Load R2 <--- 0001 (running product)
12: Load R3 <--- 0001 (always 1)
13: Multiply R2 <--- R2 x R1 (multiply N to the running product)
14: Subtract R1 <--- R1 - R3 (N = N - 1)
15: Jump to 13 if (R1 > 0) (if N isn't 0 yet, continue to multiply)
16: Halt (N is now 0, and R2 = 1 x 2 x 3 x 4 x 5 x ... x N)
d) The quantity N! grows very quickly. On our machine where memory stores values that are no
more than 16 bits long, we can not store N! for values of N that are greater than 8. If your program
from part c) were to try and compute 9!, it could cause the toy machine to crash or would cause an
error to occur. To fix this, modify your program from part c) so that it checks whether the value of
N is more than 8. If it is, it should reset the value to 8 and compute 8!.
Answer:
Here, we need to check the value of N before we calculate the factorial. To do that, we load N and
8 into two different registers, then calculate the value of 8 - N.
If (8 - N > 0), which means N < 8, we do not need to reset the value and can continue to
calculate the factorial;
Otherwise, (8 - N <= 0), which means N >= 8, we need to reset the value to 8 before we
continue to calculate the factorial.
10: Load R1 <--- N (N)
11: Load R2 <--- 0001 (running product)
12: Load R3 <--- 0001 (always 1)
13: Load R4 <--- 0008 (8)
14: Subtract R5 <--- R4 - R1 (R5 = 8 - N)
15: Jump to 17 if (R5 > 0) (if N < 8, then we needn't reset the value)
16: Load R1 <--- 0008 (otherwise, reset N to 8)
17: Multiply R2 <--- R2 x R1 (multiply N to the running product)
18: Subtract R1 <--- R1 - R3 (N = N - 1)
19: Jump to 17 if (R1 > 0) (if N isn't 0 yet, continue to multiply)
1A: Halt (N is now 0, and R2 = 1 x 2 x 3 x 4 x 5 x ... N if N < 8)
or R2 = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 if N >= 8)
(Problem 2) In this problem, you will use compression schemes like the ones discussed in class to
find a shorter representation for the phrase
They saw the theater when the terminator game came. They played the game in the theater.
a) If we were to represent this phrase as it stands (i.e. no compression), how many units of
memory would it require?
Answer:
The quote has 16 words, made up of 71 letters, 15 spaces, and 2 periods. To store it, we need
71 + 15 + 2 = 88 units of memory.
b) Identify duplicate words and tell how you would build a dictionary to reduce the amount of
memory required. Show the way the string would be represented with your dictionary and text
intermingled. Tell how much memory is saved by your scheme.
Answer:
Notice that the word "the" appears 4 times, "They", "theater" and "game" appear 2 times.
We then build our dictionary:
1 => They 2 => the 3 => theater 4 => game
The quote now reads:
"1 saw 2 3 when 2 terminator 4 came. 1 played 2 4 in 2 3."
They the theater game*1 saw 2 3 when 2 terminator 4 came. 1 played 2 4 in 2 3.
Note: we need a symbol (*) to tell when the dictionary ends; and we need to make sure there aren't
numbers or * in the text we want to compress.
We need 56 unites for the new quote above, and another 22 units for the dictionary. That is
56 + 22 = 78 units in total. We save 88 - 78 = 10 units.
c) Use the technique we saw in class to build strings of letters, not necessarily words, to build a
dictionary to further reduce the memory required. Show how your representation would look.
Tell how much memory is saved in your scheme.
Answer:
Using patterns in the quote, we can build our new dictionary:
1 => They_ 2 => _the 3 => ater 4 => _game_
The quote now reads:
"1saw223_when2_terminator4came._1played24in223."
They_#_the#ater#_game_*1saw223_when2_terminator4came._1played24in223.
Note: we use (#) to separated the patterns, we need a symbol (*) to tell when the dictionary ends;
and we need to make sure there aren't numbers or * or # in the text we want to compress.
We need 46 units for the new quote above, and another 23 units for the dictionary. That is
46 + 23 = 69 units in total. We save 88 - 69 = 19 units.
d) (Extra credit) Devise a scheme of your own to produce a representation of this particular
phrase that requires even less memory.
Answer:
Well, there can be many approaches. One common way is to break the representation into bits.
Say, if you have 4 numbers ( 0,1,2,3 ), you can use 2 bits (instead of 8 bits) to represent each
number. Or, in our quote, only 20 different symbols (letters, space, period) have appeared. You
can give a different encoding which requires only 5 bits (less than ASCII, which has 8 bits).
If you know about Haffman coding, you can give a pretty good solution :)
(Numeracy exercise) In assignment 2, you determined how many possible passwords your
computer can check during a single COS 111 lecture. In assignment 3, you determined that it
would be fairly easy to crack a password from the dictionary or made up of 8 digits. In this
assignment, we'll build on those results.
(Part a) If I chose a password made up of letters of the alphabet, all lower case, and having
exactly 6 characters. How many such words are there? How many COS111 lectures will it
take your computer to crack my password? You may assume that your computer can check
3.6 million passwords during a COS111 lecture.
Answer:
The password has exactly 6 characters, and each of them can be one of the 26 lower case letters,
so there can be 26 x 26 x 26 x 26 x 26 x 26 = 26 ^ 6 = 308,915,776 different passwords.
Assume we can check 3.6 million passwords during a COS111 lecture, we need
308,915,776
------------------- = 85.81 lectures
3,600,000
(Part b) Suppose that you use your computer to just crack passwords. So, instead of working
at it for 75 minutes twice a week, it tests passwords 24 hours a day. How many passwords
can your computer check in a day? You may assume that your computer runs at 800
megahertz (cycles per second) and can test one password in a million cycles.
Answer:
800 x 10^6 cycles 60 seconds 60 minutes 24 hours 1 password
-------------------- x ------------ x ------------ x ---------- x ----------------
second minute hour day 10^6 cycles
= 69,120,000 passwords per day
(Part c) Using the result of part b, how long would it take to crack my password if it was
constructed as in Part a. Assume that you are running your computer to try and crack
passwords 24 hours a day.
Answer:
From Part a, we know that there can be 308,915,776 different passwords;
from Part b, we know that we can check 69,120,000 passwords per day,
so we need
308,915,776
------------------ = 4.47 days
69,120,000
(Part d) How does your answer to part c change if my password has 7 letters?
Answer:
If the password has 7 letters, there can be 26^7 = 8,031,810,176 passwords.
We'll need
8,031,810,176
------------------- = 116.2 days
69,120,000
Comments? Questions? ------- Contact us at cs111@cs.princeton.edu