4 ms·

The Advantages of Base 3

36 points by nreece 17y ago

kqr2 17y ago
More information on the development of the setun ternary computer: http://www.computer-museum.ru/english/setun.htm http://www.computer-museum.ru/english/setun.htm
rv77ax 17y ago
if 0 is false and 1 is true then what is 2 ? (conspiracy ?)
- cema 17y ago
  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.
  - pbhjpbhj 17y ago
    -1 = false, 0 = unknown, +1 = true On the joke front people here seem to take a dim view of anything that might be frippery.
    - jsonscripter 17y ago
      Haha, I just got your joke. Using the word "frippery" is frippery.
ced 17y ago
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...
- randomwalker 17y ago
  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.
  - madcaptenor 17y ago
    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.
- jsn 17y ago
  > 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.
Tangurena 17y ago
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.
- asciilifeform 17y ago
  Wasted? The machine (http://en.wikipedia.org/wiki/Setun 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.

36 points by nreece 17y ago

kqr2 17y ago

More information on the development of the setun ternary computer: http://www.computer-museum.ru/english/setun.htm http://www.computer-museum.ru/english/setun.htm

rv77ax 17y ago

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

cema 17y ago
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.
- pbhjpbhj 17y ago
  -1 = false, 0 = unknown, +1 = true On the joke front people here seem to take a dim view of anything that might be frippery.
  - jsonscripter 17y ago
    Haha, I just got your joke. Using the word "frippery" is frippery.

ced 17y ago

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...

randomwalker 17y ago
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.
- madcaptenor 17y ago
  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.
jsn 17y ago
> 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.

Tangurena 17y ago

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.

asciilifeform 17y ago
Wasted? The machine (http://en.wikipedia.org/wiki/Setun 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.