Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

#1. Fibonacci Numbers, Quickly

Published

11 Jan, 2023

(Back to course page.)

Link to slides · Link to recording


Prompts for discussion:

Zeckendorf showed that each non-negative integer has a unique representation as a sum of Fibonacci numbers in which no two consecutive Fibonacci numbers occur. This observation leads to a numeral system. A natural question for a numeral system is how can we perform arithmetic operations on numbers in such a system, and how fast can we do it.

In particular:

  • Can you add and subtract nnn-digit numbers in the Zeckendorf system in O(n)O(n)O(n) time, as fast as in the binary system?

  • Can you multiply nnn-digit numbers in the Zeckendorf system in O(nlog⁡n)O(n \log n)O(nlogn) time, as fast as in the binary system?

Source


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×