 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> "Tim Attwood" <tim### [at] comcast net> wrote:
>> According to the statistics page on Project Euler there's about
>> three times as many people using C/C++ as Haskell, and about
>> twice as many using Python as Haskell.
>
> OTOH, most C++ solutions I've seen in the forum are the trivial, straightforward
> loopy and slow performant solutions, using pretty much the same obvious
> algorithm. Many Haskell solutions came up with amazingly concise and creative
> algorithms.
>
> but I was really impressed with the assembly and math solutions...
Math solutions FTW!
(E.g., problem 1, I wrote something that loops over the numbers 1 to 100
finding those that fit the divisibility requirements and summing them.
Somebody else managed to produce a closed-form *formula* for the answer.
Beat that!)
The few Haskell solutions I've seen look unecessarily wordy - like they
were written by somebody just learning Haskell. But then, the Haskell
Wiki has a section devoted to Project Euler, and most solutions there
look rather childish and unperformant too, so...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle wrote:
> Tim Attwood wrote:
>> I'm mostly stalled at 43%, I've seen several
>> problems that are easy enough to express
>> solutions to that are none-the-less difficult
>> to compute in any reasonable amount of time.
>
> Some of the questions state an iterative problem for which there is a
> direct solution.
>
> For instance, the second problem looks iterative, but there is a direct
> formula for any member of the Fibonacci series, there is a direct
> formula for the sum of a power series, and the even-valued members of
> the Fibonacci series occur at every third position starting with 0. When
> you put that together, the sum is
>
> (1/sqrt(5) * ( (phi^(n+3)-1)/(phi-1) - ((1-phi)^(n+3)-1)/(1-phi-1) )
It turns out that this formula is wrong. The correct formula is:
1/sqrt(5) *
( (phi^(n+3)-1)/(phi^3-1) - ((1-phi)^(n+3)-1)/((1-phi)^3-1) )
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
nemesis wrote:
> "Tim Attwood" <tim### [at] comcastnet> wrote:
>> According to the statistics page on Project Euler there's about
>> three times as many people using C/C++ as Haskell, and about
>> twice as many using Python as Haskell.
>
> OTOH, most C++ solutions I've seen in the forum are the trivial, straightforward
> loopy and slow performant solutions, using pretty much the same obvious
> algorithm. Many Haskell solutions came up with amazingly concise and creative
> algorithms.
I admit that for the C++ solutions I've been resorting to brute force,
but for these problems I'm not aware of any solution that avoids the
brute force approach. For instance, in the problem for summing the
prime numbers less than one million, I'm not aware of any theorem which
calculates such a sum for any range without testing each odd number for
primality and then adding the primes.
It could be that the C++ coders either aren't aware of the
computationally less-expensive solutions, or they simply assume that the
relative efficiency of C++ (save counter-arguments for another thread,
please) enables them to not worry about computational efficiency.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle <evi### [at] hotmailcom> wrote:
> For instance, in the problem for summing the
> prime numbers less than one million, I'm not aware of any theorem which
> calculates such a sum for any range without testing each odd number for
> primality and then adding the primes.
http://en.wikipedia.org/wiki/Prime-counting_function
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> John VanSickle <evi### [at] hotmailcom> wrote:
>> For instance, in the problem for summing the
>> prime numbers less than one million, I'm not aware of any theorem which
>> calculates such a sum for any range without testing each odd number for
>> primality and then adding the primes.
>
> http://en.wikipedia.org/wiki/Prime-counting_function
I didn't read all of it, but it's not obvious how helpful that would
be...other than getting an idea of the number of primes under a million.
When you get that many then you can stop (assuming the estimate is good
enough).
I'm not aware of any better way to do this than to simply get all the
primes under a million and add them up. The only variation is how one
obtains all the primes. You could use a Sieve method, or do what many
people did: Test each odd number by dividing it by all possible primes
less than sqrt(number). For all the prime problems, I was using a sieve,
but apparently for a lot of problems (all so far?), simply testing by
dividing appears to be faster. I think the sieve wins out once you the
numbers get large enough, though.
--
Diplomacy - the art of letting someone have your way.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 wrote:
> (E.g., problem 1, I wrote something that loops over the numbers 1 to 100
> finding those that fit the divisibility requirements and summing them.
> Somebody else managed to produce a closed-form *formula* for the answer.
> Beat that!)
Not particularly hard. You have a formula for the sum of all integers
from 1 to 100. And one for the sum of all multiples of 3 till 100. Ditto
for multiples of 5. Now just subtract the sum of all multiples of 15.
> The few Haskell solutions I've seen look unecessarily wordy - like they
> were written by somebody just learning Haskell. But then, the Haskell
> Wiki has a section devoted to Project Euler, and most solutions there
> look rather childish and unperformant too, so...
I do stuff in Python. Even though some manage to solve whole problems
with one line solutions, it is generally frowned upon in the Python
community if it gets challenging to read: They generally perform about
the same as more readable code.
So perhaps those Haskell users were converts from Python...
--
Diplomacy - the art of letting someone have your way.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle wrote:
> I admit that for the C++ solutions I've been resorting to brute force,
> but for these problems I'm not aware of any solution that avoids the
> brute force approach. For instance, in the problem for summing the
> prime numbers less than one million, I'm not aware of any theorem which
> calculates such a sum for any range without testing each odd number for
> primality and then adding the primes.
I've done brute force for a bunch, but at times I try to find
shortcuts. Sometimes the resulting program is even slower, but I suspect
it'll scale better.
Also, while a brute force solution in C/C++ may run in under a minute,
it occasionally will not in Python. So I'm forced to think of ways to
speed it up. I frequently find a "better" solution than mine in the
forums, though.
--
Diplomacy - the art of letting someone have your way.
/\ /\ /\ /
/ \/ \ u e e n / \/ a w a z
>>>>>>mue### [at] nawazorg<<<<<<
anl
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz <m.n### [at] ieeeorg> wrote:
> Warp wrote:
> > John VanSickle <evi### [at] hotmailcom> wrote:
> >> For instance, in the problem for summing the
> >> prime numbers less than one million, I'm not aware of any theorem which
> >> calculates such a sum for any range without testing each odd number for
> >> primality and then adding the primes.
> >
> > http://en.wikipedia.org/wiki/Prime-counting_function
> I didn't read all of it, but it's not obvious how helpful that would
> be...
I didn't mean for it to be an answer to the problem but as an interesting
thing to read about the subject.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Mueen Nawaz wrote:
> John VanSickle wrote:
>> I admit that for the C++ solutions I've been resorting to brute force,
>> but for these problems I'm not aware of any solution that avoids the
>> brute force approach. For instance, in the problem for summing the
>> prime numbers less than one million, I'm not aware of any theorem which
>> calculates such a sum for any range without testing each odd number for
>> primality and then adding the primes.
>
> I've done brute force for a bunch, but at times I try to find
> shortcuts. Sometimes the resulting program is even slower, but I suspect
> it'll scale better.
>
> Also, while a brute force solution in C/C++ may run in under a minute,
> it occasionally will not in Python. So I'm forced to think of ways to
> speed it up. I frequently find a "better" solution than mine in the
> forums, though.
It's interesting how many elaborate problems requiring multiple nested
loops and filtering take only about 10 instructions in assembly... (!)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Currently for each problem, you either get the answer right or you get
it wrong. I think it would be nice if you could check intermediate parts
of the calculation. (E.g., is 103 a prime number? Is 187 an abundant
number? etc.)
On the other hand, I suppose they don't want to give too much data away,
otherwise you could just "solve" the problem by asking the Project Euler
website a sufficient number of questions. ;-)
Currently it seems the "ratings" are simply based on what fraction of
the problems you've solved. I think it would be nice if I get a bigger
score for solving problems that few other people have solved.
I'd kinda like to make my own website like Project Euler. However, I had
a look, and to get hosting that gives you server-side scripting and a
database is 5x the price of what I'm currently paying. :-S I can't
really afford that kind of money...
I suppose the alternative is to set up a Linux box in my house and host
a website from there [again]. But it's rather annoying when you're
playing a clan match and suddenly somebody hits your website and you
can't play properly any more. :-S
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
