Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to pack ternary numbers in 8-bit bytes

compilade.net

Post reply on HN
Print view View original

41–50 of 55 posts

Re: How to pack ternary numbers in 8-bit bytes

#41

Post by ralferoo »

One way to beat this in terms of coding efficiency would be to use something like rANS (explanation [1], code [2]).

You would have a more complicated decoder with rANS though, even if you removed the frequency table lookup (because always 1/3) and you'd only produce one output at a time instead of 5 doing this with a lookup table.

It might be possible to use a combination of both techniques with e.g. a 16 bit accumulator, multiplying by 243 to get the value to lookup into bits 23-16 and then bias and shift the incoming 8 bits into the accumulator.

[1] https://fgiesen.wordpress.com/2014/02/18/rans-with-static-pr...

[2] https://github.com/rygorous/ryg_rans

Re: How to pack ternary numbers in 8-bit bytes

#43

Post by gopalv »

JoshTriplett wrote: post #2

It's impressive how close to optimal this is. You can beat the efficiency of 5 trits in 8 bits (1.6) with as few as 17 trits in 27 bits (~1.588), but once you account for rounding up to a whole number of bytes for practical reasons, then beating the efficiency requires going to at least 111 trits in 176 bits (~1.586), or perhaps more practically for fast unpacking, 161 trits in 256 bits (~1.59). At that level, even i…

> You can beat the efficiency of 5 trits in 8 bits

The single trit packing is a commonly optimized DBNULL structure for booleans.

Bits/trit approaches the 1.5 asymptote, because that is the fundamental packing limit.

The trick is to use it when you have a trit to start with, like when you have a set which is a tiny bit over a power of two.

There are places where you end up with odd numbers in set sizes, for example when storing a poker hand.

Read Cactus Kev's trick[1] which I think needs a 27 bit section & optimizing it was where I first ran into trit packing.

[1] - http://suffe.cool/poker/evaluator.html

Re: How to pack ternary numbers in 8-bit bytes

#44

Post by [deleted] »

Imustaskforhelp wrote: post #10
benj111 wrote: post #5

Earlier quoted context omitted.

Off the top of my head. Compilers. You may know that a value has known 1s and 0s and unknowns. This would allow you to represent that for optimisation purposes.

Arturo[0] language supports true,false and maybe. I really liked that idea actually, worth mentioning here. so valid arturo code can be like (picked from their in-a-nutshell documentation) i1: true i2: false i3: maybe [0]: https://arturo-lang.io/documentation/in-a-nutshell

[deleted]

Re: How to pack ternary numbers in 8-bit bytes

#46

Post by Dylan16807 »

edflsafoiewq wrote: post #31
lioeters wrote: post #21

Amusing that the link to an article on ternary numbers was posted by Mr Triplett. (: The article is well-written and illustrated. The technique described is used in llama.cpp for running language models like BitNet b1.58 whose weights are stored as ternary types. > ..in which every single parameter (or weight) of the LLM is ternary {-1, 0, 1} > significantly more cost-effective in terms of latency, memory, throughput…

PrismML released a ternary model recently. However AFAICT they don't use this packing, instead packing trits as 2 bits each (as least for the GGUF). Hy-MT2 also came out with a 1.25bit model using a technique called Sherry, where weights are trits with the additional constraint that exactly one trit in a group of four is 0. Four possible positions for the 0 times 2^3 possibility for the other three positions = 32 pos…

Requiring a zero, okay. By the time you also require that none of the other numbers are zero, I don't even call that a trit anymore, it's a bunch of weird constrained values.

Re: How to pack ternary numbers in 8-bit bytes

#47

Post by computably »

gopalv wrote: post #43
JoshTriplett wrote: post #2

It's impressive how close to optimal this is. You can beat the efficiency of 5 trits in 8 bits (1.6) with as few as 17 trits in 27 bits (~1.588), but once you account for rounding up to a whole number of bytes for practical reasons, then beating the efficiency requires going to at least 111 trits in 176 bits (~1.586), or perhaps more practically for fast unpacking, 161 trits in 256 bits (~1.59). At that level, even i…

> You can beat the efficiency of 5 trits in 8 bits The single trit packing is a commonly optimized DBNULL structure for booleans. Bits/trit approaches the 1.5 asymptote, because that is the fundamental packing limit. The trick is to use it when you have a trit to start with, like when you have a set which is a tiny bit over a power of two. There are places where you end up with odd numbers in set sizes, for example w…

The asymptote is log2(3) = 1.58496...

Re: How to pack ternary numbers in 8-bit bytes

#48

Post by Razengan »

reaperducer wrote: post #38
Razengan wrote: post #19

I was actually mucking with ChatGPT about possible "post-binary" architectures. I ended up feeling that ternary is just icky, because the "middle value" doesn't have an "opposite" Maybe we should do what quaternions did to complex numbers and just jump from 2 to 4: Quaternary CPUs I couldn't understand half of the words it spat out but it turns out that using pairs of "quits" as the atomic computation unit to represe…

I was actually mucking with ChatGPT about possible "post-binary" architectures. Ternary computers were around almost 70 years ago, and first posited well over 100 years ago. Maybe ChatGPT isn't the best place to do research.

Maybe your anti-AI knee-jerk training isn't the best model for writing HN comments.

Did I say I wasn't aware of ternary you dumdum?

Even if you want to be anal, ternary is still "post-binary" even if it came out 300 years ago.

Re: How to pack ternary numbers in 8-bit bytes

#49

Post by [deleted] »

computably wrote: post #47
gopalv wrote: post #43

Earlier quoted context omitted.

> You can beat the efficiency of 5 trits in 8 bits The single trit packing is a commonly optimized DBNULL structure for booleans. Bits/trit approaches the 1.5 asymptote, because that is the fundamental packing limit. The trick is to use it when you have a trit to start with, like when you have a set which is a tiny bit over a power of two. There are places where you end up with odd numbers in set sizes, for example w…

The asymptote is log2(3) = 1.58496...

[deleted]

Re: How to pack ternary numbers in 8-bit bytes

#50

Post by meatmanek »

newpavlov wrote: post #45

I wonder if NNs could be trained well enough with 1 bit weights (i.e. 0 and 1) with some layers doing addition, while others substraction (i.e. weight sign would be "hardcoded" into the network architecture). Or with zero-less weights (e.g. -1, -0.5, 0.5, 1).

There are 1-bit* LLMs (+1/-1, usually), though they often come with an additional scaling parameter:

https://huggingface.co/prism-ml/Bonsai-27B-gguf#weight-repre...

> Weight Representation: Q1_0_g128 Each weight is a single sign bit: 0 maps to −scale, 1 maps to +scale. Every group of 128 weights shares one FP16 scale factor. > Effective bits per weight: 1.125 (1 sign bit + 16-bit scale amortized over 128 weights)

The Bonsai ternary model also uses this group-wise scaling, so the theoretical bits per parameter is 1.71 instead of ~1.58; additionally, they actually store trits as 2 bits; with the group scaling factor it becomes 2.125 bits/weight: https://huggingface.co/prism-ml/Ternary-Bonsai-27B-gguf#memo...

Post reply on HN