4 ms·

The author of this post is oblivious to fractional bit encodings. When encoding an array of items, you can always encode the array optimally, only wasting less

The author of this post is oblivious to fractional bit encodings. When encoding an array of items, you can always encode the array optimally, only wasting less than 1 bit. For example, if we had an array of n test scores from 1-100, we only need ceil(n*log2(100)) bits. The key is that when reading the values, instead of shifting like we would normally to iterate an array, we instead divide by 100. Instead of masking bits, we get the current value by doing mod 100. Its equivalent to shifting/masking for a power of 2, but extends packing to fractional bits. It's quite beautiful. Take a look at this blog post to understand more about fractional bit representations: https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i/ https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i...

jerf 5y ago
Speaking from experience on this... you get some crazy looks from code reviewers. I got perhaps overclever with this at one point using it to generate passwords by extracting log2(44) bits progressive out of a random number to choose from my blessed set of characters for passwords and it took some patience with the security team to verify that it was safe. I did it just because it's one of the more elegant ways out of the problem of truncation of bits when you have a non-even-power-of-two set of possibilities to choose from, especially when you need to do it repeatedly from a random source. Instead of discarding or fussing about, if you need fractional bits from a given random source of bits, you just... take fractional bits. No fuss. No muss.
- jhgb 5y ago
  > by extracting log2(44) bits progressive out of a random number to choose from my blessed set of characters for passwords and it took some patience with the security team to verify that it was safe. It's safe but if you somehow depended on all the passwords having exactly equal probability, you'd be wrong (unless you're already using a random number from a limited range). Of course this is easily fixed by a range check on the random number and generating it again if it failed the check.
- goldenkey 5y ago
  I also have written about using pairing functions to extract multiple random numbers from a single rand() call Your method is more concrete than mine, mine is math, yours is binary-based CS. https://churchofthought.org/blog/2019/07/24/an-ordered-variant-of-the-cantor-pairing-function/ https://churchofthought.org/blog/2019/07/24/an-ordered-varia...
smrq 5y ago
I feel like the core idea here is really intuitive, but the presentation as fractional bit encoding obscures it—at least to me. It's just encoding an array of values with K distinct possibilities as a base-K number. I had to read the code in the link above to understand that; the exposition didn't help me at all.
- zozbot234 5y ago
  > It's encoding an array of values with K distinct possibilities as a base-K number Yes, and the encoding and decoding step needs to do arithmetic so there's a practical limit to how big these numbers can be. But sometimes you do get some real gains.
bryondowd 5y ago
Interesting concept, but seems like it only works for fairly small arrays, right? You could fit 40 base-3 values into a 64 bit integer, but in order to read/write index 39, you have to perform 39 multiplications/divisions. So no efficient random access. And is there any way to encode more than 40 base-3 values if your largest integer is 64 bits? If you need 45 elements, I guess you could use an array of 5 8-bit integers where each 8-bit element represents 5 base-3 elements. Of course, now you're limited to increasing the size of your array to increments of 5 (or more generally, smallest efficient integer size / log base 2 of the number of representable values)
- goldenkey 5y ago
  > Interesting concept, but seems like it only works for fairly small arrays, right? Any size array will work. > And is there any way to encode more than 40 base-3 values if your largest integer is 64 bits? Yes, absolutely. And with ease. Bignums make it seamless. Some languages like Perl and Python and Mathematica support them out of the box. You can still do random access, it just becomes: divide bignum by 3^n, take result mod 3. It will be costly though, like you mentioned. There is a way to bound the cost. You can chunk your elements to a number of bits that is a multiple of 8 bits, a byte. This allows you to do random access with minimal overhead, while giving you the savings, bounded by your choice of chunk size. For example, 100 of your elements can be neatly fit into 20 bytes. 101 elements would need more than 20 bytes or 160 bits, but 100 elements only needs 158.5 bits, we only lose 1.5 bits per chunk. https://www.wolframalpha.com/input/?i=log2%283%29*100.+vs+log2%283%29*101.0 https://www.wolframalpha.com/input/?i=log2%283%29*100.+vs+lo... Consider that we do this chunking. Let us say we have 10000 elements and want to look at the value of element 6000. We can immediately skip to byte (6000/100)*20=1200 and simply take the value there mod 3. This is possible to do because each chunk is no longer related to eachother. So we get random access with a small procedure that gives us a huge space savings. If we choose a byte-sized chunk size, we can graph (log2(3)*n) % 8 to look for which chunk sizes would lose the least bits of storage. https://www.wolframalpha.com/input/?i=discrete+plot+%28log2%283%29*n+mod+8%29+from+n%3D1+to+200 https://www.wolframalpha.com/input/?i=discrete+plot+%28log2%... We want to choose chunk sizes where the mod value is close to 8, since we have to round up. Hope this helps.
jhgb 5y ago
> Coding with an non-integer number of bits is counter-intuitive I've reinvented this very thing several times in the past. I don't see how it is in any way unnatural or unintuitive. You're simply numbering the members of a Cartesian product of some finite sets. The maximum number possible, if you start from number 1, is the product of the cardinalities of all of your sets. It's basically elementary school math, which is probably why I had no problems with coming up with this idea even in my dilettante past.

jerf 5y ago

Speaking from experience on this... you get some crazy looks from code reviewers. I got perhaps overclever with this at one point using it to generate passwords by extracting log2(44) bits progressive out of a random number to choose from my blessed set of characters for passwords and it took some patience with the security team to verify that it was safe. I did it just because it's one of the more elegant ways out of the problem of truncation of bits when you have a non-even-power-of-two set of possibilities to choose from, especially when you need to do it repeatedly from a random source. Instead of discarding or fussing about, if you need fractional bits from a given random source of bits, you just... take fractional bits. No fuss. No muss.

jhgb 5y ago
> by extracting log2(44) bits progressive out of a random number to choose from my blessed set of characters for passwords and it took some patience with the security team to verify that it was safe. It's safe but if you somehow depended on all the passwords having exactly equal probability, you'd be wrong (unless you're already using a random number from a limited range). Of course this is easily fixed by a range check on the random number and generating it again if it failed the check.
goldenkey 5y ago
I also have written about using pairing functions to extract multiple random numbers from a single rand() call Your method is more concrete than mine, mine is math, yours is binary-based CS. https://churchofthought.org/blog/2019/07/24/an-ordered-variant-of-the-cantor-pairing-function/ https://churchofthought.org/blog/2019/07/24/an-ordered-varia...

smrq 5y ago

I feel like the core idea here is really intuitive, but the presentation as fractional bit encoding obscures it—at least to me. It's just encoding an array of values with K distinct possibilities as a base-K number. I had to read the code in the link above to understand that; the exposition didn't help me at all.

zozbot234 5y ago
> It's encoding an array of values with K distinct possibilities as a base-K number Yes, and the encoding and decoding step needs to do arithmetic so there's a practical limit to how big these numbers can be. But sometimes you do get some real gains.

bryondowd 5y ago

Interesting concept, but seems like it only works for fairly small arrays, right? You could fit 40 base-3 values into a 64 bit integer, but in order to read/write index 39, you have to perform 39 multiplications/divisions. So no efficient random access. And is there any way to encode more than 40 base-3 values if your largest integer is 64 bits? If you need 45 elements, I guess you could use an array of 5 8-bit integers where each 8-bit element represents 5 base-3 elements. Of course, now you're limited to increasing the size of your array to increments of 5 (or more generally, smallest efficient integer size / log base 2 of the number of representable values)

goldenkey 5y ago
> Interesting concept, but seems like it only works for fairly small arrays, right? Any size array will work. > And is there any way to encode more than 40 base-3 values if your largest integer is 64 bits? Yes, absolutely. And with ease. Bignums make it seamless. Some languages like Perl and Python and Mathematica support them out of the box. You can still do random access, it just becomes: divide bignum by 3^n, take result mod 3. It will be costly though, like you mentioned. There is a way to bound the cost. You can chunk your elements to a number of bits that is a multiple of 8 bits, a byte. This allows you to do random access with minimal overhead, while giving you the savings, bounded by your choice of chunk size. For example, 100 of your elements can be neatly fit into 20 bytes. 101 elements would need more than 20 bytes or 160 bits, but 100 elements only needs 158.5 bits, we only lose 1.5 bits per chunk. https://www.wolframalpha.com/input/?i=log2%283%29*100.+vs+log2%283%29*101.0 https://www.wolframalpha.com/input/?i=log2%283%29*100.+vs+lo... Consider that we do this chunking. Let us say we have 10000 elements and want to look at the value of element 6000. We can immediately skip to byte (6000/100)*20=1200 and simply take the value there mod 3. This is possible to do because each chunk is no longer related to eachother. So we get random access with a small procedure that gives us a huge space savings. If we choose a byte-sized chunk size, we can graph (log2(3)*n) % 8 to look for which chunk sizes would lose the least bits of storage. https://www.wolframalpha.com/input/?i=discrete+plot+%28log2%283%29*n+mod+8%29+from+n%3D1+to+200 https://www.wolframalpha.com/input/?i=discrete+plot+%28log2%... We want to choose chunk sizes where the mod value is close to 8, since we have to round up. Hope this helps.

jhgb 5y ago

> Coding with an non-integer number of bits is counter-intuitive I've reinvented this very thing several times in the past. I don't see how it is in any way unnatural or unintuitive. You're simply numbering the members of a Cartesian product of some finite sets. The maximum number possible, if you start from number 1, is the product of the cardinalities of all of your sets. It's basically elementary school math, which is probably why I had no problems with coming up with this idea even in my dilettante past.