Trabb Pardo–Knuth algorithm

From Wikipedia, the free encyclopedia
  (Redirected from Trabb Pardo-Knuth algorithm)
Jump to: navigation, search

Knuth algorithm is a program introduced by Donald Knuth and Luis Trabb Pardo to illustrate the evolution of computer programming languages.

In their 1977 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a small program that involved arrays, indexing, mathematical functions, subroutines, I/O, conditionals and iteration. They then wrote implementations of the algorithm in several early programming languages to show how such concepts were expressed.

The trivial Hello world program has been used for much the same purpose.

The algorithm[edit]

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
        print result

The algorithm reads eleven numbers from an input device, stores them in an array, and then processes them in reverse order, applying a user-defined function to each value and reporting either the value of the function or a message to the effect that the value has exceeded some threshold.

ALGOL 60 implementation[edit]

   begin integer i; real y; real array a[0:10];
   real procedure f(t); real t; value t;
     f := sqrt(abs(t)) + 5*t^3;
   for i := 0 step 1 until 10 do read(a[i]);
   for i := 10 step -1 until 0 do
     begin y := f(a[i]);
           if y > 400 then write(i, "TOO LARGE")
           else write(i,y);

The problem with the usually specified function is that the term 5*t^3 gives overflows in almost all languages for very large negative values.

C++ implementation[edit]

This shows a C++ implementation equivalent to the above ALGOL 60.

 #include <algorithm>
 #include <cmath>
 #include <iostream>
 double f(int n) { return sqrt(abs(n)) + 5*n*n*n;}
 int main() {
     const int N = 11; int S[N];  
     for(int i = 0; i < N; ++i) { std::cin >> S[i]; }
     std::reverse(S, S+N); 
     for(int i = 0; i < N; ++i) { 
         double y = f(S[i]);
         if(y > 400) { std::cout << i << " TOO LARGE\n";}
         else { std::cout << y << '\n'; }

Python implementation[edit]

This shows a Python 3.5 version using a function style and then again imperatively

from math import sqrt, fabs
l = []
while len(l) < 11:
		x = float(input("Enter number {}: \n".format(len(l)+1)))
		print("Not a valid number")

def f(x):
	return sqrt(fabs(x)) + 5.0 * (x**3.0)
def p(a,b):
	return a if a < 400 else "{} is too large".format(b)

list(map(lambda y: print(p(f(y), y)), reversed(l)))

## Or the imperative version 

from math import sqrt, fabs
l = []
while len(l) < 11:
		x = float(input("Enter number {}: \n".format(len(l)+1)))
		print("Not a valid number")


for i in l:
	result = sqrt(fabs(i)) + 5.0 * (i**3.0)
	if result < 400:
		print("{} is too large".format(i))

JavaScript implementation[edit]

This shows a JavaScript implementation using the ES7 draft, equivalent to the other implementations on this page.

let [i, l, a, {sqrt, abs}] = [0, 10, [], Math],
f = x => sqrt(abs(x)) + 5 * x ** 3,
t = (x, i) => x > 400 ? `${i} TOO LARGE` : x;
while (i++ < l + 1) a.push(prompt());
for (i -= 2; i >= 0; --i) console.log(t(f(a[i]), l - i));


External links[edit]