Trabb Pardo Knuth Algorithm

April 27, 2012

In their 1973 paper “The Early Development of Programming Languages,” Luis Trabb Pardo and Donald Knuth give the following algorithm as a means of assessing programming languages:

ask for 11 numbers to be read into a sequence S
reverse sequence S
for each item in sequence S
    call a function to do an operation
    if result overflows
        alert user
    else
        print result

Though it is trivial, the algorithm involves arrays, indexing, mathematical functions, subroutines, I/O, conditionals and iteration, and thus exposes many basic operations of a programming language.

Your task is to write a program that implements the Trabb Pardo Knuth algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

12 Responses to “Trabb Pardo Knuth Algorithm”

  1. [...] today’s Programming Praxis exercise, our goal is to implement a simple algorithm that could serve as an [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2012/04/27/programming-praxis-trabb-pardo-knuth-algorithm/ for a version with comments):

    import Control.Monad
    
    f :: Double -> Double
    f x = sqrt (abs x) + 5 * x^3
    
    main :: IO ()
    main = mapM_ (putStrLn . (\x -> if x > 400 then "TOO LARGE" else show x) . f) .
           reverse =<< replicateM 11 readLn
    
  3. ardnew said

    Implementation in C. The algorithm doesn’t check if overflow occurred when reading input from the user

    #include <stdio.h>
    #include <stdint.h>
    
    #define NUM_ELEMENTS 11
    
    // Performs multiplication on 2 32-bit integers
    uint32_t mult_uint32(uint32_t a, uint32_t b, uint8_t *o)
    {
      uint64_t p = (uint64_t)a * b;
      *o = p > UINT32_MAX;
      return p;  
    }
    
    int main(void)
    {
      uint32_t sequence[NUM_ELEMENTS];
      uint32_t product;
      uint8_t  overflow;  
      size_t   i;
      
      printf("Please enter %u numbers:\n", NUM_ELEMENTS);
    
      // Read numbers into the sequence
      for (i = 0; i < NUM_ELEMENTS; ++i)
        scanf("%u", &sequence[i]);
        
      // Reverse sequence
      for (i = 0; i < NUM_ELEMENTS / 2; ++i)
      {
        sequence[i] ^= sequence[NUM_ELEMENTS - i - 1];
        sequence[NUM_ELEMENTS - i - 1] ^= sequence[i];
        sequence[i] ^= sequence[NUM_ELEMENTS - i - 1];
      }
    
      // Call a function to perform an arithmetic operation on
      // each element of the sequence
      for (i = 0; i < NUM_ELEMENTS; ++i)
      {
        product = mult_uint32(sequence[i], sequence[i], &overflow);
        
        // Alert user if overflow occurred
        if (overflow)
          printf("%u * %u = %s\n", sequence[i], sequence[i], "overflow");
        // Otherwise print result
        else
          printf("%u * %u = %u\n", sequence[i], sequence[i], product);
      }
      
      return 0;
    }
    
  4. Mike said

    Here’s a fairly literal implementation in Python 2.7:

    def tpk():
        print "Enter 11 numbers:"
        S = [input("{:2}: ".format(n)) for n in range(1,12)]
    
        S.reverse()
    
        for item in S:
            try:
                x = pow(9.9, item)
    
            except OverflowError:
                print "OverflowError for {}".format(item)
    
            else:
                print x
    
    

    Note: “input()” is generally not safe, because it actually executes the user input.

  5. [...] latest Programming Praxis Exercise is interesting. Back in 1973, Luis Trabb Pardo and Don Knuth published an algorithm that was meant [...]

  6. tartley said

    Almost the same as Mike’s, here as Python3. My personal preference is with fewer intermediate variables in this case.

    from sys import stderr
    from math import sqrt
    
    def main():
        for number in reversed([input('> ') for _ in range(11)]):
            try:
                print(sqrt(float(number)))
            except (ValueError, OverflowError) as e:
                print('{} {} for {}'.format(
                    type(e).__name__, str(e), number), file=stderr)
    

    ‘input’ in Python3 is the same as ‘raw_input’ in Python2, i.e. it doesn’t eval the input, but just returns it as a string. This means I cast to float before passing to my function ‘sqrt’. I broaden the scope of error catching from OverflowError to all ValueErrors, which includes failure to convert the entered string into a float.

  7. treeowl said

    Remco, I think a Haskell solution truer to the spirit of the exercise would probably use something like GHC’s exception system to handle numeric overflow. Yours forbids it, rather than actually dealing with it.

  8. David said

    Forth version, just don’t enter a double precision number.

    11 Constant #Elements
    
    : int-array ( compile: n -- / run: n -- addr )
        create 
            cells allot
        does>
            swap cells + ;
    
    #Elements int-array vec
    
    : get-input  ( -- )
        ." Enter " #Elements . ." numbers:" cr
        11 0 DO
            ." > " pad 25 accept cr
            pad swap number  i vec !
        LOOP ;
    
    : reverse-it ( -- )
        #Elements 2/  0 DO
            i vec @  #Elements i - 1- vec @
            i vec !  #Elements i - 1- vec !
        LOOP ;
    
    : 2^24*   ( n -- n ? )  \ multiply by 2^24,
              \ result TRUE is success, FALSE is overflow
        $1000000 m* 0= ;
    
    : show-output  ( -- )
        #Elements 0 DO
            i vec @ 2^24* IF
                .
            ELSE
                ." Overflow"
            THEN cr
        LOOP ;
    
    : tbk  ( -- )
        get-input
        reverse-it
        show-output ;
    

    Execution

    tbk Enter 11 numbers:
    > 372
    > 11
    > 42
    > 1
    > 7
    > 0
    > 3772
    > 2991
    > 44
    > 2
    > 1
    16777216
    33554432
    738197504
    Overflow
    Overflow
    0
    117440512
    16777216
    704643072
    184549376
    Overflow
     ok
    
  9. my implementation in Python:

    def tbk():
    s = raw_input("Enter 11 numbers separated by space: ")
    s = s.split(‘ ‘)
    s.reverse()

    for i in s:
    try:
    result = pow(9.9, int(i))
    except OverflowError:
    print "Overflow error for {}".format(i)
    else:
    print result

  10. tartley said

    Benjamin, see the link “Howto: posting source code” in the blog titlebar for how to post source code in your comments. Personally I found the third of the three described methods simplest.

  11. I saw that one after asking here. Should have search around before asking. Haha! Thanks anyway!

  12. In Scala:
    `
    Seq.fill(11){Console.readInt}.reverse.map(i => Try(sqrt(i)).foreach {
    case Success(root) => println(root)
    case Failure(_) => println(“Could not compute sqrt”)
    }
    `

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 599 other followers

%d bloggers like this: