6 ms·

The concept of radix economy assumes that hardware complexity for each logic element is proportional to the number of logic levels. In practice this isn't true,

by mrob 2y ago

The concept of radix economy assumes that hardware complexity for each logic element is proportional to the number of logic levels. In practice this isn't true, and base 2 is best. >Ternary circuits: why R=3 is not the Optimal Radix for Computation https://arxiv.org/abs/1908.06841 https://arxiv.org/abs/1908.06841 Previous HN discussion: https://news.ycombinator.com/item?id=38979356 https://news.ycombinator.com/item?id=38979356

deleted 2y ago
[deleted]
crdrost 2y ago
I like this article but it does kind of seem like it gets to a point of “well we know how to do binary stuff in hardware real well, we don't know how to do ternary stuff that well and doing it with binary components doesn't work great.” Also ternary gets a bit weird in some other ways. The practical ternary systems that the Soviets invented used balanced ternary, digits {–, o, +} so that 25 for example is +o–+, 25 = 27 + 0*9 – 3 + 1. If you think about what is most complicated about addition for humans, it is that you have these carries that combine adjacent numbers: and in the binary system you can prove that you relax to a 50/50 state, the carry bit is 50% likely to be set, and this relaxation happens in average by the 3rd bit or so, I think? Whereas ternary full adders only have the carry trit set ¼ of the time (so ⅛ +, ⅛ –) and it takes a few more trits for it to get there. (One of those nice scattered uses for Markov chains in the back of my head, the relaxation goes as the inverse of the second eigenvalue because the first eigenvalue is 1 and it creates the steady state. I got my first summer research job by knowing that factoid!) So you start to wonder if there's something like speculative execution possible then—half-adder-+ is definitely too simple for this but full adder + chains all these bits together and for larger numbers maybe it's not! Similarly I think that binary proliferated in part because the multiplication story for binary is so simple, it's just a few bitshifts away. But for balanced ternary it's just inversions and tritshifts too, so it has always felt like maybe it has some real “teeth” there.
- dgoldstein0 2y ago
  In terms of implementing adders, the standard solution for binary logic adders is carry lookahead adders. Perhaps an equivalent could be built in ternary logic? https://en.m.wikipedia.org/wiki/Carry-lookahead_adder https://en.m.wikipedia.org/wiki/Carry-lookahead_adder
addaon 2y ago
But it is true for one-hot encodings, yes? I may be showing my age here, but when I last took a computer architecture course domino logic (and self-clocking domino logic, even) was seen as something between the cutting edge and an obvious future for high speed data paths. No idea of this is still true, but it seems that something like domino logic would extend cleanly (and with cost linear in states) to ternary.

by mrob 2y ago

deleted 2y ago

[deleted]

crdrost 2y ago

I like this article but it does kind of seem like it gets to a point of “well we know how to do binary stuff in hardware real well, we don't know how to do ternary stuff that well and doing it with binary components doesn't work great.” Also ternary gets a bit weird in some other ways. The practical ternary systems that the Soviets invented used balanced ternary, digits {–, o, +} so that 25 for example is +o–+, 25 = 27 + 0*9 – 3 + 1. If you think about what is most complicated about addition for humans, it is that you have these carries that combine adjacent numbers: and in the binary system you can prove that you relax to a 50/50 state, the carry bit is 50% likely to be set, and this relaxation happens in average by the 3rd bit or so, I think? Whereas ternary full adders only have the carry trit set ¼ of the time (so ⅛ +, ⅛ –) and it takes a few more trits for it to get there. (One of those nice scattered uses for Markov chains in the back of my head, the relaxation goes as the inverse of the second eigenvalue because the first eigenvalue is 1 and it creates the steady state. I got my first summer research job by knowing that factoid!) So you start to wonder if there's something like speculative execution possible then—half-adder-+ is definitely too simple for this but full adder + chains all these bits together and for larger numbers maybe it's not! Similarly I think that binary proliferated in part because the multiplication story for binary is so simple, it's just a few bitshifts away. But for balanced ternary it's just inversions and tritshifts too, so it has always felt like maybe it has some real “teeth” there.

dgoldstein0 2y ago
In terms of implementing adders, the standard solution for binary logic adders is carry lookahead adders. Perhaps an equivalent could be built in ternary logic? https://en.m.wikipedia.org/wiki/Carry-lookahead_adder https://en.m.wikipedia.org/wiki/Carry-lookahead_adder

addaon 2y ago

But it is true for one-hot encodings, yes? I may be showing my age here, but when I last took a computer architecture course domino logic (and self-clocking domino logic, even) was seen as something between the cutting edge and an obvious future for high speed data paths. No idea of this is still true, but it seems that something like domino logic would extend cleanly (and with cost linear in states) to ternary.