Algorithms for computing Fibonacci numbers quickly Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/gm80hx78m

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • A study of the running time of several known algorithms and several new algorithms to compute the n[superscript th] element of the Fibonacci sequence is presented. Since the size of the n[superscript th] Fibonacci number grows exponentially with n, the number of bit operations, instead of the number of integer operations, was used as the unit of time. The number of bit operations used to compute f[subscript n] is reduced to less than 1/2 of the number of bit operations used to multiply two n bit numbers. The algorithms were programmed in Ibuki Common Lisp and timing runs were made on a Sequent Balance 21000. Multiplication was implemented using the standard n² algorithm. Times for the various algorithms are reported as various constants times n². An algorithm based on generating factors of Fibonacci numbers had the smallest constant. The Fibonacci sequence, arranged in various ways, is searched for redundant information that could be eliminated to reduce the number of operations. Cycles in the b[superscript th] bit of f[subscript n] were discovered but are not yet completely understood.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6670 in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-05-29T19:10:06Z (GMT) No. of bitstreams: 1 HollowayJamesL1989.pdf: 601336 bytes, checksum: 28ff8447a17279ab27aa8f4a3bcae6d2 (MD5)
  • description.provenance : Submitted by Katy Davis (kdscannerosu@gmail.com) on 2013-05-24T20:55:05Z No. of bitstreams: 1 HollowayJamesL1989.pdf: 601336 bytes, checksum: 28ff8447a17279ab27aa8f4a3bcae6d2 (MD5)
  • description.provenance : Made available in DSpace on 2013-06-28T23:49:16Z (GMT). No. of bitstreams: 1 HollowayJamesL1989.pdf: 601336 bytes, checksum: 28ff8447a17279ab27aa8f4a3bcae6d2 (MD5) Previous issue date: 1988-05-10
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-06-28T23:49:16Z (GMT) No. of bitstreams: 1 HollowayJamesL1989.pdf: 601336 bytes, checksum: 28ff8447a17279ab27aa8f4a3bcae6d2 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items