Mixing
Method for finding efficient algorithms?
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
TL;DR
What can you recommend to get better at finding efficient solutions to math problems?
Background
The first challenge on Project Euler says:
Find the sum of all the multiples of 3 or 5 below 1000.
The first, and only solution that I could think of was the brute force way:
target = 999
sum = 0
for i = 1 to target do
if (i mod 3 = 0) or (i mod 5 = 0) then sum := sum + i
output sum
This does give me the correct result, but it becomes exponentially slower the bigger the target is. So then I saw this solution:
target=999
Function SumDivisibleBy(n)
p = target div n
return n * (p * (p + 1)) div 2
EndFunction
Output SumDivisibleBy(3) + SumDivisibleBy(5) - SumDivisibleBy(15)
I don't have trouble understanding how this math works, and upon seeing it I feel as though I could have realised that myself. The problem is just that I never do. I always end up with some exponential, brute force like solution.
Obviously there is a huge difference between understanding a presented solution, and actually realising that solution yourself. And I'm not asking how to be Euler himself.
What I do ask tho is, are there methods and or steps, you can apply to solve math problems to find the best (or at least a good) solution?
If yes, can you guys recommend any books/videos/lectures that teach these methods? And what do you do yourself when attempting to find such solutions?
soft-question algorithms problem-solving
edited 1 hour ago
amWhy
191k27223437
asked 1 hour ago
Cortex
211
New contributor
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
4
down vote
favorite
TL;DR
What can you recommend to get better at finding efficient solutions to math problems?
Background
The first challenge on Project Euler says:
Find the sum of all the multiples of 3 or 5 below 1000.
The first, and only solution that I could think of was the brute force way:
target = 999
sum = 0
for i = 1 to target do
if (i mod 3 = 0) or (i mod 5 = 0) then sum := sum + i
output sum
This does give me the correct result, but it becomes exponentially slower the bigger the target is. So then I saw this solution:
target=999
Function SumDivisibleBy(n)
p = target div n
return n * (p * (p + 1)) div 2
EndFunction
Output SumDivisibleBy(3) + SumDivisibleBy(5) - SumDivisibleBy(15)
I don't have trouble understanding how this math works, and upon seeing it I feel as though I could have realised that myself. The problem is just that I never do. I always end up with some exponential, brute force like solution.
Obviously there is a huge difference between understanding a presented solution, and actually realising that solution yourself. And I'm not asking how to be Euler himself.
What I do ask tho is, are there methods and or steps, you can apply to solve math problems to find the best (or at least a good) solution?
If yes, can you guys recommend any books/videos/lectures that teach these methods? And what do you do yourself when attempting to find such solutions?
soft-question algorithms problem-solving
edited 1 hour ago
amWhy
191k27223437
asked 1 hour ago
Cortex
211
New contributor
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
You might benefit from George Polya's classic book, How to Solve It.
– Barry Cipra
1 hour ago
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
TL;DR
What can you recommend to get better at finding efficient solutions to math problems?
Background
The first challenge on Project Euler says:
Find the sum of all the multiples of 3 or 5 below 1000.
The first, and only solution that I could think of was the brute force way:
target = 999
sum = 0
for i = 1 to target do
if (i mod 3 = 0) or (i mod 5 = 0) then sum := sum + i
output sum
This does give me the correct result, but it becomes exponentially slower the bigger the target is. So then I saw this solution:
target=999
Function SumDivisibleBy(n)
p = target div n
return n * (p * (p + 1)) div 2
EndFunction
Output SumDivisibleBy(3) + SumDivisibleBy(5) - SumDivisibleBy(15)
I don't have trouble understanding how this math works, and upon seeing it I feel as though I could have realised that myself. The problem is just that I never do. I always end up with some exponential, brute force like solution.
Obviously there is a huge difference between understanding a presented solution, and actually realising that solution yourself. And I'm not asking how to be Euler himself.
What I do ask tho is, are there methods and or steps, you can apply to solve math problems to find the best (or at least a good) solution?
If yes, can you guys recommend any books/videos/lectures that teach these methods? And what do you do yourself when attempting to find such solutions?
soft-question algorithms problem-solving
edited 1 hour ago
amWhy
191k27223437
asked 1 hour ago
Cortex
211
New contributor
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
TL;DR
What can you recommend to get better at finding efficient solutions to math problems?
Background
The first challenge on Project Euler says:
Find the sum of all the multiples of 3 or 5 below 1000.
The first, and only solution that I could think of was the brute force way:
target = 999
sum = 0
for i = 1 to target do
if (i mod 3 = 0) or (i mod 5 = 0) then sum := sum + i
output sum
This does give me the correct result, but it becomes exponentially slower the bigger the target is. So then I saw this solution:
target=999
Function SumDivisibleBy(n)
p = target div n
return n * (p * (p + 1)) div 2
EndFunction
Output SumDivisibleBy(3) + SumDivisibleBy(5) - SumDivisibleBy(15)
I don't have trouble understanding how this math works, and upon seeing it I feel as though I could have realised that myself. The problem is just that I never do. I always end up with some exponential, brute force like solution.
Obviously there is a huge difference between understanding a presented solution, and actually realising that solution yourself. And I'm not asking how to be Euler himself.
What I do ask tho is, are there methods and or steps, you can apply to solve math problems to find the best (or at least a good) solution?
If yes, can you guys recommend any books/videos/lectures that teach these methods? And what do you do yourself when attempting to find such solutions?
soft-question algorithms problem-solving
soft-question algorithms problem-solving
edited 1 hour ago
amWhy
191k27223437
asked 1 hour ago
Cortex
211
New contributor
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 1 hour ago
amWhy
191k27223437
asked 1 hour ago
Cortex
211
New contributor
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 1 hour ago
amWhy
191k27223437
edited 1 hour ago
amWhy
191k27223437
edited 1 hour ago
amWhy
191k27223437
191k27223437
asked 1 hour ago
Cortex
211
New contributor
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 1 hour ago
Cortex
211
asked 1 hour ago
Cortex
211
211
New contributor
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Cortex is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
You might benefit from George Polya's classic book, How to Solve It.
– Barry Cipra
1 hour ago
add a comment |Â
2
You might benefit from George Polya's classic book, How to Solve It.
– Barry Cipra
1 hour ago
2
2
You might benefit from George Polya's classic book, How to Solve It.
– Barry Cipra
1 hour ago
You might benefit from George Polya's classic book, How to Solve It.
– Barry Cipra
1 hour ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
TL;DR: "Efficient solutions to math problems" don't exist. Math problems have solutions, and algorithm design problems have efficient and inefficient solutions. Recognizing which is which can be half the task.
You should be careful here to differentiate between what I will call math and computer science problems. What you see above is a math problem. Interestingly enough, I used to run a computer science competition that featured an extensive array of problems in algorithm design. Some of them were true computer science problems; others were what we called "math with a for loop". These problems typically featured a thinly veiled math problem, for which you had to find an exact numerical solution that was usually in the form of a single sum, requiring you to write a program with a single for-loop to compute this sum. Hence, "math with a for loop."
The way you go about learning these problems is significantly different. For "math with a for loop" problems, study math. Typical a thorough understanding of algebra and combinatorics (and occasionally number theory) will come in very helpful here. But this is not so important for real computer science questions. Algorithm design is hard. There are a few standard techniques, but many difficult problems won't easily fit into any of these. Here the solution is just to learn as much as you can, and to practice.
But your problem above is not a computer science problem. It's a math problem. It can very easily be rewritten into
Let $S$ be the set of all multiples of $3$ or $5$, and let $f(n)$ be the sum of the elements of $S$ below $n$. Compute $f(1000)$.
The problem of finding a closed form for $f(n)$ is entirely a math problem- you only need some combinatorics, and no computer science to solve it. Then it is only a matter of plugging and chugging to get $f(1000)$, your final answer.
answered 1 hour ago
DreamConspiracy
6641216
Personally, I doubt that there is a border between math and computer science. Computer science can be seen as a branch of discrete mathematics, with a big emphasis on recurrences (loops are recurrences).
– Yves Daoust
31 mins ago
@YvesDaoust while this may be technically true, I don't agree with what I think you may be implying here. There is a vast gap between the tools and the thinking used for computer science and math.
– DreamConspiracy
28 mins ago
Can you substantiate ? To give you my own example, I spent most of this morning decrypting the formulas for the CIE2000 color distance computation in order to optimize processing. That involved a good deal of algebra and computer architecture, in a continuum between maths and programming. Also note that a program is nothing but a theorem.
– Yves Daoust
22 mins ago
@YvesDaoust I maybe should have been more clear. Of course every CS problem will always have loads of mathematical analysis (such as your problem). But the distinction that I'm making is in the high level approaches. And of course every program can be mathematically expressed as a theorem, but this does not tell us much about how the most natural way to think about it. Coincidentally, I can give you an example from my morning. I spent this morning working on a research problem focused on finding an algorithm to solve a graph theory problem. Of course I could look at this algorithm as a
– DreamConspiracy
14 mins ago
(cont.) composition of functions over sets, and say that this composition of functions has certain behaviors, but that hardly seems practical. Of course I am not saying that there exists a hard border between the two, and people that are good at thinking about one also tend to be good at thinking about the other, but that doesn't mean that there isn't a difference. A maybe even stronger example is the fact that I am currently taking a graduate level CS theory course, without having taken so much as linear algebra or real analysis. Idk if this explanation is better, but hopefully it helps
– DreamConspiracy
7 mins ago
add a comment |Â
up vote
3
down vote
There is no general method to find efficient algorithms, as there is no method to solve math problems in general. Besides practice and culture.
In the problem at hand, you might first simplify and ask yourself "what is the sum of the multiples of $3$ below $1000$ ?". Obviously, these are $3,6,9,cdots999$, i.e. $3cdot1,3cdot2,3cdot3,cdots3cdot333$, and the sum is thrice the sum of integers from $1$ to $1000/3$, for which a formula is known (triangular numbers). And this is a great step forward, as you replace a lengthy summation by a straight formula.
Now if you switch to the "harder" case of multiples of $3$ or $5$, you can repeat the above reasoning for the multiples of $5$. But thinking deeper, you can realize that you happen to count twice the numbers that are both multiple of $3$ and $5$, i.e the multiples of $15$. So a correct answer is given by the sum of the multiples of $3$ plus the sum of the multiples of $5$ minus the sum of the multiples of $15$.
answered 1 hour ago
Yves Daoust
120k667215
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
TL;DR: "Efficient solutions to math problems" don't exist. Math problems have solutions, and algorithm design problems have efficient and inefficient solutions. Recognizing which is which can be half the task.
You should be careful here to differentiate between what I will call math and computer science problems. What you see above is a math problem. Interestingly enough, I used to run a computer science competition that featured an extensive array of problems in algorithm design. Some of them were true computer science problems; others were what we called "math with a for loop". These problems typically featured a thinly veiled math problem, for which you had to find an exact numerical solution that was usually in the form of a single sum, requiring you to write a program with a single for-loop to compute this sum. Hence, "math with a for loop."
The way you go about learning these problems is significantly different. For "math with a for loop" problems, study math. Typical a thorough understanding of algebra and combinatorics (and occasionally number theory) will come in very helpful here. But this is not so important for real computer science questions. Algorithm design is hard. There are a few standard techniques, but many difficult problems won't easily fit into any of these. Here the solution is just to learn as much as you can, and to practice.
But your problem above is not a computer science problem. It's a math problem. It can very easily be rewritten into
Let $S$ be the set of all multiples of $3$ or $5$, and let $f(n)$ be the sum of the elements of $S$ below $n$. Compute $f(1000)$.
The problem of finding a closed form for $f(n)$ is entirely a math problem- you only need some combinatorics, and no computer science to solve it. Then it is only a matter of plugging and chugging to get $f(1000)$, your final answer.
answered 1 hour ago
DreamConspiracy
6641216
Personally, I doubt that there is a border between math and computer science. Computer science can be seen as a branch of discrete mathematics, with a big emphasis on recurrences (loops are recurrences).
– Yves Daoust
31 mins ago
@YvesDaoust while this may be technically true, I don't agree with what I think you may be implying here. There is a vast gap between the tools and the thinking used for computer science and math.
– DreamConspiracy
28 mins ago
Can you substantiate ? To give you my own example, I spent most of this morning decrypting the formulas for the CIE2000 color distance computation in order to optimize processing. That involved a good deal of algebra and computer architecture, in a continuum between maths and programming. Also note that a program is nothing but a theorem.
– Yves Daoust
22 mins ago
@YvesDaoust I maybe should have been more clear. Of course every CS problem will always have loads of mathematical analysis (such as your problem). But the distinction that I'm making is in the high level approaches. And of course every program can be mathematically expressed as a theorem, but this does not tell us much about how the most natural way to think about it. Coincidentally, I can give you an example from my morning. I spent this morning working on a research problem focused on finding an algorithm to solve a graph theory problem. Of course I could look at this algorithm as a
– DreamConspiracy
14 mins ago
(cont.) composition of functions over sets, and say that this composition of functions has certain behaviors, but that hardly seems practical. Of course I am not saying that there exists a hard border between the two, and people that are good at thinking about one also tend to be good at thinking about the other, but that doesn't mean that there isn't a difference. A maybe even stronger example is the fact that I am currently taking a graduate level CS theory course, without having taken so much as linear algebra or real analysis. Idk if this explanation is better, but hopefully it helps
– DreamConspiracy
7 mins ago
add a comment |Â
up vote
3
down vote
TL;DR: "Efficient solutions to math problems" don't exist. Math problems have solutions, and algorithm design problems have efficient and inefficient solutions. Recognizing which is which can be half the task.
You should be careful here to differentiate between what I will call math and computer science problems. What you see above is a math problem. Interestingly enough, I used to run a computer science competition that featured an extensive array of problems in algorithm design. Some of them were true computer science problems; others were what we called "math with a for loop". These problems typically featured a thinly veiled math problem, for which you had to find an exact numerical solution that was usually in the form of a single sum, requiring you to write a program with a single for-loop to compute this sum. Hence, "math with a for loop."
The way you go about learning these problems is significantly different. For "math with a for loop" problems, study math. Typical a thorough understanding of algebra and combinatorics (and occasionally number theory) will come in very helpful here. But this is not so important for real computer science questions. Algorithm design is hard. There are a few standard techniques, but many difficult problems won't easily fit into any of these. Here the solution is just to learn as much as you can, and to practice.
But your problem above is not a computer science problem. It's a math problem. It can very easily be rewritten into
Let $S$ be the set of all multiples of $3$ or $5$, and let $f(n)$ be the sum of the elements of $S$ below $n$. Compute $f(1000)$.
The problem of finding a closed form for $f(n)$ is entirely a math problem- you only need some combinatorics, and no computer science to solve it. Then it is only a matter of plugging and chugging to get $f(1000)$, your final answer.
answered 1 hour ago
DreamConspiracy
6641216
Personally, I doubt that there is a border between math and computer science. Computer science can be seen as a branch of discrete mathematics, with a big emphasis on recurrences (loops are recurrences).
– Yves Daoust
31 mins ago
@YvesDaoust while this may be technically true, I don't agree with what I think you may be implying here. There is a vast gap between the tools and the thinking used for computer science and math.
– DreamConspiracy
28 mins ago
Can you substantiate ? To give you my own example, I spent most of this morning decrypting the formulas for the CIE2000 color distance computation in order to optimize processing. That involved a good deal of algebra and computer architecture, in a continuum between maths and programming. Also note that a program is nothing but a theorem.
– Yves Daoust
22 mins ago
@YvesDaoust I maybe should have been more clear. Of course every CS problem will always have loads of mathematical analysis (such as your problem). But the distinction that I'm making is in the high level approaches. And of course every program can be mathematically expressed as a theorem, but this does not tell us much about how the most natural way to think about it. Coincidentally, I can give you an example from my morning. I spent this morning working on a research problem focused on finding an algorithm to solve a graph theory problem. Of course I could look at this algorithm as a
– DreamConspiracy
14 mins ago
(cont.) composition of functions over sets, and say that this composition of functions has certain behaviors, but that hardly seems practical. Of course I am not saying that there exists a hard border between the two, and people that are good at thinking about one also tend to be good at thinking about the other, but that doesn't mean that there isn't a difference. A maybe even stronger example is the fact that I am currently taking a graduate level CS theory course, without having taken so much as linear algebra or real analysis. Idk if this explanation is better, but hopefully it helps
– DreamConspiracy
7 mins ago
add a comment |Â
up vote
3
down vote
up vote
3
down vote
TL;DR: "Efficient solutions to math problems" don't exist. Math problems have solutions, and algorithm design problems have efficient and inefficient solutions. Recognizing which is which can be half the task.
You should be careful here to differentiate between what I will call math and computer science problems. What you see above is a math problem. Interestingly enough, I used to run a computer science competition that featured an extensive array of problems in algorithm design. Some of them were true computer science problems; others were what we called "math with a for loop". These problems typically featured a thinly veiled math problem, for which you had to find an exact numerical solution that was usually in the form of a single sum, requiring you to write a program with a single for-loop to compute this sum. Hence, "math with a for loop."
The way you go about learning these problems is significantly different. For "math with a for loop" problems, study math. Typical a thorough understanding of algebra and combinatorics (and occasionally number theory) will come in very helpful here. But this is not so important for real computer science questions. Algorithm design is hard. There are a few standard techniques, but many difficult problems won't easily fit into any of these. Here the solution is just to learn as much as you can, and to practice.
But your problem above is not a computer science problem. It's a math problem. It can very easily be rewritten into
Let $S$ be the set of all multiples of $3$ or $5$, and let $f(n)$ be the sum of the elements of $S$ below $n$. Compute $f(1000)$.
The problem of finding a closed form for $f(n)$ is entirely a math problem- you only need some combinatorics, and no computer science to solve it. Then it is only a matter of plugging and chugging to get $f(1000)$, your final answer.
answered 1 hour ago
DreamConspiracy
6641216
TL;DR: "Efficient solutions to math problems" don't exist. Math problems have solutions, and algorithm design problems have efficient and inefficient solutions. Recognizing which is which can be half the task.
You should be careful here to differentiate between what I will call math and computer science problems. What you see above is a math problem. Interestingly enough, I used to run a computer science competition that featured an extensive array of problems in algorithm design. Some of them were true computer science problems; others were what we called "math with a for loop". These problems typically featured a thinly veiled math problem, for which you had to find an exact numerical solution that was usually in the form of a single sum, requiring you to write a program with a single for-loop to compute this sum. Hence, "math with a for loop."
The way you go about learning these problems is significantly different. For "math with a for loop" problems, study math. Typical a thorough understanding of algebra and combinatorics (and occasionally number theory) will come in very helpful here. But this is not so important for real computer science questions. Algorithm design is hard. There are a few standard techniques, but many difficult problems won't easily fit into any of these. Here the solution is just to learn as much as you can, and to practice.
But your problem above is not a computer science problem. It's a math problem. It can very easily be rewritten into
Let $S$ be the set of all multiples of $3$ or $5$, and let $f(n)$ be the sum of the elements of $S$ below $n$. Compute $f(1000)$.
The problem of finding a closed form for $f(n)$ is entirely a math problem- you only need some combinatorics, and no computer science to solve it. Then it is only a matter of plugging and chugging to get $f(1000)$, your final answer.
answered 1 hour ago
DreamConspiracy
6641216
answered 1 hour ago
DreamConspiracy
6641216
answered 1 hour ago
DreamConspiracy
6641216
answered 1 hour ago
DreamConspiracy
6641216
6641216
Personally, I doubt that there is a border between math and computer science. Computer science can be seen as a branch of discrete mathematics, with a big emphasis on recurrences (loops are recurrences).
– Yves Daoust
31 mins ago
@YvesDaoust while this may be technically true, I don't agree with what I think you may be implying here. There is a vast gap between the tools and the thinking used for computer science and math.
– DreamConspiracy
28 mins ago
Can you substantiate ? To give you my own example, I spent most of this morning decrypting the formulas for the CIE2000 color distance computation in order to optimize processing. That involved a good deal of algebra and computer architecture, in a continuum between maths and programming. Also note that a program is nothing but a theorem.
– Yves Daoust
22 mins ago
@YvesDaoust I maybe should have been more clear. Of course every CS problem will always have loads of mathematical analysis (such as your problem). But the distinction that I'm making is in the high level approaches. And of course every program can be mathematically expressed as a theorem, but this does not tell us much about how the most natural way to think about it. Coincidentally, I can give you an example from my morning. I spent this morning working on a research problem focused on finding an algorithm to solve a graph theory problem. Of course I could look at this algorithm as a
– DreamConspiracy
14 mins ago
(cont.) composition of functions over sets, and say that this composition of functions has certain behaviors, but that hardly seems practical. Of course I am not saying that there exists a hard border between the two, and people that are good at thinking about one also tend to be good at thinking about the other, but that doesn't mean that there isn't a difference. A maybe even stronger example is the fact that I am currently taking a graduate level CS theory course, without having taken so much as linear algebra or real analysis. Idk if this explanation is better, but hopefully it helps
– DreamConspiracy
7 mins ago
add a comment |Â
Personally, I doubt that there is a border between math and computer science. Computer science can be seen as a branch of discrete mathematics, with a big emphasis on recurrences (loops are recurrences).
– Yves Daoust
31 mins ago
@YvesDaoust while this may be technically true, I don't agree with what I think you may be implying here. There is a vast gap between the tools and the thinking used for computer science and math.
– DreamConspiracy
28 mins ago
Can you substantiate ? To give you my own example, I spent most of this morning decrypting the formulas for the CIE2000 color distance computation in order to optimize processing. That involved a good deal of algebra and computer architecture, in a continuum between maths and programming. Also note that a program is nothing but a theorem.
– Yves Daoust
22 mins ago
@YvesDaoust I maybe should have been more clear. Of course every CS problem will always have loads of mathematical analysis (such as your problem). But the distinction that I'm making is in the high level approaches. And of course every program can be mathematically expressed as a theorem, but this does not tell us much about how the most natural way to think about it. Coincidentally, I can give you an example from my morning. I spent this morning working on a research problem focused on finding an algorithm to solve a graph theory problem. Of course I could look at this algorithm as a
– DreamConspiracy
14 mins ago
(cont.) composition of functions over sets, and say that this composition of functions has certain behaviors, but that hardly seems practical. Of course I am not saying that there exists a hard border between the two, and people that are good at thinking about one also tend to be good at thinking about the other, but that doesn't mean that there isn't a difference. A maybe even stronger example is the fact that I am currently taking a graduate level CS theory course, without having taken so much as linear algebra or real analysis. Idk if this explanation is better, but hopefully it helps
– DreamConspiracy
7 mins ago
Personally, I doubt that there is a border between math and computer science. Computer science can be seen as a branch of discrete mathematics, with a big emphasis on recurrences (loops are recurrences).
– Yves Daoust
31 mins ago
Personally, I doubt that there is a border between math and computer science. Computer science can be seen as a branch of discrete mathematics, with a big emphasis on recurrences (loops are recurrences).
– Yves Daoust
31 mins ago
@YvesDaoust while this may be technically true, I don't agree with what I think you may be implying here. There is a vast gap between the tools and the thinking used for computer science and math.
– DreamConspiracy
28 mins ago
@YvesDaoust while this may be technically true, I don't agree with what I think you may be implying here. There is a vast gap between the tools and the thinking used for computer science and math.
– DreamConspiracy
28 mins ago
Can you substantiate ? To give you my own example, I spent most of this morning decrypting the formulas for the CIE2000 color distance computation in order to optimize processing. That involved a good deal of algebra and computer architecture, in a continuum between maths and programming. Also note that a program is nothing but a theorem.
– Yves Daoust
22 mins ago
Can you substantiate ? To give you my own example, I spent most of this morning decrypting the formulas for the CIE2000 color distance computation in order to optimize processing. That involved a good deal of algebra and computer architecture, in a continuum between maths and programming. Also note that a program is nothing but a theorem.
– Yves Daoust
22 mins ago
@YvesDaoust I maybe should have been more clear. Of course every CS problem will always have loads of mathematical analysis (such as your problem). But the distinction that I'm making is in the high level approaches. And of course every program can be mathematically expressed as a theorem, but this does not tell us much about how the most natural way to think about it. Coincidentally, I can give you an example from my morning. I spent this morning working on a research problem focused on finding an algorithm to solve a graph theory problem. Of course I could look at this algorithm as a
– DreamConspiracy
14 mins ago
@YvesDaoust I maybe should have been more clear. Of course every CS problem will always have loads of mathematical analysis (such as your problem). But the distinction that I'm making is in the high level approaches. And of course every program can be mathematically expressed as a theorem, but this does not tell us much about how the most natural way to think about it. Coincidentally, I can give you an example from my morning. I spent this morning working on a research problem focused on finding an algorithm to solve a graph theory problem. Of course I could look at this algorithm as a
– DreamConspiracy
14 mins ago
(cont.) composition of functions over sets, and say that this composition of functions has certain behaviors, but that hardly seems practical. Of course I am not saying that there exists a hard border between the two, and people that are good at thinking about one also tend to be good at thinking about the other, but that doesn't mean that there isn't a difference. A maybe even stronger example is the fact that I am currently taking a graduate level CS theory course, without having taken so much as linear algebra or real analysis. Idk if this explanation is better, but hopefully it helps
– DreamConspiracy
7 mins ago
(cont.) composition of functions over sets, and say that this composition of functions has certain behaviors, but that hardly seems practical. Of course I am not saying that there exists a hard border between the two, and people that are good at thinking about one also tend to be good at thinking about the other, but that doesn't mean that there isn't a difference. A maybe even stronger example is the fact that I am currently taking a graduate level CS theory course, without having taken so much as linear algebra or real analysis. Idk if this explanation is better, but hopefully it helps
– DreamConspiracy
7 mins ago
add a comment |Â
up vote
3
down vote
There is no general method to find efficient algorithms, as there is no method to solve math problems in general. Besides practice and culture.
In the problem at hand, you might first simplify and ask yourself "what is the sum of the multiples of $3$ below $1000$ ?". Obviously, these are $3,6,9,cdots999$, i.e. $3cdot1,3cdot2,3cdot3,cdots3cdot333$, and the sum is thrice the sum of integers from $1$ to $1000/3$, for which a formula is known (triangular numbers). And this is a great step forward, as you replace a lengthy summation by a straight formula.
Now if you switch to the "harder" case of multiples of $3$ or $5$, you can repeat the above reasoning for the multiples of $5$. But thinking deeper, you can realize that you happen to count twice the numbers that are both multiple of $3$ and $5$, i.e the multiples of $15$. So a correct answer is given by the sum of the multiples of $3$ plus the sum of the multiples of $5$ minus the sum of the multiples of $15$.
answered 1 hour ago
Yves Daoust
120k667215
add a comment |Â
up vote
3
down vote
There is no general method to find efficient algorithms, as there is no method to solve math problems in general. Besides practice and culture.
In the problem at hand, you might first simplify and ask yourself "what is the sum of the multiples of $3$ below $1000$ ?". Obviously, these are $3,6,9,cdots999$, i.e. $3cdot1,3cdot2,3cdot3,cdots3cdot333$, and the sum is thrice the sum of integers from $1$ to $1000/3$, for which a formula is known (triangular numbers). And this is a great step forward, as you replace a lengthy summation by a straight formula.
Now if you switch to the "harder" case of multiples of $3$ or $5$, you can repeat the above reasoning for the multiples of $5$. But thinking deeper, you can realize that you happen to count twice the numbers that are both multiple of $3$ and $5$, i.e the multiples of $15$. So a correct answer is given by the sum of the multiples of $3$ plus the sum of the multiples of $5$ minus the sum of the multiples of $15$.
answered 1 hour ago
Yves Daoust
120k667215
add a comment |Â
up vote
3
down vote
up vote
3
down vote
There is no general method to find efficient algorithms, as there is no method to solve math problems in general. Besides practice and culture.
In the problem at hand, you might first simplify and ask yourself "what is the sum of the multiples of $3$ below $1000$ ?". Obviously, these are $3,6,9,cdots999$, i.e. $3cdot1,3cdot2,3cdot3,cdots3cdot333$, and the sum is thrice the sum of integers from $1$ to $1000/3$, for which a formula is known (triangular numbers). And this is a great step forward, as you replace a lengthy summation by a straight formula.
Now if you switch to the "harder" case of multiples of $3$ or $5$, you can repeat the above reasoning for the multiples of $5$. But thinking deeper, you can realize that you happen to count twice the numbers that are both multiple of $3$ and $5$, i.e the multiples of $15$. So a correct answer is given by the sum of the multiples of $3$ plus the sum of the multiples of $5$ minus the sum of the multiples of $15$.
answered 1 hour ago
Yves Daoust
120k667215
There is no general method to find efficient algorithms, as there is no method to solve math problems in general. Besides practice and culture.
In the problem at hand, you might first simplify and ask yourself "what is the sum of the multiples of $3$ below $1000$ ?". Obviously, these are $3,6,9,cdots999$, i.e. $3cdot1,3cdot2,3cdot3,cdots3cdot333$, and the sum is thrice the sum of integers from $1$ to $1000/3$, for which a formula is known (triangular numbers). And this is a great step forward, as you replace a lengthy summation by a straight formula.
Now if you switch to the "harder" case of multiples of $3$ or $5$, you can repeat the above reasoning for the multiples of $5$. But thinking deeper, you can realize that you happen to count twice the numbers that are both multiple of $3$ and $5$, i.e the multiples of $15$. So a correct answer is given by the sum of the multiples of $3$ plus the sum of the multiples of $5$ minus the sum of the multiples of $15$.
answered 1 hour ago
Yves Daoust
120k667215
edited 36 mins ago
answered 1 hour ago
Yves Daoust
120k667215
answered 1 hour ago
Yves Daoust
120k667215
answered 1 hour ago
Yves Daoust
120k667215
120k667215
add a comment |Â
add a comment |Â
Cortex is a new contributor. Be nice, and check out our Code of Conduct.
Cortex is a new contributor. Be nice, and check out our Code of Conduct.
Cortex is a new contributor. Be nice, and check out our Code of Conduct.
Cortex is a new contributor. Be nice, and check out our Code of Conduct.
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2979100%2fmethod-for-finding-efficient-algorithms%23new-answer', 'question_page');
);
Post as a guest
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
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
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
2
You might benefit from George Polya's classic book, How to Solve It.
– Barry Cipra
1 hour ago