Skip to content

133 — Fast Doubling Fibonacci

132-এ Fibonacci-র জন্য matrix exponentiation দেখলে; এই note-এ সেটারও একটা মার্জিত shortcut — fast doubling, যেখানে matrix identity খুলে দুটো সরাসরি formula বেরোয়। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — fast doubling matrix-এর চেয়ে কম গুণে F(n) দেয়, CP-তে দ্রুততম Fibonacci পদ্ধতিগুলোর একটা। 132 ভালো বুঝে থাকলে এটা তার সুন্দর পরিমার্জন।

Source

  • Original source: CP-Algorithms — Fibonacci Numbers (Fast Doubling section)
  • Platform: CP-Algorithms — https://cp-algorithms.com/algebra/fibonacci-numbers.html
  • Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
  • Difficulty: Hard
  • Pattern: F(2k) formulas
  • Basic idea inherited from: 132 (Fibonacci using Matrix Exponentiation)

1. Problem in simple words

আগের মতোই — n-তম Fibonacci সংখ্যা F(n) দ্রুত বের করা (n বিশাল, প্রায়ই mod কোনো বড় সংখ্যায়)। কিন্তু এবার একটা আরও চটপটে পদ্ধতি: fast doubling।

মূল চাবি দুটো সুন্দর সূত্র, যা k থেকে সরাসরি 2k-তে লাফ দেয়:

F(2k)   = F(k) · (2·F(k+1) − F(k))
F(2k+1) = F(k)² + F(k+1)²

মানে F(k) আর F(k+1) জানলে, এক ধাপে F(2k) আর F(2k+1) পেয়ে যাও। n-এর binary bit ধরে ধরে এই doubling করলে O(log n)-এ F(n) — কিন্তু matrix-এর চেয়ে কম গুণে। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু এই doubling-চিন্তা গণিতগতভাবে দারুণ।

2. What is the math idea?

মূল idea — matrix identity [[1,1],[1,0]]^n-এর ঘরগুলো খুলে লিখলেই doubling formula বেরিয়ে আসে। 132-এ দেখেছিলে:

M^n = [[F(n+1), F(n)], [F(n), F(n−1)]]

এখন M^(2k) = (M^k)²। ডান পাশের বর্গটা ঘরে ঘরে গুণ করে, F(2k) আর F(2k+1)-কে F(k), F(k+1)-এর ভাষায় লিখলেই উপরের দুই সূত্র। তাই fast doubling আসলে matrix squaring-এরই হাতে-লেখা, পরিষ্কার রূপ — matrix-এর 8টা গুণের বদলে মাত্র 3টা গুণ লাগে। n-কে binary-তে (MSB থেকে) পড়ে প্রতিটা bit-এ একবার doubling, bit 1 হলে এক ধাপ বাড়তি সরানো। এই level CP-leaning হলেও মূল সুর সরল — k জানলে 2k এক লাফে।

3. Which basic idea does this inherit from?

সরাসরি 132 (Fibonacci using Matrix Exponentiation)। fast doubling-এর দুটো সূত্রই M^(2k) = (M^k)² থেকে বেরোয় — মানে 132-এর matrix-চিন্তা না বুঝলে এই formula-র উৎস বোঝা যায় না। fast doubling হলো সেই matrix squaring-এর optimized, scalar রূপ।

পেছনে আরও দাঁড়িয়ে আছে 131 (matrix exponentiation) আর 029 (binary exponentiation)-এর "binary bit ধরে এগোনো" চিন্তা। README-র recommended order-এ 131 → 132 → 133 — এটাই trilogy-র শেষ ও সবচেয়ে পরিমার্জিত ধাপ।

4. Real-life analogy

ভাবো তুমি একটা লম্বা সিঁড়ির n-তম ধাপে পৌঁছাতে চাও, কিন্তু তোমার একটা বিশেষ ক্ষমতা আছে — যেখানে আছো তার দ্বিগুণে এক লাফে যেতে পারো (k → 2k), আর চাইলে একটা মাত্র ধাপ এগোতে পারো (k → k+1)।

তাহলে n-এ পৌঁছানোর চটপটে উপায়: n-কে binary-তে ভাবো। MSB থেকে শুরু করে, প্রতিটা bit-এ "দ্বিগুণ লাফ" দাও; bit যদি 1 হয়, সেই সাথে "এক ধাপ" বাড়াও। যেমন n = 13 = 1101: শুরু 0 → 1 → 11 → 110 → 1101, প্রতি ধাপে দ্বিগুণ + (bit 1 হলে) এক বাড়তি।

fast doubling ঠিক এই — "যেখানে আছি (F(k), F(k+1)) সেখান থেকে দ্বিগুণে লাফ" — matrix-এর মতো ঘুরপথ নয়, সরাসরি দুটো সূত্রে।

5. Visual explanation

doubling formula কোথা থেকে আসে — (M^k)² খুলে:

M^k = [[F(k+1), F(k)  ],
       [F(k),   F(k−1)]]

(M^k)² = M^(2k)-এর top-left আর top-right হিসাব করি:

top-right (= F(2k)):
  F(k+1)·F(k) + F(k)·F(k−1)
  = F(k)·(F(k+1) + F(k−1))
  = F(k)·(F(k+1) + (F(k+1) − F(k)))      [F(k−1) = F(k+1) − F(k)]
  = F(k)·(2·F(k+1) − F(k))              ← সূত্র ১ ✓

top-left (= F(2k+1)):
  F(k+1)² + F(k)²                        ← সূত্র ২ ✓

ছোট যাচাই (k = 3):  F(3)=2, F(4)=3
  F(6) = F(3)·(2·F(4) − F(3)) = 2·(6 − 2) = 8   ✓  (F(6) = 8)
  F(7) = F(4)² + F(3)² = 9 + 4 = 13            ✓  (F(7) = 13)

লক্ষ করো — দুটো সূত্রই matrix বর্গের ঘর থেকে সোজা বেরোল, আর k = 3-এ হাতে মিলিয়ে F(6) = 8, F(7) = 13 পেলাম।

6. Example input and output

input n  ->  F(n)              পদ্ধতি
----------------------------------------------------------------
   0     ->  0                 base
   1     ->  1                 base
  10     ->  55                fast doubling
  20     ->  6765
  50     ->  12586269025
 100     ->  354224848179261915075   (Python big int)

mod সহ (CP-style), mod = 10⁹+7:
  F(100) mod (10⁹+7)  ->  687995182
  F(10¹⁸) mod (10⁹+7) ->  তাৎক্ষণিক (O(log n), matrix-এর চেয়েও কম গুণ)

খেয়াল করো: উত্তর 132-এর সাথে হুবহু এক (একই Fibonacci!) — শুধু পদ্ধতি দ্রুততর। base case F(0) = 0, F(1) = 1 এখানেও; recursion-এর তলানিতে n == 0 হলে (F(0), F(1)) = (0, 1) ফেরত। বড় n-এ mod, Python big int-এ mod ছাড়াও সঠিক।

7. Brute force thinking

আগের মতোই — সরল iterative loop (এটাই reference হিসেবে রাখব মিলিয়ে দেখতে):

def fib_iter(n, mod=None):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
        if mod is not None:
            a %= mod; b %= mod
    return a

ছোট ও মাঝারি n-এ নিখুঁত ও সহজ — O(n)। fast doubling-এর প্রতিটা উত্তর এই brute force-এর সাথে মিলিয়ে যাচাই করব। নির্ভরযোগ্য ভিত্তি।

8. Why brute force may be slow

loop ঘোরে n বার — n = 10⁶ হলে ঠিক আছে, কিন্তু বিশাল n-এ অচল:

n = 10⁶:             10⁶ ধাপ — তাৎক্ষণিক
n = 10¹⁸:            10¹⁸ ধাপ — অসম্ভব
matrix expo (132):    ~log n matrix গুণ (প্রতিটায় 8 scalar গুণ)
fast doubling (133):  ~log n ধাপ, প্রতি ধাপে মাত্র 3 scalar গুণ ← সবচেয়ে কম

বড় n-এ O(n) অচল। আর matrix expo (132)-এর সাথে তুলনায়, fast doubling একই O(log n) কিন্তু প্রতি ধাপে কম গুণ (matrix-এর 8টার বদলে 3টা) — তাই ধ্রুবক গুণনীয়ক ছোট, ব্যবহারিকভাবে দ্রুততর।

9. Better thinking

মূল insight — F(k), F(k+1) জানলে দুই সূত্রে F(2k), F(2k+1) পাওয়া যায়; তাই n-এর binary bit ধরে doubling করলেই O(log n)। recursive কাঠামো সবচেয়ে পরিষ্কার:

fib_pair(n) -> (F(n), F(n+1)) ফেরত দেয়
  base: n == 0 -> (0, 1)
  নাহলে:
    (a, b) = fib_pair(n >> 1)            [a = F(k), b = F(k+1), যেখানে k = n//2]
    c = a · (2·b − a)                     [F(2k)]
    d = a² + b²                           [F(2k+1)]
    যদি n বিজোড়:  return (d, c + d)       [F(2k+1), F(2k+2)]
    নাহলে:        return (c, d)           [F(2k), F(2k+1)]

কেন: n//2 = k-এর pair থেকে 2k-এর pair বানাই (c, d)। n যদি জোড় (n = 2k), উত্তর (c, d); n বিজোড় (n = 2k+1), এক ধাপ সরিয়ে (d, c+d) — কারণ F(2k+2) = F(2k) + F(2k+1) = c + d। শেষে fib_pair(n)[0] = F(n)। mod লাগলে প্রতিটা গুণ-যোগে % mod।

10. Thinking tweak

আসল "আহা" মুহূর্ত: matrix squaring-এর ঘরগুলো হাতে খুললে দুটো scalar formula বেরোয় — matrix-এর সব ঘর না রেখে শুধু F(k), F(k+1) বইলেই হয়।

132-এ পুরো 2×2 matrix square করছিলাম (8 গুণ); tweak হলো — সেই বর্গের শুধু দরকারি দুই ঘর (F(2k), F(2k+1)) আলাদা সূত্রে লেখো, তখন প্রতি ধাপে মাত্র 3 গুণ। একই O(log n), কিন্তু ছোট ধ্রুবক — matrix থেকে scalar doubling-এ নেমে এল। গণিতই বলে দিল কোন ঘরগুলো আসলে লাগে।

11. Step-by-step dry run

fib_pair(10) — recursion (n = 10):

call n n >> 1 কী ফেরে
1 10 5 fib_pair(5)-এর অপেক্ষা
2 5 2 fib_pair(2)-এর অপেক্ষা
3 2 1 fib_pair(1)-এর অপেক্ষা
4 1 0 fib_pair(0)-এর অপেক্ষা
5 0 — base → return (0, 1)

ফেরার পথ (a = F(k), b = F(k+1); c = F(2k), d = F(2k+1)):

ফেরা k (a, b) c = a(2b−a) d = a²+b² n বিজোড়? return (F(n), F(n+1))
call 5→4 0 (0, 1) 0·(2−0)=0 0+1=1 n=1 বিজোড় (d, c+d) = (1, 1)
call 4→3 1 (1, 1) 1·(2−1)=1 1+1=2 n=2 জোড় (c, d) = (1, 2)
call 3→2 2 (1, 2) 1·(4−1)=3 1+4=5 n=5 বিজোড় (d, c+d) = (5, 8)
call 2→1 5 (5, 8) 5·(16−5)=55 25+64=89 n=10 জোড় (c, d) = (55, 89)

চূড়ান্ত: fib_pair(10) = (55, 89), তাই F(10) = 55 ✓ (আর F(11) = 89)। দেখো — প্রতি ধাপে শুধু দুটো সংখ্যা বইলাম, matrix নয়।

12. Python solution

import sys
sys.setrecursionlimit(10000)


def fib_pair(n, mod=None):
    """(F(n), F(n+1)) ফেরত দেয় — fast doubling, O(log n)।"""
    if n == 0:
        return (0, 1)
    a, b = fib_pair(n >> 1, mod)          # a = F(k), b = F(k+1), k = n//2
    c = a * (2 * b - a)                   # F(2k)
    d = a * a + b * b                     # F(2k+1)
    if mod is not None:
        c %= mod
        d %= mod
    if n & 1:                             # n বিজোড় (n = 2k+1)
        return (d, (c + d) % mod if mod else c + d)
    else:                                 # n জোড় (n = 2k)
        return (c, d)


def fib(n, mod=None):
    """n-তম Fibonacci — fast doubling।"""
    return fib_pair(n, mod)[0]


# --- ছোট test গুলো (সব pass করা উচিত) ---
def fib_iter(n, mod=None):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
        if mod is not None:
            a %= mod; b %= mod
    return a

# fast doubling বনাম iterative — n = 0..60 সব মেলাও
for n in range(0, 61):
    assert fib(n) == fib_iter(n), f"F({n}) অমিল"

# known মান
assert fib(0) == 0
assert fib(1) == 1
assert fib(10) == 55
assert fib(20) == 6765
assert fib(50) == 12586269025
assert fib(100) == 354224848179261915075

# pair-এর দুই ঘর সঠিক: (F(n), F(n+1))
for n in range(0, 30):
    p = fib_pair(n)
    assert p == (fib_iter(n), fib_iter(n + 1)), f"pair({n}) অমিল"

# doubling সূত্র সরাসরি যাচাই: F(2k) ও F(2k+1)
for k in range(0, 30):
    assert fib_iter(2 * k) == fib_iter(k) * (2 * fib_iter(k + 1) - fib_iter(k))
    assert fib_iter(2 * k + 1) == fib_iter(k) ** 2 + fib_iter(k + 1) ** 2

# mod সহ — বড় n-এও দ্রুত ও সঠিক
MOD = 10**9 + 7
for n in range(0, 300):
    assert fib(n, MOD) == fib_iter(n, MOD), f"mod F({n}) অমিল"
assert fib(10**18, MOD) >= 0           # বিশাল n চলে (O(log n))

# 132-এর matrix পদ্ধতির সাথেও একই উত্তর (cross-check)
def fib_matrix(n, mod=None):
    def mm(A, B):
        x = [[0, 0], [0, 0]]
        for i in range(2):
            for j in range(2):
                s = A[i][0] * B[0][j] + A[i][1] * B[1][j]
                x[i][j] = s % mod if mod else s
        return x
    R, M, p = [[1, 0], [0, 1]], [[1, 1], [1, 0]], n
    while p:
        if p & 1: R = mm(R, M)
        M = mm(M, M); p >>= 1
    return R[0][1]
for n in range(0, 100):
    assert fib(n, MOD) == fib_matrix(n, MOD)

print(fib(10))                       # 55
print(fib(100))                      # 354224848179261915075
print(fib(10**18, MOD))             # বড় n mod — তাৎক্ষণিক
print("সব test pass!")

13. Line-by-line explanation

def fib_pair(n, mod=None):
    if n == 0:
        return (0, 1)

recursion-এর তলানি — F(0) = 0, F(1) = 1, তাই (0, 1)। এই pair থেকে উপরে উঠতে উঠতে বড় index বানাব।

    a, b = fib_pair(n >> 1, mod)
    c = a * (2 * b - a)
    d = a * a + b * b

আগে অর্ধেক index k = n//2-এর pair (a = F(k), b = F(k+1)) আনি। তারপর section 5-এর দুই সূত্রে c = F(2k), d = F(2k+1) — মাত্র 3টা গুণ (a·(...), a·a, b·b)। mod থাকলে c, d-তে % mod।

    if n & 1:
        return (d, (c + d) % mod if mod else c + d)
    else:
        return (c, d)

n যদি জোড় (n = 2k) — উত্তর (F(2k), F(2k+1)) = (c, d)। n বিজোড় (n = 2k+1) — এক ধাপ সরিয়ে (F(2k+1), F(2k+2)) = (d, c+d), কারণ F(2k+2) = F(2k) + F(2k+1)।

def fib(n, mod=None):
    return fib_pair(n, mod)[0]

pair-এর প্রথম ঘরই F(n)।

বাকি test অংশে fast doubling বনাম iterative (n = 0..60), pair-এর দুই ঘর, doubling সূত্র সরাসরি, mod, আর 132-এর matrix পদ্ধতির সাথে cross-check — সব যাচাই হয়। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

55
354224848179261915075
<একটা বড় ৯-অঙ্কের সংখ্যা>
সব test pass!

fib(10) → 55 (section 11-এর dry run-এর সাথে মিল)। fib(100) → পুরো 21-অঙ্কের Fibonacci (Python big int)। fib(10**18, MOD) → 10¹⁸-তম Fibonacci mod 10⁹+7, তাৎক্ষণিক (O(log n), matrix-এর চেয়েও কম গুণ)। তার আগে সব assert (iterative, pair, doubling সূত্র, mod, matrix cross-check) pass — তাই সব test pass!।

15. Time complexity

O(log n) — recursion-এর গভীরতা ~log₂n (প্রতি ধাপে n অর্ধেক), আর প্রতি ধাপে ধ্রুবক কাজ (মাত্র 3টা গুণ + কয়েকটা যোগ)। matrix exponentiation (132)-ও O(log n), কিন্তু fast doubling-এ প্রতি ধাপে কম scalar গুণ (3 বনাম matrix-এর 8), তাই ধ্রুবক গুণনীয়ক ছোট — ব্যবহারিকভাবে দ্রুততম Fibonacci পদ্ধতিগুলোর একটা।

16. Space complexity

O(log n) — recursion-এর call stack-এর গভীরতা ~log₂n। চাইলে iterative (n-এর bit MSB থেকে পড়ে) লিখে O(1)-এ নামানো যায়। প্রতিটা frame-এ শুধু কয়েকটা সংখ্যা (a, b, c, d) — কোনো array নেই। (mod ছাড়া বিশাল n-এ Fibonacci সংখ্যা নিজেই বড়, big-int digit-এর সাথে space বাড়ে — তাই CP-তে mod।)

17. Common mistakes

  1. জোড়/বিজোড় শাখা গুলিয়ে ফেলা — n জোড় হলে (c, d), বিজোড় হলে (d, c+d)। উল্টে ফেললে এক পদ এদিক-ওদিক, পুরো উত্তর ভুল। n & 1 দিয়ে সঠিক শাখা।
  2. 2·F(k+1) − F(k) negative হওয়া (mod-এ) — mod নিয়ে কাজ করলে 2*b − a negative হতে পারে; তখন c %= mod-এর পর Python ঠিক রাখে, কিন্তু C++/Java-তে ((2*b − a) % mod + mod) % mod লাগে।
  3. base case ভুল — n == 0 হলে (0, 1) ফেরত (F(0), F(1)); (1, 1) বা (1, 0) দিলে সব ভুল।
  4. fib_pair-এর কোন ঘর F(n) ভুলে যাওয়া — F(n) হলো pair-এর প্রথম ঘর ([0]), দ্বিতীয়টা F(n+1)।
  5. recursion limit/গভীরতা (বিশাল n) — n = 10¹⁸-এ গভীরতা ~60, তাই নিরাপদ; কিন্তু খুব রক্ষণশীল default limit-এ চাইলে iterative version বা setrecursionlimit।

18. Harder problems that inherit this idea

  • CSES — Fibonacci Numbers (https://cses.fi/problemset/task/1722) — বিশাল n-এ F(n) mod; fast doubling দ্রুততম সমাধানগুলোর একটা।
  • Codeforces — Fibonacci-ভিত্তিক বড়-n problems (https://codeforces.com/problemset) — যেখানে ধ্রুবক গুণনীয়ক ছোট হওয়া (matrix-এর চেয়ে fast doubling) সময় বাঁচায়।
  • 132 (Fibonacci via Matrix) আর 131 (Matrix Exponentiation) — এই repo-রই ভিত্তি; fast doubling সেই matrix squaring-এরই পরিমার্জিত scalar রূপ।

19. Pattern learned

Fast doubling via F(2k) formulas — F(2k) = F(k)·(2F(k+1) − F(k)), F(2k+1) = F(k)² + F(k+1)²; n-এর bit ধরে k → 2k লাফ, O(log n) কিন্তু matrix-এর চেয়ে কম গুণ। বড় শিক্ষা: matrix পদ্ধতির ঘরগুলো হাতে খুললে প্রায়ই দরকারি অংশটুকুর সরাসরি scalar সূত্র পাওয়া যায় — যা একই complexity-তে কম কাজে চলে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "fast doubling: F(2k) = F(k)(2F(k+1)−F(k)), F(2k+1) = F(k)²+F(k+1)²; recursion-এ (F(n),F(n+1)) বইয়ে, n জোড়/বিজোড় ভেদে শাখা; O(log n), matrix-এর চেয়ে কম গুণ।" Signal: "Fibonacci-র বিশাল n-তম পদ, যত দ্রুত সম্ভব" — দেখলেই fast doubling মনে পড়বে।

পরের ধাপ → 134 — Primality Test Advanced (trial division-এর সীমা থেকে শুরু, primality trilogy)। ভিত্তি → 132 — Fibonacci using Matrix Exponentiation।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-এর ছক → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — এই level CP-leaning, interview-optional।