Project Euler 2 - 2023-09-29
The second problem is supposed to be on the same level as the first one but I already struggled a bit.
I misread the task and confused “terms in the Fibonacci sequence whose values do not exceed four million” with “fourth million Fibonacci term”.
Instead of calculating to the 33th term I calculated to the 4_000_000th term. :D
15 minutes later I got a rather big number on the screen and realised I did something wrong.
Initially I created a growing list containing all elements from 1 to n which then was iterated a last time to calculate the sum of all even-valued terms. But because of a failure in the exit condition the tests ran into a timeout.
But I didn’t see that yet and believed the problem was the list with four million entries, so I refactored the solution to only work with a two element tuple and calculate the sum of the even-valued terms on every iteration.
Since this also resulted in a timeout, I checked the exit condition again and found the real problem. And since I like the two-element-tuple solution more than the initial one I kept it. :)
A quick benchmark suggests that the version using lists is 1.78 times slower than the ones using tuples.
$ mix run benchmarks/problem_2.exs
Operating System: macOS
CPU Information: Apple M1
Number of Available Cores: 8
Available memory: 16 GB
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
inputs: none specified
Estimated total run time: 14 s
Benchmarking list ...
Benchmarking tuple ...
Name ips average deviation median 99th %
tuple 5.06 M 197.69 ns ±16067.94% 125 ns 250 ns
list 2.84 M 351.74 ns ±8009.82% 292 ns 459 ns
tuple 5.06 M
list 2.84 M - 1.78x slower +154.05 ns