Rank function (computer science)

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

Under a ranking function (English ranking function ) is understood in the computer science a function with values in the natural numbers , which when running an algorithm falls from calculation step to calculation step monotonous. This property is used to prove the termination of the algorithm.

Simple example

We consider the following algorithm for adding two numbers:

sum (a, 0) = a
sum (a, b) = sum (incr (a), decr (b))

(here incr (a) means increasing the number a by 1 and decr (b) means reducing the number b by 1).

In this example

• r = b

a rank function that decreases by 1 in each calculation step.

Another example

A variant of the classic Euclidean algorithm for calculating the greatest common divisor gcd (a, b) is this recursive version: If a> b, then call gcd (ab, b). If a <b then call gcd (a, ba). Do this until a and b are the same. a and b are then the common greatest divisor.

In this example

• ${\displaystyle r=|a-b|}$

a rank function.