Fibonacci search in Python
Unimodal search that shrinks the interval by Fibonacci-number ratios, reusing evaluations exactly.
- File
fibonacci_search_unimodal.py, 42 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/fibonacci-search-unimodal/. The authors are listed in prov/FM952M.jsonl.
from typing import Callable
def fibonacci_search_max(f: Callable[[int], float], n: int) -> int:
"""Return the mode of a strictly unimodal f on the indices 1..n.
It evaluates f exactly N times, where N is the smallest number with
F(N + 2) - 1 >= n, which is the least number that any method can guarantee.
Indices above n stand for padding values that are smaller than every f(i).
"""
if n < 1:
raise ValueError("empty range")
fib = [0, 1] # @line L1
while fib[-1] < n + 1:
fib.append(fib[-1] + fib[-2])
big_n = len(fib) - 3 # F(N + 2) is the first Fibonacci number >= n + 1
lo, hi = 0, fib[big_n + 2] # @line L2
p = fib[big_n] # @line L3
fp = f(p)
k = big_n - 1 # @line L4
while k > 0: # @line L5
if p - lo > hi - p: # @line L6
q = p - fib[k]
else:
q = p + fib[k]
fq = f(q) if q <= n else None # @line L7
if fq is not None and fq > fp: # @line L8
if q > p:
lo = p
else:
hi = p
p, fp = q, fq
else: # @line L9
if q > p:
hi = q
else:
lo = q
k -= 1 # @line L10
return p # @line L11
test_fibonacci_search_unimodal.py 67 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/fibonacci-search-unimodal/. The authors are listed in prov/FM952M.jsonl.
import random
from fibonacci_search_unimodal import fibonacci_search_max
def budget(n: int) -> int:
a, b, big_n = 1, 2, 1 # F(N + 1), F(N + 2) for N = 1
while b - 1 < n:
a, b = b, a + b
big_n += 1
return big_n
def run(values):
calls = []
def f(i):
calls.append(i)
return values[i - 1]
return fibonacci_search_max(f, len(values)), calls
def test_example() -> None:
values = [2, 5, 9, 14, 20, 23, 21, 18, 11, 8, 4, 1]
mode, calls = run(values)
assert mode == 6
assert calls == [5, 8, 3, 6, 7]
def test_small() -> None:
assert run([7])[0] == 1
assert run([1, 2])[0] == 2
assert run([2, 1])[0] == 1
assert run([1, 3, 2])[0] == 2
def test_budget_values() -> None:
assert [budget(n) for n in (1, 2, 4, 7, 10, 12, 13, 100, 1000, 10 ** 6)] == [1, 2, 3, 4, 5, 5, 6, 10, 15, 29]
def test_every_mode_exact_count() -> None:
for n in range(1, 90):
for m in range(1, n + 1):
values = [-(abs(i - m)) for i in range(1, n + 1)]
mode, calls = run(values)
assert mode == m
assert len(calls) <= budget(n)
assert all(1 <= c <= n for c in calls)
assert len(set(calls)) == len(calls)
def test_random_unimodal() -> None:
rng = random.Random(11)
for _ in range(3000):
n = rng.randrange(1, 200)
m = rng.randrange(1, n + 1)
left = sorted(rng.sample(range(-10 ** 6, 10 ** 6), m - 1))
right = sorted(rng.sample(range(-10 ** 6, 10 ** 6), n - m), reverse=True)
top = max(left + right + [0]) + 1
values = left + [top] + right
mode, calls = run(values)
assert mode == m
assert len(calls) <= budget(n)
What the next level needs
- the tests did not run in this build