Talk:Binary logarithm

[Untitled]

Where did the algorithm given here come from? I would love to find an original reference for this. Kleg 22:45, 19 July 2006 (UTC)

Same here. I can sort of guess why it works (squaring the scaled input value corresponds to doubling the result), but I would love to see the actual maths behind it.

Math for the result is located at this url: http://en.literateprograms.org/Logarithm_Function_%28Python%29

$2^{n}$ not a function! A function has a domain, a range, and a graph!

lg?

Where does the name lg come from? --Abdull (talk) 20:15, 24 July 2008 (UTC)

I also wonder. In all my books lb x is used.--MathFacts (talk) 20:26, 16 August 2009 (UTC)

lg = log₁₀. the correct symbol for binary logarithm is lb = log₂ — Preceding unsigned comment added by 140.180.255.232 (talk) 19:47, 24 August 2016 (UTC)

For values of correct meaning "recommended by a standards organization" rather than what people actually use, maybe. —David Eppstein (talk) 21:06, 24 August 2016 (UTC)

Error in identity?

Isn't there an error in the identity given for integers?

It says:

$\lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n>>1)\rceil +1,{\mbox{where }}n\geq 1.$

But surely it should be:

$\lfloor \log _{2}(n)\rfloor =\lceil \log _{2}((n>>1)+1)\rceil ,{\mbox{where }}n\geq 1.$

? —Preceding unsigned comment added by 195.27.20.35 (talk) 12:05, 26 February 2010 (UTC)

python example

Python example is clearly too complex and too long. 1exec1 (talk) 17:53, 24 April 2010 (UTC)

Then refer to the OLD python code, it is much simpler

#!/usr/bin/python

from __future__ import division

def log2(X):
  epsilon = 1.0/(10**12)
  integer_value=0
  while X < 1:
    integer_value = integer_value - 1
    X = X * 2
  while X >= 2:
    integer_value = integer_value + 1
    X = X / 2
  decfrac = 0.0
  partial = 0.5
  X=X*X
  while partial > epsilon:
    if X >= 2:
      decfrac = decfrac + partial
      X = X / 2
    partial = partial / 2
    X=X*X
  return (integer_value + decfrac)

if __name__ == '__main__':
  value = 4.5
  print "     X  =",value
  print "LOG2(X) =",log2(value)

# Sample output
#
#    $ python log2.py 
#         X  = 4.5
#    LOG2(X) = 2.16992500144
#

C example

wouldn't it be nicer code to use

while(n>>=1!=0)
  ++pos;

instead of

if (n >= 1<<16) { n >>= 16; pos += 16; }
if (n >= 1<< 8) { n >>=  8; pos +=  8; }
if (n >= 1<< 4) { n >>=  4; pos +=  4; }
if (n >= 1<< 2) { n >>=  2; pos +=  2; }
if (n >= 1<< 1) {           pos +=  1; }

? -- 129.247.247.239 (talk) 11:53, 16 July 2010 (UTC)

Yes, I agree. The point of an article like this is to explain how a binary logarithm works, not to show some super-optimized and confusing C version. On the other hand, no one really writes anything in C anymore, unless it needs to run really fast... Moxfyre (ǝɹʎℲxoɯ | contrib) 15:28, 16 July 2010 (UTC)

Below is an in‑depth discussion of your decision to avoid using `__builtin_clz()` and how your loop-based approach fits into that design:

---

1. 1. 1. 1. What Your Code Does

Your snippet:

while (n >>= 1)

++pos;

accomplishes the task of calculating the integer (floor) binary logarithm of `n`. On each iteration, it right‑shifts `n` by one bit (which is equivalent to dividing by 2) and increments `pos`. When `n` eventually becomes 0, the loop terminates, and `pos` holds the number of shifts made—that is, essentially the position (or bit length minus one) of the most significant bit set in the original number.

• • Key Points:**

- **Simplicity and Portability:**

This approach is both simple and portable. It uses standard C operators and doesn’t rely on compiler-specific built‑ins.

- **Limited Iterations:**

For a 32‑bit number, the loop iterates at most 32 times (or 64 times for a 64‑bit number). In many applications, this fixed upper bound isn’t performance‑limiting.

- **Edge Cases:**

Be mindful that if `n` starts at 0 (or isn’t strictly positive), you may want to handle such cases separately since the logarithm of zero is undefined.

---

1. 1. 1. 2. Why Avoid `__builtin_clz()`

There are several reasons one might decide to avoid using compiler intrinsics like `__builtin_clz()`:

- **Portability:**

Intrinsics such as `__builtin_clz()` are GCC/Clang–specific. If your code must compile with different compilers or in environments where such built‑ins aren’t available, a pure C solution is preferable.

- **Platform Specificity:**

Although many modern CPUs implement count‑leading‑zeros (CLZ) instructions—which can make `__builtin_clz()` extremely efficient—not every target architecture has this luxury. Writing your own loop avoids assuming the existence of such an instruction.

- **Control and Clarity:**

A loop like the one in your code clearly shows the algorithmic intent. In some cases, this level of explicit control is desired over a “magic” function call that happens to be built into the compiler.

---

1. 1. 1. 3. Alternative Approaches Without `__builtin_clz()`

If you prefer to avoid compiler intrinsics but still want faster solutions than a simple loop, here are a couple of alternative ideas:

1. 1. 1. 1. a. De Bruijn Sequence Method

A well‑known trick uses a de Bruijn sequence to perform a branch‑free determination of the highest set bit index. For a 32‑bit unsigned integer, an implementation might look like this:

unsigned int log2_debruijn(uint32_t v)

{

static const int MultiplyDeBruijnBitPosition[32] = {

0, 1, 28, 2, 29, 14, 24, 3,

30, 22, 20, 15, 25, 17, 4, 8,

31, 27, 13, 23, 21, 19, 16, 7,

26, 12, 18, 6, 11, 5, 10, 9

};

// First, "fill" all bits below the highest set bit.

v |= v >> 1;

v |= v >> 2;

v |= v >> 4;

v |= v >> 8;

v |= v >> 16;

// Multiply by the De Bruijn sequence and use the upper 5 bits for the lookup.

return MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x077CB531U) >> 27];

}

• • Benefits:**

– This method computes the logarithm in a fixed number of operations without any loop branches.

– It is highly efficient on processors where multiplication is fast.

1. 1. 1. 1. b. Bit‑Binary Search

Another common alternative is to perform a binary search on the bits. For instance:

unsigned int log2_binary_search(uint32_t n)

{

unsigned int r = 0;

if (n >= 1 << 16) { n >>= 16; r += 16; }

if (n >= 1 << 8) { n >>= 8; r += 8; }

if (n >= 1 << 4) { n >>= 4; r += 4; }

if (n >= 1 << 2) { n >>= 2; r += 2; }

if (n >= 1 << 1) { r += 1; }

return r;

}

• • Benefits:**

– The number of comparisons is limited (often to 5 or 6 steps), making it efficient, especially when `n` is large.

– This method is still fully portable C code.

---

1. 1. 1. 4. Balancing Readability, Portability, and Performance

Your current implementation using:

while (n >>= 1)

++pos;

is very legible and works well for many applications, especially when:

- The input size is limited (32‑bit or 64‑bit integers).

- Execution speed is not critically dependent on this single calculation.

- You want to maintain portability without relying on non‑standard functions.

If you do encounter performance-critical sections where every cycle matters, consider benchmarking these alternatives (or even allowing the compiler’s intrinsic to be conditionally enabled on supported compilers). It’s not uncommon to see code that uses preprocessor directives to select the best available method for a given build environment.

Avoiding `__builtin_clz()` forces you to consider portable, explicit algorithms. Your loop-based approach is a solid, understandable solution. For performance-critical code, you might follow up with techniques like the de Bruijn sequence or a bit‑wise binary search. Each method has its trade‑offs in terms of speed, clarity, and portability.

Would you like to dive deeper into implementing one of these alternatives, or discuss how to benchmark these methods in a performance‑sensitive application? Dominic3203 (talk) 04:09, 16 April 2025 (UTC)

@129.247.247.239 Thank you so much! This is very useful for my research! Dominic3203 (talk) 10:28, 4 April 2025 (UTC)

the notation lb is used without an introduction

Under "Information Theory" the notation lb rather than ld is suddenly used without explanation. Is this a typo? If not, perhaps it should say something like: lg, lx, and lb are sometimes used for base 2 logs.

GA Review

This review is transcluded from Talk:Binary logarithm/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Jfhutson (talk · contribs) 21:31, 28 December 2015 (UTC)

This looks like it's probably already at GA standards. Here are my comments:

• lead formula: specify that x is the binary log of n.
• Starting with five examples seems excessive.
• italicize the Elements
• "On this basis, Michael Stifel has been credited with publishing the first known table of binary logarithms, in 1544." Last comma not needed.
• wikilink Jain
• rather than listing some logarithmic identities, why not say it obeys all logarithmic identities unless some are particularly relevant here.
• you really started to lose me with big O notation. Is there a way to make this more accessible?
• likewise with bioinformatics

That'll do for now. I don't know if any of that should hold up the GA. I'll take another look today or tomorrow. My main issue is where the article drifts into specialized subjects without explaining enough for a non-specialist.--JFH (talk) 21:31, 28 December 2015 (UTC)

• Several duplicate links. Check out this tool. Not really a GA issue though. --JFH (talk) 01:13, 29 December 2015 (UTC)
• Images: I'm pretty sure the calculator logo qualifies as de minimis, so no problems I can see.
• I'm going to go ahead and pass the article with the recommendation that my comments be addressed, but I don't think they rise to the level of GA. The prose is clear and concise even if some of the subject matter is difficult for a non-specialist. --JFH (talk) 14:03, 29 December 2015 (UTC)
  • Thanks! I'll definitely be revising this article to take your feedback into account. —David Eppstein (talk) 18:16, 29 December 2015 (UTC)

A special thanks

I don't know enough about Wikipedia to find out who wrote the "Iterative approximation" section, but to whoever did, thank you. Algorithms for calculating a logarithm are surprisingly hard to find, and that section was far and away the clearest and most helpful description I've found. I'm sure that I'm using the talk page wrong, so feel free to delete this section, but I just had to express my gratitude. Cormac596 (talk) 14:47, 1 June 2022 (UTC)

It appears to have been added as Python code by a not-logged-in editor in March 2006, and converted to roughly the current form by User:Moxfyre in September 2008. —David Eppstein (talk) 16:25, 1 June 2022 (UTC)

@Cormac596 Yep, that's right. I thought it was pretty cool, and I was learning/polishing my Python skills so I did a bit of cleanup 🤓. —Moxfyre (ǝɹʎℲxoɯ | contrib) 16:34, 1 June 2022 (UTC)

In that case, thank you Moxfyre. :) Cormac596 (talk) 20:49, 1 June 2022 (UTC)

A Commons file used on this page or its Wikidata item has been nominated for deletion

The following Wikimedia Commons file used on this page or its Wikidata item has been nominated for deletion:

• Binary logarithm plot with ticks.svg

Participate in the deletion discussion at the nomination page. —Community Tech bot (talk) 11:52, 23 August 2022 (UTC)

Calculator

My addition of a calculator in Special:Diff/1269904851 and subsequent adjustments by User:Eyesnore in Special:Diff/1270558458 were reverted as "clutter" by an IP editor in Special:Diff/1270570319. So now we're at the "D" stage of WP:BRD. Could we maybe have a broader discussion over whether this calculator is a helpful addition? —David Eppstein (talk) 06:53, 20 January 2025 (UTC)

I see no harm in including a calculator. If suitably placed, it's not clutter. Dondervogel 2 (talk) 09:15, 20 January 2025 (UTC)

I think the calculator is helpful and should be retained. I am not too thrilled by the output of "-infinity" for both 0.0 and -0.0, though, as this is only a one-sided limit. Better (and more consistent with the article) to be "(invalid input)" at 0 just like at -1. —Kusma (talk) 10:01, 20 January 2025 (UTC)

No I don't see that a calculator helps. To me it is clutter. —Quantling (talk | contribs) 16:50, 20 January 2025 (UTC)

It doesn't seem much more "clutter" than the graph is. I'm not sure I'd put it where it was (it kind of floats oddly across my screen from the table of contents), but I have no objection to including it somewhere. XOR'easter (talk) 00:20, 21 January 2025 (UTC)

Fast inverse square root

Below is a Wikipedia-style section focusing solely on how the logarithm is used to approximate the inverse square root:

---

1. 1. 1. Logarithmic Approximation

In the fast inverse square root algorithm, the floating-point number is first interpreted according to the IEEE 754 format, where any positive number can be expressed as   x = M · 2^E with M representing the mantissa and E the exponent. This means that the binary logarithm of x can be expressed as   log₂(x) = log₂(M) + E.

The algorithm exploits this property by reinterpreting the bitwise representation of x as an integer. Through a clever manipulation—specifically a right bit-shift which effectively divides the binary exponent by two—the method approximates:

  1/√x ≈ 2^(–0.5 · log₂(x)).

A magic constant is then subtracted from the shifted value to further calibrate the result, yielding a quick and efficient initial estimate. This bit-level trick is essentially a rapid computation of the logarithmic relationship that underpins the approximation.

---

This concise explanation isolates the role of the logarithm in generating the initial approximation in the fast inverse square root algorithm. Dominic3203 (talk) 10:43, 4 April 2025 (UTC)

There is no calculation of the logarithm within this algorithm; it is a trick involving the exponent of a floating point number, which is very much not the same thing as the binary logarithm of the number (because it is an integer and the logarithm generally is not). Additionally, any additions along these lines could only be made from published sources making the same arguments. Where are your sources? —David Eppstein (talk) 17:14, 4 April 2025 (UTC)

It's a little closer to the binary logarithm than that, but still not the binary logarithm. If you interpret the decimal point as being in the right place between the exponent and the mantissa, and adjust for the bias in the exponent, floating point representation is a piecewise-linear approximation to the binary logarithm. It is exactly the binary logarithm when applied to an integer power of two (modulo that decimal point and biased exponent), but is linearly interpolated when it falls between two adjacent integer powers of two. —Quantling (talk | contribs) 18:45, 4 April 2025 (UTC)

"We denote by ⁠$\iota (x)$⁠ an integer that has the same binary representation as an FP number ⁠$x$⁠ and by ⁠$\phi (i)$⁠ an FP number that has the same binary representation as an integer ⁠$i$⁠. The main idea behind FISR is as follows. If the FP number ⁠$x$⁠, given in the IEEE 754 standard, is represented as an integer ⁠$\iota (x)$⁠ , then it can be considered a coarse, biased, and scaled approximation of the binary logarithm ⁠$\log _{2}(x)$⁠...." doi:10.3390/computation9020021. –jacobolus (t) 01:33, 5 April 2025 (UTC)

@Jacobolus This is very useful!

Where can I apply this ref? Dominic3203 (talk) 05:18, 15 April 2025 (UTC)

A lot gets hidden in that word "coarse". If the "bias" (additive constant) and "scaling" (where to place the decimal point) are accounted for then floating point representation (with additional accounting for sign bit, NaN, infinities, and subnormal values) is still only a piecewise linear approximation of the binary logarithm. That's a lot to wrap up in the never-defined word "coarse". —Quantling (talk | contribs) 12:51, 15 April 2025 (UTC)

@Quantling Please state your suggestion. Dominic3203 (talk) 13:18, 15 April 2025 (UTC)

As a starting point, what do you think of?:

When the bit representation of a positive (not sub-normal) floating point number is interpreted as a positive integer then the latter can be related to the binary logarithm of the former. Specifically, the floating point value f has the same bit representation as the integer (p(f) + B)S where B is a bias, S is a scaling factor, and the function p(f) is a function that equals k whenever f = 2^k for some integer k and that is piecewise linear between these values. For example, this relationship can be exploited to compute a fast inverse square root.

Okay, maybe that could use some wordsmithing. Bigger picture, the idea is to actually describe the relationship rather than to give (possibly misleading) qualitative words that (only loosely) describe it. —Quantling (talk | contribs) 14:17, 15 April 2025 (UTC)

I think that is far too detailed and too technical to be readable. It would act like an indegestible blob sitting in the article. I think we need something much shorter and punchier, like

• The bit representation of a floating point number, reinterpreted as the bit representation of an integer, can be interpreted as a scaled approximation of the binary logarithm. The fast inverse square root algorithm applies this principle by dividing the approximated logarithm by two, rescaling, and reinterpreting the result as a floating point number again.

—David Eppstein (talk) 17:31, 15 April 2025 (UTC)

They add something to the exponent in the floating point representation, so I'd like to see "biased" in there, somewhere near "scaled" (which has to with the number of digits in the mantissa). Also, because it is an inverse square root, instead of "dividing by two" the approach is "dividing by −2" or "multiplying by −1/2". Please boldly edit if you think you've got something that could work. —Quantling (talk | contribs) 18:06, 15 April 2025 (UTC)

If adding magic constants to the exponent makes it into a binary logarithm, any logarithm is a binary logarithm. What exactly is binary about the logarithms here? —David Eppstein (talk) 18:18, 15 April 2025 (UTC)

Maybe:

• For a floating point number $x=2^{k}m$ with exponent $k$ and fixed-point mantissa $m$, the binary logarithm can be approximated by $\log _{2}x\approx k+{\tfrac {m-1}{\ln 2}}$. The fast inverse square root algorithm operates directly on the binary representation of $x$ to multiply this approximation by $-{\tfrac {1}{2}}$, converting $x$ to an approximation of $1/{\sqrt {x}}$.

That way we provide some general information about approximating the binary log without diving into the guts of the fast inverse square root algorithm. —David Eppstein (talk) 18:43, 15 April 2025 (UTC)

I'd say that it is the scale factor that mixes between logarithm bases rather than the additive bias. (I am referring back to the formula i(f) = (p(f) + B)S.) In this case, the scale factor is 2⁵² or something like that, for double-precision floating point, because that's how many bits of mantissa you have to shift over. That is, if we didn't allow the freedom of the scale factor then the floating-point bits minus the bias, interpreted as an integer, would be the logarithm with base ${\sqrt[{2^{52}}]{2}}$. The reason that this is more like a binary logarithm than some-other-base logarithm is that the scale factor is a nice integer power of two for the binary logarithm rather than some transcendental number for other common logarithms. —Quantling (talk | contribs) 20:40, 15 April 2025 (UTC)

For what it is worth, my p(f) function is p(f) = ⌊log₂ f⌋ + (f - 2^{⌊log₂ f⌋}) / (2^{⌊log₂ f⌋}). Also, S = 2⁵² and B = 1023. And together that is

i(f) = (p(f) + B)S = (⌊log₂ f⌋ + (f - 2^{⌊log₂ f⌋}) / (2^{⌊log₂ f⌋}) + 1023) · 2⁵².

So the floating point value of f = 1.0 has the same bit representation as the positive integer i = 1023 × 2⁵². —Quantling (talk | contribs) 20:50, 15 April 2025 (UTC)

@David Eppstein This is how I get the idea from a YouTube source:

https://youtube.com/watch?v=p8u_k2LIZyo&t=610 Dominic3203 (talk) 00:15, 16 April 2025 (UTC)

Here's a modified version of the code to approximate the binary logarithm (log₂(x)) using similar bit manipulation techniques:

1. include <stdint.h>

float Q_log2(float number) {

union {

float f;

uint32_t i;

} conv = { .f = number };

// Extract exponent and approximate log2

conv.i -= 0x3f2aaaab; // Magic constant for log2 approximation

conv.f *= 1.1920929e-7f; // 1/(2^23) scaling factor

// Optional Newton-Raphson refinement (1 iteration)

float y = conv.f;

float refined = y - (1.442695f * (number - (1.0f / (1.0f + y * 0.6931472f))));

return refined;

}

1. 1. 1. Key Modifications:

1. **Bit Manipulation Core**:

conv.i -= 0x3f2aaaab; // Adjusts the float's bits to approximate log2

conv.f *= 1.1920929e-7f; // Scales the result (1/2²³)

This exploits the IEEE 754 format to approximate log₂(x) by:

- Subtracting a magic constant (`0x3f2aaaab`) to account for the exponent bias

- Scaling by `1/(2²³)` to convert from fixed-point to floating-point

2. **Newton-Raphson Refinement** (Optional):

refined = y - (1.442695f * (number - (1.0f / (1.0f + y * 0.6931472f))));

This improves accuracy using one iteration of Newton-Raphson to solve `2^y ≈ number`.

1. 1. 1. Example Usage:

float x = 8.0f;

printf("log2(%f) ≈ %f\n", x, Q_log2(x)); // Output: ~3.0

1. 1. 1. Limitations:

- **Approximation**: Accuracy ~0.01-0.1 relative error (better with refinement)

- **Range**: Works for normalized numbers (0 < x < ∞)

- **Portability**: Assumes IEEE 754 32-bit floats

For higher precision, use `<math.h>`'s `log2f`, but this version offers a fast approximation using bit manipulation. Dominic3203 (talk) 00:40, 16 April 2025 (UTC)

One sentence. Not line after line of derivation using technical terms that assume the reader has intimate knowledge of IEEE floating points. We need ONE SENTENCE that describes the approximation of the log from the floating point exponent and significand, and then one sentence briefly stating the usage of it in the fast inverse square root algorithm. Neither your nor Quantling's explanations are usable as readable article text. Reading further from the fast inverse square root article, it appears the approximation they are using is not k+(m-1)/ln2 (which would be good for m very close to 1) but rather k+(m-1)+sigma for a magic constant sigma chosen to tune the approximation. —David Eppstein (talk) 00:42, 16 April 2025 (UTC)

In case it needs stating: because this piecewise linear approximation to the binary logarithm is always less than or equal to the binary logarithm the authors of the fast inverse square root algorithm observed that one could get closer to the real value on average by adding a small constant. They tuned that constant to get σ.

But I (now) agree with @David Eppstein — we need one sentence that describes that the floating point representation can be used to approximate the binary logarithm. As far as the fast inverse square root goes, in the present article I wouldn't give more than an acknowledgement that the fact of the first sentence is exploited for that. —Quantling (talk | contribs) 13:51, 16 April 2025 (UTC)

I also modified the PPAP song:

"I have a log base 2 of a, I have a log base 2 of b,"

"Ahh!"

"a times b!"

So this is why I focus on this topic. Dominic3203 (talk) 04:20, 16 April 2025 (UTC)

That the logarithm used in the fast inverse square root algorithm is base 2 isn't really significant. Ignoring σ, the calculation is simply

inverse_square_root(f) = as_float( as_int(1.0) - (as_int(f) - as_int(1.0)) / 2 )

which would work no matter what the base of the logarithm is. The as_int(1.0) appearances take care of the bias, and the scale factor is never explicitly used. (In fact, the base of the logarithm is ${\sqrt[{2^{52}}]{2}}$ but nobody cares.) —Quantling (talk | contribs) 17:34, 16 April 2025 (UTC)

It turns out that this idea for approximating binary logarithms of floating point numbers is much older than fast inverse square root and comes from a reference we are already citing: Mitchell 1962. Anyway, see new section Binary logarithm § Piecewise-linear approximation. —David Eppstein (talk) 17:42, 16 April 2025 (UTC)