| > 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+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%... We want to choose chunk sizes where the mod value is close to 8, since we have to round up. Hope this helps. |