Creating inputs that make a subtraction-based GCD algorithm slow
$begingroup$
I have a GCD algorithm that is based on comparison and subtraction. The principle looks like this:
while a != b
while (a > b)
n = 1
while (a > pow(b, n))
a = a - pow(b, n)
n = n + 1
swap a with b
I want to specifically find some numbers that makes the algorithm slow (number of loops run). For example, $5$ and $15$ makes the algorithm very fast, while $2^{15}$ and $1$ makes it slow, but $2^{15}-1$ and $2^{13}-1$ makes it even slower. However, randomly-generated numbers like $30533$ and $19015$ can be slowest, among what numbers I have now.
Is there an algorithm that can find (or better, calculate) a pair of number that makes the above GCD algorithm slow, with both numbers under a given cap. In my case, I need the numbers to be smaller than (not equal to) $2^{15}$ (or $32768$).
Enumerating is not an option for me because profiling the algorithm in my environment is very slow, also if the cap gets bigger, enumerating is impractical.
algorithms greatest-common-divisor
asked Dec 4 '18 at 11:10
iBugiBug
1449
$endgroup$
add a comment |
$begingroup$
I have a GCD algorithm that is based on comparison and subtraction. The principle looks like this:
while a != b
while (a > b)
n = 1
while (a > pow(b, n))
a = a - pow(b, n)
n = n + 1
swap a with b
I want to specifically find some numbers that makes the algorithm slow (number of loops run). For example, $5$ and $15$ makes the algorithm very fast, while $2^{15}$ and $1$ makes it slow, but $2^{15}-1$ and $2^{13}-1$ makes it even slower. However, randomly-generated numbers like $30533$ and $19015$ can be slowest, among what numbers I have now.
Is there an algorithm that can find (or better, calculate) a pair of number that makes the above GCD algorithm slow, with both numbers under a given cap. In my case, I need the numbers to be smaller than (not equal to) $2^{15}$ (or $32768$).
Enumerating is not an option for me because profiling the algorithm in my environment is very slow, also if the cap gets bigger, enumerating is impractical.
algorithms greatest-common-divisor
asked Dec 4 '18 at 11:10
iBugiBug
1449
$endgroup$
$begingroup$
I get loop count $32767$ for $gcd(2^{15},1)$ and $2736$ for $gcd(2^{15}-1,2^{13}-1)$. What do you get?
$endgroup$
– Somos
Dec 4 '18 at 13:15
$begingroup$
@Somos Sorry, I changed the actual algorithm when I kept working. I updated the question
$endgroup$
– iBug
Dec 4 '18 at 13:57
$begingroup$
Copying what's currently in your post directly into Python has $gcd(2^{15}, 1)$ at 32767 and $gcd(2^{15} - 1, 2^{13} - 1)$ at 42.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:10
1
$begingroup$
In fact $gcd(2^{15}, 1)$ is fairly easily seen to be (approximately) slowest. As long as one of the numbers is not one, the total $a + b$ drops with at least 2 every loop, for a total of at most $2^{15}$ steps, which you already achieve with $2^{15}, 1$.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:16
add a comment |
$begingroup$
I have a GCD algorithm that is based on comparison and subtraction. The principle looks like this:
while a != b
while (a > b)
n = 1
while (a > pow(b, n))
a = a - pow(b, n)
n = n + 1
swap a with b
I want to specifically find some numbers that makes the algorithm slow (number of loops run). For example, $5$ and $15$ makes the algorithm very fast, while $2^{15}$ and $1$ makes it slow, but $2^{15}-1$ and $2^{13}-1$ makes it even slower. However, randomly-generated numbers like $30533$ and $19015$ can be slowest, among what numbers I have now.
Is there an algorithm that can find (or better, calculate) a pair of number that makes the above GCD algorithm slow, with both numbers under a given cap. In my case, I need the numbers to be smaller than (not equal to) $2^{15}$ (or $32768$).
Enumerating is not an option for me because profiling the algorithm in my environment is very slow, also if the cap gets bigger, enumerating is impractical.
algorithms greatest-common-divisor
asked Dec 4 '18 at 11:10
iBugiBug
1449
$endgroup$
I have a GCD algorithm that is based on comparison and subtraction. The principle looks like this:
while a != b
while (a > b)
n = 1
while (a > pow(b, n))
a = a - pow(b, n)
n = n + 1
swap a with b
I want to specifically find some numbers that makes the algorithm slow (number of loops run). For example, $5$ and $15$ makes the algorithm very fast, while $2^{15}$ and $1$ makes it slow, but $2^{15}-1$ and $2^{13}-1$ makes it even slower. However, randomly-generated numbers like $30533$ and $19015$ can be slowest, among what numbers I have now.
Is there an algorithm that can find (or better, calculate) a pair of number that makes the above GCD algorithm slow, with both numbers under a given cap. In my case, I need the numbers to be smaller than (not equal to) $2^{15}$ (or $32768$).
Enumerating is not an option for me because profiling the algorithm in my environment is very slow, also if the cap gets bigger, enumerating is impractical.
algorithms greatest-common-divisor
algorithms greatest-common-divisor
asked Dec 4 '18 at 11:10
iBugiBug
1449
asked Dec 4 '18 at 11:10
iBugiBug
1449
edited Dec 4 '18 at 13:54
iBug
asked Dec 4 '18 at 11:10
iBugiBug
1449
asked Dec 4 '18 at 11:10
iBugiBug
1449
asked Dec 4 '18 at 11:10
iBugiBug
1449
1449
$begingroup$
I get loop count $32767$ for $gcd(2^{15},1)$ and $2736$ for $gcd(2^{15}-1,2^{13}-1)$. What do you get?
$endgroup$
– Somos
Dec 4 '18 at 13:15
$begingroup$
@Somos Sorry, I changed the actual algorithm when I kept working. I updated the question
$endgroup$
– iBug
Dec 4 '18 at 13:57
$begingroup$
Copying what's currently in your post directly into Python has $gcd(2^{15}, 1)$ at 32767 and $gcd(2^{15} - 1, 2^{13} - 1)$ at 42.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:10
1
$begingroup$
In fact $gcd(2^{15}, 1)$ is fairly easily seen to be (approximately) slowest. As long as one of the numbers is not one, the total $a + b$ drops with at least 2 every loop, for a total of at most $2^{15}$ steps, which you already achieve with $2^{15}, 1$.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:16
add a comment |
$begingroup$
I get loop count $32767$ for $gcd(2^{15},1)$ and $2736$ for $gcd(2^{15}-1,2^{13}-1)$. What do you get?
$endgroup$
– Somos
Dec 4 '18 at 13:15
$begingroup$
@Somos Sorry, I changed the actual algorithm when I kept working. I updated the question
$endgroup$
– iBug
Dec 4 '18 at 13:57
$begingroup$
Copying what's currently in your post directly into Python has $gcd(2^{15}, 1)$ at 32767 and $gcd(2^{15} - 1, 2^{13} - 1)$ at 42.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:10
1
$begingroup$
In fact $gcd(2^{15}, 1)$ is fairly easily seen to be (approximately) slowest. As long as one of the numbers is not one, the total $a + b$ drops with at least 2 every loop, for a total of at most $2^{15}$ steps, which you already achieve with $2^{15}, 1$.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:16
$begingroup$
I get loop count $32767$ for $gcd(2^{15},1)$ and $2736$ for $gcd(2^{15}-1,2^{13}-1)$. What do you get?
$endgroup$
– Somos
Dec 4 '18 at 13:15
$begingroup$
I get loop count $32767$ for $gcd(2^{15},1)$ and $2736$ for $gcd(2^{15}-1,2^{13}-1)$. What do you get?
$endgroup$
– Somos
Dec 4 '18 at 13:15
$begingroup$
@Somos Sorry, I changed the actual algorithm when I kept working. I updated the question
$endgroup$
– iBug
Dec 4 '18 at 13:57
$begingroup$
@Somos Sorry, I changed the actual algorithm when I kept working. I updated the question
$endgroup$
– iBug
Dec 4 '18 at 13:57
$begingroup$
Copying what's currently in your post directly into Python has $gcd(2^{15}, 1)$ at 32767 and $gcd(2^{15} - 1, 2^{13} - 1)$ at 42.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:10
$begingroup$
Copying what's currently in your post directly into Python has $gcd(2^{15}, 1)$ at 32767 and $gcd(2^{15} - 1, 2^{13} - 1)$ at 42.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:10
1
1
$begingroup$
In fact $gcd(2^{15}, 1)$ is fairly easily seen to be (approximately) slowest. As long as one of the numbers is not one, the total $a + b$ drops with at least 2 every loop, for a total of at most $2^{15}$ steps, which you already achieve with $2^{15}, 1$.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:16
$begingroup$
In fact $gcd(2^{15}, 1)$ is fairly easily seen to be (approximately) slowest. As long as one of the numbers is not one, the total $a + b$ drops with at least 2 every loop, for a total of at most $2^{15}$ steps, which you already achieve with $2^{15}, 1$.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:16
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%2f3025434%2fcreating-inputs-that-make-a-subtraction-based-gcd-algorithm-slow%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%2f3025434%2fcreating-inputs-that-make-a-subtraction-based-gcd-algorithm-slow%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$
I get loop count $32767$ for $gcd(2^{15},1)$ and $2736$ for $gcd(2^{15}-1,2^{13}-1)$. What do you get?
$endgroup$
– Somos
Dec 4 '18 at 13:15
$begingroup$
@Somos Sorry, I changed the actual algorithm when I kept working. I updated the question
$endgroup$
– iBug
Dec 4 '18 at 13:57
$begingroup$
Copying what's currently in your post directly into Python has $gcd(2^{15}, 1)$ at 32767 and $gcd(2^{15} - 1, 2^{13} - 1)$ at 42.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:10
1
$begingroup$
In fact $gcd(2^{15}, 1)$ is fairly easily seen to be (approximately) slowest. As long as one of the numbers is not one, the total $a + b$ drops with at least 2 every loop, for a total of at most $2^{15}$ steps, which you already achieve with $2^{15}, 1$.
$endgroup$
– Mees de Vries
Dec 4 '18 at 14:16