How to subtract two Big NumbersCalculate distance between two latitude-longitude points? (Haversine formula)How do you set, clear, and toggle a single bit?How do I iterate over the words of a string?What is JavaScript's highest integer value that a number can go to without losing precision?Determine Whether Two Date Ranges OverlapHow can I profile C++ code running on Linux?How to check if a number is a power of 2How to sum array of numbers in Ruby?Easy interview question got harder: given numbers 1..100, find the missing number(s)Divide a number by 3 without using *, /, +, -, % operators
Symbol used to indicate indivisibility
How should I respond when I lied about my education and the company finds out through background check?
Redundant comparison & "if" before assignment
The IT department bottlenecks progress. How should I handle this?
Is there any references on the tensor product of presentable (1-)categories?
Is the U.S. Code copyrighted by the Government?
What does "Scientists rise up against statistical significance" mean? (Comment in Nature)
Is it possible to have a strip of cold climate in the middle of a planet?
Closed-form expression for certain product
Why did the Mercure fail?
Biological Blimps: Propulsion
It grows, but water kills it
What is Cash Advance APR?
What should you do if you miss a job interview (deliberately)?
Is it improper etiquette to ask your opponent what his/her rating is before the game?
What is the evidence for the "tyranny of the majority problem" in a direct democracy context?
Did Swami Prabhupada reject Advaita?
Travelling outside the UK without a passport
Why Shazam when there is already Superman?
Can I sign legal documents with a smiley face?
Why did the EU agree to delay the Brexit deadline?
Did arcade monitors have same pixel aspect ratio as TV sets?
Which one is correct as adjective “protruding” or “protruded”?
Delivering sarcasm
How to subtract two Big Numbers
Calculate distance between two latitude-longitude points? (Haversine formula)How do you set, clear, and toggle a single bit?How do I iterate over the words of a string?What is JavaScript's highest integer value that a number can go to without losing precision?Determine Whether Two Date Ranges OverlapHow can I profile C++ code running on Linux?How to check if a number is a power of 2How to sum array of numbers in Ruby?Easy interview question got harder: given numbers 1..100, find the missing number(s)Divide a number by 3 without using *, /, +, -, % operators
I am trying to subtract 2 very large ints / big nums, but I have run into an issue. My code works for subtractions like 123 - 94, 5 - 29 but I can't seem to get around edge cases. For example 13 - 15 should result in -2. But if I do num1 - num2 - borrow + 10 on the first digit I get 8 and borrow becomes 1. Moving on to the last digit I end up with 1 - 1 - borrow(=1) which leaves me with -1 therefor my end result is -18 instead of being -2.
Here is my code for the subtraction:
//Infint is the class for the very large number
Infint Infint::sub(Infint other)
string result;
Infint i1 = *this;
Infint i2 = other;
if (int(i1._numberstr.length() - i2._numberstr.length()) < 0)
Infint(result) = i2 - i1;
result._numberstr.insert(result._numberstr.begin(), '-');
return result;
else if (i1._numberstr.length() - i2._numberstr.length() > 0)
int diff = i1._numberstr.length() - i2._numberstr.length();
for (int i = diff; i > 0 ; --i)
i2._numberstr.insert(i2._numberstr.begin(), '0');
int borrow = 0;
int i = i2._numberstr.length() - 1;
for (; i >= 0 ; --i)
int sub = (i1._numberstr[i] - '0') - (i2._numberstr[i] - '0') - borrow;
if (sub < 0)
sub += 10;
borrow = 1;
else
borrow = 0;
result.insert(0, to_string(sub));
while (i > 0)
result.insert(result.begin(), i1._numberstr[i1._numberstr.length() - i]);
--i;
int j = 0;
while (result[j] == '0')
j++;
result.erase(0, j);
if (borrow == 1)
result.insert(result.begin(), '-');
return Infint(result);
Would you kindly help me understand the errors or mistakes in logic I have made ?
c++ math integer-arithmetic
asked Mar 8 at 4:30
Kai.GKai.G
185
|
show 14 more comments
I am trying to subtract 2 very large ints / big nums, but I have run into an issue. My code works for subtractions like 123 - 94, 5 - 29 but I can't seem to get around edge cases. For example 13 - 15 should result in -2. But if I do num1 - num2 - borrow + 10 on the first digit I get 8 and borrow becomes 1. Moving on to the last digit I end up with 1 - 1 - borrow(=1) which leaves me with -1 therefor my end result is -18 instead of being -2.
Here is my code for the subtraction:
//Infint is the class for the very large number
Infint Infint::sub(Infint other)
string result;
Infint i1 = *this;
Infint i2 = other;
if (int(i1._numberstr.length() - i2._numberstr.length()) < 0)
Infint(result) = i2 - i1;
result._numberstr.insert(result._numberstr.begin(), '-');
return result;
else if (i1._numberstr.length() - i2._numberstr.length() > 0)
int diff = i1._numberstr.length() - i2._numberstr.length();
for (int i = diff; i > 0 ; --i)
i2._numberstr.insert(i2._numberstr.begin(), '0');
int borrow = 0;
int i = i2._numberstr.length() - 1;
for (; i >= 0 ; --i)
int sub = (i1._numberstr[i] - '0') - (i2._numberstr[i] - '0') - borrow;
if (sub < 0)
sub += 10;
borrow = 1;
else
borrow = 0;
result.insert(0, to_string(sub));
while (i > 0)
result.insert(result.begin(), i1._numberstr[i1._numberstr.length() - i]);
--i;
int j = 0;
while (result[j] == '0')
j++;
result.erase(0, j);
if (borrow == 1)
result.insert(result.begin(), '-');
return Infint(result);
Would you kindly help me understand the errors or mistakes in logic I have made ?
c++ math integer-arithmetic
asked Mar 8 at 4:30
Kai.GKai.G
185
1
13 - 15-- Why is this an "edge case" but5 - 29isn't an "edge case"? Looks like you need to review your entire logic on paper first before writing any code.
– PaulMcKenzie
Mar 8 at 4:46
1
Then make the numbers the same size by adding leading zeros to the smaller number before subtracting. Have you considered that? Then if you did that, there would be no difference at all in how you subtracted the number, since the sizes would always be the same.
– PaulMcKenzie
Mar 8 at 4:56
1
In calculating13 - 15, you calculated the units digit as8and the tens digit as-1. Shouldn't that result in-18? You wrote-12.-18makes sense in its own way, because-10 + 8is-2.
– Raymond Chen
Mar 8 at 5:00
1
@Kai.G Forget about negative numbers for the moment. Does your code work if the subtraction results in a positive number or 0? If not, get that to work first. Once you get that to work, then the issue is what to do once you get to the most significant digit and then to determine the sign of the final answer.
– PaulMcKenzie
Mar 8 at 5:04
1
Not just those numbers. What about 23 - 18, where you are forced to make borrowing to occur? Or 101 - 89?
– PaulMcKenzie
Mar 8 at 5:09
|
show 14 more comments
I am trying to subtract 2 very large ints / big nums, but I have run into an issue. My code works for subtractions like 123 - 94, 5 - 29 but I can't seem to get around edge cases. For example 13 - 15 should result in -2. But if I do num1 - num2 - borrow + 10 on the first digit I get 8 and borrow becomes 1. Moving on to the last digit I end up with 1 - 1 - borrow(=1) which leaves me with -1 therefor my end result is -18 instead of being -2.
Here is my code for the subtraction:
//Infint is the class for the very large number
Infint Infint::sub(Infint other)
string result;
Infint i1 = *this;
Infint i2 = other;
if (int(i1._numberstr.length() - i2._numberstr.length()) < 0)
Infint(result) = i2 - i1;
result._numberstr.insert(result._numberstr.begin(), '-');
return result;
else if (i1._numberstr.length() - i2._numberstr.length() > 0)
int diff = i1._numberstr.length() - i2._numberstr.length();
for (int i = diff; i > 0 ; --i)
i2._numberstr.insert(i2._numberstr.begin(), '0');
int borrow = 0;
int i = i2._numberstr.length() - 1;
for (; i >= 0 ; --i)
int sub = (i1._numberstr[i] - '0') - (i2._numberstr[i] - '0') - borrow;
if (sub < 0)
sub += 10;
borrow = 1;
else
borrow = 0;
result.insert(0, to_string(sub));
while (i > 0)
result.insert(result.begin(), i1._numberstr[i1._numberstr.length() - i]);
--i;
int j = 0;
while (result[j] == '0')
j++;
result.erase(0, j);
if (borrow == 1)
result.insert(result.begin(), '-');
return Infint(result);
Would you kindly help me understand the errors or mistakes in logic I have made ?
c++ math integer-arithmetic
asked Mar 8 at 4:30
Kai.GKai.G
185
I am trying to subtract 2 very large ints / big nums, but I have run into an issue. My code works for subtractions like 123 - 94, 5 - 29 but I can't seem to get around edge cases. For example 13 - 15 should result in -2. But if I do num1 - num2 - borrow + 10 on the first digit I get 8 and borrow becomes 1. Moving on to the last digit I end up with 1 - 1 - borrow(=1) which leaves me with -1 therefor my end result is -18 instead of being -2.
Here is my code for the subtraction:
//Infint is the class for the very large number
Infint Infint::sub(Infint other)
string result;
Infint i1 = *this;
Infint i2 = other;
if (int(i1._numberstr.length() - i2._numberstr.length()) < 0)
Infint(result) = i2 - i1;
result._numberstr.insert(result._numberstr.begin(), '-');
return result;
else if (i1._numberstr.length() - i2._numberstr.length() > 0)
int diff = i1._numberstr.length() - i2._numberstr.length();
for (int i = diff; i > 0 ; --i)
i2._numberstr.insert(i2._numberstr.begin(), '0');
int borrow = 0;
int i = i2._numberstr.length() - 1;
for (; i >= 0 ; --i)
int sub = (i1._numberstr[i] - '0') - (i2._numberstr[i] - '0') - borrow;
if (sub < 0)
sub += 10;
borrow = 1;
else
borrow = 0;
result.insert(0, to_string(sub));
while (i > 0)
result.insert(result.begin(), i1._numberstr[i1._numberstr.length() - i]);
--i;
int j = 0;
while (result[j] == '0')
j++;
result.erase(0, j);
if (borrow == 1)
result.insert(result.begin(), '-');
return Infint(result);
Would you kindly help me understand the errors or mistakes in logic I have made ?
c++ math integer-arithmetic
c++ math integer-arithmetic
asked Mar 8 at 4:30
Kai.GKai.G
185
asked Mar 8 at 4:30
Kai.GKai.G
185
edited Mar 8 at 5:02
Kai.G
asked Mar 8 at 4:30
Kai.GKai.G
185
asked Mar 8 at 4:30
Kai.GKai.G
185
asked Mar 8 at 4:30
Kai.GKai.G
185
185
1
13 - 15-- Why is this an "edge case" but5 - 29isn't an "edge case"? Looks like you need to review your entire logic on paper first before writing any code.
– PaulMcKenzie
Mar 8 at 4:46
1
Then make the numbers the same size by adding leading zeros to the smaller number before subtracting. Have you considered that? Then if you did that, there would be no difference at all in how you subtracted the number, since the sizes would always be the same.
– PaulMcKenzie
Mar 8 at 4:56
1
In calculating13 - 15, you calculated the units digit as8and the tens digit as-1. Shouldn't that result in-18? You wrote-12.-18makes sense in its own way, because-10 + 8is-2.
– Raymond Chen
Mar 8 at 5:00
1
@Kai.G Forget about negative numbers for the moment. Does your code work if the subtraction results in a positive number or 0? If not, get that to work first. Once you get that to work, then the issue is what to do once you get to the most significant digit and then to determine the sign of the final answer.
– PaulMcKenzie
Mar 8 at 5:04
1
Not just those numbers. What about 23 - 18, where you are forced to make borrowing to occur? Or 101 - 89?
– PaulMcKenzie
Mar 8 at 5:09
|
show 14 more comments
1
13 - 15-- Why is this an "edge case" but5 - 29isn't an "edge case"? Looks like you need to review your entire logic on paper first before writing any code.
– PaulMcKenzie
Mar 8 at 4:46
1
Then make the numbers the same size by adding leading zeros to the smaller number before subtracting. Have you considered that? Then if you did that, there would be no difference at all in how you subtracted the number, since the sizes would always be the same.
– PaulMcKenzie
Mar 8 at 4:56
1
In calculating13 - 15, you calculated the units digit as8and the tens digit as-1. Shouldn't that result in-18? You wrote-12.-18makes sense in its own way, because-10 + 8is-2.
– Raymond Chen
Mar 8 at 5:00
1
@Kai.G Forget about negative numbers for the moment. Does your code work if the subtraction results in a positive number or 0? If not, get that to work first. Once you get that to work, then the issue is what to do once you get to the most significant digit and then to determine the sign of the final answer.
– PaulMcKenzie
Mar 8 at 5:04
1
Not just those numbers. What about 23 - 18, where you are forced to make borrowing to occur? Or 101 - 89?
– PaulMcKenzie
Mar 8 at 5:09
1
1
13 - 15 -- Why is this an "edge case" but 5 - 29 isn't an "edge case"? Looks like you need to review your entire logic on paper first before writing any code.– PaulMcKenzie
Mar 8 at 4:46
13 - 15 -- Why is this an "edge case" but 5 - 29 isn't an "edge case"? Looks like you need to review your entire logic on paper first before writing any code.– PaulMcKenzie
Mar 8 at 4:46
1
1
Then make the numbers the same size by adding leading zeros to the smaller number before subtracting. Have you considered that? Then if you did that, there would be no difference at all in how you subtracted the number, since the sizes would always be the same.
– PaulMcKenzie
Mar 8 at 4:56
Then make the numbers the same size by adding leading zeros to the smaller number before subtracting. Have you considered that? Then if you did that, there would be no difference at all in how you subtracted the number, since the sizes would always be the same.
– PaulMcKenzie
Mar 8 at 4:56
1
1
In calculating
13 - 15, you calculated the units digit as 8 and the tens digit as -1. Shouldn't that result in -18? You wrote -12. -18 makes sense in its own way, because -10 + 8 is -2.– Raymond Chen
Mar 8 at 5:00
In calculating
13 - 15, you calculated the units digit as 8 and the tens digit as -1. Shouldn't that result in -18? You wrote -12. -18 makes sense in its own way, because -10 + 8 is -2.– Raymond Chen
Mar 8 at 5:00
1
1
@Kai.G Forget about negative numbers for the moment. Does your code work if the subtraction results in a positive number or 0? If not, get that to work first. Once you get that to work, then the issue is what to do once you get to the most significant digit and then to determine the sign of the final answer.
– PaulMcKenzie
Mar 8 at 5:04
@Kai.G Forget about negative numbers for the moment. Does your code work if the subtraction results in a positive number or 0? If not, get that to work first. Once you get that to work, then the issue is what to do once you get to the most significant digit and then to determine the sign of the final answer.
– PaulMcKenzie
Mar 8 at 5:04
1
1
Not just those numbers. What about 23 - 18, where you are forced to make borrowing to occur? Or 101 - 89?
– PaulMcKenzie
Mar 8 at 5:09
Not just those numbers. What about 23 - 18, where you are forced to make borrowing to occur? Or 101 - 89?
– PaulMcKenzie
Mar 8 at 5:09
|
show 14 more comments
1 Answer
1
active
oldest
votes
Since you got 8 at the 1s position and -1 at the 10s position. the sum of these two is -10 + 8 = -2, the correct answer (instead of -10 - 8 = -18, which is wrong).
EDIT: To systematically derive the correct answer, if you find the highest-digit difference to be negative, distribute the minus sign to all digits. Suppose the per-digit differences of two n-digit values are
an-1, ..., a0
with aj be the difference at digit of 10j, and you find that an-1 < 0. Then total difference of the two numbers could be calculated as
-1 * (-an-1 * 10n-1 + ... + -a0)
It should be fairly straight-forward to derive the correct (negative) answer by going through the sum from 10n-1 down to 1s.
answered Mar 8 at 5:08
EdyEdy
36918
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
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
,
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%2fstackoverflow.com%2fquestions%2f55056748%2fhow-to-subtract-two-big-numbers%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Since you got 8 at the 1s position and -1 at the 10s position. the sum of these two is -10 + 8 = -2, the correct answer (instead of -10 - 8 = -18, which is wrong).
EDIT: To systematically derive the correct answer, if you find the highest-digit difference to be negative, distribute the minus sign to all digits. Suppose the per-digit differences of two n-digit values are
an-1, ..., a0
with aj be the difference at digit of 10j, and you find that an-1 < 0. Then total difference of the two numbers could be calculated as
-1 * (-an-1 * 10n-1 + ... + -a0)
It should be fairly straight-forward to derive the correct (negative) answer by going through the sum from 10n-1 down to 1s.
answered Mar 8 at 5:08
EdyEdy
36918
add a comment |
Since you got 8 at the 1s position and -1 at the 10s position. the sum of these two is -10 + 8 = -2, the correct answer (instead of -10 - 8 = -18, which is wrong).
EDIT: To systematically derive the correct answer, if you find the highest-digit difference to be negative, distribute the minus sign to all digits. Suppose the per-digit differences of two n-digit values are
an-1, ..., a0
with aj be the difference at digit of 10j, and you find that an-1 < 0. Then total difference of the two numbers could be calculated as
-1 * (-an-1 * 10n-1 + ... + -a0)
It should be fairly straight-forward to derive the correct (negative) answer by going through the sum from 10n-1 down to 1s.
answered Mar 8 at 5:08
EdyEdy
36918
add a comment |
Since you got 8 at the 1s position and -1 at the 10s position. the sum of these two is -10 + 8 = -2, the correct answer (instead of -10 - 8 = -18, which is wrong).
EDIT: To systematically derive the correct answer, if you find the highest-digit difference to be negative, distribute the minus sign to all digits. Suppose the per-digit differences of two n-digit values are
an-1, ..., a0
with aj be the difference at digit of 10j, and you find that an-1 < 0. Then total difference of the two numbers could be calculated as
-1 * (-an-1 * 10n-1 + ... + -a0)
It should be fairly straight-forward to derive the correct (negative) answer by going through the sum from 10n-1 down to 1s.
answered Mar 8 at 5:08
EdyEdy
36918
Since you got 8 at the 1s position and -1 at the 10s position. the sum of these two is -10 + 8 = -2, the correct answer (instead of -10 - 8 = -18, which is wrong).
EDIT: To systematically derive the correct answer, if you find the highest-digit difference to be negative, distribute the minus sign to all digits. Suppose the per-digit differences of two n-digit values are
an-1, ..., a0
with aj be the difference at digit of 10j, and you find that an-1 < 0. Then total difference of the two numbers could be calculated as
-1 * (-an-1 * 10n-1 + ... + -a0)
It should be fairly straight-forward to derive the correct (negative) answer by going through the sum from 10n-1 down to 1s.
answered Mar 8 at 5:08
EdyEdy
36918
edited Mar 8 at 5:21
answered Mar 8 at 5:08
EdyEdy
36918
answered Mar 8 at 5:08
EdyEdy
36918
answered Mar 8 at 5:08
EdyEdy
36918
36918
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f55056748%2fhow-to-subtract-two-big-numbers%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
1
13 - 15-- Why is this an "edge case" but5 - 29isn't an "edge case"? Looks like you need to review your entire logic on paper first before writing any code.– PaulMcKenzie
Mar 8 at 4:46
1
Then make the numbers the same size by adding leading zeros to the smaller number before subtracting. Have you considered that? Then if you did that, there would be no difference at all in how you subtracted the number, since the sizes would always be the same.
– PaulMcKenzie
Mar 8 at 4:56
1
In calculating
13 - 15, you calculated the units digit as8and the tens digit as-1. Shouldn't that result in-18? You wrote-12.-18makes sense in its own way, because-10 + 8is-2.– Raymond Chen
Mar 8 at 5:00
1
@Kai.G Forget about negative numbers for the moment. Does your code work if the subtraction results in a positive number or 0? If not, get that to work first. Once you get that to work, then the issue is what to do once you get to the most significant digit and then to determine the sign of the final answer.
– PaulMcKenzie
Mar 8 at 5:04
1
Not just those numbers. What about 23 - 18, where you are forced to make borrowing to occur? Or 101 - 89?
– PaulMcKenzie
Mar 8 at 5:09