Skip to content

Instantly share code, notes, and snippets.

@rbrito
Forked from kinow/Euler1.java
Created Nov 1, 2011
Embed
What would you like to do?
Project Euler 1
#!/usr/bin/env python
import sys
if sys.platform == "win32":
from time import clock as default_timer
else:
from time import time as default_timer
def bruno(n):
total = 0 # total of the multiples of 3 or 5 seen so far
next_mult_3 = 0 # the next multiple of 3 to be considered
next_mult_5 = 0 # the next multiple of 5 to be considered
i = 0
while i < n:
if i % 3 == 0:
total += i
elif i % 5 == 0:
total += i
i+=1
return total
def rbrito(n):
total = 0 # total of the multiples of 3 or 5 seen so far
next_mult_3 = 0 # the next multiple of 3 to be considered
next_mult_5 = 0 # the next multiple of 5 to be considered
while next_mult_3 < n or next_mult_5 < n:
if next_mult_3 < next_mult_5:
total += next_mult_3
next_mult_3 += 3
elif next_mult_3 > next_mult_5:
total += next_mult_5
next_mult_5 += 5
else: # a common multiple, count only once
total += next_mult_3
next_mult_3 += 3
next_mult_5 += 5
return total
def n_choose_2(n):
return n*(n-1)/2
def rbrito2(n):
n = n-1 # Up to n-1
sum_3 = 3 * n_choose_2(1 + n/3)
sum_5 = 5 * n_choose_2(1 + n/5)
sum_15 = 15 * n_choose_2(1 + n/15)
return sum_3 + sum_5 - sum_15
if __name__ == '__main__':
n = 10000
start = default_timer()
for i in xrange(1000):
bruno(n)
length = default_timer() - start
print("Function bruno took:\t%f s." % length)
start = default_timer()
for i in xrange(1000):
rbrito(n)
length = default_timer() - start
print("Function rbrito took:\t%f s." % length)
start = default_timer()
for i in xrange(1000):
rbrito2(n)
length = default_timer() - start
print("Function rbrito2 took:\t%f s." % length)
@kinow

This comment has been minimized.

Copy link

@kinow kinow commented Nov 1, 2011

I am going home right now, but once I get there I will implement something similar in Java... imperative and functional just to practice and make sure I will never forget about this solution.

Thanks Brito!

@rbrito

This comment has been minimized.

Copy link
Owner Author

@rbrito rbrito commented Nov 2, 2011

If you are allowed to use (integer) divisions, can you compute something even faster than what I wrote above?

@kinow

This comment has been minimized.

Copy link

@kinow kinow commented Nov 4, 2011

What about this one?

https://gist.github.com/1340351

Would it be right to say that in both cases, the algorithm is O(n)?

@kinow

This comment has been minimized.

Copy link

@kinow kinow commented Nov 4, 2011

I'm using TIMETHIS (I'm using a Windows machine right now) and sometimes it says that yours is faster, sometimes it says the contrary. Will wait to hear from you what is the right answer :)

C:\tmp>timethis python bruno.py

TimeThis : Command Line : python bruno.py
TimeThis : Start Time : Fri Nov 04 18:14:02 2011

233168

TimeThis : Command Line : python bruno.py
TimeThis : Start Time : Fri Nov 04 18:14:02 2011
TimeThis : End Time : Fri Nov 04 18:14:03 2011
TimeThis : Elapsed Time : 00:00:00.432

C:\tmp>timethis python brito.py

TimeThis : Command Line : python brito.py
TimeThis : Start Time : Fri Nov 04 18:14:08 2011

233168

TimeThis : Command Line : python brito.py
TimeThis : Start Time : Fri Nov 04 18:14:08 2011
TimeThis : End Time : Fri Nov 04 18:14:08 2011
TimeThis : Elapsed Time : 00:00:00.297

@rbrito

This comment has been minimized.

Copy link
Owner Author

@rbrito rbrito commented Nov 8, 2011

@kinow, I don't know what timethis is, but you can have much better clock resolution if you use the python facilities regarding time.

As I don't know what python version you are using, I have refrained from using the timeit module (which I just learned about a few minutes ago) and I am choosing whichever is better time.clock() or time.time() for each platform.

This way, we isolate the time spent with loading, initilization etc. of the Python interpreter and focus on the real meat of what we are trying to measure.

On my Debian system running Linux in 32bit mode, here is what I get:

Function bruno took: 0.002701 s.
Function rbrito took: 0.001027 s.

I get the function rbrito consistently being faster than the function bruno here.

@rbrito

This comment has been minimized.

Copy link
Owner Author

@rbrito rbrito commented Nov 8, 2011

@kinow, If I run the functions listed above 1000 times, here is what I get:

Function bruno took: 2.774621 s.
Function rbrito took: 0.944093 s.

But, just for fun, I will be including a new function that is faster. Than both of these.

@rbrito

This comment has been minimized.

Copy link
Owner Author

@rbrito rbrito commented Nov 8, 2011

@kinow, with the latest version of this program, here is the output that I get:

Function bruno took: 2.740573 s.
Function rbrito took: 0.970601 s.
Function rbrito2 took: 0.001944 s.

If I am not mistaken, the function rbrito2 is about 1400 times faster than bruno, and about 500 times faster than rbrito.

@kinow

This comment has been minimized.

Copy link

@kinow kinow commented Nov 8, 2011

:-O

But it was fun trying to use the integer divisions and understand your implementation with a single loop.

Could I see this new version? Please.

@rbrito

This comment has been minimized.

Copy link
Owner Author

@rbrito rbrito commented Nov 8, 2011

@kinow, I made a mistake with my benchmarking, as I forgot that I had left my processor with its clock in dynamic frequency mode (read that as: "it starts at its minimum frequency and when necessary, it goes to a higher frequency").

This might have given my solutions an unfair advantage regarding to your solution, as it was executed first, with a possible lower clock.

I have now locked the frequencies at their lowest (which is good on its own, as the program takes a larger amount of time and the resolution of the clock doesn't play a role as large as before) and this is what I get in a Phenon II X4 910 @800mhz, with Linux 2.6.38, in 64 bit mode (Debian sid as userland):

Function bruno took: 8.062006 s.
Function rbrito took: 2.748817 s.
Function rbrito2 took: 0.004651 s.

Regarding the "new version", they are all listed in this gist (actually, right there at the top), as I updated the code in this repository. See the revisions listed at the right... If you have any questions, feel free to drop me an e-mail.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment