The fastest algorithm to solve equation with 2 unknown parametrs in c?
up vote
0
down vote
favorite
I am counting the value of possible combinations of x and y. It works but when I put big numbers it takes way too long. Do you have any ideas for better algorithm?
ax + by = c
The input of program is a, b and c, which should be non-negative numbers.
My code looks like this:
int combs=0;
for(int x=0; x < c; x++) {
for(int y=0; y < c; y++) {
if( (a*x) + (b*y) == c) {
combs++;
}
}
}
c algorithm equation
edited Nov 11 at 15:16
Broman
6,190112241
asked Nov 11 at 15:09
Petr Konecny
64
|
show 1 more comment
up vote
0
down vote
favorite
I am counting the value of possible combinations of x and y. It works but when I put big numbers it takes way too long. Do you have any ideas for better algorithm?
ax + by = c
The input of program is a, b and c, which should be non-negative numbers.
My code looks like this:
int combs=0;
for(int x=0; x < c; x++) {
for(int y=0; y < c; y++) {
if( (a*x) + (b*y) == c) {
combs++;
}
}
}
c algorithm equation
edited Nov 11 at 15:16
Broman
6,190112241
asked Nov 11 at 15:09
Petr Konecny
64
Are there limits on a, b, and c?
– pstrjds
Nov 11 at 15:11
They have to be bigger or equal to 0, thats all.
– Petr Konecny
Nov 11 at 15:12
What is the allowable range ofx,y? Can x or y be negative?
– chux
Nov 11 at 16:13
2
en.wikipedia.org/wiki/Diophantine_equation
– Matt Timmermans
Nov 11 at 16:34
1
@Petr Konecny "it takes way too long" --> This can be solved without any iterations onx,y, yet looks like you have an acceptable solution already - too bad.
– chux
Nov 11 at 19:11
|
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am counting the value of possible combinations of x and y. It works but when I put big numbers it takes way too long. Do you have any ideas for better algorithm?
ax + by = c
The input of program is a, b and c, which should be non-negative numbers.
My code looks like this:
int combs=0;
for(int x=0; x < c; x++) {
for(int y=0; y < c; y++) {
if( (a*x) + (b*y) == c) {
combs++;
}
}
}
c algorithm equation
edited Nov 11 at 15:16
Broman
6,190112241
asked Nov 11 at 15:09
Petr Konecny
64
I am counting the value of possible combinations of x and y. It works but when I put big numbers it takes way too long. Do you have any ideas for better algorithm?
ax + by = c
The input of program is a, b and c, which should be non-negative numbers.
My code looks like this:
int combs=0;
for(int x=0; x < c; x++) {
for(int y=0; y < c; y++) {
if( (a*x) + (b*y) == c) {
combs++;
}
}
}
c algorithm equation
c algorithm equation
edited Nov 11 at 15:16
Broman
6,190112241
asked Nov 11 at 15:09
Petr Konecny
64
edited Nov 11 at 15:16
Broman
6,190112241
asked Nov 11 at 15:09
Petr Konecny
64
edited Nov 11 at 15:16
Broman
6,190112241
edited Nov 11 at 15:16
Broman
6,190112241
edited Nov 11 at 15:16
Broman
6,190112241
6,190112241
asked Nov 11 at 15:09
Petr Konecny
64
asked Nov 11 at 15:09
Petr Konecny
64
asked Nov 11 at 15:09
Petr Konecny
64
64
Are there limits on a, b, and c?
– pstrjds
Nov 11 at 15:11
They have to be bigger or equal to 0, thats all.
– Petr Konecny
Nov 11 at 15:12
What is the allowable range ofx,y? Can x or y be negative?
– chux
Nov 11 at 16:13
2
en.wikipedia.org/wiki/Diophantine_equation
– Matt Timmermans
Nov 11 at 16:34
1
@Petr Konecny "it takes way too long" --> This can be solved without any iterations onx,y, yet looks like you have an acceptable solution already - too bad.
– chux
Nov 11 at 19:11
|
show 1 more comment
Are there limits on a, b, and c?
– pstrjds
Nov 11 at 15:11
They have to be bigger or equal to 0, thats all.
– Petr Konecny
Nov 11 at 15:12
What is the allowable range ofx,y? Can x or y be negative?
– chux
Nov 11 at 16:13
2
en.wikipedia.org/wiki/Diophantine_equation
– Matt Timmermans
Nov 11 at 16:34
1
@Petr Konecny "it takes way too long" --> This can be solved without any iterations onx,y, yet looks like you have an acceptable solution already - too bad.
– chux
Nov 11 at 19:11
Are there limits on a, b, and c?
– pstrjds
Nov 11 at 15:11
Are there limits on a, b, and c?
– pstrjds
Nov 11 at 15:11
They have to be bigger or equal to 0, thats all.
– Petr Konecny
Nov 11 at 15:12
They have to be bigger or equal to 0, thats all.
– Petr Konecny
Nov 11 at 15:12
What is the allowable range of
x,y? Can x or y be negative?– chux
Nov 11 at 16:13
What is the allowable range of
x,y? Can x or y be negative?– chux
Nov 11 at 16:13
2
2
en.wikipedia.org/wiki/Diophantine_equation
– Matt Timmermans
Nov 11 at 16:34
en.wikipedia.org/wiki/Diophantine_equation
– Matt Timmermans
Nov 11 at 16:34
1
1
@Petr Konecny "it takes way too long" --> This can be solved without any iterations on
x,y, yet looks like you have an acceptable solution already - too bad.– chux
Nov 11 at 19:11
@Petr Konecny "it takes way too long" --> This can be solved without any iterations on
x,y, yet looks like you have an acceptable solution already - too bad.– chux
Nov 11 at 19:11
|
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
A much faster way is to do some math first. ax+by=c => y=(c-ax)/b
int combs=0;
for(int x=0; x < c; x++) {
int y = (c-a*x)/b;
if( (a*x) + (b*y) == c)
combs++;
}
Getting rid of that nested loop is the most important detail to improve performance. Another thing you could do is to do as Antti Haapala suggested in comments below and use ax instead of x.
int combs=0;
for(int ax=0; ax < c; ax+=a) {
int y = (c-ax)/b;
if( (ax) + (b*y) == c)
combs++;
}
answered Nov 11 at 15:15
Broman
6,190112241
Lazy thinking today, but isn't it enough to check for zero remainder?
– Antti Haapala
Nov 11 at 15:40
@AnttiHaapala Quite possible. I don't know.
– Broman
Nov 11 at 16:00
also you don't need to loop untilcbutceil(c / a). Or useaxas the variable, and increase bya:)
– Antti Haapala
Nov 11 at 16:03
What do you mean by zero reminder? :)
– Petr Konecny
Nov 11 at 16:16
This will counts as solutionsy < 0, yet notx < 0. Suggestx < c-->x < c/ato prevent that - faster too.
– chux
Nov 11 at 19:09
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
A much faster way is to do some math first. ax+by=c => y=(c-ax)/b
int combs=0;
for(int x=0; x < c; x++) {
int y = (c-a*x)/b;
if( (a*x) + (b*y) == c)
combs++;
}
Getting rid of that nested loop is the most important detail to improve performance. Another thing you could do is to do as Antti Haapala suggested in comments below and use ax instead of x.
int combs=0;
for(int ax=0; ax < c; ax+=a) {
int y = (c-ax)/b;
if( (ax) + (b*y) == c)
combs++;
}
answered Nov 11 at 15:15
Broman
6,190112241
Lazy thinking today, but isn't it enough to check for zero remainder?
– Antti Haapala
Nov 11 at 15:40
@AnttiHaapala Quite possible. I don't know.
– Broman
Nov 11 at 16:00
also you don't need to loop untilcbutceil(c / a). Or useaxas the variable, and increase bya:)
– Antti Haapala
Nov 11 at 16:03
What do you mean by zero reminder? :)
– Petr Konecny
Nov 11 at 16:16
This will counts as solutionsy < 0, yet notx < 0. Suggestx < c-->x < c/ato prevent that - faster too.
– chux
Nov 11 at 19:09
add a comment |
up vote
5
down vote
accepted
A much faster way is to do some math first. ax+by=c => y=(c-ax)/b
int combs=0;
for(int x=0; x < c; x++) {
int y = (c-a*x)/b;
if( (a*x) + (b*y) == c)
combs++;
}
Getting rid of that nested loop is the most important detail to improve performance. Another thing you could do is to do as Antti Haapala suggested in comments below and use ax instead of x.
int combs=0;
for(int ax=0; ax < c; ax+=a) {
int y = (c-ax)/b;
if( (ax) + (b*y) == c)
combs++;
}
answered Nov 11 at 15:15
Broman
6,190112241
Lazy thinking today, but isn't it enough to check for zero remainder?
– Antti Haapala
Nov 11 at 15:40
@AnttiHaapala Quite possible. I don't know.
– Broman
Nov 11 at 16:00
also you don't need to loop untilcbutceil(c / a). Or useaxas the variable, and increase bya:)
– Antti Haapala
Nov 11 at 16:03
What do you mean by zero reminder? :)
– Petr Konecny
Nov 11 at 16:16
This will counts as solutionsy < 0, yet notx < 0. Suggestx < c-->x < c/ato prevent that - faster too.
– chux
Nov 11 at 19:09
add a comment |
up vote
5
down vote
accepted
up vote
5
down vote
accepted
A much faster way is to do some math first. ax+by=c => y=(c-ax)/b
int combs=0;
for(int x=0; x < c; x++) {
int y = (c-a*x)/b;
if( (a*x) + (b*y) == c)
combs++;
}
Getting rid of that nested loop is the most important detail to improve performance. Another thing you could do is to do as Antti Haapala suggested in comments below and use ax instead of x.
int combs=0;
for(int ax=0; ax < c; ax+=a) {
int y = (c-ax)/b;
if( (ax) + (b*y) == c)
combs++;
}
answered Nov 11 at 15:15
Broman
6,190112241
A much faster way is to do some math first. ax+by=c => y=(c-ax)/b
int combs=0;
for(int x=0; x < c; x++) {
int y = (c-a*x)/b;
if( (a*x) + (b*y) == c)
combs++;
}
Getting rid of that nested loop is the most important detail to improve performance. Another thing you could do is to do as Antti Haapala suggested in comments below and use ax instead of x.
int combs=0;
for(int ax=0; ax < c; ax+=a) {
int y = (c-ax)/b;
if( (ax) + (b*y) == c)
combs++;
}
answered Nov 11 at 15:15
Broman
6,190112241
edited Nov 11 at 19:16
answered Nov 11 at 15:15
Broman
6,190112241
answered Nov 11 at 15:15
Broman
6,190112241
answered Nov 11 at 15:15
Broman
6,190112241
6,190112241
Lazy thinking today, but isn't it enough to check for zero remainder?
– Antti Haapala
Nov 11 at 15:40
@AnttiHaapala Quite possible. I don't know.
– Broman
Nov 11 at 16:00
also you don't need to loop untilcbutceil(c / a). Or useaxas the variable, and increase bya:)
– Antti Haapala
Nov 11 at 16:03
What do you mean by zero reminder? :)
– Petr Konecny
Nov 11 at 16:16
This will counts as solutionsy < 0, yet notx < 0. Suggestx < c-->x < c/ato prevent that - faster too.
– chux
Nov 11 at 19:09
add a comment |
Lazy thinking today, but isn't it enough to check for zero remainder?
– Antti Haapala
Nov 11 at 15:40
@AnttiHaapala Quite possible. I don't know.
– Broman
Nov 11 at 16:00
also you don't need to loop untilcbutceil(c / a). Or useaxas the variable, and increase bya:)
– Antti Haapala
Nov 11 at 16:03
What do you mean by zero reminder? :)
– Petr Konecny
Nov 11 at 16:16
This will counts as solutionsy < 0, yet notx < 0. Suggestx < c-->x < c/ato prevent that - faster too.
– chux
Nov 11 at 19:09
Lazy thinking today, but isn't it enough to check for zero remainder?
– Antti Haapala
Nov 11 at 15:40
Lazy thinking today, but isn't it enough to check for zero remainder?
– Antti Haapala
Nov 11 at 15:40
@AnttiHaapala Quite possible. I don't know.
– Broman
Nov 11 at 16:00
@AnttiHaapala Quite possible. I don't know.
– Broman
Nov 11 at 16:00
also you don't need to loop until
c but ceil(c / a). Or use ax as the variable, and increase by a :)– Antti Haapala
Nov 11 at 16:03
also you don't need to loop until
c but ceil(c / a). Or use ax as the variable, and increase by a :)– Antti Haapala
Nov 11 at 16:03
What do you mean by zero reminder? :)
– Petr Konecny
Nov 11 at 16:16
What do you mean by zero reminder? :)
– Petr Konecny
Nov 11 at 16:16
This will counts as solutions
y < 0, yet not x < 0. Suggest x < c --> x < c/a to prevent that - faster too.– chux
Nov 11 at 19:09
This will counts as solutions
y < 0, yet not x < 0. Suggest x < c --> x < c/a to prevent that - faster too.– chux
Nov 11 at 19:09
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%2f53250060%2fthe-fastest-algorithm-to-solve-equation-with-2-unknown-parametrs-in-c%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
Are there limits on a, b, and c?
– pstrjds
Nov 11 at 15:11
They have to be bigger or equal to 0, thats all.
– Petr Konecny
Nov 11 at 15:12
What is the allowable range of
x,y? Can x or y be negative?– chux
Nov 11 at 16:13
2
en.wikipedia.org/wiki/Diophantine_equation
– Matt Timmermans
Nov 11 at 16:34
1
@Petr Konecny "it takes way too long" --> This can be solved without any iterations on
x,y, yet looks like you have an acceptable solution already - too bad.– chux
Nov 11 at 19:11