Project Euler – Problem 2

The first problem from Project Euler collection was quite a tasty appetizer. I have moved on to the second one looking for another challenge and I found four (almost five…)! Looking more deeply into the solutions and their implications often brings new questions and arouses curiosity: that’s what I’d call “recreational mathematics”. It’s quite a long read below this point, I hope you enjoy it as much as I enjoyed writing!

Even Fibonacci numbers: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Foreword: I’ll be using the <‘> as thousands separator to make involved numbers easier to read, since they’ll be usually quite long (like, 19-digit long!).

First approach is a “brute force” computation: evaluate all terms of Fibonacci sequence up to 4’000’000 picking the even-valued ones, add them, measure execution time (using /usr/bin/time for the task) and that’s it. There are quite few of them (see more on the OEIS – Online Encyclopedia of Integer Sequences page):

2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, 3524578

The requested solution is, finally, 4’613’732. Easy but… wait! SPOILER ALERT! Execution time is 0.00 s? Do I have an infinitely fast computer? And what’s that monster number down there?

Pretty fast, huh?

The script can accept an argument for the limit, defaulting to 4’000’000, which allows me to push the process over and over, up to that huge thing; I was trying to bump the last significant digit of the result at least to 1 (that is 1/100th s), without success. Let’s see the code, at last:

#!/bin/bash
tin=$(date +"%s %-N") # format: ssssssssss NNNNNNNNN sum=0 fib0=0 fib1=1 fibn=0 # 4000000 / 2880067194370816120 lim=${1:-4000000}
while [[ $fib0 -le$lim && $fib0 -ge 0 ]] do if [[$fib0%2 -eq 0 ]]
then sum=$((sum+fib0)) #echo$fib0
fi
fibn=$((fib0+fib1)) fib0=$fib1
fib1=$fibn done echo$sum
tend=$(date +"%s %-N") ttot=$((((${tend:0:10}-${tin:0:10})*1000000000)+(${tend:11}-${tin:11})))
echo "Total execution time: $ttot ns" exit 0 Challenge #1: In a matter of (nano)seconds! First of all, I tackled the execution time problem using date command, polling the values of Unix epoch (%s flag) and nanoseconds without leading zeroes (%-N flag) at the beginning and at the end of the script. I feel the urge write my birthday date in Unix epoch, for some reason Notice the value from the second run of date is 1 digit shorter than the first one, default output would be “050178346″). Leading zeroes yield pretty weird (wrong!) results. Echoes The shell, be it bash or any other, is also not the best tool for maths, but I’ll just pretend I am not aware of that… Challenge #2: Monsters & Co. Overflow in action $\text{M = }2'880'067'194'370'816'120$, the monster number. The shell is unable to deal with arbitrarily large numbers. The Largest Positive Integer (see Stack Overflow thread) that can be correctly evaluated is $\text{LPI = }2^{63}-1=9'223'372'036'854'775'807$ (that is about 9×1018 or 9 quintillions). Trying to compute a larger value causes an overflow and wreaks havoc on your maths. The search limit and the result must therefore be kept lower or equal than $\text{LPI}$. The condition “$fib0 -ge 0detects the overflow and stops the process.

M is the largest Fibonacci even term smaller than LPI, the 90th in the sequence. The next even term, the 93rd, is $12'200'160'415'121'876'738$.

Finally, the actual execution times are revealed: 2111658 ns ≅ 2.111 ms ≅ 0.002 s (adding 12 terms) and ~0.0029 s (adding 31 terms), both below the precision provided by time.

Approaching the limit…

An additional run shows how much execution time is affected by echo-ing the even-valued terms (almost 20% more); different runs under the same conditions usually yield little variations in execution times. For the sake of simplicity I am therefore showing one-shot runs of the scripts.

To echo, or not to echo – that is the question…

Challenge #3: Might as well jump!

Looking for a smarter, more efficient way to solve the problem, I noticed that even terms appear every 3 iterations in the sequence, that is when two odd numbers are added to make the next term. So F0, F3, F6, … will all be relevant.

|-> F0     0 EVEN <-| F1      1 odd | F2      1 odd |
|-> F3     2 EVEN <-| F4      3 odd | F5      5 odd |
|-> F6     8 EVEN <-| F7     13 odd | F8     21 odd |
|-> F9    34 EVEN <-| F10    55 odd | F11    89 odd |


I still have to evaluate all the terms, but I can avoid checking whether they’re even or odd. A little variation in the code does the trick: index j makes the calculation loop 3 times before it can serve a surely even value to add to the total.

[ ... ]
while [[ $fib0 -le$lim && $fib0 -ge 0 ]] do sum=$((sum+fib0))
for j in 1 2 3
do
fibn=$((fib0+fib1)) fib0=$fib1
fib1=$fibn done done echo$sum
[ ... ]

How effective has the modification been? Let’s see…

Compared to the “brute force” version, execution takes almost 18% less time (2111658 – 1794253 = 317405 ns). “Impressive, most impressive!“, Darth Vader would say. In the long run up to 2’880 zillions the difference is almost 22%, marking a significant gain in performance.

Challenge #4: Who needs scripts when you have one-liners?

Well, that sounds a little like trolling myself, but it’s true: an awk one-liner can do the job. I eventually generated the list of Fibonacci terms and stored it in a file for testing purposes, in the neat format you’ve seen above (F<index> <TAB> <number> <TAB> <EVEN/odd tag>). That was just perfect for awk to process: I didn’t even bother to show execution time, y’know, although the trip through awk seems to push it up somewhere around 0.003 s.

awk, what else?

One more, somehow simpler… Put it all together and pipe to bc, that is meant to do the maths.

Here with his fellow bc

Cost – benefits comparison: each one-liner took me a minute to write/test/debug (sort of…) while the full script took me about half an hour. I think I can bear with 1 fu***n’ millisecond more of the one-liner!

Challenge #5: Floating away

Close, very close…

A further optimization of the “jumps” described in Challenge #3 would be to evaluate only the relevant terms. The task can be accomplished, for example, using the Binet’s Fibonacci number formula, that requires floating point operations. That goes beyond capabilities of bash, that only accepts integers, and looks weird in zsh, just… you see… 0.00000000000000002 weirder that normal.

So I’ll save this challenge for the (near?) future, probably for some snake-themed language (that’s not true, the story is different!), if you know what I mean…

Cheers!

Informazioni su Man from Mars

https://extendedreality.wordpress.com/
1. Ralph Magpie

what better opportunity to use python to solve …….

Mi piace

2. Pingback: Visto nel Web – 190 | Ok, panico

3. Pingback: A Man from Mars | Ok, panico