Skip to content

README.md

Latest commit

 

History

History
163 lines (114 loc) · 5.51 KB

README.md

File metadata and controls

163 lines (114 loc) · 5.51 KB
Raw

⚡ FastFib — O(log n) Fibonacci Engine

A MERN-stack API that computes massive Fibonacci numbers in logarithmic time using Matrix Exponentiation + Binary Exponentiation

Node.js Express Algorithm License

Compute fib(10^15) almost as fast as fib(10) — because brute force doesn't scale, but linear algebra does.

📸 Demo

Idle State x = 1,000,000,000,000
Matrix Power Calculator — idle Matrix Power Calculator — result

The dashboard pairs the calculator with a live time-complexity visualizer, plotting O(2^x), O(x), and O(log x) side-by-side so the payoff of matrix exponentiation is visible, not just theoretical. It even ballparks real execution time at 10⁸ ops/sec:

Approach Est. time for n = 10⁶
Naive O(2^x) ~10³⁰¹⁰²² years (never finishes)
Iterative DP O(x) ~0.01 seconds
Matrix Exponentiation O(log x) ~0.0000002 seconds

Note the query above — x = 1,000,000,000,000 (10¹²) resolves instantly, returning 730695249 (the result mod 1,000,000,007).

🚀 Why This Exists

The naive Fibonacci recurrence is O(n) — fine for small inputs, hopeless for large ones. This project replaces that with a closed-form matrix power trick, so the n-th Fibonacci number (mod 1e9+7) is computed in O(log n) time, regardless of how astronomically large n gets.

fib(1)                    →  instant
fib(1,000)                →  instant
fib(1,000,000,000,000)    →  instant  (naive recursion would never finish)

🧠 The Algorithm

Fibonacci numbers satisfy the identity:

| F(n)    F(n-1) |   =   | 1  1 | ^ (n-1)
| F(n-1)  F(n-2) |       | 1  0 |

So F(n) is simply the top-left entry of M^(n-1), where M = [[1,1],[1,0]]. That's exactly what the code does — power(M, x - 1) followed by reading P[0][0]. Finding F(n) therefore reduces to raising a 2×2 matrix to the power n-1. Instead of multiplying the matrix n-1 times, this project uses binary exponentiation (a.k.a. exponentiation by squaring) to do it in log₂(n) multiplications:

power(M, n):
    result = Identity
    while n > 0:
        if n is odd:  result = result × M
        M = M × M
        n = n >> 1
    return result
Approach Time Complexity fib(10^9)
Naive recursion O(2^n) 🔴 Never finishes
Iterative DP O(n) 🟡 ~seconds
Matrix Exponentiation O(log n) 🟢 Instant

Extra engineering details baked in:

  • ⚙️ BigInt arithmetic throughout — no precision loss even at extreme magnitudes.
  • 🧮 Modular reduction (mod 1,000,000,007) at every multiplication step, the standard competitive-programming convention for keeping numbers bounded.
  • 🧩 Pure, dependency-free math logic — no external big-number libraries required.

🛠️ Tech Stack

  • Backend: Node.js + Express — a single lightweight route exposing the algorithm
  • Frontend: Static HTML/CSS/JS dashboard served directly from Express (frontend/public), featuring:
    • A calculator panel that calls /calculate and renders the result
    • A live complexity-comparison chart (O(2^x) vs O(x) vs O(log x))
    • Precomputed real-world execution-time estimates for each approach
  • Core Engine: Hand-written matrix multiplication + binary exponentiation over BigInt

📁 Project Structure

node_js_febbo/
├── backend/
│   ├── server.js         # Express server + matrix exponentiation engine
│   ├── package.json
│   └── package-lock.json
└── frontend/
    └── public/           # Static frontend, served by Express
        └── index.html

🔌 API Reference

GET /calculate

Computes F(x), the x-th Fibonacci number, modulo 1,000,000,007.

Query Parameters

Param Type Description
x number The index n of the Fibonacci number to compute

Example Request

GET /calculate?x=50

Example Response

{
  "result": "12586269025"
}

⚡ Quick Start

# 1. Clone the repository
git clone https://github.com/Sumit-do/node_js_febbo.git
cd node_js_febbo/backend

# 2. Install dependencies
npm install

# 3. Run the server
npm start

The server boots on http://localhost:5001, serving both the static frontend and the /calculate API from the same Express instance.

🎯 What This Project Demonstrates

  • ✅ Translating a mathematical identity (Fibonacci ↔ matrix powers) into working code
  • ✅ Binary exponentiation — a core competitive-programming primitive with uses far beyond Fibonacci (modular power, DP speed-ups, string hashing)
  • ✅ Safe big-number handling in JavaScript via BigInt
  • ✅ A minimal, no-bloat Express API design

📄 License

Released under the ISC License.

Built with ⚙️ algorithms and ☕ by Sumit