Disputes periodically arising in thematic forums about whether a programmer needs mathematics have long become a common place and area of ββholy wars. Being on our (right) side of the border separating good from evil, I want to share one example that clearly demonstrates how much it is needed and even (we will not be afraid of this word) is necessary.
Consider an interesting programming problem, which has a somewhat olympiad character.
Pnp: From this point forward, supporters of the idea that programming today consists of beautifully designed web pages can stop reading, you are absolutely right, you donβt need math ...
Well, you donβt need to insist on that, you are no worse than us, and your work is really important, because I already agreed that we have different ideas about programming ...
Yes, you are absolutely right that these olympiads will not be able, with the help of the last framework, to draw seven red perpendicular lines in one line of code ...
Nevertheless, I consider it to be my idea that is correct (this is a fatal property of highly organized matter in the form of protein bodies), therefore I will state the arguments in its support.
I formulate the problem - how many different numbers of length K ending in a given p button can be typed on the telephone keypad (keyboard) if we need to move around the buttons with a chess knight. It is understood that you saw the keyboard (I still have a regular mobile phone, not a smartphone, so I see it every day, a more advanced reader should contact Internet for help) and you know how a chess horse walks (easy to google). mathematics has nothing to do with it so far, if you do not have in mind the ability to calculate options.
The first solution is quite obvious - we take all 10 buttons one after another (we denote their number by n for generality), consider all possible numbers of long K from it and count those that end on the desired button. The resulting numbers are summarized and the answer is ready. The total number of viewed options is approximately expressed as n * B (K), where B (K) is the number of possible moves of length K. In fact, you need to consider the sum of n positions, since B (p, K) obviously depends on the number of the button but as a first estimate come down.
Before proceeding to search B, one can significantly reduce the number of options by applying (no, not yet mathematics) common sense. Since the movement of the buttons on depends on the background, we can reverse the task and search for all numbers of length K starting from the desired button p. Then the total number of options will be B (p, K), which is n times less. Wow, we just found a way to speed up the search for a solution 10 times - cool, let's see how much is left.
We need to evaluate B (p, K), for which we determine that at each move we have from 2 to 3 scenarios. It follows (in general, this is combinatorics, but intuitively) that the total number of options will be from 2 ** K to 3 ** K (hereinafter I use K-1 as K). We can even improve this estimate by moving to a probabilistic model. Considering the presence of a finger in each button at the moment is equally probable (a strong statement, most likely incorrect, but acceptable with rough estimates), we can calculate the average number of move options 7 * 2 + 2 (buttons 4 and 6) * 3 = 20/9 ~ 2.22 . Then the estimate will be 2.22 ** K, and we know for sure that we have at least 2 ** K. Then for K = 100 we get a lower bound 2 ** 100 = (2 ** 10) ** 10> (10 ** 3) ** 10 = 10 ** 30.
If we consider one option in a nanosecond (and this is not easy even on a powerful desktop PC), then we need 10 ** 30/10 ** 9 = 10 ** 21 seconds. Further, we recall the wonderful mnononic "Ο seconds are equal to a century" and the required time will be 10 ** 21 / 3.14 * 10 ** 9 ~ 3 * 10 ** 11 centuries. It seems to me that few readers will live to see the end of the calculations using the proposed methodology. An exhibitor is terrible, only factorial is worse than her.
We will improve the solution based on the fact that we are interested in the number of options, but not the options themselves. You can offer the obvious formula B (p, K) = the sum of B (p ', K-1) for all p' in which we get in 1 move from p. We start from the final button and assign it a weight of 1, then carry out the procedure of summing the current weights to the next, repeat to the desired depth.
We illustrate what was said with an example, starting with the number 1 {1234567890}:
initial weight {1000000000},
after the first transfer {0000010100} (2 options),
after the second transfer {2010001001} (5 options),
after the third {0102040300} (10 options) and so on.
The algorithm is simple, it can be implemented even with your hands. The general estimate of the execution time is K iterations, at each of which for n weights we modify no more than n related weights, total n ** 2 * K. For the previously considered case 10 * 10 * 100 = 10 ** 4 - quite a bit.
It remains only to evaluate the duration of each operation - this is addition (garbage question), but not simple addition (from this place in more detail). We have already set the lower limit of the response to 2 ** K, that is, we definitely need at least K bits to represent the result. The upper limit is 3 ** K, for our case 3 ** 100 = (3 ** 5) ** 20 <(2 ** 8) * 20 = 2 ** 160, that is, we are guaranteed to fit into 160 bits. We can assume that 128 bits are enough for us, since 2.2 ** 100 <2 ** 128, but accepting such a statement on faith is scary, so we need a number with at least 160 bits or 49 decimal digits, depending on your number library high accuracy.
PNP: Do not offer a floating point, we need a completely accurate result.
In the accepted assumptions, the addition operation will occupy 160/8 = 20 bytes / 4 = 5 additions of integers 32 bits long, which in no way affects the time order (it remains linear in K), but can significantly increase the real calculation time (by several times).
In any case, the result is simply excellent - we turned the task from fundamentally unsolvable in a reasonable time to completely solvable: if one elementary addition operation is performed in a microsecond (and this is easy to ensure even on the Arduino board), then the total time will not exceed 10 ** 4 * 20 / 10 ** 6, less than a second) and we did without any math.
Nevertheless, and if we need Larger K - of course, the linear order of calculations - this is wonderful, but it can (and will) lead to significant time losses for large values. It turns out that you can significantly improve the expected time, watch your hands.
What we do at each step of the calculation (pseudo-code):
= 0; 1 2 * ( 1 2) * 1 2. =
2 ( 1 * )
0 1, . '=* =(...((*)*)...). , =***. , . **3, ***3 β , ? , β¦
β , **3 , , , ( ) ( ), . , 100 99 8. , 2*log2(), ( =100 1000/10=100 ) , 2*log2()***3. , , , . , , log2(K), , , 100.
- ( , ), , , .