-
-
Save rbrito/1331277 to your computer and use it in GitHub Desktop.
#!/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) |
:-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.
@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.
@kinow, with the latest version of this program, here is the output that I get:
If I am not mistaken, the function
rbrito2
is about 1400 times faster thanbruno
, and about 500 times faster thanrbrito
.