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 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^9and easily fit the data into
- 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
BigIntvalues and check them only if the
Intbased test passes.
- The good thing is tha Julia ships with the
digitsfunction so I can easily get a vector of digits of a given number.
- I need to combine
BigIntcalculations to cut down the processing time. Most of the time it should be enough to analyze just
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.
The following code contains the implementation of the algorithm following the observations I have described above:
big1, big2 = big(1), big(1)
small1, small2 = 1, 1
k = 2
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 &&
Note that we perform computations both on
Int values (
small2) and on
BigInt values (
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
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.
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.