Ada - gregorymorrison/euler1 GitHub Wiki

I had a semester of Ada way back when I started programming. This language was introduced back in 1980. I didn't think I'd remember much of it, but surprisingly writing this felt like putting on a pair of old shoes. It is about as unsexy as languages get - everything is explicit, but the compiler also holds your hand with great error messages. Here is Euler1 in Ada:

-- Euler1_1 in Ada
with Ada.Text_IO;
with Ada.Integer_Text_IO;

procedure Euler is

    function Euler1(size : in Integer) return Integer is
        result: Integer;
    begin
        result := 0;
        for i in 1..size-1 loop
            if i mod 3 = 0 or i mod 5 = 0 then
                result := result + i;
            end if;
        end loop;
        return result;
    end Euler1;

begin
    Ada.Text_IO.Put ("Euler1 - ");
    Ada.Integer_Text_IO.Put (Integer(Euler1(1000)), 6);
end Euler_1;

You'll notice that Ada is not case-sensitive, so be careful when defining things that you don't have a name collision.

Next is a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.

-- Euler1 in Ada
with Ada.Integer_Text_IO;

procedure Euler1_3 is

    function Euler(n : in Integer; acc : in Integer := 0) return Integer is
    begin
        if n = 0 then
	    return acc;
	elsif n mod 3 = 0 or n mod 5 = 0 then
	    return Euler(n-1, acc+n);
	else
	    return Euler(n-1, acc);
	end if;
    end Euler;

begin
    Ada.Integer_Text_IO.Put (Integer( Euler(n => 999) ));
end Euler1_3;

You can see here the use of default parameter values, passing parameters by name, and optional parameter passing - awesome! Why the heck is this not more common (I'm looking at you, Java)?

Here’s another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, Euler() returns Euler() calculated on the half of the list before the pivot element, Euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together.

-- Euler1 in Ada
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure Euler1_4 is
    type Integers is array (Natural range <>) of Integer;

    function myRange(size : in Integer) return Integers is
	ints : Integers(1..size);
    begin
	for i in 1..size loop
	    ints(i) := i;
	end loop;
	return ints;
    end;
	
    function Euler(ints : in Integers) return Integer is
	pivot : Integer;
	pivotval : Integer;
        pre : Integer := 0;
        post : Integer := 0;
    begin
	if ints'Length = 0 then 
	    return 0;
	end if;
	   
	pivot := ints((ints'Last-ints'First) / 2 + ints'First);
	if pivot = 0 then
	    return 0;
	end if;
	
        pivotval := ints(pivot);
	if pivotval mod 3 > 0 and pivotval mod 5 > 0 then
	    pivotval := 0;
	end if;

	if ints'First < pivot then
	    pre := Euler( ints(ints'First..pivot-1) );
	end if;

        if pivot < ints'Last then
	   post := Euler( ints(pivot+1..ints'Last) );
	end if;

	return pre + pivotval + post;
    end Euler;

    function Euler1(size : in Integer) return Integer is
    begin
        return Euler( myRange(size));
    end Euler1;

begin
    Put(Integer ( Euler1(999) ));
end Euler1_4;

Notice that to pass an array to a function, I have created a type "Integers" of Integer Array. Ada does have a range generator function, but it appears to return a type "Range". Ada's strong typing means that Euler() expects a type of "Integers", and I couldn't figure out how to generate a range of "Integers" so I just rolled my own, myRange().

Arrays in Ada are interesting. They don't have a 0-based or 1-based index; they let you define the index as desired. So I started out by creating an array with indices [1..999]. Then when calling Euler() recursively, I pass in an array slice each time (yay, array slicing!). The problem, though, is that Euler() then gets passed an array with indices such as [250..499]. You can see, then, that array properties like ints'First and ints'Last are required for us to know how to discover what indices we have in a given iteration. Expect a learning curve with this!

Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation:

-- Euler1 in Ada
with Ada.Integer_Text_IO;

procedure Euler1_2 is

    function mySum(n : in Integer; size : in Integer) return Integer is
    begin
        return n * (((size/n) **2 + (size/n)) / 2);
    end mySum;

    function Euler(size : in Integer) return Integer is
    begin
	return mySum(3,size) + mySum(5,size) - mySum(15,size);
    end Euler;

begin
    Ada.Integer_Text_IO.Put (Integer( Euler(999) ));
end Euler1_2;

If you haven't tried this language before, it's worth giving it a chance. It produces very robust code, and has some great modern features like concurrency support. And it runs screamingly fast. I used the GNAT compiler to run this code, which also runs screamingly fast on this code. To install on Ubuntu,

$ apt-get install gnat

To compile, bind, link, and execute:

$ gcc -c euler1_1.adb
$ gnatbind euler1_1
$ gnatlink euler1_1
$ ./euler1_1
Euler1 = 233168
$

Because I'm a masochist looking to brush up on his bash skills, let's try to write these steps as a bash one-liner:

$ echo euler1_2 | xargs -I {} sh -c 'gcc -c $1.adb && gnatbind $1 && gnatlink $1 && ./$1' sh {}
    233168
$

Luckily, GNAT also has a command to do all of this for us - gnatmake:

$ gnatmake euler1_2
$ ./euler1_2
    233168
$