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!

## Problem 2 [link]

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?

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.

Notice the value from the second run of `date`

is 1 digit shorter than the first one, default output would be “**0**50178346″). Leading zeroes yield pretty weird (wrong!) results.

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.**

, the monster number. The shell is unable to deal with arbitrarily large numbers. The **L**argest **P**ositive **I**nteger (see Stack Overflow thread) that can be correctly evaluated is

(that is about 9×10^{18} 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 . The condition “`$fib0 -ge 0`

” *detects* 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 .

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`

.

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.

### 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.

One more, somehow simpler… Put it all together and pipe to `bc`

, that is meant to do the maths.

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’* **milli**second more of the one-liner!

### Challenge #5: Floating away

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!

what better opportunity to use python to solve …….

Mi piaceMi piace

Time will come…

Mi piaceMi piace

Pingback: Visto nel Web – 190 | Ok, panico

Pingback: A Man from Mars | Ok, panico

Pingback: Project Euler: problem 6 | Extended Reality

Pingback: Project Euler: problem 20 | Extended Reality