It was just an observation that the F_{a+b} identity allows a better complexity setup than Dijkstra's recursion, provided one has to calculate multiple Fn in the integers. On 9/20/18 6:57 , Bill Gosper wrote:
Is this about theoretical complexity, or a programming competition? Fibonaccis are so easy to calculate (e.g. x^n mod x^2-x-1, or {{1,1},{1,0}}^n) that I never gave it much thought. My interest just now was how to define them for fractional n. The Binet and Cheby formulæ tend rapidly to agreement, producing interesting(?) algebraic near-identities. E.g., Binet(11/2) = 𝛕^(11/2)/√5 ~ 6.30880376931698 Cheb(11/2) = √(89/√5) ~ 6.30888341939335 —rwg On 2018-09-19 21:21, Andres Valloud wrote:
Bill,
Some claim Dijkstra's recursion:
http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF
is very fast at calculating F_n, however it seems that using
F_{a+b} = F_{a+1} F_b + F_a F_{b-1}
recursively and splitting n = a+b such that a = 2^k leads to caching just triplets around each 2^k pivot (k greatest such that 2^k < n). This caching is harder to do as effectively with Dijkstra's algorithm, so the splitting F_{a+b} method becomes competitive while using less memory.
Do you have an opinion on the subject?
Andres.
On 9/19/18 20:11 , Bill Gosper wrote:
World's smallest(?) fibonacci formula: F_n+1 = U_n(i/2)/i^n. where U:= Чебышёв polynomial, 2nd kind := sin((n+1)acos z)/√(1-z)/√(1+z). This provides an alternate (complex) interpolation for nonintegers. Slightly nonobvious: With this definition, Im(F_x+1)/Im(F_x) = -1/GoldenRatio (x real noninteger), which can be coaxed out of Mathematica. —rwg
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun