14,664,021 members
Articles » General Programming » Algorithms & Recipes » Math
Article
Posted 9 Aug 2020

4.1K views
1 bookmarked

# Shooting Fibonacci Rabbits

Rate this:
17 Oct 2020GPL3
Two and three states Fibonacci Rabbit's Machines
Two state Fibonacci Rabbit's machine is well known and widely used at the moment. As to the three state I have found only a couple of number attempts to implement one, yet these were not successful. This is an attempt to provide C++17 code base for both two and three state Fibonacci Rabbit's machines.

## Practical Appliance

• Mathematical modeling and Educational purpose
• Finite/non-finite state machines (in Quantum Computing for instance)
• Probabilities, Combination and Permutation
• Random Number Generators
• Security and Cryptography

## Playing with Rabbits

### Two State (Standard) Machine

#### Prerequisites and Terminology

```0 - Junior Pair of Rabbits
1 - Mature Pair of Rabbits```

#### Algo

The algo is the simplicity itself:

• Junior Pair of Rabbits (0) breeds Mature Pair of Rabbits (1)
• 0->1
• Mature Pair of Rabbits (1) breeds Mature (1) (that is themselves) and Junior Pair (0)
• 1->10
• Rabbits never die

#### Running and Testing

Into ./r-seq folder, you will find one initial file for Rabbit Sequence: r-seq.001.

```\$ cat ./r-seq/r-seq.001
1```

After the code is compiled, the simplest way in running a binary file is:

```\$ ./rabbit-seq ./r-seq/r-seq.001
Growing ./r-seq/r-seq.001 to: ./r-seq/r-seq.002 ... Done.```

And the result is:

```\$ find ./r-seq/ -type f -name "r-seq.*"         \
-exec echo -n "{}:\"" \;                \
-exec cat {} \;                         \
-exec echo "\"" \;                      \
| sort
./r-seq/r-seq.001:"1"
./r-seq/r-seq.002:"10"```

For better convenience, there is a growing script:

```# growing one level only
\$ ./grower.sh 1
Growing ./r-seq/r-seq.002 to: ./r-seq/r-seq.003 ... Done.

# growing four levels
\$ ./grower.sh 4
Growing ./r-seq/r-seq.003 to: ./r-seq/r-seq.004 ... Done.
Growing ./r-seq/r-seq.004 to: ./r-seq/r-seq.005 ... Done.
Growing ./r-seq/r-seq.005 to: ./r-seq/r-seq.006 ... Done.
Growing ./r-seq/r-seq.006 to: ./r-seq/r-seq.007 ... Done.```

Checking the result:

```\$ find ./r-seq/ -type f -name "r-seq.*"         \
-exec echo -n "{}:\"" \;              \
-exec cat {} \;                       \
-exec echo "\"" \;                    \
| sort
./r-seq/r-seq.001:"1"
./r-seq/r-seq.002:"10"
./r-seq/r-seq.003:"101"
./r-seq/r-seq.004:"10110"
./r-seq/r-seq.005:"10110101"
./r-seq/r-seq.006:"1011010110110"
./r-seq/r-seq.007:"101101011011010110101"```

#### Phi Number

or Golden Number or Golden Ratio

There is an additional script in checking phi Number:

```./phi.sh
0 2/1
1 3/2
2 5/3
3 8/5
4 13/8
5 21/13
6 34/21
7 55/34
8 89/55
9 144/89
10 233/144
11 377/233
12 610/377
13 987/610
14 1597/987
15 2584/1597```

Here is a deviation from know Golden Number: 1.618033988749895

```./phi.sh | awk '{print \$2 "-1.618033988749895"}' | bc -l
.38196601125010500000
-.11803398874989500000
.04863267791677166666
-.01803398874989500000
.00696601125010500000
-.00264937336527961539
.00101363029772404761
-.00038692992636558824
.00014782943192318181
-.00005646066000735956
.00002156680566055555
-.00000823767693362661
.00000314652861958885
-.00000120186464909837
.00000045907178686423
-.00000017534976976519```

So far, so good, forks like magic.

### Three State Machine

Welcome to the shooting Range, hunting tickets for Fibonacci Rabbits are at the stake! :)

#### Terminology

```0 - Junior Pair of Rabbits
1 - Mature Pair of Rabbits
2 - Deceased Pair of Rabbits```

I have found two algos satisfying the task:

##### Algo A
• Junior Pair of Rabbits (0) breeds Mature Pair of Rabbits (1)
• 0->1
• Mature Pair of Rabbits (1) breeds Deceased Pair (2), Mature (1) and Junior Pair (0)
• 1->210
• Deceased Pair disappears
• 2->
##### Algo B
• Junior Pair of Rabbits (0) breeds Mature Pair of Rabbits (1) and Junior Pair (0)
• 0->10
• Mature Pair of Rabbits (1) breeds Deceased Pair (2) and Junior Pair (0)
• 1->20
• Deceased Pair disappears
• 2->

#### Running and Testing

I am going to run the tests only for Algo A. As to Algo B, the result is identical, I do encourage you to make this exercise yourself.

In order to switch from two state to three state, it will take some manual changes into the code and recompilation of cause.

Change:

```/////////////////////////////////////////////////////////////////
//! this is an Entry Point for Rabbit Generator
//! two state machine
processor<gens::st2::gen>(inFileStream, outFileStream);
//! three state machine algo A
// processor<gens::st3::gen_a>(inFileStream, outFileStream);
//! three state machine algo B
// processor<gens::st3::gen_b>(inFileStream, outFileStream);
```

to:

```/////////////////////////////////////////////////////////////////
//! this is an Entry Point for Rabbit Generator
//! two state machine
// processor<gens::st2::gen>(inFileStream, outFileStream);
//! three state machine algo A
processor<gens::st3::gen_a>(inFileStream, outFileStream);
//! three state machine algo B
// processor<gens::st3::gen_b>(inFileStream, outFileStream);
```

Recompiling:

`\$ make clean && make`

Let's grow some rabbits first:

```# removing from prev. experiments:
\$ for f in `ls ./r-seq/r-seq.* | grep -v 001`; do rm -f \$f; done

# growing
\$ ./grower.sh 15
Growing ./r-seq/r-seq.001 to: ./r-seq/r-seq.002 ... Done.
Growing ./r-seq/r-seq.002 to: ./r-seq/r-seq.003 ... Done.
Growing ./r-seq/r-seq.003 to: ./r-seq/r-seq.004 ... Done.
Growing ./r-seq/r-seq.004 to: ./r-seq/r-seq.005 ... Done.
Growing ./r-seq/r-seq.005 to: ./r-seq/r-seq.006 ... Done.
Growing ./r-seq/r-seq.006 to: ./r-seq/r-seq.007 ... Done.
Growing ./r-seq/r-seq.007 to: ./r-seq/r-seq.008 ... Done.
Growing ./r-seq/r-seq.008 to: ./r-seq/r-seq.009 ... Done.
Growing ./r-seq/r-seq.009 to: ./r-seq/r-seq.010 ... Done.
Growing ./r-seq/r-seq.010 to: ./r-seq/r-seq.011 ... Done.
Growing ./r-seq/r-seq.011 to: ./r-seq/r-seq.012 ... Done.
Growing ./r-seq/r-seq.012 to: ./r-seq/r-seq.013 ... Done.
Growing ./r-seq/r-seq.013 to: ./r-seq/r-seq.014 ... Done.
Growing ./r-seq/r-seq.014 to: ./r-seq/r-seq.015 ... Done.
Growing ./r-seq/r-seq.015 to: ./r-seq/r-seq.016 ... Done.```

Checking the result:

```\$ find ./r-seq/ -type f -name "r-seq.*"         \
-exec echo -n "{}:\"" \;              \
-exec cat {} \;                       \
-exec echo "\"" \;                    \
./r-seq/r-seq.001:"1"
./r-seq/r-seq.002:"210"
./r-seq/r-seq.003:"2101"
./r-seq/r-seq.004:"2101210"
./r-seq/r-seq.005:"21012102101"
./r-seq/r-seq.006:"210121021012101210"
./r-seq/r-seq.007:"21012102101210121021012102101"
./r-seq/r-seq.008:"21012102101210121021012102101210121021012101210"
./r-seq/r-seq.009:"2101210210121012102101210210121012102101210121021012102101210121021012102101"
./r-seq/r-seq.010:"2101210210121012102101210210121012102101210121021012102101210121021012102101
21012102101210121021012102101210121021012101210"```

Looks fairly good.

#### Checking phi:

```./phi.sh | awk '{print \$2 "-1.618033988749895"}' | bc -l
1.38196601125010500000
-.28470065541656166667
.13196601125010500000
-.04660541732132357143
.01832964761374136363
-.00692287763878388889
.00265566642251879310
-.00101271215415031915
.00038706388168394736
-.00014780988810638212
.00005646351141153266
-.00002156638964655280
.00000823773762899232
-.00000314651976451365
.00000120186594077712```

Looks good too.

### TODO

* I have NOT found an algo (and better implementation) for uniqueness (non-repetitiveness) check of a Fractal. It is to be proved that N level could be produced by only N-1 one, it could not be generated from scratch.

this is done: The check is implemented: Uniqueness / non-repetitiveness check for Fibonacci Rabbit Fractal · Issue #1 · george-shagov/fibonacci-rabbits

## Meta

https://github.com/george-shagov/fibonacci-rabbits

## Share

 Software Developer (Senior) Russian Federation
No Biography provided

 First Prev Next
 Seems somewhat misleading given that classical Fibonacci sequences are normally written as simple functions Member 1172068119-Oct-20 6:40 Member 11720681 19-Oct-20 6:40
 Re: Seems somewhat misleading given that classical Fibonacci sequences are normally written as simple functions Member 1172068119-Oct-20 7:46 Member 11720681 19-Oct-20 7:46
 Uniqueness / non-repetitiveness check for Fibonacci Rabbit Fractal George Shagov17-Oct-20 0:07 George Shagov 17-Oct-20 0:07
 Re: Uniqueness / non-repetitiveness check for Fibonacci Rabbit Fractal OriginalGriff17-Oct-20 0:10 OriginalGriff 17-Oct-20 0:10
 thanks for this good info! Southmountain18-Aug-20 6:42 Southmountain 18-Aug-20 6:42
 Re: thanks for this good info! George Shagov16-Oct-20 23:27 George Shagov 16-Oct-20 23:27
 Re: thanks for this good info! Southmountain17-Oct-20 11:07 Southmountain 17-Oct-20 11:07
 Last Visit: 24-Oct-20 22:26     Last Update: 24-Oct-20 22:26 Refresh 1