Due 5:00 PM, Wednesday, Oct 14, in the box outside Room 311, CS
building, or in class. Answers need not be long, merely clear so we can
understand what you have done. Please submit typed material, not
hand-written, if at all possible, and keep a copy for yourself just in
case something goes astray. Thanks.
In The Social Atom (2007), author Mark Buchanan says "Take a piece of whisper-thin paper, say 0.1 mm thick. Now suppose you fold it in half twenty-five times in a row, doubling its thickness each time. How thick will it be? Almost everyone asked such a question will grossly underestimate the result." Right now, make your own estimate, which you should be able to do in your head on the basis of what we've done in class. When you do the rest of this exercise you can assess whether you are better than "almost everyone".
(a) If Buchanan is correct about the thickness of a piece of paper, how thick will the folded paper be?
(b) Is Buchanan's estimate of 0.1 mm much too high, much too low, or about right, and why? (You can make your own estimate by observation near printers.)
(c) Von Neumann's Preliminary discussion of the logical design of an electronic computing instrument (1946) says (§5.2), "... a binary coding of the decimal system -- each decimal digit being represented by at least a tetrad of binary digits. Thus an accuracy of ten decimal digits requires at least 40 binary digits. In a true binary representation of numbers, however, about 33 digits suffice to achieve a precision of 1010. The use of the binary system is therefore somewhat more economical of equipment than is the decimal." Is 33 bits enough to represent decimal numbers as large as 1010, and why do you say so?
(d) For practice, write out the decimal value 109 in binary, in hex, and in tetrads (a representation which today is often called "binary coded decimal": 4 bits for each decimal digit).
"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) Von Neumann discusses an architectural tradeoff: whether to include an instruction for multiplication or to synthesize it by using the addition instruction. What section of the 1946 paper first raises this issue? How would you summarize the tradeoff in a single sentence?
(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 place in the program where arithmetic is done, then making a change that follows the existing pattern. Start by View Source and save that file on your own computer as an ASCII text file with extension .html. Your answer should specify the additional code you wrote and an indication of where in the existing program you added it; do not submit the whole program, but you are most strongly advised to try your version of the simulator to be sure it works.
We want you to write two short programs for the toy computer used in class; the instruction-set description is repeated here:
get get a number from keyboard into accumulator print print contents of accumulator load Val load accumulator with Val (Val unchanged) store Lab store accumulator contents into memory location labeled Lab (accumulator unchanged) add Val add Val to contents of accumulator (Val unchanged) sub Val subtract Val from contents of accumulator (Val unchanged) goto Lab go to instruction labeled Lab ifpos Lab go to instruction labeled Lab if accumulator is greater than or equal to zero ifzero Lab go to instruction labeled Lab if accumulator is zero stop stop running Num initialize this memory location to numeric value Num (once, before program runs)
If Val is a name like Sum, it refers to a labeled memory location. If Val is a number like 17, that value is used directly. So add Sum means to add the contents of the memory location named Sum to the accumulator value (leaving Sum's contents unchanged), while add 1 means to add 1 to the accumulator value.
It's impossible to be sure that any program, even little ones like these, is correct without running it. 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 quite 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 write the two programs below.
(a) Write a program that gets one integer from the keyboard and prints three times its value (e.g., if the number is 10, the program prints 30.) This should be about 6 lines long, or 4 lines if you use your mul instruction. Think about the class example that adds two numbers.
(b) Write a program that gets one number from the keyboard, prints that number and successive lower numbers down to 0 inclusive, then stops. For instance, if the initial number is 4, the program prints 4, 3, 2, 1, 0 on successive lines. This can be done in 6 instructions, so if you find yourself writing a lot more, you're 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 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 is likely to contain code analogous to this, though not necessarily the same:
Top GET IFZERO Done ... GOTO Top Done ...