4 ms·

I'm curious what the benefits of ternary numbers are here? The section on balanced ternary numbers in Knuth's work was super fun to read; but I didn't realize

by taeric 2y ago

I'm curious what the benefits of ternary numbers are here? The section on balanced ternary numbers in Knuth's work was super fun to read; but I didn't realize this was relevant nowadays? At the outset, it seems like it is more about storing ternary weights in binary without having to convert a multidigit ternary number? That is, if you have 20 weights, if this was binary, you could store all 20 weights as a single 20 bit number. I'm assuming you could convert the 3^20 number to binary and do the same? Is that roughly what is happening, here, with most of the effort in how to get out each trit? Edit: I should add that I was largely misunderstanding parts of the article. I was reading this as akin to BCD, but with ternary. Reading it without that misunderstanding, I can see that they are largely doing what I said here.

winwang 2y ago
PAM3 for data transfer: https://www.synopsys.com/designware-ip/technical-bulletin/pam3-technology-implementation-usb4-v2.html https://www.synopsys.com/designware-ip/technical-bulletin/pa...
- taeric 2y ago
  At the physical layer, this makes a ton of sense. Apologies for completely ignoring that part. I was specifically curious on encoding each "digit" of a ternary number independently in a computer. Which.... yeah, that isn't what this article was even saying.
- pezezin 2y ago
  It is also worth noting that Gigabit Ethernet uses PAM5.
Mokosha 2y ago
I don't know what the benefits of ternary numbers are in this particular case, but a similar technique is used in ASTC[1]. In this case, a fixed-size block of pixels stores one or more pairs of colors using a lower resolution than your usual 8bpp. Then, these color "endpoints" are interpolated using weights that allow you to approximate the original colors. For storing the endpoints, sometimes you can get a better trade-off of resolution/bit if you can pack ternary numbers in the bitstream instead of being restricted to power-of-two boundaries. [1]: https://developer.arm.com/documentation/102162/0430/The-ASTC-format https://developer.arm.com/documentation/102162/0430/The-ASTC...
thechao 2y ago
Ternary is a thing; however, there's a lot of times when you're hand-rolling a compression scheme. In those cases, it is common to consider all sorts of nonstandard bases. So, for instance, if you need to encode a pair of numbers, and that pair is in the (rectangular) range: `[0,2]*[0,4]`, then it can be efficiently encoded in a 4b value, using the generalized version of the technique outlined in the article. I know that a lot of GPU block textures rely pretty heavily on products-of-weird-bases, usually 3, 5, and 7. Here's some 'good' combinations (high utilization rates, easy to decode): 3^5 ~ 8b 5^3 ~ 7b 2 * 5 * 7^2 ~ 9b 2 * 3 * 5 ~ 5b 11 * 11 ~ 7b 3 * 5 * 7 ~ 7b etc.
- taeric 2y ago
  Yeah, I was making the mistake of thinking this was storing ternary in a BCD like scheme. I... honestly don't know how I talked myself into that.
- hinkley 2y ago
  Doom also famously redefined a circle as 256° and reworked all of their trigonometry and polar coordinate translations to match. And so the smallest increment of angle you could do in the game was around 85 arc minutes.
  - kristianp 2y ago
    > famously redefined a circle as 256° Famously? Where can I read about Doom's odd trigonometry?
    - kristianp 2y ago
      I found one reference here: https://www.doomworld.com/forum/topic/103245-question-about-the-trigonometry-in-the-doom-source/ https://www.doomworld.com/forum/topic/103245-question-about-...
AlchemistCamp 2y ago
At the hardware level, I think the answer is that 3 is closer to e than 2 is. For a software emulation of ternary, I have no idea.
astrobe_ 2y ago
true, false, unknown is something you need sometimes.
av_conk 2y ago
There's emerging work on using the quantum analogue for trits (qutrits) in quantum computing. They are more robust to certain errors.
WorldMaker 2y ago
It's not directly relevant "nowadays", but it is also fun to note that hardware ternary computers existed, for example: https://en.wikipedia.org/wiki/Setun https://en.wikipedia.org/wiki/Setun Also, I forget which RAM format it was, but I recall that one of the RAM formats still in use is essentially ternary at the physical hardware level and uses the "sign" of the (-1, 0, 1) trit as a "check half-digit" for very fast checksums in hardware (and then the absolute value as the bit), because the physical hardware was going to be three-state anyway and cheap checksums are something RAM will always want.
- amelius 2y ago
  > but it is also fun to note that hardware ternary computers existed Maybe we should also have a post about storing bits in trits, then.
  - taeric 2y ago
    At a base level, this is just how to store numbers and convert between radixes? That is, the confusion I had in my thread was I was thinking "pack numbers" meant something more than just storing a radix three number. Where the "packing" was just taking advantage of the standard positional values. For example, consider that the number 123 can be seen as three numbers 0-9 as opposed to one number. How do you extract the three numbers? It can take a few instructions for similar reasons as the ternary case. Stated differently, if you can see how the numbers 0x12, 18, 022 (octal), and 0b10010 (binary) are all the same number, then you can see how the storage of them is roughly all the same. Now, for fun, you can also see how getting out the different "digits" of a number can be very different based on the base and limiting yourself to only working with binary shifts.
    - WorldMaker 2y ago
      Right by "packing" problem this article is maybe more about a "word-alignment" problem, finding the smallest "word" that most efficiently stores base-3 words in base-2 words with the least wasted values in that word. It's an interesting coincidence that 5 trits per 8 bits is rather optimal, because the 8-bit "byte" is such a useful and important "word" shape in modern binary computers. For the other side perspective, as amelius asked: the historic Setun used 18-trit words and that is surprisingly efficient at storing 28-bit words (0.643 bits per trit; the most efficient up to 32-bits of possible word alignment is 30-bits in 19-trits at 0.633 repeating bits per trit) if for some reason you needed to do interop. Of course 28-bit words aren't a standard binary word-size and if you wanted to try to find a word alignment that fits for both modern binary computers and Setun, might be 16-bits in 11-trits (0.6875 bits per trit). I suppose if you were building ternary hardware today you might shoot for a 41-trit word to align with modern 64-bit words (0.641 bits per trit).

by taeric 2y ago

winwang 2y ago

PAM3 for data transfer: https://www.synopsys.com/designware-ip/technical-bulletin/pam3-technology-implementation-usb4-v2.html https://www.synopsys.com/designware-ip/technical-bulletin/pa...

taeric 2y ago
At the physical layer, this makes a ton of sense. Apologies for completely ignoring that part. I was specifically curious on encoding each "digit" of a ternary number independently in a computer. Which.... yeah, that isn't what this article was even saying.
pezezin 2y ago
It is also worth noting that Gigabit Ethernet uses PAM5.

Mokosha 2y ago

I don't know what the benefits of ternary numbers are in this particular case, but a similar technique is used in ASTC[1]. In this case, a fixed-size block of pixels stores one or more pairs of colors using a lower resolution than your usual 8bpp. Then, these color "endpoints" are interpolated using weights that allow you to approximate the original colors. For storing the endpoints, sometimes you can get a better trade-off of resolution/bit if you can pack ternary numbers in the bitstream instead of being restricted to power-of-two boundaries. [1]: https://developer.arm.com/documentation/102162/0430/The-ASTC-format https://developer.arm.com/documentation/102162/0430/The-ASTC...

thechao 2y ago

Ternary is a thing; however, there's a lot of times when you're hand-rolling a compression scheme. In those cases, it is common to consider all sorts of nonstandard bases. So, for instance, if you need to encode a pair of numbers, and that pair is in the (rectangular) range: `[0,2]*[0,4]`, then it can be efficiently encoded in a 4b value, using the generalized version of the technique outlined in the article. I know that a lot of GPU block textures rely pretty heavily on products-of-weird-bases, usually 3, 5, and 7. Here's some 'good' combinations (high utilization rates, easy to decode): 3^5 ~ 8b 5^3 ~ 7b 2 * 5 * 7^2 ~ 9b 2 * 3 * 5 ~ 5b 11 * 11 ~ 7b 3 * 5 * 7 ~ 7b etc.

taeric 2y ago
Yeah, I was making the mistake of thinking this was storing ternary in a BCD like scheme. I... honestly don't know how I talked myself into that.
hinkley 2y ago
Doom also famously redefined a circle as 256° and reworked all of their trigonometry and polar coordinate translations to match. And so the smallest increment of angle you could do in the game was around 85 arc minutes.
- kristianp 2y ago
  > famously redefined a circle as 256° Famously? Where can I read about Doom's odd trigonometry?
  - kristianp 2y ago
    I found one reference here: https://www.doomworld.com/forum/topic/103245-question-about-the-trigonometry-in-the-doom-source/ https://www.doomworld.com/forum/topic/103245-question-about-...

AlchemistCamp 2y ago

At the hardware level, I think the answer is that 3 is closer to e than 2 is. For a software emulation of ternary, I have no idea.

astrobe_ 2y ago

true, false, unknown is something you need sometimes.

av_conk 2y ago

There's emerging work on using the quantum analogue for trits (qutrits) in quantum computing. They are more robust to certain errors.

WorldMaker 2y ago

It's not directly relevant "nowadays", but it is also fun to note that hardware ternary computers existed, for example: https://en.wikipedia.org/wiki/Setun https://en.wikipedia.org/wiki/Setun Also, I forget which RAM format it was, but I recall that one of the RAM formats still in use is essentially ternary at the physical hardware level and uses the "sign" of the (-1, 0, 1) trit as a "check half-digit" for very fast checksums in hardware (and then the absolute value as the bit), because the physical hardware was going to be three-state anyway and cheap checksums are something RAM will always want.

amelius 2y ago
> but it is also fun to note that hardware ternary computers existed Maybe we should also have a post about storing bits in trits, then.
- taeric 2y ago
  At a base level, this is just how to store numbers and convert between radixes? That is, the confusion I had in my thread was I was thinking "pack numbers" meant something more than just storing a radix three number. Where the "packing" was just taking advantage of the standard positional values. For example, consider that the number 123 can be seen as three numbers 0-9 as opposed to one number. How do you extract the three numbers? It can take a few instructions for similar reasons as the ternary case. Stated differently, if you can see how the numbers 0x12, 18, 022 (octal), and 0b10010 (binary) are all the same number, then you can see how the storage of them is roughly all the same. Now, for fun, you can also see how getting out the different "digits" of a number can be very different based on the base and limiting yourself to only working with binary shifts.
  - WorldMaker 2y ago
    Right by "packing" problem this article is maybe more about a "word-alignment" problem, finding the smallest "word" that most efficiently stores base-3 words in base-2 words with the least wasted values in that word. It's an interesting coincidence that 5 trits per 8 bits is rather optimal, because the 8-bit "byte" is such a useful and important "word" shape in modern binary computers. For the other side perspective, as amelius asked: the historic Setun used 18-trit words and that is surprisingly efficient at storing 28-bit words (0.643 bits per trit; the most efficient up to 32-bits of possible word alignment is 30-bits in 19-trits at 0.633 repeating bits per trit) if for some reason you needed to do interop. Of course 28-bit words aren't a standard binary word-size and if you wanted to try to find a word alignment that fits for both modern binary computers and Setun, might be 16-bits in 11-trits (0.6875 bits per trit). I suppose if you were building ternary hardware today you might shoot for a 41-trit word to align with modern 64-bit words (0.641 bits per trit).