The D programming language is a natively compiled, systems programming language. In many respects, D is very similar to C++: it shares C++'s runtime performance, low-level access, abstractions, and most of its syntax. It also improves on C++ in many areas, for example in its expressiveness, compilation speed, and grammatical simplicity. That isn't to say that D is a perfect language. D still has relatively poor tool chain support, and some language features still need some TLC. However, on the whole, D is a very balanced language that will feel familiar to anyone that has done any programming in a modern C-style language (i.e. C++, C#, or Java).

Code::Blocks is a free, open source, cross platform IDE that is easy to use, and features the same look-and-feel as Visual Studio. While Code::Blocks advertises itself as a C++ IDE, it natively supports D projects.

This article will describe how to install the DMD compiler as well as the Code::Blocks IDE.

Step 1 - Installing DMD

DMD is the Digital Mars D compiler. Digital Mars is a small software company owned by Walter Bright, who invented the D programming language, so the DMD compiler can be seen as the reference implementation for other D compilers. It is also the first (and only) thing you'll need to get started with D programming.

Download the Windows Installer (direct link to file)

(If the link doesn't work, head to the download page, and select the Windows one-click installer for D language version 2).

Once the download has finished, run it, and follow the instructions.

When you are asked what component you want to install, only select D2. You don't need anything else (however, feel free to install the other components if you know you want to). Click "Next" once you have select the component you want.

Note that when prompted for the directory to install D to, you may enter another directory, but this guide will assume that you have installed to the default (C:\D). If you do select another directory, be sure to take this into account whenever C:\D is mentioned.

Once you have selected the directory, the installer will download the necessary files, and continue to install DMD.

At this stage you should have a fully functioning D2 compiler, and you could start doing some D coding now if you so desired. However, writing code in notepad, and compiling via the command prompt isn't very fun; what we need is an IDE.

Step 2 - Installing Code::Blocks

To install Code::Blocks, head to their download page, and select the Windows setup download. Note that you do not need the "mingw" version as that is for C++ -- the regular (smaller) download will suffice. As per usual, once the download has finished, run it, and follow the instructions.

IMPORTANT: When asked what components to install, ensure that you select the D lexer. This is not included in the standard install! Again, feel free to install whatever other components you think you might want to use, but this is the only change that is required.

Hit "Next", select your install directory (it doesn't matter where) and hit "Next" again. Finally, once the install is complete it will ask if you want to run Code::Blocks now. Click "Yes".

Step 3 - Your First D Program

When Code::Blocks starts up, it will pop up with a window titled "Compilers auto-detection". From the list select "Digital Mars D Compiler" (NOT "Digital Mars Compiler"), click "Set as default" then click "OK". Next, the annoying "Tip of the day" window will pop up. Close it. You will then be asked about file associations. Select "No, leave everything as it is", and click "OK". Close the scripting console.

Code::Blocks is now ready for use. Click the "Create a new project" in the middle of the screen. You will be presented with an array of project templates to choose from. Find the one called "D application", select it, then click the "Go" button at the top-right. This will take you to the D project wizard, click "Next" on the first page. The next page will ask for your project's name and folder. For the name, you can type anything you like; I went with "Test". For the folder, again, put it wherever you like; your home folder is as good a place as any. Click "Next". You are now given some configuration options. Ensure that the Digital Mars D Compiler is selected, and everything else should be left as it is. Click "Finish".

You are now ready to start coding. From the "Management" pane, expand the "D Sources" folder, and double-click "hello.d". You will be presented with some very ugly, non-idiomatic D2 code. This is what I get:

version(Tango) extern(C) int printf(char *, ...);

int main(char[][] args)
{
    printf("hello world\n");
    printf("args.length = %d\n", args.length);
    for (int i = 0; i < args.length; i++)
	printf("args[%d] = '%s'\n", i, cast(char *)args[i]);
    return 0;
}

What an ugly mess! Obviously the guys at Code::Blocks haven't updated their sample code for D2 yet!

That's not all they haven't updated. If you try to compiler this code (by hitting the button), you'll get an error message:

"Test - Debug" uses an invalid compiler. Probably the toolchain path within the compiler options is not setup correctly?!

This is because Code::Blocks is looking in C:\dmd for the DMD compiler, but it's not there. To fix this, open up the "Settings" menu and select "Compiler and debugger...". Ensure that the selected compiler is the "Digital Mars D Compiler" and head to the "Toolchain executables" tab. In the installation directory text box, enter "C:\D\dmd2\windows\bin", and click "OK".

Now, try to compile again (by hitting  the button). If the sample code is the same as above, then you'll get some compile error messages about printf not being defined. Let's replace that code with some more idiomatic D2 code. Remove the sample code, and use the following instead:

import std.stdio;

void main()
{
    writeln("Hello, world!");
}

That's more like it! Compiling now should produce no errors, and if you run the code you should see the console pop up with the words "Hello, world!" displayed. Congratulations, you have written your first D program!

Problem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Solution

The naive approach to this algorithm would be to just implement the recursive Fibonacci function and do what the problem says. We'd end up with something like this:

int fib(int n) { return n < 2 ? n : fib(n-1) + fib(n-2); }
int sum = 0;
for (int n = 0; fib(n) < 4000000; ++n)
  if (fib(n) % 2 == 0)
    sum += fib(n);

Luckily, 4 million is small enough so that this algorithm runs fairly quickly (about half a second on my machine). If the upper bound was much bigger, we would run into very serious performance issues. The reason is because the implementation of the Fibonacci function shown there runs in exponential time i.e. the time that it takes to calculate fib(n) is proportional to . In concrete terms, we're talking milliseconds to calculate fib(10), and millions of years to calculate fib(100) (that's not an exaggeration -- it's actually around 5 million years for my computer).

Since we do actually get an answer before the end of the universe, we could just move onto the next problem, but we wouldn't have learned much. It's worthwhile putting in some extra effort now to make our Fibonacci function run faster.

There are many ways to generate Fibonnaci quickly, so I'll only mention a few here.

Iterative

The iterative method simply starts at fib(1) and works its way up to fib(n), remembering the previous two values at each stage:

int fib(int n)
{
  if (n < 2)
    return n;
  int fp = 0, f = 1;
  foreach (i; 1..n)
  {
    swap(fp, f);
    f += fp;
  }
  return fp;
}

As we only have one simple loop with no recursion, this approach obviously runs in time linear in .

Memoization

Memoization is a common technique for improving the complexity of recursive functions. The concept is simple: once you have calculated a value, store it somewhere and use that value instead of calculating it again. The beauty of memoization is that it allows you to keep your elegant recursive definition.

int fib(int n)
{
	static int[] cache = [0, 1];
	if (n >= cache.length)
	  cache ~= fib(n-1) + fib(n-2);
	return cache[n];
}

Note that I have been a little cheeky with the memoization part here by simply appending the newly calculated value onto the end of the array, assuming that it will be in the right position. If you think about it though, it always will be in the right position, because fib(n-1) would have been calculated before the append, which means that the array will be elements long when the append actually happens, which is what we want.

The performance here is linear in for the first time you calculate a value then constant for subsequent invocations.

Closed-Form Formula

Interestingly, there exists a closed form formula for calculating the nth Fibonacci number. It is:

Let's put it into action:

int fib(int n)
{
	double phi = (1.0 + sqrt(5.0)) / 2.0;
	double f = (pow(phi, n) - pow(1.0 - phi, n)) / sqrt(5.0);
	return cast(int)(f + 0.5);
}

Assuming pow(double, int) is implemented using the exponentiation by squaring algorithm, this will run in logarithmic time.

Problem

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Solution

This problem is trivial to solve. We can test whether an integer is a multiple of an integer by testing if . In most popular programming languages (including D), this is achieved by using the modulo operator (%).

bool divides(int m, int n) { return n % m == 0; }

Using this, the straight-forward, imperative solution is to simply iterate through the numbers 1 to 999, summing those that divide by either 3 or 5.

int sum = 0;
foreach (n; 1..1000)
  if (divides(3, n) || divides(5, n))
    sum += n;

While there's nothing wrong with this solution, it's arguably not as concise as it could be. Fortunately, the Phobos library provides utilities for making this easier and more literal through its std.algorithm and std.range modules.

auto numbers = iota(1, 1000);
auto multiples = filter!("a%3==0 || a%5==0")(numbers);
int sum = reduce!("a+b")(0, multiples);

We could also write this all on one line if we wanted:

int sum = reduce!("a+b")(0, filter!("a%3==0 || a%5==0")(iota(1, 1000)));

So what's happening here?

First, the iota(a, b) function simply returns the numbers in the range . Next, the filter function takes those numbers as an argument and returns a range of those numbers that satisfy the given predicate. Here, the predicate is "a%3==0 || a%5==0" i.e. the number is divisible by 3 or 5. Now, we have all the numbers under 1000 that are divisible by 3 or 5, all we have to do is sum them; this is what reduce!("a+b") does. The reduce function starts with the first argument (0) and iteratively moves through the elements of the second argument, applying the function ("a+b") to its current value and that element.

Is this the best we can do? No. It turns out that this problem is best solved using maths. Clearly, if you count from 1 to 1000, every third number is going to a multiple of 3, and every fifth number is going to be a multiple of 5. This means that there are numbers divisible by 3, and numbers divisible by 5.

But what is the sum of all those numbers? It should be easy to see that the sum of is just 3 times the sum of and it is known that the sum of is .

So do we just add those two quantities together? Not quite. If we add them together then we will be adding the numbers that are divisible by both 3 and 5 twice. Using the inclusion-exclusion principle we just need to subtract those numbers from the total to get the correct amount. How many numbers are divisible by both 3 and 5? If you look at those numbers, it's quite easy to see the pattern: they are divisible by 15. Note that while it may seem that the 15 comes about because , it is actually because (See: Least common multiple).

Our solution now becomes simply:

int sum(int m)
{
  int n = 999 / m;
  return m * n * (n + 1) / 2;
}

int answer = sum(3) + sum(5) - sum(15);