Math::N...ibonacci(3)

📦
version 75 · 2 versions
, in fedora 43

💖 Math::NumSeq::Fibonacci — the Fibonacci numbers, bestie 💖

Okay so this page is Math::N...ibonacci(3), from the User Contributed Perl Documentation, and it's literally about one of the most iconic sequences in all of math. The Fibonacci numbers. Main character energy fr fr. Let's get into it. 🐚✨

🌸 NAME 🌸

Math::NumSeq::Fibonacci — Fibonacci numbers, periodt. 💅

✨ SYNOPSIS ✨

use Math::NumSeq::Fibonacci;
my $seq = Math::NumSeq::Fibonacci->new;
my ($i, $value) = $seq->next;

That's it, that's the whole vibe. Create it, pull numbers out of it, slay. 🫶

🦋 DESCRIPTION 🦋

The Fibonacci numbers are F(i) = F(i-1) + F(i-2), and the sequence starts from 0,1, giving you:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
starting i=0

Each one is just the two before it added together. No cap, that's the whole recipe and it ate. 🔥

👑 FUNCTIONS 👑

There's some common behaviour shared across all sequence classes, so peep "FUNCTIONS" in Math::NumSeq for the stuff everybody's got. 💜

  • "$seq = Math::NumSeq::Fibonacci->new ()" — makes a brand new sequence object and hands it to you. Fresh out the box. 🎀

🌈 Iterating

  • "($i, $value) = $seq->next()" — gives you the next index and value in the sequence. When $value gets bigger than what a Perl unsigned integer can hold, it returns a Math::BigInt instead, so the precision stays intact. No rounding, no drama. 💅
  • "$seq->seek_to_i($i)" — jumps the current position in the sequence over to $i. Then the next time you call next() it'll return that $i and its matching value. Teleportation but make it math. ✨

🧚 Random Access

  • "$value = $seq->ith($i)" — returns the $i'th Fibonacci number. 📍

For negative <$i>, the sequence gets extended backwards like F[i]=F[i+2]-F[i+1]. Same Fibonacci numbers, but they come out negative at negative even i. Behold:

  i     F[i]
 ---    ----
  0       0
 -1       1
 -2      -1       <----+ negative at even i
 -3       2            |
 -4      -3       <----+

And again — when $value exceeds the range of a Perl unsigned integer, you get back a Math::BigInt to keep the precision. 🧮

  • "$bool = $seq->pred($value)" — returns true if $value actually shows up in the sequence, so basically: is this a positive Fibonacci number or not? vibe check passed or failed. ✅
  • "$i = $seq->value_to_i_estimate($value)" — gives you an estimate of the i that goes with $value. More on that in "Value to i Estimate" down below. 👇

🔥 FORMULAS 🔥

💫 Ith

You can compute Fibonacci F[i] with a powering procedure that does two squares per step. It keeps a pair of values, F[k] and F[k-1], and advances them according to the bits of i, going from high to low:

start k=1, F[k]=1, F[k-1]=0
add = -2       # 2*(-1)^k

loop
  F[2k+1] = 4*F[k]^2 - F[k-1]^2 + add
  F[2k-1] =   F[k]^2 + F[k-1]^2

  F[2k] = F[2k+1] - F[2k-1]

  bit = next bit of i, high to low, skip high 1 bit
  if bit == 1
     take F[2k+1], F[2k] as new F[k],F[k-1]
     add = -2 (for next loop)
  else bit == 0
     take F[2k], F[2k-1] as new F[k],F[k-1]
     add = 2 (for next loop)

For the very last (least significant) bit of i, there's a glow-up optimization: one single multiply for that final step instead of two squares. 💅

bit = least significant bit of i
if bit == 1
   F[2k+1] = (2F[k]+F[k-1])*(2F[k]-F[k-1]) + add
else
   F[2k]   = F[k]*(F[k]+2F[k-1])

That "add" amount is 2*(-1)^k, which means +2 or -2 depending on whether k is odd or even — which really just means whether the previous bit taken from i was 1 or 0. And that's easy to spot from each bit, so you can carry it into the next loop iteration or into the final F[2k+1] formula. 🎯

For small i it's usually faster to just successively add F[k+1]=F[k]+F[k-1]. But once you're in bignum territory, doubling k->2k with two squares beats doing k many individual additions for the same result. Efficiency icon behavior. 👑

🐚 Value to i Estimate

F[i] grows as a power of phi, the golden ratio. The exact value is:

F[i] = (phi^i - beta^i) / (phi - beta)    # exactly

phi = (1+sqrt(5))/2 = 1.618
beta = -1/phi = -0.618

Since abs(beta)<1, that beta^i term shrinks real fast. So if you take a log (natural logarithm) to get i:

log(F[i]) ~= i*log(phi) - log(phi-beta)
i ~= (log(F[i]) + log(phi-beta)) / log(phi)

Or the same thing with log base 2, which you can estimate from the highest bit position of a bignum:

log2(F[i]) ~= i*log2(phi) - log2(phi-beta)
i ~= (log2(F[i]) + log2(phi-beta)) / log2(phi)

Math girlies stay winning. 🧠✨

🌟 SEE ALSO 🌟

  • Math::NumSeq
  • Math::NumSeq::LucasNumbers
  • Math::NumSeq::Fibbinary
  • Math::NumSeq::FibonacciWord
  • Math::NumSeq::Pell
  • Math::NumSeq::Tribonacci
  • Math::Fibonacci
  • Math::Fibonacci::Phi

🏠 HOME PAGE 🏠

<http://user42.tuxfamily.org/math-numseq/index.html>

📜 LICENSE 📜

Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.

And that's the whole page, bestie!! 🫶 This was perl v5.42.0, dated 2025-07-25, and it's Math::N...ibonacci(3) — go forth and compute some spirals. Byeee 💖✨🐚

📦 where this page comes from