## Trabb Pardo Knuth Algorithm

### April 27, 2012

We’ll give two solutions. Scheme uses lists, not arrays, as its basic aggregate data type, so our first version of the program uses lists:

(define (tpk len)
(define (f x) (+ (sqrt (abs x)) (* 5 x x x)))
(let loop ((len len) (nums '()))
(if (positive? len)
(loop (- len 1) (cons (read) nums))
(for-each
(lambda (x)
(let ((result (f x)))
(display (if (< 400 result) "TOO LARGE" result))
(newline)))
nums))))

Here’s an example:

> (tpk 11)
TOO LARGE
322.0
136.732050807569
41.4142135623731
6.0
0.0
-4.0
-38.5857864376269
-133.267949192431
-318.0
-622.7639320225

Although we used lists, the Trabb Pardo Knuth algorithm is intended to be used with arrays. Here is the fully-imperative array version in Scheme:

(let ((vec (make-vector len 0)))
((or (= i len)(eof-object? num)) vec)
(vector-set! vec i num))))

(define (vector-reverse vec)
(do ((lo 0 (+ lo 1))
(hi (- (vector-length vec) 1) (- hi 1)))
((<= hi lo) vec)
(let ((t (vector-ref vec lo)))
(vector-set! vec lo (vector-ref vec hi))
(vector-set! vec hi t))))

(define (f num) (+ (sqrt (abs num)) (* 5 num num num)))

(define (tpk len)
(do ((i 0 (+ i 1))) ((= i len))
(let ((result (f (vector-ref vec i))))
(display (if (< 400 result) "TOO LARGE" result))
(newline)))))

Here, read-number returns a vector of len numbers, vector-reverse reverses the vector by repeatedly swapping from the left and right, and tpk encodes the algorithm. Output from (tpk 11) is the same as for the prior version.

You can run the program at http://programmingpraxis.codepad.org/8OFS3rH7. It is also available at http://ideone.com/gOKJ7, where you can actually see input and output of the program.

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 […]

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) .

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;

// 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:
`