By: Blog by Bogumił Kamiński

Re-posted from: https://bkamins.github.io/julialang/2023/11/24/pe104.html

Introduction

Today my post was inspired by an interesting write-up by Christopher Rackauckas:
ChatGPT performs better on Julia than Python (and R) for Large Language Model (LLM) Code Generation. Why?.
The general take away of this text is that writing Julia code with LLM support is efficient.

A thing that I think is relevant here is that when you write code you typically want to get your job done as fast as possible.
Getting the job done typically involves three steps (possibly repeated):

• Thinking about the algorithm.
• Implementing it.
• Running the code.

Each of these steps takes time. And you, usually, want to get a solution in a minimum possible total time.

My experience is that Julia is really fast to code with once you learn it (and as Chris explained using LLMs
boosts this time even further).

Since Julia is compiled it also offers fast code execution times.

So we are left with algorithm design time. And this is the point that lead me to write this post.
The reason is that my experience is that I often decide to use non-optimal algorithms, because
with Julia I know my code will be reasonably fast anyway. This is especially the case if I can
see a simple solution that uses basic functionalities in-built into Julia and do not require too much thought.

To test-drive this assertion today I chose a Project Euler problem that I have not solved before and decided
to write down my thought process when solving it. My choice was problem 104, because it was a first relatively easy
(so I assumed I would not need to spend too much time on it) problem I have not solved yet.

The code was written under Julia 1.9.2.

The problem

The Project Euler problem 104 is stated as follows (abbreviated):

Find the number of the smallest Fibonacci number for which
its first nine digits contain all the digits 1 to 9 (not necessarily in order)
and the same condition holds for its last nine digits.

Thinking about the algorithm

The observations I made are the following:

• I assumed that the problem is not trivial – I need to do some optimizations to solve it in a reasonable time.
• The last nine digits are easier; I can just track values modulo 10^9 and easily fit the data into Int type.
• The number formed by last nine digits must be divisible by 9 as the sum of numbers from 1 to 9 is 45.
• The first nine digits are harder. I could get them by using the Binet’s Formula, but this would require analysis of round-off error of floating-point operations.
  This would take thinking time, so maybe it is enough to just use the BigInt values and check them only if the Int based test passes.
• The good thing is tha Julia ships with the digits function so I can easily get a vector of digits of a given number.
• I need to combine Int and BigInt calculations to cut down the processing time. Most of the time it should be enough to analyze just Int values.

As you can see, I decided not to invest too much into the thinking time,
hoping that the implementation of the above algorithm will be easy and its run time will be acceptable.

Implementing it

The following code contains the implementation of the algorithm following the observations I have described above:

function pe104()
    big1, big2 = big(1), big(1)
    small1, small2 = 1, 1
    k = 2
    while true
        k += 1
        big1, big2 = big1 + big2, big1
        small1, small2 = (small1 + small2) % 10^9, small1

        small1 % 9 == 0 &&
        sort!(digits(small1)) == 1:9 &&
        sort!(last(digits(big1), 9)) == 1:9 &&
        return k
    end
end

Note that we perform computations both on Int values (small1 and small2) and on BigInt values (big1 and big2).
In the code we do three tests to decide if a given k is good. The tests are ordered in the increasing order of computational cost.
Note that since the Int values are computed modulo 10^9 I do not need to do any trimming of vector of digits returned by digits(small1).

Running the code

Let us check how much time it takes to find the solution:

julia> @time pe104();
 16.634432 seconds (696.82 k allocations: 4.441 GiB, 3.01% gc time)

Note that I put ; at the end of the line to suppress printing of the solution (in hope to encourage you to run the code yourself).
The point is that the run time of the code is just a few seconds. The code is clearly not optimal and could be significantly faster.
However, I am sure that speeding it up would take me more time than I would save in run time. Thus, I am happy with what I got.

Conclusions

In general Julia allows you to write efficient code. There are many applications where it is crucial and it is worth to spend a lot of time
on optimization of run-time. This is especially true if you write your code once and run it millions of times.

However, in many cases, like the one presented today, Julia is fast enough so even code that is not fully performant is good enough.
Often such simpler code takes: less time to design, less time to implement, and less time to prove its correctness.