Skip to content
Tutorials Center
My learning

Topics

Lesson 181 of 225 ยท Math and Bit Manipulation

Fast Doubling Fibonacci and Newton's Method

Compute Fibonacci numbers in O(log n) with fast doubling, find integer square roots exactly and solve equations numerically with Newton's method in Python.

The matrix power in Fast Exponentiation already gives Fibonacci numbers in O(log n) steps. But there is an even leaner way, called fast doubling, which jumps from n to 2n directly using two small identities. No matrices, fewer multiplications, and about 20 lines of code.

The second half of this lesson turns to a very different problem that shares the same flavor of "make the answer converge quickly": Newton's method. It finds roots of equations numerically, and a pure-integer version gives exact integer square roots of numbers with thousands of digits.

The slow ways first

The recursive definition F(n) = F(n-1) + F(n-2) with F(0) = 0, F(1) = 1 takes exponential time if coded naively. A loop is O(n) additions, fine for n = 10**5, but hopeless for n = 10**18.

Two identities

Starting from the matrix [[1,1],[1,0]] raised to the power n, you can derive (and verify by hand for small n) these identities:

TEXT
F(2k)   = F(k) * (2*F(k+1) - F(k))
F(2k+1) = F(k)^2 + F(k+1)^2

So if you know the pair (F(k), F(k+1)), you get (F(2k), F(2k+1)) with three multiplications. If the target index is odd, one more addition steps from 2k, 2k+1 to 2k+1, 2k+2.

The recursion halves n each time: O(log n) steps with O(log n) recursion depth.

flowchart TD
  A["fib_pair(n)"] --> B{"n == 0?"}
  B -->|yes| C["return (0, 1)"]
  B -->|no| D["(a, b) = fib_pair(n // 2)"]
  D --> E["c = a * (2b - a)<br/>d = a^2 + b^2"]
  E --> F{"n odd?"}
  F -->|yes| G["return (d, c + d)"]
  F -->|no| H["return (c, d)"]

Each call returns the pair (F(n), F(n+1)).

Python Fast doubling Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python handles the huge integers directly: F(100000) has about 70,000 bits. For F(10**18) the exact number would have about 2 * 10^17 digits, far more than any computer can store, so contests ask for the result modulo a prime. Apply the modulus after every multiplication:

Python Fast doubling modulo m, compared with matrix power

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both give the same answers. Fast doubling does 3 multiplications per level while the matrix version does 8 per squaring, so doubling is roughly two to three times faster in practice.

Negative values appear in 2*b - a. In languages with truncating % you must add m before reducing. Python's % already returns a non-negative result for a positive m.

Two useful facts: gcd(F(a), F(b)) = F(gcd(a, b)), and the Pisano period (the cycle length of F(n) mod m) is always at most 6m. That lets you reduce a gigantic n when the modulus is small.

Integer square root with Newton's method

How do you compute floor(sqrt(n)) for a 1000-digit n? Floating point math.sqrt loses digits after about 15. The classic answer is Newton's method applied to f(x) = x^2 - n. Start with a guess x that is at least the true root and repeat:

TEXT
x_next = (x + n // x) // 2

while x_next < x. When the sequence stops decreasing, x is exactly floor(sqrt(n)). The guess doubles its correct digits each step once it gets close, so a starting guess like 1 << ((n.bit_length() + 1) // 2) needs only about log2(bit_length) iterations.

Python Integer square root by Newton iteration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In real code use math.isqrt, which is exact and fast. The lesson teaches why it works, and the same loop shape computes integer cube roots or k-th roots.

Newton's method for real roots

For a smooth function f, the tangent line at x crosses zero at x - f(x) / f'(x). Taking that crossing as the next guess gives the iteration

TEXT
x_next = x - f(x) / f'(x)

Near a simple root the number of correct digits roughly doubles each step (quadratic convergence). Compare it with bisection, which gains one bit per step.

Python Newton's method versus bisection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Newton needs about 5 to 6 steps where bisection needs about 40. The price: it needs the derivative, a good starting guess, and can diverge or bounce when f'(x) is near zero or the start is far from a root. Production code often combines the two: bisection to bracket the root safely, Newton to finish quickly.

When to use what

Task Tool Cost
F(n) for huge n, exact or modulo fast doubling O(log n) multiplications
Any linear recurrence of order k matrix power O(k^3 log n)
floor(sqrt(n)) for big integers math.isqrt (Newton inside) O(M(d) log d), d = digits
Root of a smooth function Newton, safeguarded with bisection quadratic convergence

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the fast-doubling recursion return for index n?

    Carrying the neighbouring value lets F(2k) and F(2k+1) be computed from F(k) and F(k+1) without any other lookups.
  2. 2. How many recursive levels does fib_pair(10**18) use?

    n is halved at each level, so the depth is log2(10**18), roughly 60.
  3. 3. What is the formula for the Newton step on f(x) = x^2 - n?

    x - f(x)/f'(x) = x - (x^2 - n)/(2x) = (x + n/x)/2, the average of x and n/x.
  4. 4. Why is bisection often used together with Newton's method?

    Newton can jump far away when the derivative is small. A bracket from bisection keeps the search safe, and Newton steps finish the job quickly.

Summary

  • Fast doubling uses F(2k) = F(k)(2F(k+1) - F(k)) and F(2k+1) = F(k)^2 + F(k+1)^2 to compute F(n) in O(log n) steps.
  • Reduce modulo m after every multiplication; the pair-returning recursion avoids repeated work.
  • Newton's iteration x = (x + n // x) // 2 computes exact integer square roots; math.isqrt does it for you.
  • For real functions, x - f(x)/f'(x) converges quadratically near a simple root but needs a derivative and a decent start.
  • Combine Newton with bisection when robustness matters.

Next: Combinatorics and Counting