Project Euler #1 - One Problem, Three Solutions, Seven Languages

I haven’t posted here in a long time, and I apologize for that. No particular reason, but all good: programming in F#, learning lots of new programming stuff, enjoying the fall and winter holiday season (including hand-making some Christmas gifts), etc.

As I mentioned, one of the things I’ve been doing is learning new programming skills. I ignored F# during its early history, and the past year has shown me that was a mistake. So I decided to take a look at some of the other things I’ve been ignoring. That led me into various spots, including: Lua, Python, Ruby, MongoDB, MySQL, PostgresQL, Silverlight 4, SVN, Haskell, NetBeans, revisiting Scheme, the world of Visual Studio extensions, etc.

There’s a popular programming book by Bruce Tate, titled “Seven Languages in Seven Weeks.” In that spirit, I’d like to present something similar here: three views of Project Euler, problem number one, in seven languages. Some of these languages I’ve worked in for a long time; some of them I’ve just learned, but here goes. (As always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

First is F#. Of all the languages listed here, F# is my favorite. Not by a wide margin, perhaps, but my favorite nonetheless. I think this is because of the vision of its creators: to build a language based on thoughtful consideration of all that has come before, both academic and pragmatic. At this, it succeeds brilliantly. (And no, Don Syme did not pay me to say this, lol.)

// Naive Implementation,

// based on problem statement.

// Illustrates aggregate operators

// and pipes.

let euler_1_naive a b bound =

  seq {1..bound-1} 

  |> Seq.filter (fun i->((i%a=0)||(i%b=0)))

  |> Seq.sum

// Sums stepped ranges.

// Illustrates aggregate operators

// and pipes.

let euler_1_iteration a b bound =

  (seq {a..a..bound-1} |> Seq.sum)+

  (seq {b..b..bound-1} |> Seq.sum)-

  (seq {a*b..a*b..bound-1} |> Seq.sum)

// Numeric (one possible factoring).

// Illustrates the use of nested functions,

// closures and immutable parameters.

let euler_1_numeric a b bound =

  let b1 = bound-1

  let f n =

    let c = b1/n

    c*(c+1)/2*n

    (f a)+(f b)-(f (a*b))

Next is Python. Python is an interesting language; it embodies a lot of characteristics that make it fun and easy to program in: orthogonality, lack of syntactic fluff, etc. On the other hand, it is a very businesslike language with a lot of excellent libraries available. If I were Java and C#, I’d watch my back.

# Python 3.1.3 and NetBeans w/Python plug-in.

def euler_1_naive (a,b,bound):
    """Naive Implementation,
       based on problem statement.
       Illustrates comprehensions
       and implicit booleans."""
    return sum(
      i for i in range(1,bound)
        if (not ((i%a) and (i%b))))


def euler_1_iteration (a,b,bound):
    """Sums stepped ranges.
       Illustrates aggregate operators."""
    return sum(range(a,bound,a))+\
           sum(range(b,bound,b))-\
           sum(range(a*b,bound,a*b))


def euler_1_numeric (a,b,bound):
    """Numeric (one possible factoring).
       Illustrates the use of nested functions
       and closures."""
    bound -= 1
    def f (n):
        """Compute sum of n-divisible."""
        c = int(bound/n)
        return int(c*(c+1)/2)*n
    return f(a)+f(b)-f(a*b)

And here is Ruby. What to say about Ruby? Superficially, it strikes one as incoherent and arbitrary. But a closer look shows this to be a mistake. What looked like incoherence and randomness is really richness and a wonderful idiosyncrasy. Ruby is a complex, Raku bowl of a language, which reflects the mind of its creator, Yukihiro Matsumoto, and records all the incidents and accidents of its history. Of all the languages here, it is the one that draws the most passion from the programmers who use it, and I can see why. There’s a lot to be said for a language in which you can do something five times by coding “5.times {…}”

# Ruby 1.9.2 and NetBeans w/Ruby plug-in.

# Naive Implementation,
# based on problem statement.
# Illustrates filtering.
def euler_1_naive (a,b,bound)
  ((0...bound).find_all{
      |i|(i%a==0)||(i%b==0)}).reduce(:+)
end


# Sums stepped ranges.
# Illustrates aggregate operators.
def euler_1_iteration (a,b,bound)
  (a...bound).step(a).reduce(:+)+
  (b...bound).step(b).reduce(:+)-
  (a*b...bound).step(a*b).reduce(:+)
end


# Numeric (one possible factoring).
# Illustrates the use of lambdas
# and closures."""
def euler_1_numeric (a,b,bound)
  bound -= 1
  #Compute sum of n-divisible.
  f = lambda {|n|
    c = bound/n
    c*(c+1)/2*n
  }
  f.call(a)+f.call(b)-f.call(a*b)
end

Lua, like Ruby and F#, reflects the visions of its creators. Like Python, it is simple and orthogonal. So simple and orthogonal, in fact, that it has only one non-value type: an associative table. Everything else – objects, lists, arrays, stacks, etc. – must be built using those tables. Lua’s simplicity and speed, coupled with the fact that it is implemented in a highly portable subset of C, make Lua a great choice for new processors, small machines, embedded scripting and similar environments. Think of it as a FORTH for the new millennium. I wish GPU shader languages looked like Lua.

function euler1Naive (a,b,bound)
  acc = 0
  for i=0,bound-1 do
    if (i%3==0) or (i%5==0) then 
      acc = acc+i 
    end
  end
  return acc
end


function euler1Iterative (a,b,bound)
  bound = bound-1
  function f(n) 
    acc = 0
    for i=n,bound,n do
      acc = acc+i
    end
    return acc
  end
  return f(a)+f(b)-f(a*b)
end


function euler1Numeric (a,b,bound)
  bound = bound-1
  function f(n) 
    c = math.floor(bound/n)
    return math.floor(c*(c+1)/2)*n
  end
  return f(a)+f(b)-f(a*b)
end

Good old Java, C#, and C/C++; the three tireless workhorses of modern computing. When programmed procedurally, all three are so similar that I will show only a single example: the naïve implementation in Java. Of course, the reasons why a programmer might prefer one of these languages over the others are real and important, but are simply beyond the scope of a snippet. In most cases it has to do with platform, ecosystem, and considerations of speed vs. safety. (In this example, and in the C# case below, I have omitted the enclosing class definition for brevity.)

public static int euler_1_naive (
    int a,
    int b,
    int bound)
{
    int sum = 0;
    for (int i=1;i<bound;i++)
        if (((i%a)==0)||((i%b)==0))
           sum += i;
    return sum;
}

Many procedural languages are growing to become more functional. To illustrate that, here is an example in C#, which makes us of a locally defined delegate.

// C# 4.0 and Visual Studio 2010.

// Sums stepped ranges.

public static int Euler_1_iteration (

  int a,

  int b,

  int bound) 

{

  Func<int,int,int> f = 

    (sum,n) => {

      for (int i=n;i<bound;i+=n) 

        sum+=i;

      return sum; };

  return f(f(-f(0,a*b),b),a);

}

C++0X also adds functional features and other modern constructs to the C++ language. The example below shows the definition of a lambda and the use of the “auto” keyword (a great boon to readability). The lambda syntax appears a bit arcane and robotic, but then, everything about C and C++ is a bit arcane and robot. *Which is exactly what programmers like about it.* (And if you really, *really* like that kind of thing, you might want to try FORTH.)

// Numeric (one possible factoring).

// Illustrates the use of lambdas, auto

// and closures.

int euler_1_numeric (

  int a,

  int b,

  int bound)

{

  bound -= 1;

  auto f = [bound] (int n) -> int 

  { 

    int c = bound / n;

    return c*(c+1)/2*n;

  };

  return f(a)+f(b)-f(a*b);

}

Last, here are a couple of examples that use template-based metaprogramming in C++. In case you haven’t encountered that before, it’s basically a way of tricking the compiler into running a program at *compile time* that leaves a correct value or structure in the compiled code. In these examples, the correct Project Euler #1 value is left in the enumeration value RET. Template-based metaprogramming can be a bit hard to wrap your mind around at first, and the examples here are not especially reflective of how it might be useful in the real world. Suffice to say that it can be a powerful technique for creating complex data structures and increasing runtime efficiency (for example, by permitting constant folding and similar techniques in ways that go beyond even optimizing compilers).

// Template metaprogram 1.

// Sums stepped ranges.

// Illustrates partial template

// instantiation.

template<int i, int acc, int n>

struct SRSum

{

  enum { 

    RET=SRSum<i,acc+i,n-1>::RET+acc 

  };

};

template<int i, int acc>

struct SRSum<i,acc,0>

{

  enum { RET=acc };

};

template<int a, int b, int bound> 

struct Euler1Iterate

{

  enum { 

    RET=(SRSum<a,0,(bound-1)/a>::RET)+ 

        (SRSum<b,0,(bound-1)/b>::RET)-

        (SRSum<(a*b),0,(bound-1)/(a*b)>::RET)

  };

};

// Template metaprogram 2.

// Numeric.

template<int n, int bound>

struct NSum 

{

private: enum { C=(bound-1)/n };

public: enum { RET=C*(C+1)/2*n };

};

template<int a, int b, int bound> 

struct Euler1Numeric

{

  enum { 

    RET=NSum<a,bound>::RET+ 

        NSum<b,bound>::RET-

        NSum<(a*b),bound>::RET 

  };

};

// Test both.

int _tmain(int argc, _TCHAR* argv[])

{

  return (Euler1Iterate<3,5,1000>::RET+

          Euler1Numeric<3,5,1000>::RET)/2;

}

Finally, a short word about benchmarks. The compiled versions (C/C++/C#/Java/F#) all ran a lot faster than the scripting language versions (Lua/Python/Ruby). That was no surprise. What was surprising, however, was just how fast the scripted versions were – even given the startup time. Plenty fast enough for almost anything other than data or numeric intensive programs, and certainly fast enough to handle most user tasks. Of the three scripting languages, Lua lived up to its reputation as the fastest, but Ruby and Python weren’t far behind (Ruby was slightly faster than Python).

And that’s it: one problem, three solutions, seven languages.

-Neil

p.s. I apologize for not syntax highlighting several of the samples. I have a VS2008 add-in that will do it, but I don’t know how to do it in NetBeans.