The Trabb Pardo-Knuth algorithm is a program introduced by Donald Knuth and Luis Trabb Pardo to illustrate the evolution of computer programming languages.
In their 1980 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a trivial program which 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 simpler Hello world program has been used for much the same purpose.
The algorithm
ask for 11 numbers into set S
reverse set S
for each item in set S
do an operation
if result overflows
alert user
else
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.
Versions
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);
end
end
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.
The following Perl implementation is 79 bytes.
map print(($_>400?"TOO LARGE":$_).$/),reverse map 5*($x=<>)**3+sqrt abs$x,1..11
Python version
The following Python version of the algorithm uses the common Python idiom of using a list instead of an array:
from math import sqrt
def f(t):
return sqrt(abs(t))+5*t**3
a = [int(raw_input()) for i in range(11)]
for i in range(10,-1,-1):
y = f(a[i])
if y > 400:
print i, "TOO LARGE"
else:
print i, y
Ruby version
The Ruby version takes advantage of some of its features:
# by pietro gagliardi | june 25, 2007
x = []
11.times do
x = x + [gets.to_i]
end
r = 0
x.reverse.each do |val|
begin
if r == 1 then
r = 0
else
val = 5 * val ** 3
puts val.to_s
end
rescue
puts "overflow"
r = 1
retry
end
end
Ruby handles extremely large values very easily, even on 64-bit systems, so the possibility of an overflow in the above program would be slim. If it does happen, the variable r and the retry statement ensures that the exception does not occur again on the same value.
References
- "The Early Development of Programming Languages" in A History of Computing in the Twentieth Century, New York, Academic Press, 1980. ISBN 0-12-491650-3 (Reprinted in Knuth, Donald E., et al, Selected Papers on Computer Languages, Stanford, CA, CSLI, 2003. ISBN 1-57586-382-0)