fiboservice

FiboService is a service for calculating fibonacci numbers using matrix multiplication. I'm working on this simple project to improve as a programmer.

https://github.com/ptohidi/fiboservice

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

✓
CITATION.cff file
Found CITATION.cff file
✓
codemeta.json file
Found codemeta.json file
✓
.zenodo.json file
Found .zenodo.json file
✓
DOI references
Found 1 DOI reference(s) in README
✓
Academic publication links
Links to: zenodo.org
○
Academic email domains
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (6.3%) to scientific vocabulary

Keywords

fibonacci practice python

Last synced: 6 months ago · JSON representation ·

Repository

FiboService is a service for calculating fibonacci numbers using matrix multiplication. I'm working on this simple project to improve as a programmer.

Basic Info

Host: GitHub
Owner: ptohidi
License: mit
Language: Python
Default Branch: main
Homepage:
Size: 46.9 KB

Statistics

Stars: 0
Watchers: 1
Forks: 0
Open Issues: 0
Releases: 2

Topics

fibonacci practice python

Created about 2 years ago · Last pushed almost 2 years ago

Metadata Files

Readme License Citation Codeowners

FiboService

FiboService is a Python package that I have made for practicing purposes. It calculates Fibonacci numbers using 2x2 matrix multiplication and caches the results for faster calculation.

Theory

The Fibonacci numbers are defined by the following recurrence relation:

$Fn = F{n-1} + F_{n-2},$

with seed values $F0 = 0$ and $F1 = 1$.

It can be shown by mathematical induction that if we define the matrix $A$ as: math A = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}, then, $\forall n \in \mathbb{N}$, we will have: math A^n = \begin{bmatrix}F_{n+1} & F_n \\ F_n & F_{n-1}\end{bmatrix}. In this package, we make use of this property to calculate the Fibonacci numbers: math \begin{bmatrix}F_{n+1} & F_n \\ F_n & F_{n-1}\end{bmatrix} = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^n

We can calculate $A^n$ using the binary representation of $n$ and the following recursive formula:

math A^n = \begin{cases} A^{\frac{n}{2}} \times A^{\frac{n}{2}} & \text{if } n \text{ is even} \\ A^{n-1} \times A & \text{if } n \text{ is odd} \end{cases}.

Using this approach, we can calculate $A^n$ in $O(\log n)$ operations. Specifically, the number of matrix multiplications needed to calculate $A^n$ is equal to the number of ones in the binary representation of $n$ plus the length of the binary representation of $n$ minus 2.

License

See the LICENSE file for license rights and limitations (MIT).

Emoji Section

:godmode:

Owner

Name: Pouria Tohidi
Login: ptohidi
Kind: user
Location: Baltimore
Company: Johns Hopkins University

Repositories: 1
Profile: https://github.com/ptohidi

Citation (CITATION.cff)

cff-version: 1.2.0
message: If you use this software, please cite it as below.
authors:
- family-names: "Tohidi"
  given-names: "Pouria"
  orcid: "https://orcid.org/0000-0003-1477-7577"
title: "FiboService"
version: 0.1
date-released: 2024-01-15
url: "https://github.com/ptohidi/FiboService"

ecosyste.ms

Data

Tools

Indexes

Applications

Experiments

Open Source Science