Fun to Program -- Fibonacci numbers

This was originally written and created around 2013 and may require to be updated. (2021)

Fibonacci numbers

The Fibonacci numbers are a sequence of integers, starting with 0, 1 and continuing 1, 2, 3, 5, 8, 13, …, each new number being the sum of the previous two.

Let’s check simple code snippets to obtain Fibonacci numbers implemented in different languages to study the following:

basic while-loop syntax
integer overflow behavior

Shell

Before we start, let’s check the integer overflow behavior of the shell on the 64-bit GNU/Linux platform.

Dash behavior for the integer overflow etc.

$ echo "$(echo 2^62 | bc)    $((4611686018427387904))"
4611686018427387904    4611686018427387904
$ echo "$(echo 2^63-1 | bc)  $((9223372036854775807))"
9223372036854775807  9223372036854775807
$ echo "$(echo 2^63 | bc)    $((9223372036854775808))"
9223372036854775808    9223372036854775807
$ echo "$(echo 2^64-1 | bc) $((18446744073709551615))"
18446744073709551615 9223372036854775807
$ echo "$(echo 2^64 | bc)   $((18446744073709551616))"
18446744073709551616   9223372036854775807
$ echo "$((2**62))"
/path/to/sh/../../bin/p: 1: eval: arithmetic expression: expecting primary: "2**
62"

Bash behavior for the integer overflow etc.

$ echo "$(echo 2^62 | bc)    $((4611686018427387904))"
4611686018427387904    4611686018427387904
$ echo "$(echo 2^63-1 | bc)  $((9223372036854775807))"
9223372036854775807  9223372036854775807
$ echo "$(echo 2^63 | bc)    $((9223372036854775808))"
9223372036854775808    -9223372036854775808
$ echo "$(echo 2^64-1 | bc) $((18446744073709551615))"
18446744073709551615 -1
$ echo "$(echo 2^64 | bc)   $((18446744073709551616))"
18446744073709551616   0
$ echo "$((2**62))"
4611686018427387904

The arithmetic expression always returns the largest positive integer when overflows for Dash.

The “**” operator for arithmetic expression in “$((...))” is not POSIX but an usable extension for Bash.

TIP: For arbitrary precision calculation, always use “bc”.

Here is a shell program for the Fibonacci numbers.

Source code for the shell script: fibo

#!/bin/sh 
N="$1"
A=0
B=1
while [ "$B" -lt "$N" ]; do
    echo "$B"
    C=$B 
    B=$(($A+$B))
    A=$C 
    if [ "$B" -lt "0" ]; then
        echo "E: OVER FLOW at $B, stopped."
        exit 1
    fi
done

Even with some overflow protection is coded in this to avoid infinite loop, if you provide an argument to “./fibo” which is larger than “$(echo '2^63' | bc)” then this program will fail in a cryptic way.

Error with the integer overflow for the shell script

$ ./fibo "$(echo 2^63-1 | bc)"|tail
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
E: OVER FLOW at -6246583658587674878, stopped.
$ ./fibo "$(echo 2^63 | bc)"|tail
./fibo: 5: [: Illegal number: 9223372036854775808

TIP: Do not abuse shell code when integer overflow may occur. Its response to the overflow is cryptic.

Python

Here is a Python program for the Fibonacci numbers.

Source code for the Python script: fibo

#!/usr/bin/python3
import sys
n = int(sys.argv[1])
a, b = 0, 1
while b < n:
    print(b)
    a, b = b, a + b

TIP: Python3 integer supports the arbitrary precision number which does not overflow :-)

Lua

Here is a Lua program for the Fibonacci numbers.

Source code for the Lua script: fibo

#!/usr/bin/lua
    n = arg[1] +0;
    a = 0;
    b = 1;
    while ( b < n ) do
        print(b);
        a, b = b, a + b;
    end

Lua automatically converts large integer numbers to the double type.

Behavior with the large integer for the Lua script

$ ./fibo "$(echo 2^51 | bc)"|tail
27777890035288
44945570212853
72723460248141
1.1766903046099e+14
1.9039249070914e+14
3.0806152117013e+14
4.9845401187926e+14
8.0651553304939e+14
1.3049695449287e+15
2.111485077978e+15

TIP: Be careful with the behavior of Lua for large integer numbers :-)

Perl

Here is a Perl program for the Fibonacci numbers.

Source code for the Perl script: fibo

#!/usr/bin/perl -w
    $n = "$ARGV[0]" + 0;
    $a = 0;
    $b = 1;
    while ( $b < $n ) {
        print "$b\n";
        $c = $b;
        $b = $a + $b;
        $a = $c;
    }

Perl automatically converts large integer numbers to the double type.

Behavior with the large integer for the Perl script

$ ./fibo "$(echo 2^65 | bc)"|tail
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
12200160415121876738
1.97402742198682e+19
3.19404346349901e+19

TIP: Be careful with the behavior of Perl for large integer numbers :-)

C

Before we start, let’s check the integer overflow behavior of “strtol” on the 64-bit GNU/Linux platform using simple test code. (This is more like how Dash behaves as of 2013.)

C long behavior for the integer overflow

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv)
{
    long n = strtol(argv[1], NULL, 10);
    printf("Parsed as %ld\n", n);
    return EXIT_SUCCESS;
}

Let’s compile and test this C code.

Testing the C strtol with the integer overflow

$ gcc -Wall -o strtol-test strtol-test.c
$ ./strtol-test 9223372036854775807
Parsed as 9223372036854775807
$ ./strtol-test 9223372036854775808
Parsed as 9223372036854775807
$ ./strtol-test 18446744073709551615
Parsed as 9223372036854775807
$ ./strtol-test 18446744073709551616
Parsed as 9223372036854775807

The C strtol always returns the largest positive integer when overflows,

Here is a C program for the Fibonacci numbers.

Source code for the C: fibo.c

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv)
{
    long n = strtol(argv[1], NULL, 10);
    long a = 0;
    long b = 1;
    long c;
    while (b < n) {
        printf("%ld\n", b);
        c = b;
        b = a + b;
        a = c;
        if (b < 0) {
            printf("E: overflow %ld\n", b);
            exit(EXIT_FAILURE);
        }
    }
    return EXIT_SUCCESS;
}

The C long sufferes overflow and needs to be dealt carefully.

Error with the integer overflow for C

$ ./fibo "$(echo 2^63-1 | bc)"|tail
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
E: overflow -6246583658587674878

TIP: Be careful with overflow.

Vala

Here is a vala program for the Fibonacci numbers.