\myheading{Binary logarithm} Sometimes denoted as lb(), binary logarithms are prominent in computer science, because numbers are usually stored and processed in computer in binary form. \leveldown{} \myheading{Weights} An interesting problem I've found in the Simon Singh --- Fermat's Last Theorem (1997) book: \begin{framed} \begin{quotation} The \textit{Arithmetica} which inspired Fermat was a Latin translation made by Claude Gaspar Bachet de Méziriac, reputedly the most learned man in all of France. As well as being a brilliant linguist, poet and classics scholar, Bachet had a passion for mathematical puzzles. His first publication was a compilation of puzzles entitled \textit{Problemes plaisans et délectables qui se font par les nombres}, which included river-crossing problems, a liquid-pouring problem and several think-of-a-number tricks. One of the questions posed was a problem about weights: \begin{framed} \begin{quotation} What is the least number of weights that can be used on a set of scales to weigh any whole number of kilograms from 1 to 40 \end{quotation} \end{framed} Bachet had a cunning solution which shows that it is possible to achieve this task with only four weights...\\ \\ ...\\ \\ In order to weigh any whole number of kilograms from 1 to 40 most people will suggest that six weights are required: 1, 2, 4, 8, 16, 32 kg. In this way, all the weights can easily be achieved by placing the following combinations in one pan:\\ \\ 1 kg = 1,\\ 2 kg = 2,\\ 3 kg = 2 + 1,\\ 4 kg = 4,\\ 5 kg = 4 + 1,\\ ...\\ 40 kg = 32 + 8.\\ \\ However, by placing weights in both pans, such that weights are also allowed to sit alongside the object being weighed, Bachet could complete the task with only four weights: 1, 3, 9, 27 kg. A weight placed in the same pan as the object being weighed effectively assumes a negative value. Thus, the weights can be achieved as follows:\\ \\ 1 kg = 1,\\ 2 kg = 3 - 1,\\ 3 kg = 3,\\ 4 kg = 3 + 1,\\ 5 kg = 9 - 3 - 1,\\ ...\\ 40 kg = 27 + 9 + 3 + 1.\\ \end{quotation} \end{framed} We'll talk here only about the first part of the solution: 1/2/4/8/etc kg. weights. Indeed, any weight can be achieved using only a combination of weights in $2^n$ form. Say, 11 kg is: \begin{itemize} \item 1 kg weight = 1 (on) \item 2 kg weight = 1 (on) \item 4 kg weight = 0 (off) \item 8 kg weight = 1 (on) \end{itemize} It's like a number encoded in binary form. How many weights you would need to weight an $n$ kg? It's $\left \lceil log_2 n \right \rceil$. And $\left \lceil log_2 40 \right \rceil = 6$. As of the second part of the problem, \SSBE has an example about it. \myheading{A burned LED garland} \begin{figure}[H] \centering \includegraphics[scale=2]{log/led_garland.png} \caption{A burned LED garland} \end{figure} It doesn't work: LED D7 has been burned, but yet, you don't know, which. You have an ohmmeter to find it. You can check them all, but there 8 of them. Or, you can divide that chain by two and try the left pin of D1 and the right pin of D4. Working? If yes, try the left pin of D4 and the right pin of D8. It doesn't. No you have a failed chain of 4 LEDs, you know that the right half of chain is failing, but the left is OK. You divide that chain by two and repeat the process. Approximately, a number of all measurements is a binary logarithm of number of LEDs. At best (by luck, you always hit failed part of chain), a number of all measurements is binary logarithm of number of LEDs (8) minus 1, and that is 3. At worst (being unlucky, you always hit working part of chain then you switch to failed part), is the same number, doubled, that is 6. \myheading{Browing a telephone book} Another example: \begin{framed} \begin{quotation} In daily life a telephone book can be used as a one-way function; given a name one can easily find the corresponding telephone number but not the other way around. Looking up a telephone number of a person amounts to finding the name of that person. This takes $log_2$ L operations, if L is the number of names in the telephone guide. Finding the name if the telephone number is given means going through the whole book, name after name. The complexity is L. Property F2 is based on the exponential relation between $log_2$ L and L. \end{quotation} \end{framed} ( Henk C.A. van Tilborg -- FUNDAMENTALS OF CRYPTOLOGY ) % https://eeisti.fr/grug/Arel/ATrier/Signal%20%26amp%3B%20Information%20%20Application/7-Cryptography4.pdf \myheading{Denoting a number of bits for some value} How many bits we need to allocate to store googol number ($10^{100}$)? \begin{lstlisting}[caption=Wolfram Mathematica] In[]:= Log2[10^100] // N Out[]= 332.193 \end{lstlisting} Binary logarithm of some number is the number of how many bits needs to be allocated. If you have a variable which always has $2^x$ form, it's a good idea to store a binary logarithmic representation ($\log_2 (x)$) instead of it. There are at least two reasons: 1) the programmer shows to everyone that the number has always $2^x$ form; 2) it's error-prone, it's not possible to accidentally store a number in some other form to this variable, so this is some kind of protection; 3) logarithmic representation is more compact. There is, however, performance issue: the number must be converted back, but this is just one shifting operation (\texttt{1<canOverflow() && (constant > 0)) { // If it cannot overflow, we can do lots of optimizations. uint32_t rest = constant - (1 << shift); // See if the constant has one bit set, meaning it can be // encoded as a bitshift. if ((1 << shift) == constant) { masm.ma_sll(dest, src, Imm32(shift)); return true; } ... \end{lstlisting} Thus, for example, $x=y \cdot 1024$ (which is the same as $x=y \cdot 2^{10}$) translates into $x=y<<10$. \myheading{Calculating binary logarithm} If all you need is integer result of binary logarithm ($abs(\log_2(x))$ or $\lfloor \log_2(x) \rfloor$), calculating is just counting all binary digits in the number minus 1. In practice, this is the task of calculating leading zeroes. Here is example from Mozilla libraries ( \texttt{mfbt/MathAlgorithms.h} \footnote{\url{http://fossies.org/linux/seamonkey/mozilla/mfbt/MathAlgorithms.h}} ): \begin{lstlisting}[caption=Mozilla libraries,style=customc] class FloorLog2 { public: static uint_fast8_t compute(const T aValue) { return 31u - CountLeadingZeroes32(aValue | 1); } }; inline uint_fast8_t CountLeadingZeroes32(uint32_t aValue) { return __builtin_clz(aValue); } \end{lstlisting} Latest x86 CPUs has LZCNT (Leading Zeroes CouNT) instruction for that \footnote{GNU \texttt{\_\_builtin\_clz()} function on x86 architecture can be thunk for LZCNT}, but there is also BSR (Bit Scan Reverse) instruction appeared in 80386, which can be used for the same purpose. More information about this instruction on various architectures: \url{https://en.wikipedia.org/wiki/Find_first_set}. There are also quite esoteric methods to count leading zeroes without this specialized instruction: \url{http://yurichev.com/blog/de_bruijn/}. \myheading{O(log n) time complexity} Time complexity\footnote{\url{https://en.wikipedia.org/wiki/Time_complexity}} is a measure of speed of a specific algorithm in relation to the size of input data. O(1) -- time is always constant, to matter what size of input data. Simplest example is object getter -- it just returns some value. O(n) -- time is linear, growing according to the size of input data. Simplest example is search for some value in the input array. The larger array, the slowest search. O(log n) -- time is logarithmic to the input data. Let's see how this can be. Let's recall child's number guessing game\footnote{\url{http://rosettacode.org/wiki/Guess_the_number}}. One player think about some number, the other should guess it, offering various versions. First player answers, is guessed number is larger or less. A typical dialogue: \begin{lstlisting} -- I think of a number in 1..100 range. -- Is it 50? -- My number is larger. -- 75? -- It is lesser. -- 63? -- Larger. -- 69? -- Larger. -- 72? -- Lesser. -- 71? -- Correct. \end{lstlisting} Best possible strategy is to divide the range in halves. The range is shorten at each step by half. At the very end, the range has length of 1, and this is correct answer. Maximal number of steps using the strategy described here are $\log_2(initial\_range)$. In our example, initial range is 100, so the maximum number of steps is 6.64... or just 7. If the initial range is 200, maximum number of steps are $\log_2(200)=7.6..$ or just 8. The number of steps increasing by 1 when the range is doubled. Indeed, doubled range indicates that the guesser needs just one more step at the start, not more. If the initial range is 1000, numbers of steps are $\log_2(1000)=9.96...$ or just 10. This is exactly O(log n) time complexity. Now let's consider couple of practical real-world algorithms. One interesting thing is that if the input array is sorted, and its size is known, and we need to find some value in it, the algorithm works exactly in the same way as child's number guessing game! The algorithm starts in the middle of array and compare the value there with the value sought-after. Depending on the result (larger or lesser), the \textit{cursor} is moved left or right and operating range is decreasing by half. This is called binary search\footnote{\url{https://en.wikipedia.org/wiki/Binary_search_algorithm}}, and there is the \texttt{bsearch()} function in standard C/C++ library\footnote{\url{http://en.cppreference.com/w/cpp/algorithm/bsearch}}.\\ \\ Here is how binary search is used in git: \url{https://www.kernel.org/pub/software/scm/git/docs/git-bisect.html}.\\ \\ Another prominent example in CS is binary trees. They are heavily used internally in almost any programming language, when you use set, map, dictionary, etc. Here is a simple example with the following numbers (or keys) inserted into binary tree: 0, 1, 2, 3, 5, 6, 9, 10, 11, 12, 20, 99, 100, 101, 107, 1001, 1010. \input{log/binary_tree_tikz} And here is how binary tree search works: put \textit{cursor} at the root. Now compare the value under it with the value sought-after. If the value we are seeking for is lesser than the current, take a move into left node. If it's bigger, move to the right node. Hence, each left descendant node has value lesser than in ascendant node. Each right node has value which is bigger. The tree must be rebalanced after each modification (I gave examples of it in my book about reverse engineering (\url{http://beginners.re/}, 51.4.4)). Nevertheless, lookup function is very simple, and maximal number of steps is $\log_n(number\_of\_nodes)$. We've got 17 elements in the tree at the picture, $\log_2(17)=4.08...$, indeed, there are 5 tiers in the tree. \levelup{}