CMU-CS-20-118
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-20-118

Linear Time Addition of Finonacci Encodings

Maoyuan (Raymond) Song

M.S. Thesis

May 2020

CMU-CS-20-118.pdf


Keywords: Theory, Algorithms, Compression, Fibonacci Codes, Zeckendorf's Theorem

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 reports@cs.cmu.edu