Faffing round the edges Its easier than getting stuck in

28Nov/080

Problem 1 again

So I read a comment on reddit about how bad my maths was (and how badly I abuse Erlang too). I started reading Algorithms in a Nutshell as I figured I might have enough maths now to understand it. Well I don't really but I did understand the Big O notation stuff at the start enough to understand the comment on reddit:

Ah, what a misuse of Erlang, especially considering that all the 3 programs presented are all O(n) far from the optimal O(1). The guy should learn some math rather than experimenting with 'creating a process for every number'. His next post about problem 2 is not much better (he does 'find the sum of fibs below 4mln' by evaluating fib(n) from scratch until it becomes bigger than 4mln), but at least there he confesses: 'I am really let down by my lack of maths at school.'

So I read the PDF again from Project Euler solution (which I earned the right to read by misusing myself to a solution).

I think I understand the optimal solution well enough, and I was certainly able to implement it:

problem1(Target) ->
	sumDivBy(3, Target) + sumDivBy(5, Target) - sumDivBy(15, Target).

sumDivBy(N, Target) ->
	P = Target div N,
	N * (P * (P+1)) div 2.

And that is much better.

Now I'm not tooooo cut up by the comments (not ready yet). I didn't get any maths education beyond 16, and what I got up to then was rubbish but at least I am trying to rectify it. My parallel processing attempt was educational for me. I can never do anything without a practical motivation.

The problem is: I understand how the above solution works and I can see that it is optimal but without being taught it I doubt I would have got anywhere near it on my own.

Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

You must be logged in to post a comment.

No trackbacks yet.

 

November 2008
M T W T F S S
« Oct   Dec »
 12
3456789
10111213141516
17181920212223
24252627282930

Archives