COS 109: Problem Set 3

Tue Sep 15 10:21:30 EDT 2020

Due midnight, Thursday Sept 24

Collaboration policy for COS 109: Working together to really understand the material in problem sets and labs is encouraged, but once you have things figured out, you must part company and compose your written answers independently. That helps you to be sure that you understand the material, and it obviates questions of whether the collaboration was too close.

You must list any other class members with whom you collaborated.

Problem set answers need not be long, merely clear enough that we can understand what you have done, though for computational problems, show enough of your work that we can see where your answer came from. Thanks.

And a reminder from earlier problem sets: don't forget that if the data you start with is approximate, the results cannot be precise.

It's a big help if you write numbers in a standard form so we don't have to struggle to figure out what you meant. So it's better to write 1.23 * 10^9 or 1.23 x 109 than 1230000000; that way neither party has to count zeroes. In general, scientific notation is better for numbers that are outside the range say 0.001 to 10,000. We won't take a hard line on this right away, but please start to use this kind of scientific notation when you can.

And to reiterate: please type your answers if at all possible, especially if your penmanship, like mine, is less than impeccable. Thanks.

1. All the Colors of the 24-bit Rainbow

(a) The site colornames.org is an entertaining attempt to crowd-source names for all of the 224 colors that are possible with 24 bits. Name three previously unnamed colors and report the name and the hexadecimal value of your colors. (At the moment, only about 10 percent of colors have been named. so you should have a lot of choice.)

(b) The standard RGB representation of colors uses 8 bits for the red component, 8 bits for green, and 8 bits for blue (24 bits in all), and thus 6 hexadecimal digits can express any given color. For instance, red is FF0000, green is 00FF00, blue is 0000FF, and yellow is red plus green, or FFFF00. Suppose that a specialized display instead devotes more bits to green (where the human eye is most sensitive): it uses 7 bits for red, 10 bits for green and 7 bits for blue. Assuming that the bits are stored left to right in RGB order, what are the hexadecimal representations of red, green, blue, yellow, cyan and magenta for this display?
 

2. Bits, Bytes, Bases

Again, do some practice with the practice problem generator. Don't use it to answer these questions, however -- if you do, how would you know whether you can answer such questions?

(a) How many bits are required to store the population of the US? How many bytes?

(b) The population of California is about 1/8 of the population of the USA. How many bits would be required to store the population of California? How many bytes?

(c) The US gross domestic product (GDP) is about $2 trillion. How many bytes would be required to store this number?

(d) The US national debt right now is about $28 trillion. How many bytes would be required to store that number? [This site has more big numbers than you would believe, some that should maybe worry us.]

(e) The number of monthly active Facebook users worldwide is 2.7 billion. How many bytes are necessary to store this number?
 

3. Bloody Instructions

"We still have judgment here; that we but teach
bloody instructions, which, being taught, return
to plague th' inventor."
      (Macbeth, Act I, Scene VII.)
(a) The 1946 paper Preliminary discussion of the logical design of an electronic computing instrument discusses an architectural tradeoff: whether to include an instruction for multiplication or to synthesize it by using the addition instruction. What section of the paper first raises this issue?

(b) The toy simulator (toysim.html) is a Javascript program running in a web page. The toy machine does not have a multiply instruction. Modify the simulator by adding a multiply instruction, with the operation name mul. (The Javascript multiplication operator is *.) This requires a bit of detective work to find the places in the program where instructions are checked for validity and executed, then making changes that follow the existing pattern.

Start by making your own copy of toysim.html, which you can do by control-clicking on the link and selecting "Save Link As..." in Firefox and Chrome, or "Save Linked File As..." in Safari. Use a text editor (as in Labs 1 and 2) to modify the HTML file, by adding just a handful of lines of code. Do not change the formatting of the original; follow the pattern of indentation that you see when you add your new lines.

Your answer should specify the additional code you wrote and tell where in the existing program you added it. Do not submit the whole program, but copy and paste your added code along with a couple of lines of the original that are on each side to show where you added it.

Here's an example of a program that uses mul to double input numbers, stopping when it reads a zero.

 foo get
     ifzero bar
     mul 2
     print
     goto foo
 bar stop
 
You can use this program to verify that your version implements mul properly. Be sure you understand how it works.
 

4. Get With the Program

We want you to write two short programs for the toy computer used in class. It's impossible to be sure that any program, even little ones like these, is correct without running it, so you must test your code and your understanding by using the toy simulator. Be careful about typographical conventions and the like, since the simulator is fragile. The code you submit should be cut and pasted from a working version.

Real programs are always developed incrementally. You may find it easier to start with something small and simple, like some of the programs in the notes, to be sure you understand how the simulator works and how to get numbers in and print them out again, before you try to solve the assigned problem.

(a) Write a program that gets one number from the keyboard and prints its square and its fourth power. That is, if the original number is 10, the program prints 100 and 10000.) This should be about 9 instructions long, and will use your mul instruction.

You will need to set aside a memory location to store a value. It's best to put that at the end of the program, or at least in a place where the simulator will not think it's an instruction.

(b) Write a program that gets one number from the keyboard, prints that number and every other number down to 0 inclusive in steps of 2, then stops. For instance, if the initial number is 6, the program prints 6, 4, 2, 0 on successive lines. If the initial number is 7, the program prints 7, 5, 3, 1. This can be done in 5 instructions. It doesn't matter how many instructions your solution takes, but if you find yourself writing a lot more, you're likely on the wrong track. Think about the class example that adds up numbers. You might it helpful to figure out the operations that have to be performed each time through the loop, then worry about how to start and stop the loop.

This part requires a loop; if your program doesn't have some kind of loop, it's wrong. The loop has to end somehow; if your program doesn't make some test that can terminate the loop, it's wrong. Thus your program will contain code analogous to this, though not the same:

Top	GET
	IFZERO Done
	...
	GOTO Top
Done	...

Submission

Please use this Word template for your answers. It would be a great help if you could type your answers so I can read them, but if you prefer to write by hand, that's OK as long as you are very neat. (That is, not like me!).

Submit your problem set in PDF format by uploading a file called pset3.pdf to https://tigerfile.cs.princeton.edu/COS109_F2020/Pset3. You can submit as many times as you like; we will only look at the last one.