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
Why can't I see bouncing of a switch on an oscilloscope?
LaTeX closing $ signs makes cursor jump
How to say job offer in Mandarin/Cantonese?
What are these boxed doors outside store fronts in New York?
What's the output of a record cartridge playing an out-of-speed record
Dragon forelimb placement
Approximately how much travel time was saved by the opening of the Suez Canal in 1869?
What would happen to a modern skyscraper if it rains micro blackholes?
Why does Kotter return in Welcome Back Kotter?
Is this a crack on the carbon frame?
Can a Warlock become Neutral Good?
What's the point of deactivating Num Lock on login screens?
Example of a continuous function that don't have a continuous extension
What are the differences between the usage of 'it' and 'they'?
Why "Having chlorophyll without photosynthesis is actually very dangerous" and "like living with a bomb"?
Is it tax fraud for an individual to declare non-taxable revenue as taxable income? (US tax laws)
Why dont electromagnetic waves interact with each other?
Languages that we cannot (dis)prove to be Context-Free
Can an x86 CPU running in real mode be considered to be basically an 8086 CPU?
How can bays and straits be determined in a procedurally generated map?
"You are your self first supporter", a more proper way to say it
If I cast Expeditious Retreat, can I Dash as a bonus action on the same turn?
The Two and the One
Did Shadowfax go to Valinor?
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
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
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