5

I have two binary integers, x0 and x1 that are 8 bits (so they span from 0 to 255). This statement is always true about these numbers: x0 & x1 == 0. Here is an example:

bx0 = 100 # represented as 01100100 in binary
bx1 = 129 # represented as 10000001 in binary

So I need to do the following operation on these numbers. First, interpret these binary representations as ternary (base-3) numbers, as follows:

tx0 = ternary(bx0) # becomes  981 represented as 01100100 in ternary
tx1 = ternary(bx1) # becomes 2188 represented as 10000001 in ternary

Then, swap all of the 1 in the ternary representation of tx1 to 2:

tx1_swap = swap(tx1) # becomes 4376, represented as 20000002 in ternary

Then use a ternary version of OR on them to get the final combined number:

result = ternary_or(tx0, tx1_swap) # becomes 5357, represented as 21100102 in ternary

I don't need the ternary representation saved at any point, I only need the result, where for example result=5357. Of course I could code this by converting the numbers to binary, converting to ternary, etc.. but I need this operation to be fast because I am doing this many times in my code. What would a fast way to implement this in python?

Paul Terwilliger
  • 1,596
  • 1
  • 20
  • 45
  • 1
    Good luck with this, it doesn't sound like anything there would be built-in, optimized operations for. – Barmar Nov 07 '18 at 19:56
  • 2
    What have you tried so far, and what are the results that you find unsatisfactory? Have you tried your base case (converting and converting again) and timed it? – G. Anderson Nov 07 '18 at 19:57
  • 3
    Posting an example and the time you need to be under for that example would be useful. – Alex Nov 07 '18 at 19:58
  • 3
    This whole thing sounds very strange. What real-world application is there for replacing all the 1 with 2 in a ternary number? – Barmar Nov 07 '18 at 20:00
  • 1
    @Barmar Real world application: http://www.open-aurec.com/wbforum/viewtopic.php?t=5623 – Paul Terwilliger Nov 07 '18 at 20:00
  • 1
    What do you have in mind when you say "a ternary version of OR"? Can you draw a truth table for this operation? –  Nov 07 '18 at 20:07
  • @duskwuff after posting this I found out that `swap` is just multiplying by two and `ternary_or` is just addition... oops – Paul Terwilliger Nov 07 '18 at 20:11
  • 1
    @PaulTerwilliger Addition isn't OR-like; it can generate carries. –  Nov 07 '18 at 20:13
  • 1
    @duskwuff the way that the problem is generated there will never be any carries – Paul Terwilliger Nov 07 '18 at 20:15
  • tbh doing this operation (just straight as you've described it, no clever optimizations) in C would be blindingly fast. You could use Cython, ctypes, or SWIG if you needed a top level Python function...but it seems like the wrong type of problem for "speed" in Python. – Matt Messersmith Nov 07 '18 at 20:18
  • I've decided I'm going to use a lookup table for `ternary` because a list of 255 integers shouldn't be large in memory... and the other two operations are just multiplication by two and addition. Thanks for the comments, I want to give someone credit so if anyone wants to write-up that solution I'll give them the green check mark. If not I'll write it up myself. – Paul Terwilliger Nov 07 '18 at 20:23
  • 2
    Does `int(format(bx0, "b"), base=3) + 2 * int(format(bx1, "b"), base=3)` achieve what you ask for? – Mark Dickinson Nov 07 '18 at 20:32
  • Yep that works as well! @MarkDickinson – Paul Terwilliger Nov 07 '18 at 20:34
  • Ah, an X-Y problem. I probably wouldn't attack the black/white/both board problem using "ternary" numbers. It's obviously cumbersome and computers don't know how to work in radix 3. Perhaps better would be numbers consisting of 2-bit bit fields where the left bit was white and the right one black, or something like that. Computers like bit fields. – lurker Nov 07 '18 at 20:44
  • @lurker, one application would be if you want to store a table of values on an embedded device, you'd want to use as little memory as possible. For example, there are only 3^8 = 6561 possible positions for 8 ternary state squares. But if one uses your method, the look up table would have to have 4^8 = 65536 keys, roughly ten times bigger! – Andriy Makukha Dec 10 '18 at 09:52
  • @OhneKleidung yes that is true. Op didn't indicate they were trying to reduce memory footprint. – lurker Dec 10 '18 at 10:43
  • @lurker, yeah, I don't think it is a concern if one uses Python... But I need a similar solution for C/C++. – Andriy Makukha Dec 10 '18 at 10:50

2 Answers2

2

The fastest way to do this is probably with decimal addition:

a = 1100100
b = 10000001
result = int(str(a+2*b),3) #5357

You won't find ternary-wise operators in python (or any other language that I know of.) Since you need to go above bitwise operations, your next-fastest option is integer addition, which every computer on Earth is optimized to complete.

Other solutions that convert to ternary to get this done will require you to cast back and forth to strings which takes much longer than decimal addition. This only requires one string cast at the end, assuming you even need the decimal version of the final ternary number.

killian95
  • 803
  • 6
  • 11
1

Re-explanation for dummies like me:

A straightforward way to "encode" two binary mutually exclusive numbers (w & b == 0) in ternary would be:

white_black_empty = lambda w, b: int(format(b, 'b'), base=3) + \
                                 int(format(w, 'b').replace('1','2'), base=3)

Here are all possible 2-bit variants:

white_black_empty(0b00, 0b00) == 0
white_black_empty(0b00, 0b01) == 1
white_black_empty(0b01, 0b00) == 2
white_black_empty(0b00, 0b10) == 3
white_black_empty(0b00, 0b11) == 4
white_black_empty(0b01, 0b10) == 5
white_black_empty(0b10, 0b00) == 6
white_black_empty(0b10, 0b01) == 7
white_black_empty(0b11, 0b00) == 8

By observing that int(format(w, 'b').replace('1','2'), base=3) is actually equal to double of int(format(w, 'b'), base=3) (for example, 20220023 == 10110013*2), we get the solution that @Mark Dickinson posted in the comments above:

white_black_empty = lambda w, b: int(format(b, 'b'), base=3) + \
                                 int(format(w, 'b'), base=3)*2
Andriy Makukha
  • 7,580
  • 1
  • 38
  • 49