Project Euler 1

bruno.py

#!/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)

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!

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

What about this one?

https://gist.github.com/1340351

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

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

@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.

@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.

@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.

:-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.