The Advantages of Base 3 | Hacker News Reader

The Advantages of Base 3

americanscientist.org

36 pointsnreece15 comments

The average number of choices to be endured is minimized when there are three items per menu.

Can anyone provide proof of that? I calculate that for 100 choices convenientely separatable into a balanced tree, then base 2 yields: 7 levels * 2 = 14 choices, while base 3 yields: 5 levels * 3 = 15 choices. So, advantage to base 2. For 1000:

   base 2: 10 * 2 = 20 choices
   base 3: 7 * 3 = 21 choices

(I neglected the incompleteness of the tree to simplify, maybe that'd make a difference)

I suppose, the average number of choice to listen to could be 1.5 and 2 respectively. However, if I know that it's a binary or ternary phone system, then the right numbers are 1 and 2 instead, because I don't have to listen to the last option; I already know that it's "everything else". Then base 2 would again trounce base 3 for 100 and 1000, and probably any number.

Finally, if his proposition is right, does it mean that a ternary tree is a more efficient data structure than a binary tree, when there is a natural ternary separation?

EDIT: I figured out the first part... the number of choices would be k * log[n] / log[k]. So the important factor is k / log[k], which is 2.88 for base 2 and 2.73 for base 3. It's really close, but assuming as I said that we should multiply by 1 and 2 instead of 2 and 3, then I don't think his assertion holds at all, in theory or in practice...

100 and 1000 are both slightly less than powers of 2, so 2 has a slight advantage for these numbers. For sufficiently large numbers, 3 always wins. Here is a proof:

If there are a total of N options, the number of choices is x * d, where d is the smallest integer larger than log_x(N). When N is large enough you can approximate d by log_x(N), so the number of choices is x log N / log x. We are looking for the x that minimizes x / log x (in any base). Let us arbitrarily choose base 2. So 2 / log 2 is 2, whereas 3 / log 3 is only 1.89.

Incidentally, to see that the minimum of the continuous function x / log x is reached at e (although this has no relevance to the discrete problem), take the derivative and set it to zero, giving 1 / log(x) - 1 / log^2(x) = 0, or log x = 1, giving x=e (differentiation rules are always in base e.)

Finally, if his proposition is right, does it mean that a ternary tree is a more efficient data structure than a binary tree, when there is a natural ternary separation?

This whole argument is based on an arbitrary -- and IMO, rather flimsy -- measure of efficiency as the product of depth and width. The optimal branching factor for an n-ary tree depends on many factors and is heavily dependent on the details of the implementation; no single n is always optimal. For example, when traversal of the tree involves disk seeks, a very large n such as 512 or 1024 is used.

For what it's worth, over the range N = [59050, 65536] = [3^10+1, 2^16], the number of choices in a ternary tree is 311 = 33, and in a base-2 tree is 216 = 32; 65536 is the largest N for which binary wins over ternary. They tie a few times for even higher N, for the last time at the interval [3^17 + 1, 2^27] = [129140164, 134217728]; ternary trees with number of leaves in this interval have 18 levels, binary trees have 27.

The point is that "sufficiently large" here turns out to be so large that nobody would actually build a phone tree that large, which is true for lots of mathematical results about "sufficiently large" numbers.

> However, if I know that it's a binary or ternary phone system, then the right numbers are 1 and 2 instead

Not really, it's 1 and 1.66(6) (you never listen to the 3rd option).

Also, for e.g. 1000: in base 3 a lot of 7th level menus will contain less than 3 choices, while in base 2 almost all of 10th level menus will contain 2choices.

You never listen to the third option? You seem to be assuming that these menu systems are sufficiently well designed that if you hear "1" and "2" and what you want is neither of them, you can just blindly press "3". This is almost never the case.

Oh, I read it as if 1 or 2 IS what you want, then you never hear 3.

You do understand that it wasn't my assumption, don't you? It's what ced assumes, I'm just exposing some errors in his calculations.

Responding to your edit: I don't think you should take the phone menu example too seriously, I think that was just meant as a fun diversion. The real question is whether a ternary-logic microprocessor would require a smaller area than a binary one, under the plausible assumption that this is proportional to depth * width. I think that would almost certainly not be the case -- binary is just so much more natural than ternary that you're just going to end up simulating ternary with binary anyway. In fact that is exactly what seems to have happened in the attempt that he describes to build a ternary computer.

The most efficient base for computation is e. The closest integer is 3, which is why the Soviets wasted lots of time and effort making a trinary computer.

Wasted? The machine (http://en.wikipedia.org/wiki/Setun) worked marvelously, and was amazingly cheap and efficient for the amount of computational power it yielded, using the available technology.

More information on the development of the setun ternary computer:

http://www.computer-museum.ru/english/setun.htm

if 0 is false and 1 is true then what is 2 ? (conspiracy ?)

0 is not false; false is 0. If you really want a logic model here, use fuzzy logic with 3 discrete values.

An aside: why was the above comment modded down so much? I think it was simply a joke. Not a deep joke and not a funny one, but not offensive or anything like that. Folks, relax already.

-1 = false, 0 = unknown, +1 = true

On the joke front people here seem to take a dim view of anything that might be frippery.

Haha, I just got your joke.

Using the word "frippery" is frippery.

Reply on news.ycombinator.com