To the question of numbers

“Well, without a fight? Volleyball is so volleyball! "
Well, USB - so USB

It’s not in my rules to pamper the KDPV reader, but could not resist.

But we will begin, as promised, with the time service at MK. Consider the problem associated with this service - there is a set of numbers and among them it is worth highlighting those that do not exceed some other predetermined number. And moving on to time, we can say that we will need to determine the moment when our current time (T) becomes an interval (I) larger than the origin of the interval (C).

How can we solve this problem, and what does Ouroboros have to do with it?

To begin with, we must be able to get the number T that characterizes the current moment in time (it would be nice to understand how it relates to time, although this is not necessary, to start working it is enough to know the size of the number and the behavior of this number with increasing time - it increases or decreases ) Next, we must be able to remember the current T in some variable C (for which it is required that they be of the same type - that’s why we need to know the size). Next, we must be able to associate the desired interval with a certain number of And (and here we need knowledge of the exact behavior of the number T) and we can carry out a simple comparison operation by performing it in the form

T = C + I

- as soon as this equality is fulfilled, we have reached We need a moment in time.

Everything would be fine, but there is a slippage problem - time flows regardless of our behavior, the T variable changes at the same time, and if for some reason we do not perform the comparison at the time of equality, the condition will be lost and we will never know what we need the time has come for us (in fact, in the real world we will find out, but more on that later). Therefore, the hard condition = should be replaced by the soft> =, or <=, if the variable T decreases with time and we get the condition T> = C + I, which is already much more difficult to miss (if at all possible) and everything turns out just fine, it’s not clear, how the rest of the post will be filled.

In fact, this solution has pitfalls, but they are pitfalls so that they are not immediately noticed. Consider one of them, which so many times has already struck careless sailors, which you won’t count. And this stone is called limited bit depth or overflow.

The problem arises due to the fact that time is infinite, and the digit capacity of numbers in the MK is limited and we basically cannot pull an uncountable set onto a countable one, this is an axiom. Therefore, our number T, no matter what size it is, cannot uniquely determine a certain point in time, but will have a period. The duration of this period will be the maximum number, decreasing in T + 1, multiplied by the time T increases by unity Pr = (Max + 1) * To. For example, if T increases by 1 every microsecond, and the width of T is 32 bits, then the period will be (2 ^ 32) * 1е-6 = 4 * (2 ^ 10) ^ 3 * 1е-6 ~ 4 * 10 ^ 3 ^ 3 * 1e-6 = 4 * 10 ^ (9-6) = 4000 seconds, which is a little over an hour. If T increases by 1 every millisecond, then the period will increase a thousand times and amount to 4e6 seconds, that is, approximately 46 days. Of course,

And what happens when our number reaches its maximum value - different options are possible: it can “lie down” and continue to remain unchanged (but then we lose the ability to fix the continuation of the flow of time), it can begin to decrease (simulating the work of the pendulum, but here computational complexity) and can take a minimum value, usually it is zero (the latter phenomenon is called overflow).

How can you increase the time interval after which this phenomenon will occur - you need to increase any of the factors, but increasing the first will complicate operations with the number T, and increasing the second will make it impossible to work at intervals less than the minimum step, which is not always acceptable. Therefore, the choice of step and bit depth is always a compromise, which allows not to overestimate the requirements for MK and not to reduce the convenience of work.

There is another way to extend the period - to make the relationship between time and the number T non-linear, a power function with an exponent less than unity or a logarithm (piecewise-linear approximation of it) is best (and quite easily implemented on MK), but this option is more theoretical interest rather than a real solution, since the increment step and, accordingly, the accuracy increase with time, and this is unacceptable to us.

So what threatens us with the periodicity of the values ​​of T and the overflow associated with it (wraparound, recount, reroll, warp) - by the fact that the monotonicity of the behavior of T is violated, that is, some next moment in time can be represented by a number not greater than the previous one (if we have T grows with time), and smaller and, accordingly, our formula will stop working, and the manifestations of this will be very unpleasant - the program will form a time interval significantly smaller than expected.

Here is a drawing that you should keep in mind to understand what is happening.



Consider an example of this, for brevity, we assume that T is placed in a byte and its maximum value will be 255. If the initial time for the formation of the interval C = 20, and the interval I = 08, then according to our formula, time will elapse, starting from the moment 28 which is correct, but in the case of C = 250, already at T = 251, the condition 251> = (250 + 8) = 258 - 256 = 2 will be fulfilled, which clearly does not meet our expectations. This will not happen too often, near the end of the period, and if you are absolutely sure that your device will never work so much time, you can neglect this feature and use the formula proposed earlier to track time intervals, which many library authors do. I am categorically against such a practice for two reasons - firstly,

To obtain the correct (true in any case) formula, we must subject the original T> = C + And to a simple transformation and subtract C from both sides, getting a new condition T - C> = I. From the point of view of mathematics, these conditions are equivalent, but mathematics works with ideal numbers that have infinite width, although it is not at all helpless and in the case of bounded numbers, you just need to impose the appropriate conditions. So, given these conditions, our new formula always works correctly. Of course, it is true in the case when T is greater than C, but it also works when T is less than C and this happens due to the remarkable property of subtraction. We represent T in the form

T = C + D, where D is the additive with respect to the start, and even if we could get an overflow even in the process of adding, then the value T = C + D is Max <C, in any case, our formula turns into

(C + D ) - C = C - C + D = D,

that is, we get the time interval we are looking for (or rather, the number that characterizes it) for any C and T. Why it turns out this way is ordinary street magic, that is, a transition from an absolute coordinate system relative with beginning at point C.

The computational complexity of the original formula has one addition and one comparison, the modified one is one subtraction and one comparison, that is, they are not different (addition, subtraction and comparison have the same complexity), so why not use the correct one, since it costs nothing. The only limitation of this method should be noted - we cannot order an interval equal to or greater than the maximum representable, that is, we can order, but we get an interval much smaller, and this is very bad, although obvious. And another, less obvious limitation - if we order an interval close to the maximum possible, then there will be very few control points at which the condition is satisfied, and if we skip them, we will go to the second round, and so on. But even in this case, we are guaranteed that we will receive at least what we ordered,

So, we have created an absolutely correct method for counting time intervals, which works in all possible situations (of course, taking into account the indicated restrictions), but, as you know, there is no limit to perfection. Let's take a closer look at the resources involved in this method - we need to remember two variables and we need to perform two operations such as addition. To reduce resource requirements, you need to return to the original formula

T> = C + I

and pay attention to the fact that both values ​​on the right side are known at the time the interval begins to form and you can calculate the end time of the delay

P = C + I,

and the formula turns in the expression

T> = P.

Unfortunately, its main drawback - false operation during overflow, remains valid, but we can go the tried way and use the subtraction Т - П> = 0.

Unfortunately, ordinary street magic let us down (the fakir was drunk and the focus failed), since this condition is always fulfilled, since the difference of any two numbers is a number from 0 to Max and is always not less than zero. Actually, the result is predictable, since for two arbitrary numbers it is completely impossible to determine which one precedes the other, from the word "completely" impossible.

Let’s try to create an additional criterion and assume that T precedes P if (T - P) <(P - T). Not bad for a start, but a direct calculation using this formula will require three subtractions - we will reduce it. First of all, we establish the indisputable fact that (T - P) + (P - T) = 0 = Max + 1.

From this obvious fact, we can deduce that T - P will be more than P - T in that and only that if - ->> = (Max + 1) / 2. Since the second expression is obviously constant and will be calculated at the compilation stage, the resulting condition П - Т> = (Max + 1) / 2 requires only two subtraction operations, and we have already reduced the memory by one storage unit, but we can go further.

Note that to fulfill the last condition, it is necessary that the most significant bit of the result be set, and we could use the conditional jump commands according to the value of the result bit, but they are not in every MK and the translator can use them insufficiently. Fortunately, just to work with the most significant bit, any MK has such commands and any translator implements them very well - commands for checking the sign of a number. The fact is that if we consider the result as a number in an additional code, then the sign is encoded in the high bit and checking that the most significant bit of the number contains one and that the number is negative, match. Therefore, our comparison condition can be written as T - P <0.

We draw attention to the fact that we carry out the subtraction operation with unsigned numbers and only interpret the result as a signed number during the comparison operation. This circumstance should be taken into account when writing program code that implements this algorithm, for example, for language C, the corresponding fragment can be performed as follows:

if ( (long) (Т - П) < 0) ....

So, we need to remember only one number (P) and the computational complexity of the check is one subtraction operation (the comparison will use its result and will not require additional operations), it is hardly possible to achieve better indicators. What we had to pay for such beauty - now we can’t order an interval of more than half of the maximum possible number, or rather, we can order it, but it will stop instantly, so it’s up to you to decide whether to win this restriction. On Linux systems, the latter option was adopted, and the fact that the details are hidden behind the macro is syntactic sugar.

Well, and in conclusion, a little to the side - I recently discovered (actually long ago, I just forgot it) that the behavior of the C language compiler (at least some of them) I personally can’t call logical. For example, the following code fragment does not behave at all as I would like:

typedef unsigned char Timet;
Timet S = 0xF8, I = 12, T = S + I + 2;
// прости, MISRA, за предыдущую строку, я знаю, что так нельзя, но это в учебных целях
if ( (T - S) >= I) printf ( "time"); // не всегда срабатывает
register Timet D = (T - S);
if (D >= I) printf ("time"); // а вот это всегда
It is completely incomprehensible to me why in this form I see only one message about the expiration of time, and if I change the type of Timet to unsigned long, I get two messages. That is, of course, I am disingenuous, I understand why this happens, I do not understand why such a decision was made when implementing the compiler. But, by the way, this problem is practically solved very easily - turn on MISRA support (rule 10.1.b) and get a ban on the use of an unsuccessful string and we will have to do everything correctly, that is, reliably, we will simply be forced to write an intermediate assignment. Moreover, this assignment does not cost anything and a good compiler will make very efficient code. Yes, this is a crutch, “but it works,” unfortunately, there is simply no other solution.

I must say that the following code fragment looks even funnier

if ( (c = uc ) == uc) printf ( "is equal");

during the execution of which you will not receive, quite justifiably, the expected message of equality for some values ​​of the uc variable, and we will not receive “what is most terrible, no warning bicycle ”. And I do not need to say that these two bytes are not equal - they are equal and this is the whole horror of the situation.