5
\$\begingroup\$

I want to check the truth of A + B - (A & B) == A | B for N-bit numbers. For example, here's a "truth" table for 2-bit numbers. (I know I'm taking liberty with the concept of a "truth" table.)

Truth table for A + B - (A & B) == A | B

Here's the simple code I threw together in Python.

def check_truth(bits):    

    for x in range(2**bits): 
        for y in range(bits*2):
            if x + y - (x & y) != x | y:
                return "False for {} bits".format(bits)

    return "True for {} bits".format(bits)

It spits out the correct answer, but it's obviously really inefficient. I am not good at algorithm analysis, but it's something like \$O(2^N)\$ right?

It's pretty much just a one-time-use function, but I'm curious how it could be improved. For example, I figure you could skip over number pairs that had been tested before. Any other ideas?

\$\endgroup\$
  • 2
    \$\begingroup\$ Why do x and y have different upper bounds? \$\endgroup\$ – 200_success Jun 23 '16 at 5:15
  • \$\begingroup\$ Because I'm a dummy I guess \$\endgroup\$ – galois Jun 24 '16 at 0:55
8
\$\begingroup\$
  1. Make the function return True or False.
  2. You can use all and a generator comprehension instead of returning early.
  3. You should make the range have the same input.

Putting these together you can get:

def check_truth(bits):
    return all(
        x + y == (x | y) + (x & y)
        for x in range(bits ** 2)
        for y in range(bits ** 2)
    )

print("{} for {} bits".format(check_truth(bits), bits))

The simplest way to prove:

$$x + y = (x \land y) + (x \lor y)$$

Is to think of integers as a bunch of wires that are passed to an infinite full adder. Due to how full adders work, they will not care how the bits are placed, as it makes no logical difference to its functionality. So \$010 + 101 = 111 + 000\$, which means as long as we know there are the same amount of bits on each section of the equation, then we know they are the same. Since we know \$a = x \lor y\$ and \$b = x \land y\$, we can test if there are any missing or new bits. And so using the following 'table' shows that each level will have the same amount of bits:

$$ x, y, a, b\\ 0, 0, 0, 0\\ 1, 0, 1, 0\\ 0, 1, 1, 0\\ 1, 1, 1, 1\\ $$

And so to get the best performance we can re-write check_truth:

def check_truth(bits):
    return True

To make a more compelling argument, we could sub \$a\$ and \$b\$ into a full adder equation, and show there's no difference, but if you think about this logically you should notice it's always true.

$$ S = C \oplus (A \oplus B)\\ C_1 = ((A \oplus B) \land C) \lor (A \land B) $$

Sub \$A = x \lor y\$ and \$B = x \land y\$:

$$ S = C \oplus ((x \lor y) \oplus (x \land y))\\ C_1 = (((x \lor y) \oplus (x \land y)) \land C) \lor ((x \lor y) \land (x \land y)) $$

Simplify some things:

$$ (x \lor y) \oplus (x \land y) = x \oplus y\\ (x \lor y) \land (x \land y) = x \land y $$

Sub simplified versions into main function:

$$ S = C \oplus (x \oplus y)\\ C_1 = ((x \oplus y) \land C) \lor (x \land y) $$

See that it works the same way.

\$\endgroup\$
  • \$\begingroup\$ This is excellent, and totally solved the initial problem of proving it in general. Thanks \$\endgroup\$ – galois Jun 24 '16 at 0:55
0
\$\begingroup\$

If you are looking for performance, you might want to use NumPy module that supports broadcasting to perform operations in a vectorized manner at Python level. For our case, there is no dependency at all between iterations across those two nested loops and as such it should be very well suited to use NumPy's vectorized capabilities.

To start off, lets import the module : import numpy as np.

Let's look closely at your code.

1] You have two loops with iterators as :

for x in range(bits**2): 
    for y in range(bits**2):

On NumPy, we can store these ranges as two arrays :

X = np.arange(bits**2)
Y = np.arange(bits**2)

2] Next up, you have the conditional statement :

if x + y - (x & y) != x | y:

For this, we can create a 2D output boolean array that has all the conditional checks performed for all iterations across the two nested loops using range arrays X and Y stored earlier. To do such an expansion onto 2D, we need to extend one of the arrays as 2D by adding a new axis, for which we have a shorthand in None.

Thus, x + y would translate to X[:,None] + Y. Proceeding similarly for rest of the conditional statement code, we would have a translation for the complete conditional statement as :

if ((X[:,None] + Y) - (X[:,None] & Y) != (X[:,None] | Y)).any():

That's all!

So, for completeness, the full implementation would be -

def check_truth_vectorized(bits):   
    X = np.arange(bits**2)
    Y = np.arange(bits**2)
    if ((X[:,None] + Y) - (X[:,None] & Y) != (X[:,None] | Y)).any():
        return "False for {} bits".format(bits)
    return "True for {} bits".format(bits)

Let's do a runtime test against the original code and check if there's any speedup, hopefully there should be some! We would be varying number of bits as 2, 5, 10, 15 to see how it scales up.

In [11]: %timeit check_truth(2)
100000 loops, best of 3: 5.87 µs per loop

In [12]: %timeit check_truth_vectorized(2)
10000 loops, best of 3: 37 µs per loop

In [13]: %timeit check_truth(5)
10000 loops, best of 3: 103 µs per loop

In [14]: %timeit check_truth_vectorized(5)
10000 loops, best of 3: 51.3 µs per loop

In [15]: %timeit check_truth(10)
1000 loops, best of 3: 1.44 ms per loop

In [16]: %timeit check_truth_vectorized(10)
10000 loops, best of 3: 178 µs per loop

In [17]: %timeit check_truth(15)
100 loops, best of 3: 7.21 ms per loop

In [18]: %timeit check_truth_vectorized(15)
1000 loops, best of 3: 799 µs per loop

So, we are seeing huge speedups for the NumPy based vectorized codes for no. of bits as 5 onwards and seems to scale well!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.