Generalization of the "binary" algorithm

Let's consider one more the "binary" algorithm in the framework of our model of the "Indicator Elements". In general case the "binary" algorithm consists of n steps and uses only 1 IE, which movement is submitted to the condition of S = 0. We can mark this algorithm in (n, 1, S)-algorithm.

We can generalize the "binary" algorithm if we increase the number of IE from1 to k, where k takes its values from the set {1, 2, 3, ...}. Then we can consider the (n, k, 0)-algorithms, which are the generalization of the (n, 1, 0)-algorithm, that is, the "binary" algorithm.

In this case the first step of the (n, k, 0)-algorithm on the line segment AB consists of applying the k IE's to the points of the line segment AB as is shown in Fig.1.

The first step of the optimal (n, k, 0)-algorithm
Figure 1. The first step of the optimal (n, k, 0)-algorithm.

It is clear that the "effectiveness" of the (n, k, 0)-algorithm T depends on n and k, that is, the "effectiveness" is some function T = F(n, k). We have to find the "optimal" (n, k, 0)-algorithm, that is, the measurement algorithm, which provides the maximum value of the "effectiveness" function T = F(n, k).

We wouldn't like to tire our readers by the keenness of the mathematical reasoning and would like to give the final result. It was proved that the first step of the optimal (n, k, 0)-algorithm consists in applying the k IE's to the points C1, C2, ..., Cj, Cj+1, ..., Ck, which divide the line segment AB into k + 1 equal parts. According to the "indications" of the k IE's after the first step we select the new line segment Cj, Cj+1, which is divided by the k IE's again into k + 1 equal parts. This procedure is repeating on each step and ends after the n-th step.

The "effectiveness" function for the "optimal" (n, k, 0)-algorithm has the following form:

F(n, k) = (k+1)n.(1)

For the case k = 1 this formula is reduced to the "effectiveness" function of the "binary" algorithm.

Note that like to the "binary" algorithm, which "generates" the binary number system the optimal (n, k, 0)-algorithm "generates" the positional number system with the radix R = k + 1, i.e.

A = an-1 Rn-1 + an-2 Rn-2 + ... + ai Ri + ... + a1 R1 + a0 R0,(2)

where ai Î {0, 1, 2, ..., k} is the numeral of the i-th digit.

In particular, for the case k = 9 the formula (2) is reduced to the classical decimal number system

A = an-1 10n-1 + an-2 10n-2 + ... + ai 10i + ... + a1 101 + a0 100,

which is studied in secondary school.

For the case k = 59 the formula (2) is reduced to the Babylonian sexagecimal number system. It follows from this consideration that the "optimal" (n, k, 0)-algorithms "generate" all the well-known positional number systems.