Ternary Computing

eviltwinimposter writes: "This month's American Scientist has an article about base-3 or ternary number systems, and their possible advantages for computing and other applications. Base-3 hardware could be smaller because of decreased number of components and use ternary logic to return less than, greater than, or equal, rather than just the binary true or false, although as the article says, '...you're not going to find a ternary minitower in stock at CompUSA.' Ternary also comes the closest of any integer base to e, the ideal base in terms of efficiency, and has some interesting properties such as unbounded square-free sequences. Also in other formats."

Comments

Ternary trees

[mauddib~]

Dr. Dobbs recently had an interesting article about ternary trees (http://www.ddj.com/articles/1998/9804/9804a/9804a .htm), which also discussed some performance comparisons between binary trees and hashes.
We just did some testing, comparing those search algorithms with eachother. Although hashes are more or less comparable in speed with ternary trees, binary trees are much slower.

Some sample output: (btw, we didn't balance the ternary tree, although we did some really basic balancing on the binary tree).

testing binary tree
elements = 235807
235807 insertions in 97.995633 seconds
tree depth = 7882
235807 lookups in 95.111857 seconds

testing hash table
elements = 235807
235807 insertions in 0.442643 seconds
tree depth = 63709 (number of buckets in use)
235807 lookups in 0.345933 seconds

testing ternary tree
elements = 235807
235807 insertions in 0.744229 seconds
tree depth = 93
235807 lookups in 0.386081 seconds

Clearly the ternary tree and hash are much faster than the binary tree. Although there are still some optimisations to make, we believe that the ternary tree will outperform the binary tree at all times.

We also made some (very) cool graphs with Graphviz, but unfortunately have no good place to share it with the rest of the /. reading audience.