Fibonacci number system

(In this post, “number” means “positive integer”.)

Simply speaking, if we substitute 2’s or 10’s power system as the basis for presentation with Fibonacci series, we can get  Fibonacci “based” number system.

For example, number 16 (base 10) can be converted into Fibonacci number system like this:

16 -> The biggest smaller Fibonacci number 13 take out 1 time -> Remainder is 3

3 –> The biggest smaller Fibonacci number 8 take out 0 time –> Remainder is 3

3 –> The biggest smaller Fibonacci number 5 take out 0 time –> Remainder is 3

3 –> The biggest smaller Fibonacci number 3 take out 1 time –> Remainder is 0

0 –> The biggest smaller Fibonacci number 2 take out 0 time –> Remainder is 0

0 –> The biggest smaller Fibonacci number 1 take out 0 time –> Remainder is 0

(and ignore the first Fibonacci number 1)

Output -> 16 (base 10) = 100100 (base Fibonacci).

It is easy to see that:

  1. Each number has unique representation
  2. Each representation has unique number
  3. Because for n>3, Fibonacci(n) < 2 * Fibonacci(n-1), the representation is using only 2 symbols, 1 and 0
  4. Because Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), there could be no two consecutive 1s in Fibonacci number system. 0110 (base Fibonacci) is the same as 1000 (base Fibonacci) and the only latter one is valid
  5. Because 11 is an invalid sequence, Fibonacci presentation of a number will be longer than base 2 presentation (normal binary)

Stay tuned for the code and more observations about basic arithmetic operations – or start sharing here 🙂

BTW, we can use any strictly increasing monotonic series as the basis for a number system which has first element as 1. (That is, it is possible to come up with factorial number system also.)

Here is the code:

using namespace std;
#include <iostream>
#include <string>
#include <fstream>

const int size = 50; // maximum size of presentation
unsigned long int f[size]; // place value holder
int value = 100; // number of integers to convert

void fill (unsigned long int *f);
void convert (int i, int j, std::string &s);
int findMSP (int i);

int main(int argc, char** argv) {

ofstream outfile;
outfile.open(“FibonacciNumbers.csv”);

// Create a long enough place value array
fill(f);

// now convert integers from 1 through ‘value’ to the new place value system
for (int i = 1; i < value; i++) {

std:string presentation;
convert(i, findMSP(i), presentation);
outfile << i << “,” << presentation << endl;

}

outfile.close();

return 0;

}

// core logic

void convert (int i, int j, std::string &s) {

int mul = i/f[j];

i %= f[j];

s.append(1,(char)mul+’0′);

if (j >= 1) convert (i, –j, s);
else return;

}

// just how many places are needed for the number in the new place value system
int findMSP (int i) {

int j = size – 1;
for (; j >=1; j–) {

if (f[j] <= i) break;

}
return j;

}

void fill (unsigned long int *f) {

// fibonacci for now
f[0] = 1;
f[1] = 2;
for (int i = 2; i < size; i++) {

f[i] = f[i-1] + f[i-2];

}

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s