Julia - gregorymorrison/euler1 GitHub Wiki

Julia, a new language introduced in 2011(?), attempts to be a high-level, high-performance scientific computing platform. It was inspired by Matlab and extended with features from other modern languages - Lisp, Perl, Python, Ruby, Lua. So, along with having first-class functions, regular expressions, and multiple dispatch, it has built-in libraries for linear algebra, combinatorics, and signal processing. The runtime also transparently optimizes your process across multiple cores when it makes sense.

Here's a simple imperative version of Euler1. It took me maybe 15 minutes to write this code - five minutes to get the syntax, and ten minutes to make sense of the cryptic compiler errors. Note the return value is simply the value of the last line of a function:

# Euler1 in Julia

function euler1(n)
    result = 0
    for i = 1:n
        if i%3 == 0 || i%5 == 0
            result += i 
        end
    end
    result
end

println("euler1 = $(euler1(999))")

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.

# Euler1 in Julia

function euler(n, acc)
    if n == 1
        acc
    elseif n%3 == 0 || n%5 == 0
        euler(n-1, acc+n)
    else
        euler(n-1, acc)
    end
end

function Euler1(n)
    euler(n, 0)
end

println("euler1 = $(Euler1(999))")

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. Note the short-circuit conditional in the middle of that mess. Oddly, I couldn't get the right answer without defining the variables pre, post, and i, even though they are never manipulated. This code demonstrates Julia's range generation and array slicing. Arrays in Julia are 1-based. It also displays a string template, declared types, and implicit return values without the return keyword.

# Euler1 in Julia

function euler(L::Array)
    if length(L) == 0
        0
    else
        pivot = round(Int, length(L)/2) + 1
        pre =  euler( L[1:pivot-1] )
        post = euler( L[pivot+1:end] )
        i = (L[pivot]%3 == 0 || L[pivot]%5 == 0) ? L[pivot] : 0

        pre + i + post
    end
end

function euler1(size::Int)
    return euler( collect(1:size) )
end

println( "euler1 = $(euler1(999))" )

Julia's implementation of Functional programming puts a big smile on my face. It's so straightforward and clean, it couldn't really be any simpler. First-class functions, lambdas, map, filter, reduce... everything in its right place:

# Euler1 in Julia

myMap    = x -> x
myFilter = x -> x%3==0 || x%5==0
myReduce = (x,y) -> x+y

function euler1(n::Int)
    mapped = map(myMap, collect(1:n))
    filtered = filter(myFilter, mapped)
    reduce(myReduce, filtered)
end

println("euler1 = $(euler1(999))")

Julia has support for symmetric coroutines, a sort of producer/consumer paradigm. Producers are like lightweight threads that go to sleep when they are not executing. This is kind of a contrived example, but it shows how coroutines work. The main thread, euler1(), loops through the numbers from 1 to 1000. For each number, it calls the other thread, euler(), that has a function which takes a number and returns a result. The main thread blocks until the child thread returns. I know what you're thinking - that's a function, right? Well, a function would normally be implemented using a stack frame. This implementation uses a separate thread. Like I said, it's a trivial, contrived example:

# Euler1 in Julia

function euler(c::Channel)
    i = 0
    while true
        if i%3 ==0 || i%5 == 0
             put!(i) 
        end
        i += 1
    end
end

function euler1(n)
    task = Channel(euler)

    result = 0
    while true
        i = take!(task)
        if i >= n
            break
        end
        result += i
    end

   result
end

println("euler1 = $(euler1(1000))")

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 Julia

function mySum(n::Int, size::Int)
    (floor(size/n)^2 + floor(size/n)) * n / 2
end

function euler1(size::Int)
    mySum(3, size) + mySum(5, size) - mySum(15, size)
end

println("euler1 = $(euler1(999))")

Julia has an online REPL that lets you can kick its tires without installing anything - http://julia.forio.com/repl.htm. It seems like a great idea, though I didn't have a lot of luck with it - it kept locking up on me. Instead, I opted to install it from source using these directions. The process was simple, though it took hours to compile on my netbook. I also tried simply downloading a compiled binary, which also worked fine, using the following simple instructions:

mkdir julia && cd julia
wget https://julialang-s3.julialang.org/bin/linux/x64/1.2/julia-1.2.0-linux-x86_64.tar.gz
tar -xzf julia-1.2.0-linux-x86_64.tar.gz
sudo ln -s ./julia-1.2.0/bin/julia /usr/local/bin/julia

Update - those instructions were so last-century. Today, just install julia from the apt package manager:

apt install julia

To run your code, simply pass it as an argument to the runtime:

$ julia euler1.j
233168
$