Lably
Skip to content

TPK algorithm

Program to compare computer programming languages

  • 15 min read
  • 2 chapters

Related on Lably

Through Computer program, Function (mathematics) and Function (computer programming)

Lab · Class 11–12Relations and FunctionsLab · Class 12Relations and FunctionsLab · Class 12Inverse Trigonometric FunctionsLab · Class 11Trigonometric Functions

To explain the name "TPK", the authors referred to Grimm's law (which concerns the consonants 't', 'p', and 'k'), the sounds in the word "typical", and their own initials (Trabb Pardo and Knuth). In a talk based on the paper, Knuth said:

You can only appreciate how deep the subject is by seeing how good people struggled with it and how the ideas emerged one at a time. In order to study this—Luis I think was the main instigator of this idea—we take one program—one algorithm—and we write it in every language. And that way from one example we can quickly psych out the flavor of that particular language. We call this the TPK program, and well, the fact that it has the initials of Trabb Pardo and Knuth is just a funny coincidence.

The algorithm

Knuth describes it as follows:

We introduced a simple procedure called the “TPK algorithm,” and gave the flavor of each language by expressing TPK in each particular style. […] The TPK algorithm inputs eleven numbers a0,a1,…,a10; then it outputs a sequence of eleven pairs (10,b10),(9,b9),…,(0,b0), where

bi={f(ai),if f(ai)≤400;999,if f(ai)>400;f(x)=|x|+5x3.

This simple task is obviously not much of a challenge, in any decent computer language.

In pseudocode:

<b id="mwJg">ask</b> for 11 numbers to be read into a sequence <i id="mwJw">S</i> <b id="mwKA">reverse</b> sequence <i id="mwKQ">S</i> <b id="mwKg">for each</b> <i id="mwKw">item</i> <b id="mwLA">in</b> sequence <i id="mwLQ">S</i> <b id="mwLg">call</b> a function to do an operation <b id="mwLw">if</b> <i id="mwMA">result</i> overflows <b id="mwMQ">alert</b> user <b id="mwMg">else</b> <b id="mwMw">print</b> <i id="mwNA">result</i>

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.

Sign in to keep reading

One more chapter is free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard