CSCI 567, Fall 2006 Assignment 10

Linkage Stack

The classic example of computational recursion is given by the factorial algorithm, here taken from Algorithms in C by Robert Sedgewick, p. 52. For non-negative N: 
int factorial(int N)
     {
          if (N==0) return 1;
          return N * factorial(N-1);
     }
Unfortunately, both the value N! and the computation time grow much too quickly to use as a demonstration of linkage stack operation (12! is the largest factorial which can be held in a 32-bit register). On the other hand, computation size and time of a sum grow only linearly, so we will compute sum(N) (also written N?) instead of N! in this assignment. Knuth, in The Art of Computer Programming, Volume 1, calls this the termial function, with algorithm: 
int termial(int N)
     {
          if (N==0) return 0;
          return N + termial(N-1);
     }
Requirements -
  1. You are to write a program called termget and an external subroutine called termial which will calculate N? recursively using the above termial algorithm.

  2. The termget program will read a file of numbers from T90MES1.C567.AS10(N), with one number on each record. [You may use X-macros (XREAD, XPRNT, XDECI, XDECO) for this program.] termget should check for valid numbers N with 0 <= n <= 999 and print an error message for invalid numbers. It should call termial, then print a double-spaced line indicating both N and N?. For example: 
    The termial of         100 is        5050

The termial of        1000 is too large.
    termget will call termial once for each N, to calculate N?. You will have to use the same calling sequence that termial uses to call itself.

  3. The termial subroutine will accept an integer in a register. It will call itself recursively as many times as necessary to calculate N?, using the linkage stack to save registers. termial should be short (fewer than 24 machine instructions), and will need no storage - keep everything in registers.

  4. The job should be structured as follows: 
    //logonidA JOB
//S1       EXEC HLASMCEG,EPARM='LIST,MAP,XREF'
//ASM.SYSIN DD  *
TermGet  CSect ,
TermGet  AMode 24                  Needed for X-macros
TermGet  RMode 24
         Print NoGen
         .
         .         loop to read N and calculate N?
         .
         End   TermGet
*PROCESS RENT
Termial  CSect
*
*********************************************************************
*
*   This routine calculates the termial value of the integer passed.
*
*   Input: R0 has number whose termial is to be calculated
*
*   Output: R15 has the sum N?
*
         .
         .
         .
         End   ,
//GO.INPUT DD DSN=T90MES1.C567.AS10(N),DISP=SHR

  5. You should not overestimate the resources required. In particular, if it is expanded, the linkage stack size should not be greater than will be needed.

Turn in the output from the job.

This page was last modified on Wednesday, March 28, 2007, at 08:09:59 PM GMT