2

In long addition the overflow is carried across columns like so

$$ \begin{array}{cccc} & \tiny{1} & \tiny{1} & \\ & 3 & 5 & 8 \\ + & 2 & 9 & 6 \\ \hline \\ & 6 & 5 & 4 \\ \end{array} $$

I'm doing some crypto work at the moment and I need to perform an operation like long addition except the carries are disregarded:

$$ \require{cancel} \begin{array}{cccc} & \cancel{\tiny{1}} & \cancel{\tiny{1}} & \\ & 3 & 5 & 8 \\ + & 2 & 9 & 6 \\ \hline \\ & 5 & 4 & 4 \\ \end{array} $$

Is there a way to do this in a fixed number of steps? If the addends were in binary, I could do this in one step with a simple bitwise XOR. But in decimal, I'm finding I have to do it digit by digit, which is time consuming. I've been doodling around with things like 10's complement but I can't think of anything.

Also does this operation have a name? "Digitwise addition" doesn't seem to be a thing. It's a struggle to Google this because the keywords are so generic.

P.S. I'm also interested in long subtraction that disregards the borrows. :-)

jjs
  • 21
  • You'll have to be a bit more specific on what you're wanting to do. Talking about bitwise XOR being a single operation suggests you're wanting an efficient implementation of the base-10 version on a computer, but I'm not sure. – Kyle Miller Feb 01 '19 at 17:28
  • @KyleMiller. Ultimately that is exactly what I want, so maybe I've asked this in the wrong place. I felt that since this is such a simple operation that, working out each digit individually as if it were long addition, I might be missing some mathematical shortcut. – jjs Feb 01 '19 at 17:45
  • It would be helpful if you added the context which leads you to say that XOR and the usual addition count as single steps. Even XOR might be multiple steps if your numbers are big enough (say a hundred bits each). If your question is actually about SIMD, this is probably not the right site for the question, but what you can do is store a separate BCD digits across the sixteen lanes of an SSE register. This is sixteen digits that you can add in two instructions: unsigned add of two such registers followed by mod 10. Subtraction is (a+10-b)%10 across the lanes, to account for how % works. – Kyle Miller Feb 01 '19 at 17:57
  • @KyleMiller I was wondering at the possibility of there being a mathematical trick... like how if you want to add the numbers 1 to n, you could add them one by one, but it's easier if you know the answer is equal to n(n+1)/2 (pardon the bad analogy!).

    I wasn't considering SIMD but it's an interesting thought, and it's reassuring that your approach is to operate on the digits individually albeit in parallel.

    Thanks for the answers

     – jjs Feb 01 '19 at 20:02

0 Answers0