#!/usr/bin/python3

from collections import deque
from itertools import count
import decimal

# Only for reference.
def fibonacci(n):
	a = 1
	b = 0
	swp = 0

	for i in range(n):
		swp = a
		a += b
		b = swp
	return a

_fibonacci_series_context_stack = deque()

class FibonacciSeriesContext(object):
	def __init__(self):
		self._pre_calculated = {0: 1, 1: 1}
		self._biggest = 1

	def __contains__(self, other):
		return other in self._pre_calculated
	
	def __getitem__(self, n):
		return self._pre_calculated[n]
	def __setitem__(self, n, v):
		self._pre_calculated[n] = v

	def get_biggest_pair(self):
		return ((self._biggest - 1, self._pre_calculated[self._biggest - 1])
			, (self._biggest, self._pre_calculated[self._biggest]))
	def __enter__(self):
		_fibonacci_series_context_stack.append(self)
		return self
	def __exit__(self, *exc):
		_fibonacci_series_context_stack.pop()
		return False

_fibonacci_series_context_stack.append(FibonacciSeriesContext())


def getfibonacciseriescontext():
	return _fibonacci_series_context_stack[-1]

def fast_ctx_fibonacci(n, context = getfibonacciseriescontext()):
	if(n in context):
		return context[n]

	(n_start_minus_one, b), (n_start, a) = context.get_biggest_pair()

	for i in range(n_start, n):
		swp = a
		a += b
		b = swp
		context[n] = a

	return a
	


if( __name__ == "__main__"):

	decimal.getcontext().prec = 5
	golden_ratio = decimal.Decimal((1 + decimal.Decimal(5).sqrt()) / 2)
	print("Seeking n, such that F(n + 1) / F(n) = ", golden_ratio)
	print("Precision is 1e-5.")

	# Try to approximate the result faster using big steps first.

	# At first try steps of 100. This way we can approximate an interval
	# with width 100 where we do the fine approximation.
	
	for i in count(1, 100):
		if(fast_ctx_fibonacci(i) / decimal.Decimal(fast_ctx_fibonacci(i - 1)) == golden_ratio):
			break

	n_stop = i
	n_start = n_stop - 101

	print("Found that n is in range({}, {})".format(n_start, n_stop))

	for i in range(n_start, n_stop):
		if(fast_ctx_fibonacci(i) / decimal.Decimal(fast_ctx_fibonacci(i - 1)) == golden_ratio):
			break
	n = i + 1

	print("n = ", n)

	print("F(n + 1) / F(n) = %0.6g" % (fast_ctx_fibonacci(n + 1) / fast_ctx_fibonacci(n)))