# Why does Halstead's formula for estimated program length look like this?

According to the Halstead's software metrics:

Estimated program length: Can you please explain me, why the formula uses logarithm to base 2? Why not something else? Why exactly logarithm? What’s the reason? Is that somehow related to how we think?

I understand that allows to determine internal computer (bits) representation of n, but in this case n is just number of operators/operands. So, I really do not understand what this estimation represents and why the formula looks like this?

Because the effective difference between 1 and 2 operators/operands in a program is larger than the difference between 101 and 102. Logarithms were chosen to model that diminishing significance.

Why base 2? Eh, probably because we're computer nerds. If Halstead had chosen base 10 or base e it would still produce a model that would roughly compare two programs length the same way. It'd just produce different numbers for each when doing it.

If Halstead didn't care about that diminishing significance he might chosen a similar formula

L = n12 + n22

You might notice that this looks suspiciously like the pythagorean theorem:

c2 = a2 + b2

Which leaves me thinking of L as less like a linear measure like "program length" and more like an area measure of program complexity. Halsteads formula seems like a watered down version of this formula:

L = n1 * n2

Which, if you believe in that diminishing significance, certainly needs watering down.

• Ok, I got the point, log here for reducing the final estimation. But I did not get your point about measuring of the effective difference. Why it is larger between 1 and 2 operators/operands in compare with 101 and 102? Can you pls, give me an simple example of calculation of it. Oct 1, 2019 at 17:52
• Here's a simple example: the binary language has two words: one and zero. English has considerably more. Which language would be more impacted by the addition of a new word? Oct 1, 2019 at 20:40
• Intuitively, it's clear. I understand your point, and I like it. But how it is related to the formula of Estimated program length? From the formula, it seems like a vice versa. For example, `(10^6+1)*log2(10^6+1) - 10^6*log2(10^6) = 21.4` and `3*log2(3) - 2*log2(2) = 2.75` Oct 2, 2019 at 9:04
• Right, compare that to the "similar formula" ‭2,000,001‬ and 5. Oct 2, 2019 at 12:38
• Wait, I do not understand. If I add a new word to a language with `2*10^6` words -> estimated length of the language will increase `at 22 "points"` according to the formula. If I add, for example, 3 new words to a language, which contains only `2` words -> estimated length will increase only `at 10 "points"`, again according to the formula. Effective difference in the first case is higher. It disproves your assumption. Oct 2, 2019 at 21:43