Quick logarithm calculation

Question

In coming up with an algorithm for finding $\log (10)$ base $2$, these are my thoughts. I wanted to know if this makes sense and how could I truly make it more efficient. The requirements are strictly not using any kind of tables.

Suppose I want to find $\log (11)$ base $2$.

• Step1: Calculate the next highest power of $2$ from $11$ - answer $16$ and next lowest power of $2$ - answer $8$

• Step2: Calculate the index of this power - answer $4$ ($2^4$) and $2^3$ ($8$)

• Step3: Logarithm must be between $3$ and $4$.

• Step4: Set low = $3$, high = $4$

• Step5: Keep bisecting the interval till $2^x = 11$, everytime is $2^x > 11$ reset high or if $2^x<11$ reset low.

Where do you think this will overflow?

Answer 1

What you are proposing is essentially a "binary search" based on the Intermediate Value Theorem. You are looking for the solution to the equation $\log_2 11 - x = 0$, or what is equivalent, $2^x - 11 = 0$. Since exponential and logarithmic functions are continuous for all real numbers, it is safe to apply this Theorem. You know that $2^3 - 11 < 0$ and $2^4 - 11 > 0$ , so the Theorem tells us that there must be a value of $x$ between 3 and 4 .

So your approach of dividing the interval in half each time and discarding the interval for which the sign of $2^x - 11$ does not change is reasonable. You would continue this procedure until you reach the level of precision (number of decimal places) that you desire. The method is pretty efficient: you will gain another decimal place every two to three cycles. (In five or six passes, I already reached an estimate of $\log_2 11 \approx 3.46$ to two decimal places. The calculator value is 3.459431619...)

Answer 2

I have decided to add an answer in response to my comments above. There is an efficient algorithm, which is described here. I will outline the algorithm below in MATLAB format.

function y = mylog (x,tol)
    % calculate log(x) in base 2 to tolerance tol

    y = 0; % initialise output
    b = 0.5; % initialise mantissa

    % arrange the input into a known range
    while x < 1
        x = x*2;
        y = y - 1;
        % move one bit to the left
    end
    while x >= 2
        x = x/2;
        y = y + 1;
        % move one bit to the right
    end
    % x is now in the range 1<=x<2

    % loop until desired tolerance met
    while b > tol
        x = x*x;

        % update the index
        if x >= 2
            x = x/2;
            y = y + b;
        end

        % scale for the next bit
        b = b/2;
    end
end