Editing Fibonacci sequence (section)

=== Computer science ===
[[File:Fibonacci Tree 6.svg|thumb|upright=1.2|Fibonacci tree of height 6. [[AVL tree#Balance factor|Balance factor]]s green; heights red.<br />The keys in the left spine are Fibonacci numbers.]]

* The Fibonacci numbers are important in [[Analysis of algorithms|computational run-time analysis]] of [[Euclidean algorithm|Euclid's algorithm]] to determine the [[greatest common divisor]] of two integers: the worst case input for this algorithm is a pair of consecutive Fibonacci numbers.<ref>{{Citation| first= Donald E |last= Knuth| author-link= Donald Knuth | year =1997|title=The Art of Computer Programming | volume = 1: Fundamental Algorithms|edition= 3rd | publisher = Addison–Wesley |isbn=978-0-201-89683-1 | page = 343}}</ref>
* Fibonacci numbers are used in a polyphase version of the [[merge sort]] algorithm in which an unsorted list is divided into two lists whose lengths correspond to sequential Fibonacci numbers—by dividing the list so that the two parts have lengths in the approximate proportion {{mvar|φ}}. A tape-drive implementation of the [[polyphase merge sort]] was described in ''[[The Art of Computer Programming]]''.
* {{anchor|Fibonacci Tree}}A Fibonacci tree is a [[binary tree]] whose child trees (recursively) differ in [[Tree height|height]] by exactly 1. So it is an [[AVL tree]], and one with the fewest nodes for a given height—the "thinnest" AVL tree. These trees have a number of vertices that is a Fibonacci number minus one, an important fact in the analysis of AVL trees.<ref>{{citation|last1=Adelson-Velsky|first1=Georgy|last2=Landis|first2=Evgenii|year=1962|title=An algorithm for the organization of information|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=146|pages=263–266|language=ru}} [https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf English translation] by Myron J. Ricci in ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref>
* Fibonacci numbers are used by some [[pseudorandom number generator]]s.<!-- Knuth vol. 2 -->
* Fibonacci numbers arise in the analysis of the [[Fibonacci heap]] data structure.
* A one-dimensional optimization method, called the [[Fibonacci search technique]], uses Fibonacci numbers.<ref>{{Citation| first1 = M | last1 = Avriel | first2 = DJ | last2 = Wilde | title= Optimality of the Symmetric Fibonacci Search Technique |journal=Fibonacci Quarterly|year=1966 |issue=3 |pages= 265–69| doi = 10.1080/00150517.1966.12431364 }}</ref>
* The Fibonacci number series is used for optional [[lossy compression]] in the [[Interchange File Format|IFF]] [[8SVX]] audio file format used on [[Amiga]] computers. The number series [[companding|compands]] the original audio wave similar to logarithmic methods such as [[μ-law]].<ref>{{Citation | title = Amiga ROM Kernel Reference Manual | publisher = Addison–Wesley | year = 1991}}</ref><ref>{{Citation | url = https://wiki.multimedia.cx/index.php?title=IFF#Fibonacci_Delta_Compression | contribution = IFF | title = Multimedia Wiki}}</ref>
* Some Agile teams use a modified series called the "Modified Fibonacci Series" in [[planning poker]], as an estimation tool. Planning Poker is a formal part of the [[Scaled agile framework|Scaled Agile Framework]].<ref>{{citation|author=Dean Leffingwell |url=https://www.scaledagileframework.com/story/ |title=Story |publisher=Scaled Agile Framework |date=2021-07-01 |accessdate=2022-08-15}}</ref>
* [[Fibonacci coding]]
* [[Negafibonacci coding]]