3 ms·
I was writing a program similar to the 4-coloring problem. I represented colors as 2-bits (color 0, 1, 2, and 3). I also created a bitmask representation of re
by dragontamer 8y ago
I was writing a program similar to the 4-coloring problem. I represented colors as 2-bits (color 0, 1, 2, and 3).
I also created a bitmask representation of relations, which would represent 1-variable in 4-bits, 2-variables in 16-bits, 3-variables in 64-bits, and 4-variables in 256 bits.
Ex: Texas / Oklahoma / Arizona relation would be a 64-bit number ("true" means a color-set is in the relation. "False" means the color-set is not in the relation), and extracting or packing the data into these three variables would be a pdep or pext operation.
Extracting data (pext) would be a "select" operation. While PDEP + OR would be a "update" operation over the relation. I've written a join for fun, but I haven't gotten much further than that. First, because pdep / pext were slow on my machine. Second, because I figured out an alternative solution to my particular problem.
---------
I think the pext / pdep instructions have HUGE implications to 4-coloring problem, 3-SAT, Constraint Solvers, etc. etc. More researchers probably should look into those two instructions.
Just look at Binary Decision Diagrams, and other such combinatorial data structures, and you can definitely see the potential uses of PEXT / PDEP all over the place.
https://en.wikipedia.org/wiki/Binary_decision_diagram https://en.wikipedia.org/wiki/Binary_decision_diagram
- itissid 8y agoWouldn't this sort of thing be also very common in applying bit map masks to bit arrays in frameworks like numpy?
- dragontamer 8y agoI can't say that I've used numpy before. But this function looks similar to pext / pdep: https://docs.scipy.org/doc/numpy-1.15.0/reference/generated/numpy.packbits.html https://docs.scipy.org/doc/numpy-1.15.0/reference/generated/...