| Line 11: | Line 11: | ||
This is a gentle first problem, but it is designed to illustrate what project Euler is really about. | This is a gentle first problem, but it is designed to illustrate what project Euler is really about. | ||
| − | + | ---- | |
| + | '''The Naive''' | ||
| − | We | + | Finding the solution is simple: check if n is divisible by either 3 or 5 and and all the numbers which are. We only need to check natural numbers up to 1000, but with our computers, 3000 operation is, really, nothing. Answer is computed instantaneously. To see an example of brute-force calculations, click [http://www.pastie.org/3272313 here]. |
---- | ---- | ||
| − | ''' | + | '''Little Gauss''' |
| + | |||
| + | Through Project Euler, I've developed an instinct for identifying bad solutions, and the naive approach is one that stinks in disgrace. The weakest aspect of the naive approach is that as we increase the upper limit to 10000, 100000, or even 100000000, the program would take longer to find the correct solution (complexity of the problem grows linearly). | ||
| + | |||
| + | For example, using the time object in python, I summarize the time it takes the program to compute the sum of all multiples of 3 and 5 for following n. | ||
| + | {| width="200" border="1" cellpadding="1" cellspacing="1" | ||
| + | |- | ||
| + | | '''n''' | ||
| + | | '''Time (seconds)''' | ||
| + | |- | ||
| + | |- | ||
| + | | 1000 | ||
| + | | 0.0000 (negligible) | ||
| + | |- | ||
| + | |- | ||
| + | | 10000 | ||
| + | | 0.0050 | ||
| + | |- | ||
| + | |- | ||
| + | | 10000 | ||
| + | | 0.580 | ||
| + | |- | ||
| + | |- | ||
| + | | 100000 | ||
| + | | 0.6400 | ||
| + | |- | ||
| + | |- | ||
| + | | 1000000 | ||
| + | | 5.49500 | ||
| + | |- | ||
| + | |} | ||
| + | |||
| + | Time increase about tenfold for tenfold increase of the input. Perhaps five seconds does appear like a long time, but at my level of programming, any program I write that takes more than a second to produce an answer is poorly written. (Although time comparison is not too useful since time depends on other factors such as computing power, language, etc., the result is sensible in terms of number of computational steps increasing by tenfold). | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
[[MA 375 Spring 2012 Walther Project Euler|Back to Project Euler]] | [[MA 375 Spring 2012 Walther Project Euler|Back to Project Euler]] | ||
[[2012 Spring MA 375 Walther|Back to MA375]] | [[2012 Spring MA 375 Walther|Back to MA375]] | ||
Revision as of 16:17, 28 January 2012
Problem 1
Find the sum of all the multiples of 3 or 5 below 1000.
This is a gentle first problem, but it is designed to illustrate what project Euler is really about.
The Naive
Finding the solution is simple: check if n is divisible by either 3 or 5 and and all the numbers which are. We only need to check natural numbers up to 1000, but with our computers, 3000 operation is, really, nothing. Answer is computed instantaneously. To see an example of brute-force calculations, click here.
Little Gauss
Through Project Euler, I've developed an instinct for identifying bad solutions, and the naive approach is one that stinks in disgrace. The weakest aspect of the naive approach is that as we increase the upper limit to 10000, 100000, or even 100000000, the program would take longer to find the correct solution (complexity of the problem grows linearly).
For example, using the time object in python, I summarize the time it takes the program to compute the sum of all multiples of 3 and 5 for following n.
| n | Time (seconds) |
| 1000 | 0.0000 (negligible) |
| 10000 | 0.0050 |
| 10000 | 0.580 |
| 100000 | 0.6400 |
| 1000000 | 5.49500 |
Time increase about tenfold for tenfold increase of the input. Perhaps five seconds does appear like a long time, but at my level of programming, any program I write that takes more than a second to produce an answer is poorly written. (Although time comparison is not too useful since time depends on other factors such as computing power, language, etc., the result is sensible in terms of number of computational steps increasing by tenfold).
