Computer Science Department
School of Computer Science, Carnegie Mellon University
Linear Time Addition of Finonacci Encodings
Maoyuan (Raymond) Song
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.
Srinivasan Seshan, Head, Computer Science Department