bc

bc, introduced in 1975, is a calculator language for Unix. It's a simple Procedural language with syntax derived from C that allows you to script complex calculations. It's designed as a desktop calculator, not as a general-purpose language, so it's missing a lot of functionality such as objects, first-class functions, pointers - originally it didn't even have any IO routines. bc does run screamingly fast. It does arbitrary-length math, which means you can have it do operations on numbers of unlimited length. And it does have math-based functions, such as being able to define the floating point precision you'd like. It's mainly a glorified calculator, surprise. It is a Turing-Complete language though - just one that you won't want to write anything too complex in. bc has been modernized over the years, with GNU adding a print statement for scripting, rudimentary exception handling, etc.

Here's a version of Euler1 in bc - surprise, it looks much like C. Note here the declaration of local variables using the auto keyword:

#!/usr/bin/bc --quiet
/* Euler1 in bc */

define euler1(size) {
    auto i, retval
    retval = 0

    for (i = 1; i < size; i++) {
        if (i % 3 == 0 || i % 5 == 0) { retval += i }
    }
    return retval;
}

print "euler1 = ", euler1(1000), "\n"
quit

Here's 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.

#!/usr/bin/bc -q
/* Euler1 in bc */

define euler(n, acc) {
    if (n == 1) return acc;

    if (n % 3 == 0 || n % 5 == 0) {
        return euler(n-1, acc+n);
    } else {
        return euler(n-1, acc);
    }
}

define euler1(size) { return euler(size,0); }

print "euler1 = ", euler1(999), "\n"
quit

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:

#!/usr/bin/bc -q
/* Euler1 in bc */

define range(start, end) {
    auto ints, i;
    for (i = start; i < end; i++) {
        ints[i-start] = i;
    }
    return ints;
}

define euler(ints, size) {
    auto pivot, pivotval, preints, presize, pre, postints, postsize, post;
    if (size == 0) {
        return 0;
    }

    pivot = size / 2;
    pivotval = 0;
    if (ints[pivot] % 3 == 0 || ints[pivot] % 5 == 0) {
        pivotval = ints[pivot];
    }

    pre = 0;
    if (ints[pivot]-ints[0] > 0) {
        preints = range(ints[0], ints[pivot]);
        presize = ints[pivot] - ints[0];
        pre = euler(preints, presize);
    }

    post = 0;
    if (ints[size-1] - ints[pivot] > 0) {
        postints = range(ints[pivot]+1, ints[size-1]+1);
        postsize = (ints[size-1]+1) - (ints[pivot]+1);
        post = euler(postints, postsize);
    }

    return pre + pivotval + post;
}

define euler1(size) {
    auto ints;
    ints = range(0, size);
    return euler(ints, size);
}

print "Euler1 = ", euler1(1000), "\n";
quit;

I almost gave up on this version of Quicksort because of bc's limitations. bc has an even worse idea of namespaces than Awk. If you don't explicitly declare a variable as local, it is global; seriously? And even worse, a function maintains its local variable values upon subsequent calls - there is no way to reinitialize a function's variables (that I could find) once they have been initialized. WTF, bc?

bc has associative arrays like bash and awk, which are basically just maps. But at least awk provides you some array functions like length and delete. bc provides no array functions, so there's no good way I could find to clear out an array or find its length. bc looks seriously gimped.

But bc uses large parts of C, and after the pain of writing my C version, I realized that it would work in bc almost verbatim. Yay!

Likewise, bc has no first-class functions, though I'm not surprised. Its roots adhere closely to its C heritage.

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.

#!/usr/bin/bc -q
/* Euler1 in bc */

define my_sum(n, size) {
    return ((size/n)^2 + (size/n)) * n / 2;
}

define euler1(size) {
    return my_sum(3,size) + my_sum(5,size) - my_sum(15,size);
}

print "euler1 = ", euler1(999), "\n";
quit

Your Linux distro probably already has bc installed. Simply add a shebang to the top of your script and execute it:

$ ./euler1.bc
233168
$