IronPythonFibonacciLargeNumbers

Enter a topic name to show or a new topic name to create; then press Enter
Summary
some script examples of calculating Fibonacci numbers dynamically

Mini-programs below are from Literate Programming Also see the more naive methods of IronPythonFibonacciNumbers

Fibonacci sequence: F(n)=\cases{0&\text{n=0}\cr 1&\text{n=1}\cr F(n-1)+F(n-2)&\text{n>1}}

Large Fibonacci by Matrix

The explanation for this is at Literate Programming - Quick exact computation of large individual Fibonacci numbers

def mul(A, B) :
    a, b, c = A
    d, e, f = B
    return a*d + b*e, a*e + b*f, b*e + c*f
def pow(A, n) :
    if n == 1 :	return A
    if n & 1 == 0 :  return pow(mul(A, A), n//2)
    else:		return mul(A, pow(A, A), (n-1)//2))
def fib(n) :
    if n < 2 :    return n
    return pow((1, 1, 0), n-1) [0]
so = UtilityProperties.Now + UtilityProperties.Newline
so = so + 'fib(321) is: ' + str(fib(321))
ScriptOutput = so

2017-11-23 11:29:15

fib(321) is: 5439356428629292972296177350244602806380313370817060034433662955746

Large Fibonacci Numbers (2nd method)

def powLF (n) :
    if n == 1 :	return (1, 1)
    L, F = powLF (n / 2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1 :
	return ((L + 5*F) >> 1, (L + F) >> 1)
    else :
	return (L, F)
def fib (n) :
    if n & 1 :
	return powLF (n) [1]
    else :
	L, F = powLF (n / 2)
	return L * F
so = UtilityProperties.Now + UtilityProperties.Newline
so = so + 'fib(321) is: ' + str(fib(321))
ScriptOutput = so

2017-11-23 11:29:15

fib(321) is: 5439356428629292972296177350244602806380313370817060034433662955746

Large Fibonacci Numbers - E.W. Dijkstra Method

This is a method that uses very few iterations to calculate large values

fibs = {0: 0, 1: 1}
def fib (n) :
    if n in fibs :    return fibs [n]
    if n % 2 == 0 :
	fibs [n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib (n / 2)
	return fibs [n]
    else :
	fibs [n] = (fib((n - 1) / 2) ** 2) + (fib((n + 1) / 2) ** 2)
	return fibs [n]
so = UtilityProperties.Now + UtilityProperties.Newline
so = so + 'fib(321) is: ' + str(fib(321)) + UtilityProperties.Newline
so = so + 'fib(1021) is: ' + str(fib(1021)) + UtilityProperties.Newline
ScriptOutput = so

2017-11-23 11:29:16

fib(321) is: 5439356428629292972296177350244602806380313370817060034433662955746

fib(1021) is: 1063887467721366034773241589607300969338754108028802783023342188374708360698208971002440910085618509255043832759588753162705581482604835891067739816451104054196448910313767363259999214876196527034160759045008061321


Version: 12   Revised: 2013-08-31 09:19:28 Last Updated by: jwdavidson@gmail.com Rename Show Links to Topic