Algorythm to find factoradic for given number n which works in time O(log n)
I have just written a code which does its job, but I have to optimize it to work in time O(log n). The problem is that I'm not sure whether its time complexity is good and if it's not, how should I fix it?
Factoradic representation of a number is a sequence sk, sk-1 ... s2, s1 that:
-> n = 1! * s1 + 2! * s2 + ... + k! * sk
-> si ≤ for i ∈ {1, 2, ..., k}
-> sk > 0
-> eg. 107 = 4! * 4 + 3! * 1 + 2! * 2 + 1! *1
My code:
unsigned long long int n;
unsigned long long int maxFact[21] = {0};
maxFact[0] = 1;
maxFact[1] = 1;
cout<<"Insert n: "; cin >> n;
int i = 2;
while (maxFact[i-1] * i <= n) // find higher factorial <= n
{
maxFact[i] = maxFact[i-1] * i;
i++;
}
cout << "Factoradic representation of " << n << ":" << endl;
while (i > 1)
{
cout << n / maxFact[i-1] << " ";
n = n % maxFact[i-1];
i--;
}
c++ runtime time-complexity big-o
edited Nov 28 '18 at 8:16
Bishal Gautam
835518
asked Nov 28 '18 at 0:47
whiskeyowhiskeyo
1013
add a comment |
I have just written a code which does its job, but I have to optimize it to work in time O(log n). The problem is that I'm not sure whether its time complexity is good and if it's not, how should I fix it?
Factoradic representation of a number is a sequence sk, sk-1 ... s2, s1 that:
-> n = 1! * s1 + 2! * s2 + ... + k! * sk
-> si ≤ for i ∈ {1, 2, ..., k}
-> sk > 0
-> eg. 107 = 4! * 4 + 3! * 1 + 2! * 2 + 1! *1
My code:
unsigned long long int n;
unsigned long long int maxFact[21] = {0};
maxFact[0] = 1;
maxFact[1] = 1;
cout<<"Insert n: "; cin >> n;
int i = 2;
while (maxFact[i-1] * i <= n) // find higher factorial <= n
{
maxFact[i] = maxFact[i-1] * i;
i++;
}
cout << "Factoradic representation of " << n << ":" << endl;
while (i > 1)
{
cout << n / maxFact[i-1] << " ";
n = n % maxFact[i-1];
i--;
}
c++ runtime time-complexity big-o
edited Nov 28 '18 at 8:16
Bishal Gautam
835518
asked Nov 28 '18 at 0:47
whiskeyowhiskeyo
1013
1
It might help if you define what a "factoradic" representation of a number is.
– hnefatl
Nov 28 '18 at 0:50
@hnefatl I don't know why, but it kept showing me that my definition of factoradic representation was a part of the code, but finally got it over.
– whiskeyo
Nov 28 '18 at 1:16
add a comment |
I have just written a code which does its job, but I have to optimize it to work in time O(log n). The problem is that I'm not sure whether its time complexity is good and if it's not, how should I fix it?
Factoradic representation of a number is a sequence sk, sk-1 ... s2, s1 that:
-> n = 1! * s1 + 2! * s2 + ... + k! * sk
-> si ≤ for i ∈ {1, 2, ..., k}
-> sk > 0
-> eg. 107 = 4! * 4 + 3! * 1 + 2! * 2 + 1! *1
My code:
unsigned long long int n;
unsigned long long int maxFact[21] = {0};
maxFact[0] = 1;
maxFact[1] = 1;
cout<<"Insert n: "; cin >> n;
int i = 2;
while (maxFact[i-1] * i <= n) // find higher factorial <= n
{
maxFact[i] = maxFact[i-1] * i;
i++;
}
cout << "Factoradic representation of " << n << ":" << endl;
while (i > 1)
{
cout << n / maxFact[i-1] << " ";
n = n % maxFact[i-1];
i--;
}
c++ runtime time-complexity big-o
edited Nov 28 '18 at 8:16
Bishal Gautam
835518
asked Nov 28 '18 at 0:47
whiskeyowhiskeyo
1013
I have just written a code which does its job, but I have to optimize it to work in time O(log n). The problem is that I'm not sure whether its time complexity is good and if it's not, how should I fix it?
Factoradic representation of a number is a sequence sk, sk-1 ... s2, s1 that:
-> n = 1! * s1 + 2! * s2 + ... + k! * sk
-> si ≤ for i ∈ {1, 2, ..., k}
-> sk > 0
-> eg. 107 = 4! * 4 + 3! * 1 + 2! * 2 + 1! *1
My code:
unsigned long long int n;
unsigned long long int maxFact[21] = {0};
maxFact[0] = 1;
maxFact[1] = 1;
cout<<"Insert n: "; cin >> n;
int i = 2;
while (maxFact[i-1] * i <= n) // find higher factorial <= n
{
maxFact[i] = maxFact[i-1] * i;
i++;
}
cout << "Factoradic representation of " << n << ":" << endl;
while (i > 1)
{
cout << n / maxFact[i-1] << " ";
n = n % maxFact[i-1];
i--;
}
c++ runtime time-complexity big-o
c++ runtime time-complexity big-o
edited Nov 28 '18 at 8:16
Bishal Gautam
835518
asked Nov 28 '18 at 0:47
whiskeyowhiskeyo
1013
edited Nov 28 '18 at 8:16
Bishal Gautam
835518
asked Nov 28 '18 at 0:47
whiskeyowhiskeyo
1013
edited Nov 28 '18 at 8:16
Bishal Gautam
835518
edited Nov 28 '18 at 8:16
Bishal Gautam
835518
edited Nov 28 '18 at 8:16
Bishal Gautam
835518
835518
asked Nov 28 '18 at 0:47
whiskeyowhiskeyo
1013
asked Nov 28 '18 at 0:47
whiskeyowhiskeyo
1013
asked Nov 28 '18 at 0:47
whiskeyowhiskeyo
1013
1013
1
It might help if you define what a "factoradic" representation of a number is.
– hnefatl
Nov 28 '18 at 0:50
@hnefatl I don't know why, but it kept showing me that my definition of factoradic representation was a part of the code, but finally got it over.
– whiskeyo
Nov 28 '18 at 1:16
add a comment |
1
It might help if you define what a "factoradic" representation of a number is.
– hnefatl
Nov 28 '18 at 0:50
@hnefatl I don't know why, but it kept showing me that my definition of factoradic representation was a part of the code, but finally got it over.
– whiskeyo
Nov 28 '18 at 1:16
1
1
It might help if you define what a "factoradic" representation of a number is.
– hnefatl
Nov 28 '18 at 0:50
It might help if you define what a "factoradic" representation of a number is.
– hnefatl
Nov 28 '18 at 0:50
@hnefatl I don't know why, but it kept showing me that my definition of factoradic representation was a part of the code, but finally got it over.
– whiskeyo
Nov 28 '18 at 1:16
@hnefatl I don't know why, but it kept showing me that my definition of factoradic representation was a part of the code, but finally got it over.
– whiskeyo
Nov 28 '18 at 1:16
add a comment |
1 Answer
1
active
oldest
votes
Based on the example used in this definition of factoradic you can use div() to more rapidly determine the coefficients. You could implement that like
div_t result;
while (n != 0) {
result = div(n, i);
n = result.quot;
maxFact[i++] = result.rem;
}
Where div() and div_t are included from stdlib.h.
This is fairly similar to what you have, except that maxFact is now storing the coefficients explicitly and only needs one loop for calculations. Your code looks like it is at least close to O(log n) but doing it as the above reduces the flops/n while still being algorithmically O(log n) - slightly more efficient, but not algorithmically superior. In fact the code in this answer runs on average 3x faster than the code in the question for n larger than 10- but we are splitting microseconds here (even up to the precision limit of n) so a factor of 3 is practically meaningless.
Hope this helps
answered Nov 28 '18 at 2:58
William MillerWilliam Miller
1,407317
This helps a lot, but I would also like to know if there is any way to change my algorithm not to use any other libraries and work on basic operators (+ - * / %).
– whiskeyo
Nov 28 '18 at 7:01
You can get the quotient and remainder separately using the/and%operators, there is no more primitive way to get both at once besides usingdiv(). That would be fairly simple though - use the code in answer but replaceresult = div(n, i)with the linessize_t quot = n / Iandsize_t rem = n % Ithen usequotandreminstead ofresult.quotandresult.rem. If this answer is sufficient then be sure to hit the check mark below the voting arrows to accept it - in case you didn’t already know.
– William Miller
Nov 28 '18 at 8:28
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%2f53510457%2falgorythm-to-find-factoradic-for-given-number-n-which-works-in-time-olog-n%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
Based on the example used in this definition of factoradic you can use div() to more rapidly determine the coefficients. You could implement that like
div_t result;
while (n != 0) {
result = div(n, i);
n = result.quot;
maxFact[i++] = result.rem;
}
Where div() and div_t are included from stdlib.h.
This is fairly similar to what you have, except that maxFact is now storing the coefficients explicitly and only needs one loop for calculations. Your code looks like it is at least close to O(log n) but doing it as the above reduces the flops/n while still being algorithmically O(log n) - slightly more efficient, but not algorithmically superior. In fact the code in this answer runs on average 3x faster than the code in the question for n larger than 10- but we are splitting microseconds here (even up to the precision limit of n) so a factor of 3 is practically meaningless.
Hope this helps
answered Nov 28 '18 at 2:58
William MillerWilliam Miller
1,407317
This helps a lot, but I would also like to know if there is any way to change my algorithm not to use any other libraries and work on basic operators (+ - * / %).
– whiskeyo
Nov 28 '18 at 7:01
You can get the quotient and remainder separately using the/and%operators, there is no more primitive way to get both at once besides usingdiv(). That would be fairly simple though - use the code in answer but replaceresult = div(n, i)with the linessize_t quot = n / Iandsize_t rem = n % Ithen usequotandreminstead ofresult.quotandresult.rem. If this answer is sufficient then be sure to hit the check mark below the voting arrows to accept it - in case you didn’t already know.
– William Miller
Nov 28 '18 at 8:28
add a comment |
Based on the example used in this definition of factoradic you can use div() to more rapidly determine the coefficients. You could implement that like
div_t result;
while (n != 0) {
result = div(n, i);
n = result.quot;
maxFact[i++] = result.rem;
}
Where div() and div_t are included from stdlib.h.
This is fairly similar to what you have, except that maxFact is now storing the coefficients explicitly and only needs one loop for calculations. Your code looks like it is at least close to O(log n) but doing it as the above reduces the flops/n while still being algorithmically O(log n) - slightly more efficient, but not algorithmically superior. In fact the code in this answer runs on average 3x faster than the code in the question for n larger than 10- but we are splitting microseconds here (even up to the precision limit of n) so a factor of 3 is practically meaningless.
Hope this helps
answered Nov 28 '18 at 2:58
William MillerWilliam Miller
1,407317
This helps a lot, but I would also like to know if there is any way to change my algorithm not to use any other libraries and work on basic operators (+ - * / %).
– whiskeyo
Nov 28 '18 at 7:01
You can get the quotient and remainder separately using the/and%operators, there is no more primitive way to get both at once besides usingdiv(). That would be fairly simple though - use the code in answer but replaceresult = div(n, i)with the linessize_t quot = n / Iandsize_t rem = n % Ithen usequotandreminstead ofresult.quotandresult.rem. If this answer is sufficient then be sure to hit the check mark below the voting arrows to accept it - in case you didn’t already know.
– William Miller
Nov 28 '18 at 8:28
add a comment |
Based on the example used in this definition of factoradic you can use div() to more rapidly determine the coefficients. You could implement that like
div_t result;
while (n != 0) {
result = div(n, i);
n = result.quot;
maxFact[i++] = result.rem;
}
Where div() and div_t are included from stdlib.h.
This is fairly similar to what you have, except that maxFact is now storing the coefficients explicitly and only needs one loop for calculations. Your code looks like it is at least close to O(log n) but doing it as the above reduces the flops/n while still being algorithmically O(log n) - slightly more efficient, but not algorithmically superior. In fact the code in this answer runs on average 3x faster than the code in the question for n larger than 10- but we are splitting microseconds here (even up to the precision limit of n) so a factor of 3 is practically meaningless.
Hope this helps
answered Nov 28 '18 at 2:58
William MillerWilliam Miller
1,407317
Based on the example used in this definition of factoradic you can use div() to more rapidly determine the coefficients. You could implement that like
div_t result;
while (n != 0) {
result = div(n, i);
n = result.quot;
maxFact[i++] = result.rem;
}
Where div() and div_t are included from stdlib.h.
This is fairly similar to what you have, except that maxFact is now storing the coefficients explicitly and only needs one loop for calculations. Your code looks like it is at least close to O(log n) but doing it as the above reduces the flops/n while still being algorithmically O(log n) - slightly more efficient, but not algorithmically superior. In fact the code in this answer runs on average 3x faster than the code in the question for n larger than 10- but we are splitting microseconds here (even up to the precision limit of n) so a factor of 3 is practically meaningless.
Hope this helps
answered Nov 28 '18 at 2:58
William MillerWilliam Miller
1,407317
answered Nov 28 '18 at 2:58
William MillerWilliam Miller
1,407317
answered Nov 28 '18 at 2:58
William MillerWilliam Miller
1,407317
answered Nov 28 '18 at 2:58
William MillerWilliam Miller
1,407317
1,407317
This helps a lot, but I would also like to know if there is any way to change my algorithm not to use any other libraries and work on basic operators (+ - * / %).
– whiskeyo
Nov 28 '18 at 7:01
You can get the quotient and remainder separately using the/and%operators, there is no more primitive way to get both at once besides usingdiv(). That would be fairly simple though - use the code in answer but replaceresult = div(n, i)with the linessize_t quot = n / Iandsize_t rem = n % Ithen usequotandreminstead ofresult.quotandresult.rem. If this answer is sufficient then be sure to hit the check mark below the voting arrows to accept it - in case you didn’t already know.
– William Miller
Nov 28 '18 at 8:28
add a comment |
This helps a lot, but I would also like to know if there is any way to change my algorithm not to use any other libraries and work on basic operators (+ - * / %).
– whiskeyo
Nov 28 '18 at 7:01
You can get the quotient and remainder separately using the/and%operators, there is no more primitive way to get both at once besides usingdiv(). That would be fairly simple though - use the code in answer but replaceresult = div(n, i)with the linessize_t quot = n / Iandsize_t rem = n % Ithen usequotandreminstead ofresult.quotandresult.rem. If this answer is sufficient then be sure to hit the check mark below the voting arrows to accept it - in case you didn’t already know.
– William Miller
Nov 28 '18 at 8:28
This helps a lot, but I would also like to know if there is any way to change my algorithm not to use any other libraries and work on basic operators (+ - * / %).
– whiskeyo
Nov 28 '18 at 7:01
This helps a lot, but I would also like to know if there is any way to change my algorithm not to use any other libraries and work on basic operators (+ - * / %).
– whiskeyo
Nov 28 '18 at 7:01
You can get the quotient and remainder separately using the
/ and % operators, there is no more primitive way to get both at once besides using div(). That would be fairly simple though - use the code in answer but replace result = div(n, i) with the lines size_t quot = n / I and size_t rem = n % I then use quot and rem instead of result.quot and result.rem. If this answer is sufficient then be sure to hit the check mark below the voting arrows to accept it - in case you didn’t already know.– William Miller
Nov 28 '18 at 8:28
You can get the quotient and remainder separately using the
/ and % operators, there is no more primitive way to get both at once besides using div(). That would be fairly simple though - use the code in answer but replace result = div(n, i) with the lines size_t quot = n / I and size_t rem = n % I then use quot and rem instead of result.quot and result.rem. If this answer is sufficient then be sure to hit the check mark below the voting arrows to accept it - in case you didn’t already know.– William Miller
Nov 28 '18 at 8:28
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%2f53510457%2falgorythm-to-find-factoradic-for-given-number-n-which-works-in-time-olog-n%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
It might help if you define what a "factoradic" representation of a number is.
– hnefatl
Nov 28 '18 at 0:50
@hnefatl I don't know why, but it kept showing me that my definition of factoradic representation was a part of the code, but finally got it over.
– whiskeyo
Nov 28 '18 at 1:16