Mixing
Perform addition that disregards carries
$begingroup$
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. :-)
arithmetic
asked Feb 1 at 17:21
jjsjjs
112
$endgroup$
add a comment |
$begingroup$
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. :-)
arithmetic
asked Feb 1 at 17:21
jjsjjs
112
$endgroup$
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:28
$begingroup$
@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.
$endgroup$
– jjs
Feb 1 at 17:45
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:57
$begingroup$
@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
$endgroup$
– jjs
Feb 1 at 20:02
add a comment |
$begingroup$
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. :-)
arithmetic
asked Feb 1 at 17:21
jjsjjs
112
$endgroup$
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. :-)
arithmetic
arithmetic
asked Feb 1 at 17:21
jjsjjs
112
asked Feb 1 at 17:21
jjsjjs
112
edited Feb 1 at 17:28
jjs
asked Feb 1 at 17:21
jjsjjs
112
asked Feb 1 at 17:21
jjsjjs
112
asked Feb 1 at 17:21
jjsjjs
112
112
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:28
$begingroup$
@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.
$endgroup$
– jjs
Feb 1 at 17:45
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:57
$begingroup$
@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
$endgroup$
– jjs
Feb 1 at 20:02
add a comment |
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:28
$begingroup$
@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.
$endgroup$
– jjs
Feb 1 at 17:45
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:57
$begingroup$
@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
$endgroup$
– jjs
Feb 1 at 20:02
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:28
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:28
$begingroup$
@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.
$endgroup$
– jjs
Feb 1 at 17:45
$begingroup$
@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.
$endgroup$
– jjs
Feb 1 at 17:45
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:57
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:57
$begingroup$
@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
$endgroup$
– jjs
Feb 1 at 20:02
$begingroup$
@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
$endgroup$
– jjs
Feb 1 at 20:02
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3096495%2fperform-addition-that-disregards-carries%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3096495%2fperform-addition-that-disregards-carries%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:28
$begingroup$
@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.
$endgroup$
– jjs
Feb 1 at 17:45
$begingroup$
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.
$endgroup$
– Kyle Miller
Feb 1 at 17:57
$begingroup$
@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
$endgroup$
– jjs
Feb 1 at 20:02