Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
With an adder circuit where A+B=C, I am trying to have a method to determine when C will be valid based on a change in A or B. I know that it is possible to just determine the longest the circuit would take, but is it possible to determine if the result (C) is equal to A+B. This would speed up the result of the operation as if A and B had a small change, C could be determined faster than a full adder cycle.
In general: If you know A, B, and C, can you determine if A+B=C faster than adding A+B
Consider computing $\overline{a_{n-1}\ldots a_0}+\overline{b_{n-1}\ldots b_0}=\overline{c_{n-1}\ldots c_0}$. If the last $(k+1)$-bits are correctly computed, then $c_{k+1}$ is correct if and only if $$\big((a_k\wedge b_k)\vee((a_k\oplus b_k)\wedge \neg c_k)\big)\oplus a_{k+1}\oplus b_{k+1}=c_{k+1}.$$ That is because the first part, $(a_k\wedge b_k)\vee((a_k\oplus b_k)\wedge \neg c_k)$ indicates whether there is a carry-over. So you can check the correctness for each bit in parallel.
However, in theory both questions require $\Omega(\log n)$-depth bounded fan-in circuits. Good thing is, for the checking problem the $\log n$ part in the circuit depth is only for a $n$-bit $\textsf{AND}$, so I think it is a constant boost in the performance.
In theory, there are other ways to check the result without re-generating it, using modular arithmetic. In practice, these methods probably won't be useful at all, but I'll outline what I'm talking about anyway.
Remember the "cast out 9's" method for checking your arithmetic? From a mathematical perspective, "casting out 9's" amounts to reducing each number modulo 9. Then, we check whether $(A \bmod 9) + (B \bmod 9) = (C \bmod 9)$. If the result was generated correctly (i.e., if $A+B=C$), this check will always succeed. If the result was generated incorrectly (i.e., if $A+B \ne C$), then the check might fail.
We can generalize this, as follows. Pick a random $k$-bit prime, call it $p$. Reduce $A$, $B$, and $C$ modulo $p$. Now, check whether $(A \bmod p) + (B \bmod p) = (C \bmod p)$. If this check fails, then we're sure that $C$ was generated incorrectly. If this check succeeds, then with high probability $C$ was generated correctly. In particular, if we have $A,B,C$ such that $A+B \ne C$, then with high probability (over the choice of $p$) we'll have $(A \bmod p) + (B \bmod p) \ne (C \bmod p)$.
How high is the probability of detecting an error? Basically, it is exponentially small in $k$. The probability can be bounded explicitly using the fact that an error goes undetected iff $A+B-C$ is a multiple of $p$ and using an upper bound on the number of $k$-bit prime divisors that $A+B-C$ can have (at most $2 \log n / \log k$, where $n$ is the number of bits in $A,B,C$) and using the prime number theorem (there are at least $2^k/k$ $k$-bit prime numbers). You end up with a probability that's at most something like $(2 k \log n / \log k)/2^k$, and this is asymptotically exponentially decreasing in $k$.
In particular, if you want the probability of an error going undetected to be at most $1/2^t$, it suffices to choose $k=O(t \log t \log \log n)$. In practice, if $t \ge 64$, the chance of an undetected error is far smaller than the chance of a cosmic ray messing everything up. So, if we think of $t$ as constant, then we need a $k=O(\log \log n)$-bit prime.
Is this faster than just doing the addition? I doubt it.
So basically checking if A+B=C is the decision problem version of the function problem of finding the value of A+B. I guess the decision problem can be solved by subtraction i.e A-C and then comparing the result with B. The circuit for the full subtractor is more complex (having more number of gates) then the full adder. So, finding the addition value is much more easy then checking the addition result.
