4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Welcome to CS.SE! Are you looking for a deterministic algorithm (one that is never wrong)? Or would you be willing to accept a randomized algorithm (one where the probability of being wrong is far, far less than the chance of being struck by a cosmic ray; or where the probability of being wrong is exponentially small)? And, how large are the numbers $A,B,C$ (in bits), roughly? $\endgroup$
    – D.W.
    Nov 23, 2016 at 3:34
  • $\begingroup$ Thank you. I originally was only looking for deterministic, but would be interested in non-deterministic. These numbers would normally be <=64 bits. $\endgroup$ Nov 23, 2016 at 12:23
  • $\begingroup$ Can you clarify your model of computation and what counts as "faster"/"slower"? Are you talking about latency, i.e., circuit depth? Number of gates, i.e., circuit size? Something else? $\endgroup$
    – D.W.
    Nov 23, 2016 at 17:49
  • $\begingroup$ By faster, I am talking about latency on the scale of gates. $\endgroup$ Nov 23, 2016 at 19:24

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You may reduce the time a tiny bit by replacing $(a_k\oplus b_k)$ with $a_k \vee b_k$. $\endgroup$
    – gnasher729
    Nov 24, 2016 at 23:20
  • $\begingroup$ And by moving the two xor's to the right hand side - ... = $a_{k+1}\oplus b_{k+1}\oplus c_{k+1})$ so that left and right hand side can be calculated in parallel. $\endgroup$
    – gnasher729
    Nov 24, 2016 at 23:31
2
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ The poster asked if there was a better solution, not a worse one. And I don't know what makes you think a subtractor is any more difficult than an adder. $\endgroup$
    – gnasher729
    Nov 23, 2016 at 8:47
  • $\begingroup$ The question is about whether checking A+B=C is efficient or computing A+B is efficient in terms of designing a logical circuit. You can check on internet about the circuit diagrams of both full added and full subtractor and check the number of logic gates required for each $\endgroup$
    – Ankur
    Nov 23, 2016 at 9:52
  • $\begingroup$ The question was whether there are shortcuts that let you determine whether A+B=C, without determining A+B itself. That's an essential question that is repeated everywhere - given any problem, is there a way to solve the problem faster than by solving obvious sub-problems? Example: By definition, a prime number is a positive integer with exactly two divisors. Can we determine whether p is a prime number without determining the number of divisors? $\endgroup$
    – gnasher729
    Nov 24, 2016 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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