Fibonacci Encoding is a binary coding theme with applications in cryptography and data transmission. However, fast addition of Fibonacci Encodings is non-trivial due to carrying being bi-directional. We present and prove correctness for an O(n) algorithm that when given two Fibonacci encoded natural numbers of length n, returns a Fibonacci Encoding representing their sum ,without decoding. The algorithm is implemented and tested against the naïve algorithm.

28 pages

Thesis Committee:
Carl Kingsford (Chair)
Daniel Sleator

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]