Generalization of Fibonacci's measurement algorithms

The further generalization of Fibonacci's measurement algorithms based on the "Asymmetry Principle of Measurement" consists of the following. Let's increase the number of balances participated in measurement from 1 to k. Let's put the same measurable load Q on the left cup of the balances. There is the case of the "parallel" measurement of the load Q by using the k balances for n steps. The "parallel" case is used very often in modern analog-to-digital converters of electrical values for the increase of their speed acting. In the latter case the measurable electrical value is given in parallel with the measuring inputs of k comparators (the electrical equivalent of the balance).

Let's suppose that all the balances, realizing the measuring, have the "inertness" p, (p = 0, 1, 2, 3, ...). This brings up into the problem of finding out the "parallel" optimal (n, k, S)-algorithm by using k balances having the "inertness" p. For simulation of the "inertness" of the balances (or "Indicator Elements") we introduce the concept of the state of the j-th IE at the l-th step (j = 1, 2, 3, ... , k; l = 1, 2, 3, ..., n). Let's mark the latter in pj(l). It follows from the "physical" consideration of the "weighing problem" that the integer function pj(l) has the following properties:

0 £ pj(l) £ p;(1)
pj(l + 1) = pj(l) - 1.(2)

Let's clarify the "physical" essence of properties (1), (2). Note that the expression pj(l) = 0 means that the j-th balance is at the initial position and the expression pj(l) = p means that this one is at the opposite position. The expression (2) reflects the process of the passage of the j-th balance from the opposite position to the initial position. According to (2) the state of the IE is decreased by 1 at the next step. Thus, if the j-th IE at the l-th step of the algorithm passes from the state pj(l - 1) = 0 to the state pj(l) = p, then its states at the next steps of the measurement algorithm are decreased successively according to the rule:

pj(l + 1)=p - 1;
pj(l + 2)=p - 2;
pj(l + p - 1)=1;
pj(l + p)=0.

Note that the expression pj(l) = 0 means that the j-th IE at the l-th step of the algorithm may be applied to the points of the "indeterminacy interval".

After such preliminary remarks let's try to synthesize the optimal (n, k, S)-algorithm. Before the l-th step we will renumber all the "Indicator Elements" so that we arrange them according to the rule:

pk(l) ³ pk-1(l) ³ pk-2(l) ³ ... ³ p2(l) ³ p1(l),(3)

where pj(l) is the state of the j-th IE at the l-th step (j = 1, 2, 3, ..., k; l = 1, 2, 3, ...).

We denote the IE-states at the first step of the (n, k, S)-algorithm by p1, p2, p3, ..., pk. The initial IE-states are arranged in accordance with (3), i.e.

pk ³ pk-1 ³ pk-2 ³ ... ³ p2 ³ p1.(4)

Let's mark now the "effectiveness" function of the optimal (n, k, S)-algorithm in

Fp(n, k) = Fp(n; p1, p2, p3, ..., pk).

Let's suppose that the initial IE-states p1, p2, p3, ..., pk are arranged according with (4) so that

p1 = p2 = p3 = ... = pt = 0.

However we see that our reader is tired with this very complicated mathematical reasoning and we give the final result for the "effectiveness" function:


We can see that for the given p the "effectiveness" function of the "optimal" algorithm is expressed with the highly complicated recurrent formula (5). However the partial cases of this recurrent formula gives a number of the "unexpected" results. These results are demonstrated in the following table.

And about what this table tells us? Thus the "unexpectedness" of the main result of the algorithmic measurement theory consists of the following. The general recurrent correlation (5), (6) gives, in general form, an infinite number of new, at present unknown optimal measurement algorithms. As this takes place all well-known classical measurement algorithms used in measurement practice (the "binary" algorithm, the "counting" algorithm) are partial cases of the general optimal measurement algorithms. The basic recurrent correlation (5), (6) includes a number of well-known combinatorial formulas as special cases, in particular the formula (k + 1)n, the formula given the binomial coefficients, the Fibonacci recurrent formula and finally the formulas for binary (2n) and natural (n + 1) numbers.

Fibonacci's mathematicians suggested many interesting generalizations of the Fibonacci recurrent correlation. It is clear that the basic recurrent correlation of the algorithmic measurement theory may be considered as a very wide generalization of Fibonacci's recurrent correlation. And such an approach is interesting for extension of "Fibonacci" investigations.

The next methodological conclusion consists of the following: the algorithmic measurement theory is the source of new ideas in the development of the positional number system theory. This idea can bring into development of the new number systems and new computer arithmetic, that is of great interest for modern computer science. One of them is p-Fibonacci codes. And we will tell about p-Fibonacci codes at the next page of our Museum. Follow us!