Sub Process_Globals
Private fx As JFX
Private MainForm As Form
Dim phi, phim As BigDecimal
phi.Initialize(1.61803398874989484820458683436563811772030917980576)
phim.initialize(-0.61803398874989484820458683436563811772030917980576)
Dim p5 As Double = 2.23606797749979 ' = sqrt(5)
End Sub
Sub fibonacy(n As Int) As Int
Dim bd As BigDecimal
bd.Initialize5(phi.Pow(n).Subtract(phim.Pow(n))) '.Divide(p5))
Return Round( bd/p5)
End Sub
It goes up to 46 because I can't get the bigdecimal to divide by sqrt(5).
Nice. But there is still some room for improvement...
My implementation is actually quite simple and not far from the "naive solution". It solves Fibonnaci(1000) in 23ms.
This is the result:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
With this code I get the same result as you @Erel for 300 and 500 numbers so I'm guessing its a working solution. It took some getting my head around how BigNumbers work! I've also no idea how fast or slow it is at working the solution out.
B4X:
Private Sub Fibonacci(N As Int) As BigInteger
Dim result As BigInteger
If N = 1 Then result.Initialize(1)
If N = 2 Then result.Initialize(1)
If N > 2 Then
Dim n_1 As BigInteger
Dim n_2 As BigInteger
n_1.Initialize(1)
n_2.Initialize(1)
For i = 1 To (N-2)
result.Initialize(0)
result.Add(n_1)
result.Add(n_2)
n_2.Initialize7(n_1)
n_1.Initialize7(result)
Next
End If
Return result
End Sub
Sub fibonacy(n As Int) As String
Dim phi, phim As BigDecimal
phi.Initialize(1.61803398874989484820458683436563811772030917980576)
phim.initialize(-0.61803398874989484820458683436563811772030917980576)
Dim bd As BigDecimal
bd.Initialize5(phi.Pow(n).Subtract(phim.Pow(n))) '.Divide(p5))
Dim sqrt5 As BigDecimal
sqrt5.Initialize(Sqrt(5))
Return bd.Divide2(sqrt5, 1000, bd.ROUND_HALF_EVEN).Round(1000, bd.ROUND_HALF_EVEN).ToBigInteger.ToString
End Sub
A polite way of saying 'old school'
Your naive implementation gave me a headache trying to suss out how it actually worked, recursively calling itself.
My solution using BigNumbers too: (little bit like Randomcoder)
B4X:
Sub Fibonacci( n As Int) As BigInteger
Dim k As Int
Dim i,res As BigInteger
i.Initialize(1)
res.Initialize(0)
For k=1 To n
Dim temp As BigInteger
temp.initialize(i)
temp.Add(res)
i=res
res=temp
Next
Return res
End Sub