Memoized ncr recursive factorial problem not working for large inputs
I'm trying to calculate nck combinations problem using recursion and memoization. It is working well for small inputs. However, it is failing for large inputs.
ans = n! / ( (n-k)! * k! )
For 8C3, answer is 56. [working]
For 156C12, expected output is 281014969393251275 [not working]
How do I scale or optimize this?
Click here to run the code: http://cpp.sh/9ijiy
#include <iostream>
#include <map>
using namespace std;
long long int calls=0; // I know global vars are bad, but, i'm only using it for checking number of recursive calls
long long int fact(int n)
{
calls++;
static map<int, long long int> cache = {{0,1},{1,1}}; // factorial of 0 and 1 is 1
if(cache.find(n) == cache.end()) // if n is NOT found
{
long long int ans = (long long int)n*fact(n-1);
cache.insert(pair<int, long long int>(n,ans));
}
return cache[n];
}
long long int combin(int n, int k)
{
return fact(n)/(fact(n-k)*fact(k));
}
int main()
{
calls=0; cout << "8C3 is " << combin(8,6) << endl;
cout << "Number of calls is " << calls << endl;
calls=0; cout << "156C12 is " << combin(156,12) << endl;
cout << "Number of calls is " << calls << endl;
return 0;
}
c++ memoization
asked Nov 15 at 22:22
Manjunath
1531314
add a comment |
I'm trying to calculate nck combinations problem using recursion and memoization. It is working well for small inputs. However, it is failing for large inputs.
ans = n! / ( (n-k)! * k! )
For 8C3, answer is 56. [working]
For 156C12, expected output is 281014969393251275 [not working]
How do I scale or optimize this?
Click here to run the code: http://cpp.sh/9ijiy
#include <iostream>
#include <map>
using namespace std;
long long int calls=0; // I know global vars are bad, but, i'm only using it for checking number of recursive calls
long long int fact(int n)
{
calls++;
static map<int, long long int> cache = {{0,1},{1,1}}; // factorial of 0 and 1 is 1
if(cache.find(n) == cache.end()) // if n is NOT found
{
long long int ans = (long long int)n*fact(n-1);
cache.insert(pair<int, long long int>(n,ans));
}
return cache[n];
}
long long int combin(int n, int k)
{
return fact(n)/(fact(n-k)*fact(k));
}
int main()
{
calls=0; cout << "8C3 is " << combin(8,6) << endl;
cout << "Number of calls is " << calls << endl;
calls=0; cout << "156C12 is " << combin(156,12) << endl;
cout << "Number of calls is " << calls << endl;
return 0;
}
c++ memoization
asked Nov 15 at 22:22
Manjunath
1531314
add a comment |
I'm trying to calculate nck combinations problem using recursion and memoization. It is working well for small inputs. However, it is failing for large inputs.
ans = n! / ( (n-k)! * k! )
For 8C3, answer is 56. [working]
For 156C12, expected output is 281014969393251275 [not working]
How do I scale or optimize this?
Click here to run the code: http://cpp.sh/9ijiy
#include <iostream>
#include <map>
using namespace std;
long long int calls=0; // I know global vars are bad, but, i'm only using it for checking number of recursive calls
long long int fact(int n)
{
calls++;
static map<int, long long int> cache = {{0,1},{1,1}}; // factorial of 0 and 1 is 1
if(cache.find(n) == cache.end()) // if n is NOT found
{
long long int ans = (long long int)n*fact(n-1);
cache.insert(pair<int, long long int>(n,ans));
}
return cache[n];
}
long long int combin(int n, int k)
{
return fact(n)/(fact(n-k)*fact(k));
}
int main()
{
calls=0; cout << "8C3 is " << combin(8,6) << endl;
cout << "Number of calls is " << calls << endl;
calls=0; cout << "156C12 is " << combin(156,12) << endl;
cout << "Number of calls is " << calls << endl;
return 0;
}
c++ memoization
asked Nov 15 at 22:22
Manjunath
1531314
I'm trying to calculate nck combinations problem using recursion and memoization. It is working well for small inputs. However, it is failing for large inputs.
ans = n! / ( (n-k)! * k! )
For 8C3, answer is 56. [working]
For 156C12, expected output is 281014969393251275 [not working]
How do I scale or optimize this?
Click here to run the code: http://cpp.sh/9ijiy
#include <iostream>
#include <map>
using namespace std;
long long int calls=0; // I know global vars are bad, but, i'm only using it for checking number of recursive calls
long long int fact(int n)
{
calls++;
static map<int, long long int> cache = {{0,1},{1,1}}; // factorial of 0 and 1 is 1
if(cache.find(n) == cache.end()) // if n is NOT found
{
long long int ans = (long long int)n*fact(n-1);
cache.insert(pair<int, long long int>(n,ans));
}
return cache[n];
}
long long int combin(int n, int k)
{
return fact(n)/(fact(n-k)*fact(k));
}
int main()
{
calls=0; cout << "8C3 is " << combin(8,6) << endl;
cout << "Number of calls is " << calls << endl;
calls=0; cout << "156C12 is " << combin(156,12) << endl;
cout << "Number of calls is " << calls << endl;
return 0;
}
c++ memoization
c++ memoization
asked Nov 15 at 22:22
Manjunath
1531314
asked Nov 15 at 22:22
Manjunath
1531314
edited Nov 15 at 22:27
asked Nov 15 at 22:22
Manjunath
1531314
asked Nov 15 at 22:22
Manjunath
1531314
asked Nov 15 at 22:22
Manjunath
1531314
1531314
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Well, since you're having 156! along the way, which is 276 digits long (according to google) it's not going to fit in any of the default c++ data type for sure. The only solution I can think of is implementing some other, extending way of storing and operating on really big numbers. The first that comes to mind is implementing column multiplication (that thing from elementary school) and using strings (instead of long long) to store intermediate values in your cache. It's not gonna be efficient (of particularly pleasant to code), but since strings can hold infinitely (not really, but good enough) long sequence of characters it's possible to do.
answered Nov 15 at 22:43
vrtex
457
1
A better solution would be to rethink howcombinworks so as to avoid computing factorials of large numbers.
– 1201ProgramAlarm
Nov 16 at 0:39
Yes, that's what i need some help with. The range of long long int is 9223372036854775807 on my machine, i.e19 digits long. My final expected answer 156C12=281014969393251275 is18 digits long, within the limits of long long int
– Manjunath
Nov 16 at 14:33
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%2f53328706%2fmemoized-ncr-recursive-factorial-problem-not-working-for-large-inputs%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
Well, since you're having 156! along the way, which is 276 digits long (according to google) it's not going to fit in any of the default c++ data type for sure. The only solution I can think of is implementing some other, extending way of storing and operating on really big numbers. The first that comes to mind is implementing column multiplication (that thing from elementary school) and using strings (instead of long long) to store intermediate values in your cache. It's not gonna be efficient (of particularly pleasant to code), but since strings can hold infinitely (not really, but good enough) long sequence of characters it's possible to do.
answered Nov 15 at 22:43
vrtex
457
1
A better solution would be to rethink howcombinworks so as to avoid computing factorials of large numbers.
– 1201ProgramAlarm
Nov 16 at 0:39
Yes, that's what i need some help with. The range of long long int is 9223372036854775807 on my machine, i.e19 digits long. My final expected answer 156C12=281014969393251275 is18 digits long, within the limits of long long int
– Manjunath
Nov 16 at 14:33
add a comment |
Well, since you're having 156! along the way, which is 276 digits long (according to google) it's not going to fit in any of the default c++ data type for sure. The only solution I can think of is implementing some other, extending way of storing and operating on really big numbers. The first that comes to mind is implementing column multiplication (that thing from elementary school) and using strings (instead of long long) to store intermediate values in your cache. It's not gonna be efficient (of particularly pleasant to code), but since strings can hold infinitely (not really, but good enough) long sequence of characters it's possible to do.
answered Nov 15 at 22:43
vrtex
457
1
A better solution would be to rethink howcombinworks so as to avoid computing factorials of large numbers.
– 1201ProgramAlarm
Nov 16 at 0:39
Yes, that's what i need some help with. The range of long long int is 9223372036854775807 on my machine, i.e19 digits long. My final expected answer 156C12=281014969393251275 is18 digits long, within the limits of long long int
– Manjunath
Nov 16 at 14:33
add a comment |
Well, since you're having 156! along the way, which is 276 digits long (according to google) it's not going to fit in any of the default c++ data type for sure. The only solution I can think of is implementing some other, extending way of storing and operating on really big numbers. The first that comes to mind is implementing column multiplication (that thing from elementary school) and using strings (instead of long long) to store intermediate values in your cache. It's not gonna be efficient (of particularly pleasant to code), but since strings can hold infinitely (not really, but good enough) long sequence of characters it's possible to do.
answered Nov 15 at 22:43
vrtex
457
Well, since you're having 156! along the way, which is 276 digits long (according to google) it's not going to fit in any of the default c++ data type for sure. The only solution I can think of is implementing some other, extending way of storing and operating on really big numbers. The first that comes to mind is implementing column multiplication (that thing from elementary school) and using strings (instead of long long) to store intermediate values in your cache. It's not gonna be efficient (of particularly pleasant to code), but since strings can hold infinitely (not really, but good enough) long sequence of characters it's possible to do.
answered Nov 15 at 22:43
vrtex
457
answered Nov 15 at 22:43
vrtex
457
answered Nov 15 at 22:43
vrtex
457
answered Nov 15 at 22:43
vrtex
457
457
1
A better solution would be to rethink howcombinworks so as to avoid computing factorials of large numbers.
– 1201ProgramAlarm
Nov 16 at 0:39
Yes, that's what i need some help with. The range of long long int is 9223372036854775807 on my machine, i.e19 digits long. My final expected answer 156C12=281014969393251275 is18 digits long, within the limits of long long int
– Manjunath
Nov 16 at 14:33
add a comment |
1
A better solution would be to rethink howcombinworks so as to avoid computing factorials of large numbers.
– 1201ProgramAlarm
Nov 16 at 0:39
Yes, that's what i need some help with. The range of long long int is 9223372036854775807 on my machine, i.e19 digits long. My final expected answer 156C12=281014969393251275 is18 digits long, within the limits of long long int
– Manjunath
Nov 16 at 14:33
1
1
A better solution would be to rethink how
combin works so as to avoid computing factorials of large numbers.– 1201ProgramAlarm
Nov 16 at 0:39
A better solution would be to rethink how
combin works so as to avoid computing factorials of large numbers.– 1201ProgramAlarm
Nov 16 at 0:39
Yes, that's what i need some help with. The range of long long int is 9223372036854775807 on my machine, i.e
19 digits long. My final expected answer 156C12=281014969393251275 is 18 digits long, within the limits of long long int– Manjunath
Nov 16 at 14:33
Yes, that's what i need some help with. The range of long long int is 9223372036854775807 on my machine, i.e
19 digits long. My final expected answer 156C12=281014969393251275 is 18 digits long, within the limits of long long int– Manjunath
Nov 16 at 14:33
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2f53328706%2fmemoized-ncr-recursive-factorial-problem-not-working-for-large-inputs%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
