Assignment 3

CISC221, Fall 2001

Queen's University

Due: Thu November 15, 2001 (11:00)

Where: in drop box 221 Goodwin Hall

No late assignments! See below notes for furhter instructions.

 

Objective

The goal of this assignment is to further your knowledge of assembly language by having you code an algorithm which involves integer arithmetic, branches, loops, and subroutines.

Assignment 3: Approximating Cube Roots

The ACME Widget Company has a warehouse where it stores finished widgets and the packing boxes that it uses to ship the widgets to its customers. Every packing box is a cube which is exactly C centimetres on each side, thus having a capacity of C3 cubic centimetres. Boxes are available in any size from C = 2 (i.e. 2 x 2 x 2) up to C = 30 (i.e., 30 x 30 x 30) centimetres. Each ACME widget takes up exactly 1 cubic centimetre of space in the box. The larger the packing box, the more expensive it is, so ACME would like to pack each shipment in the smallest possible box.

Employees in the ACME warehouse carry a pocket version of the PEP/6 computer, which they have been using to track inventory. ACME would like you to write a program in PEP/6 assembly language that will tell the employees the size of the smallest sized box into which a given shipment will fit. The employee will key into the computer the number of widgets, N, in the shipment, and the PEP/6 will output the size, C, of the smallest box that can contain that many widgets (where C is the length of one side of the box).

Phrased mathematically, the program should take the number N and output the smallest integer greater than or equal to the cube root of N (i.e., whose cube is bigger than N). For example:

input

output

8

2

(23 = 8)

875

10

(103 = 1000)

6740

19

(193 = 6859)

 

The program should calculate the box size required by successively cubing the integers 2, 3, 4, 5, ... 30 until the resulting cubic capacity is bigger than the input number of widgets. For example, if the input number were 75, the algorithm would proceed by calculating 2 * 2 *2 = 8, 3 * 3 * 3 = 27, 4 * 4 * 4 = 64 and 5 * 5 * 5 = 125, at which point it would stop since 125 > 75 and print out 5 as the required box size.

If a shipment is too large to fit into a single box, you should output the dimensions of a set of boxes into which it would fit, rather than outputting an error message saying that the shipment is too large.

Since the PEP/6 computer does not have a multiply instruction, you should write a subroutine (function) which takes two positive integer arguments (say x and y) and returns the positive integer which is their product (x*y). The subroutine must necessarily use a loop of successive additions (e.g., 10 * 5 = 10 + 10 + 10 + 10 + 10). To input and output the numbers, use the DECI and DECO instructions of the PEP/6 operating system.

Your program should gracefully reject (with an error message) input which is inappropriate, out of range or for which there is no solution, although you can assume that the input will be a decimal number. (Note that DECI rejects non-integer input gracefully.)

As with all assembly language programs, you would start by designing a high level language (Java or C) program and then translate the declarations and statements of that program into PEP/6 assembly language. You will save yourself time if you actually write and debug the high level language program first, because, as you will discover, debugging in assembly language is difficult. (Remember to write the solution without using any multiplications, however, or your high level language program won't help!)

The assembly language statements in your final program should be commented on the right with the high level language statements they are intended to implement, and the entire high level language program should appear as a comment at the beginning of the assembly language program, to document your program design. (Your editor may have a command that will make it easy to turn your high-level program into assembly language comments. In vi, the command :1,$s/^/;/ prefixes every line with the PEP/6 comment marker.)

What to hand in

  1. A printed listing of your assembly language program. You can use the listing file produced by the assembler, to get a nicely formatted file without extra effort.

    The listing should include the design documentation for the program in comments (the high level language version of the program, together with any other information about your design that you think would make it easier for another programmer to understand and modify your code).

  2. A printed listing of a set of test runs designed to demonstrate that every aspect of your program is working properly, including every kind of error handling. Testing will be easier if you write your program to allow multiple inputs in one run (though you'll have to think of some way to tell the program when there is no more data).
  3. In addition to the the hardcopy submission requirements of Assignment 3 please submit your program electronically using the following Unix command: turnin-cisc221 where is the name (including any required path information if not in the current directory) of your assembler source file. If you are using the Windows version of PEP6 or PEP7, save your source file as PLAIN TEXT with a .txt extension and submit this file electronically. DO not use the the turnin command to submit a Windows .odc file. It can't be read on a Unix system.