TPK algorithm: Difference between revisions

Revision as of 21:58, 19 April 2021

Revision as of 05:05, 20 September 2021

Line 1:

The '''TPK algorithm''' is a simple [[computer program|program]] introduced by [[Donald Knuth]] and [[Luis Trabb Pardo]] to illustrate the evolution of computer [[programming language]]s. In their 1977 work "The Early Development of Programming Languages", Trabb Pardo and Knuth introduced a small program that involved [[Array data structure|arrays]], indexing, mathematical [[Function (mathematics)|function]]s, [[subroutine]]s, [[I/O]], [[conditional (programming)|conditional]]s and [[iteration]]. They then wrote implementations of the algorithm in several early programming languages to show how such concepts were expressed.

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).<ref name="edpl"/> In a talk based on the paper, Knuth said:<ref name="chm"/>

Line 7:

==The algorithm==

Knuth describes it as follows:<ref>Donald Knuth, ''TPK in INTERCAL'', Chapter 7 of ''Selected Papers on Fun and Games'', 2011 (p. 41)</ref>

{{quote|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 number <math>a_0, a_1, \ldots, a_{10}</math>; then it outputs a sequence of eleven pairs <math>(10, b_{10}), (9, b_9), \ldots, (0, b_0),</math> where

<math>b_i = \begin{cases}

f(a_i), & \text{if }f(a_i) \le 400; \\

999, & \text{if }f(a_i) > 400; \end{cases} \quad f(x) = \sqrt{|x|} + 5x^3.</math>

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

In pseudocode:

'''ask''' for 11 numbers to be read into a sequence ''S''

'''reverse''' sequence ''S''