A useful intermediate representation would be "binary coded ternary" (BCT?) whereby 121 gets represented as 011001. The code 11 isn't used, just like 1010 through 1111 are not used in binary-coded decimal (BCD).
The 10 bit BCT representation of a five digit ternary number could index into an array of 1024 entries, each yielding its numeric value, that fits into a byte.
Likewise, a reverse table of 243 values can map to a 10 bit BCT.
Conversions between BCT and textual digits are trivial.
GP's suggestion is that you use 4 instead of 3. If you have 5 numbers, you multiply them by 4^5, 4^4, etc, and then add them. You waste some fractional bits, but you can do everything with masks and shifts instead of multiplications and divisions by three.
Suppose you have the ternary number "12102". We can encode each digit in two bits: 01,10,01,00,10 very easily. That gives us 0110010010, a ten bit number: a "binary coded ternary" whose value, in decimal, is 402. Now, we use that as an index into a table bct_value[402]. That table just looks up the numeric value of this code as an integer value in the range 0 to 242, which is also an 8 bit binary number: 146. That's our encoding of the five ternary digits in one byte. With the precomputed table, we just look up. We can also have a reverse table that takes 146 to 402, which we can break into groups of two bits and map to digits.
Mind you, the reference implementation from the blog is really poor in terms of code quality and performance because I was not allowed to open-source what I actually developed for my client, but the ideas still stand.
Delta compression can make a huge difference in some cases; because cpu cycles are cheap and bitwise operations are very fast it has the potential to bring serious benefits in some scenarios, ie. lower latency of transmitting (numeric) data over networks.
Isn't it possible to use SQLite or something for something like this? That would greatly simplify most of these tasks, making your dataset reachable through a fast declarative language.
As many games of Go as 100000 is, it's not so big you couldn't use a regular, untuned database.
I'm not questioning the usefulness of bitfields. But in this case, it would be silly not to use a database instead.
The method that the article describes (storing two-dimensional arrays of "empty", "black", and "white" in 2 bits) is also not the best one to use to store Go games. Chopping up games and creating deltas from them, or storing the moves rather than the sheets themselves and recreating those sheets on the fly, are best for data compression.
I guess we never do bit shifting in higher level languages at all. E.g. in Python, there is no point to do this, there is only one type of int (64 bit) and it still creates a new int object, which is not very fast.
You certainly can do this in python and often will need to when dealing with binary formats. The struct library is a great help for this. (https://docs.python.org/2/library/struct.html)
Where you can, you should use struct. For example, decoding a 32-bit integer in struct is faster than doing it manually:
In [11]: %timeit hex(b[0] | (b[1] << 8) | (b[2] << 16) | (b[3] << 24))
The slowest run took 6.89 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 715 ns per loop
In [12]: %timeit hex(struct.unpack('<I', b)[0])
The slowest run took 8.77 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 587 ns per loop
The resulting code is also going to be cleaner, especially if you end up needing to unpack multiple members at once, which is common when parsing a binary file.
The struct module is, I believe, written in C. (Pedantically, the struct module isn't; the C module _struct is hidden/private, but if you open the source for struct.py, you'll see it referenced.)
The struct library is great for decoding binary file formats, but it has no facilities for sub-byte packing such as what the article talks about. But if you have a structure composed of little or big-ending encoded 8-/16-/32-/64-bit signed/unsigned integers in a file (quite common) … struct is amazing.
If you're reading a file format that does bit packing, such as what the article is talking about, then as you read over the bytes / members of that file, you're probably going to need to get those out of the resulting bytes/decoded integers with Python's bit-shifting instructions. For example, if I have an unsigned 16-bit LE in a file, where the high four bits are flags, and the low 12 bits a value of some ilk, I can parse that with something like,
packed = fileobj.read(2)
# (missing: check the read for early EOF)
packed, = struct.unpack('<H', packed)
flags = packed >> 12
value = packed & 0xfff
> there is only one type of int (64 bit)
Python's integer type isn't 64 bits. It's however many bits you need it to be. For example, I can compute 2 raised to the 128th power, without use of floating point math (and thus, get an exact answer):
In [13]: 2**128
Out[13]: 340282366920938463463374607431768211456
In [14]: type(2**128)
Out[14]: int
This computation would not fit in a 64 bit integer. (For the non-Python programmers, there is a floating-point type, "float", which in CPython corresponds to an IEEE double.)
> which is not very fast.
It's fast enough for most things. :-) There's numpy, and always C/C++/Rust if you need more speed.
Recently I was asked how to get the value of the upper four bits of a byte.
It was asked as: how can I split a byte? Do I need to convert it to bitstring?
If he was a front-end engineer I wouldn't be so surprised but he has 3 years experience working in telecoms, CompSci with networking module at UMass. Uses Wireshark on a regular basis.
A very odd knowledge gap in this domain. So yes I think many engineers don't know these things.
For any topic, no matter how trivial, there is always an infinite amount of people who have never heard of it.
For instance, the ones who breathe tends to take it for granted, yet there are more than 350 000 people who just discovered breathing for the first time today.
Gonna be tough to find a source corroborating that there are an infinite number of people.
That said, I agree with the sentiment here. I can understand people brother having seen packing before. There are lots of programmers and engineers out there that simply haven't had a need. Especially ones who haven't dealt with binary formats or tight resource constraints.
It's got only ten upvotes, and there's always a bit of randomness in what hits the front page. Not everyone here is even a developer, and it is certainly an accessible article.
This method is only optimal if your numbers have ranges that fit nicely into powers of two. See here for optimal bit packing: https://codeplea.com/optimal-bit-packing
And if you need to store values that are not powers of 2, you can use the following kind of encoding/decoding. In python3:
from math import *
def number_to_trits(n):
# little-endian encoding
# (i.e. smallest precision trit first)
trits = []
v = n
for i in range(1,9):
v, d = divmod(v, 3**i)
trits.append(d)
return trits
print(number_to_trits(8))
# [2, 2, 0, 0, 0, 0, 0, 0]
def trits_to_number(trits):
n = 0
for i, trit in enumerate(trits):
n += trit*3**i
return n
print(trits_to_number([2,2]))
# 8
45 comments
[ 3.4 ms ] story [ 99.4 ms ] threadThe code gets more complex and slow, but not really by much.
The word is "ternary", by the way.
A useful intermediate representation would be "binary coded ternary" (BCT?) whereby 121 gets represented as 011001. The code 11 isn't used, just like 1010 through 1111 are not used in binary-coded decimal (BCD).
The 10 bit BCT representation of a five digit ternary number could index into an array of 1024 entries, each yielding its numeric value, that fits into a byte.
Likewise, a reverse table of 243 values can map to a 10 bit BCT.
Conversions between BCT and textual digits are trivial.
The way I have in mind is the same way you'd separate out the digits in a decimal number, except you'd use 3 instead of 10 in the math.
Writing is the harder part. I suppose you could just make 15 such tables, one for each possible value you could write.
https://en.wikipedia.org/wiki/Bit_field
http://erlang.org/doc/programming_examples/bit_syntax.html
Mind you, the reference implementation from the blog is really poor in terms of code quality and performance because I was not allowed to open-source what I actually developed for my client, but the ideas still stand. Delta compression can make a huge difference in some cases; because cpu cycles are cheap and bitwise operations are very fast it has the potential to bring serious benefits in some scenarios, ie. lower latency of transmitting (numeric) data over networks.
As many games of Go as 100000 is, it's not so big you couldn't use a regular, untuned database.
The method that the article describes (storing two-dimensional arrays of "empty", "black", and "white" in 2 bits) is also not the best one to use to store Go games. Chopping up games and creating deltas from them, or storing the moves rather than the sheets themselves and recreating those sheets on the fly, are best for data compression.
Bitfields are great, but not for this.
http://number-none.com/product/Packing%20Integers/index.html
I recently implemented a bitpacker in a game VM that didn't have bitwise operations, and the math-based version worked perfectly.
I wrote some very slow code to set/get the Nth bit in an array of bytes.
I was planning on using it for Chess bitboards - https://en.wikipedia.org/wiki/Bitboard, but it could be used for say 8 booleans to the byte.
unsigned char getbit(unsigned char * bits,unsigned long n){
}void setbit(unsigned char * bits,unsigned long n, unsigned char val){
Followed link. Chuckled at how stupid it was. Expected cynical comments...nope, people are serious.
Wow.
And yes I realize this will be dead. No wonder I stopped coming to HN...
But this is just really simple bit packing. Is this something many engineers (maybe frontend/JS) don't know about now?
You can, but probably it's even slower than doing regular bit shifting operations (<<, >>, &, |, ^, ~)
The struct module is, I believe, written in C. (Pedantically, the struct module isn't; the C module _struct is hidden/private, but if you open the source for struct.py, you'll see it referenced.)
Python's integer type isn't 64 bits. It's however many bits you need it to be. For example, I can compute 2 raised to the 128th power, without use of floating point math (and thus, get an exact answer):
This computation would not fit in a 64 bit integer. (For the non-Python programmers, there is a floating-point type, "float", which in CPython corresponds to an IEEE double.)> which is not very fast.
It's fast enough for most things. :-) There's numpy, and always C/C++/Rust if you need more speed.
Packing may be performed automatically, unfortunately in an implementation specific way.
In C, you can also specify the size of your fields within integer types:
struct{ unsigned char lowByte:3, midByte:3, highByteLowBits:2; };
And unfortunately too, the actual layour depends on the implementation.
So in most cases, you still have to implement bit shuffling yourself to produce the exact layout that is needed for external files.
If he was a front-end engineer I wouldn't be so surprised but he has 3 years experience working in telecoms, CompSci with networking module at UMass. Uses Wireshark on a regular basis.
A very odd knowledge gap in this domain. So yes I think many engineers don't know these things.
Maybe civil engineers.
Definitely not IT engineers because, well, it's in the name
For instance, the ones who breathe tends to take it for granted, yet there are more than 350 000 people who just discovered breathing for the first time today.
That said, I agree with the sentiment here. I can understand people brother having seen packing before. There are lots of programmers and engineers out there that simply haven't had a need. Especially ones who haven't dealt with binary formats or tight resource constraints.
http://hyperboleandahalf.wikia.com/wiki/Alot