Machine Problem 3, due Jul. 8

A function

The binomial coeficients are defined by the following formulas:

• The classic formula

  (	n	)		n!
  			=
  	k			k!(n – k)!

• An inductive definition

  ( n )   =   1 0

  ( n )   =   1 n

  ( n ) ( n – 1 ) ( n – 1 )   =     +   k k k – 1

It is trivial to reduce the inductive definition to a recursive function, call it binom( n, k ), but there is another way to compute the binomial coefficients, using Pascal's triangle. Here are the first five rows of the triangle:

Note in Pascal's triangle that each entry is the sum of the two entries immediately to the left and right above it. If you number the rows starting with zero, and you number the items in each row from left to right starting at zero, the entry at row n item k of each row is the binomial coefficient.

This leads naturally to an algorithm for computing the triangle a row at a time using an array. The array size needs to be proportional to the number of rows of the triangle you want to print. Initially, the array holds row 0 of the triangle, with just one initialized entry, item 0 is equal to 1. For each row, the first and last item are 1; to compute the other items in each row, sum pairs of adjacent items. It's slightly simpler to compute the values in each row from right to left, but with an added temporary variable, it can be done left to right. Repeat this until you've computed the highest row you need.

An assignment

Write a SMAL Hawk program that computes and displays Pascal's triangle, displaying as many rows of the triangle as will fit on the screen, but no more than 15, and displaying each line roughly centered on the screen.

Each number sould be displayed in a field of width 4 characters, so each row begins 2 characters to the right of the previous row.

You are free to use either the recursive function suggested by the inductive definition of the binomial coefficients, or the array-based algorithm. They produce the same output. The array-based approach is faster, particularly for large triangles. The recursive solution produces a smaller program.

As usual, quality commentary and clean code are required. Your submission must be in a file named mp3.a and you should use the submit shell command for the class CS2630 and the mp3 assignment.

Useful background

Note that the Hawk monitor passes two parameters to the main program: On entry, R3 will hold the number of columns in the display window, and R4 will hold the number of lines. The center column number can therefore be computed with SR R3,1, although if you are printing in fields of width 4, you'll get the best looking result if you subtract a bit from that.

You can allocate space for a static array using the COMMON directive. Or, you can allocate an array in the activation record of the main program, as demonstrated in the main program for the second example given in class on June 28 and distributed on line with the notes. In either case, if you use an array, don't forget to multiply the number of words by 4.