COS 109: Problem Set 3

Mon Sep 25 10:04:56 EDT 2023

Due midnight, Wednesday Sept 27

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.

1. All the Colors of the 24-bit Rainbow

(a) The site is an entertaining attempt to crowd-source names for all of the 224 RGB colors that are possible with 24 bits. Visit the site, name three previously unnamed colors, and report the names and the hexadecimal values of your colors. (As of September 2023, only a little over 21 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 24-bit 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 several more bits to green, where the human eye is most sensitive, but fewer for red and blue: it uses 6 bits for red, 12 bits for green and 6 bits for blue. Assuming that the 24 bits are stored left to right in 3 bytes in RGB order, what are the hexadecimal representations of red, green, blue, yellow, cyan and magenta for this display? (Hint: draw a picture.)

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 if by coincidence they were to appear on an exam?

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

(b) How many bytes is this?

(c) The population of the European Union is about 2.25 times the population of the USA. How many bytes would be required to store a number representing the population of the EU?

(d) How many bytes would be required to store a number representing the population of the whole world?

(e) The US national debt right now is about $32 trillion. How many bytes would be required to store that number? [This site displays more big numbers than you would believe, some of which should maybe worry you as future taxpayers.]

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 Machine is a simplified "toy" version of what a real computer is like under the hood. Like a real computer, it has its own repertoire of instructions, and its own low-level assembly language for writing instructions.

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 instruction name mul. (The Javascript multiplication operator is *.) This requires a bit of detective work to find the several places in the program where instructions are checked for validity and executed, then making changes that follow the existing pattern. Hint: Try to figure out how the other arithmetic instructions work, then go from there.

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.

Copy and paste your added code along with one line of the original from each side of your code, to show where you added it. Do not submit the whole program, just your additional lines with a line of context on each side.

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

foo get
    ifzero bar
    mul 2
    goto foo
bar stop
You can use this program to verify that your version of Toysim 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 copied 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. Then make sure you can get a number from the keyboard, print it back out, and stop properly.

(a) Write a program that gets one number from the keyboard and prints the number, its square and its cube. That is, if the original number is 10, the program prints 10, 100 and 1000.) This takes 8 instructions, and will use your mul instruction.

You will need to set aside a memory location to store the input value. Put that at the end of the program, where the simulator will not think it's an instruction.

(b) Write a program that gets one number from the keyboard, and counts backwards from that number down to 0 inclusive, in steps of 7, then stops. For instance, if the initial number is 28, the program prints 28, 21, 14, 7, 0 on successive lines. If the initial number is 29, the program prints 29, 22, 15, 8, 1. (This apparently silly program mimics a clinical test called Serial sevens, which is used to assess mental status after head injuries.)

This can be done in 5 instructions; it will not use mul and won't need a storage location, but it does need a loop. 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.

Hint: Think about the class example that adds up numbers. You might find 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.

If your Toy program is failing, it might be because you haven't got the syntax right. Check over your program to make sure you haven't made any typos and that your spaces and newlines are in the right places.


Please use this this Google Doc as a template for your answers. It would be a great help if you type your answers so we 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!)

Either way, convert your answers to PDF and submit them by uploading a file called pset3.pdf to the "Pset3" assignment in Gradescope. When submitting on Gradescope, you will be asked to label each question with the page of the PDF your answer appears on (feel free to reach out if this causes any issues). You can submit as many times as you like; we'll only look at the last one.