Re: Fibonacci function/command in excel?...tia sal

Tech-Archive recommends: Speed Up your PC by fixing your registry

Hi. I know this really doesn't apply here, but I thought you may find the
following topic interesting. I know that MMult was a bit of "overkill", but
certain math programs take advantage of that with a more efficient version.
The fastest algorithms look at the bit pattern of the number in binary form
and choose 1 of 2 simple operations. They then use a more efficient form of
MMult. For example, 128 (2^7) can be calculated in 7 loops.

Sub Fib_128()
Dim v, t, j

'// Note: Log(128)/Log(2) = 7
v = Array(CDec(1), CDec(1), CDec(0))
For j = 1 To 7
t = v(1) * v(1)
v = Array(v(0) * v(0) + t, v(1) * (v(0) + v(2)), t + v(2) * v(2))
Next j
Debug.Print v(1)
End Sub

Returns: 251728825683549488150424261

The real speed comes from wanting to do Fibonacci (16384) (ie 2^14) where
you only need to loop 7 more times.
Excel can't do that directly, of course. The real code is written slightly
more efficiently then that above.
Anyway, just gee-wiz. :>) The op probably only wanted Fibonacci (10).
:>)

--
Dana DeLouis
Win XP & Office 2003


"Tushar Mehta" <tmUnderscore200310@xxxxxxxxxxxxxxxxxxxx> wrote in message
news:MPG.1d10e561764520e298b02d@xxxxxxxxxxxxxxxxxxxxxxx
> Oh, yes, it was interesting. But, then, so are many of your posts.
>
> I realized the limitation of the code I shared while writing it but
> figured...wtf...
>
> The alternative that I thought of was
>
> X0=1: X1=1
> for i=3 to n
> Xtemp=CDec(X0+X1): X0=X1: X1=Xtemp
> next i
> FibonacciNumber=X1
>
> --
> Regards,
>
> Tushar Mehta
> www.tushar-mehta.com
> Excel, PowerPoint, and VBA add-ins, tutorials
> Custom MS Office productivity solutions
>
> In article <uftE84DbFHA.2876@xxxxxxxxxxxxxxxxxxxx>,
> delouis@xxxxxxxxxxxxx says...
>> Hi Tushar. Yes, it's definitely not too efficient. I just thought it
>> was
>> interesting. :>)
>> I noticed that your example can't squeeze out the largest number
>> possible...139 because X1 will overflow inside the loop. Perhaps as an
>> idea, stop the loop just prior to X1 overflowing, and go from there.
>> Perhaps:
>>
>> Function FibonacciNumber(ByVal n As Long)
>> Dim I As Long, X0 As Variant, X1 As Variant
>> X0 = CDec(1): X1 = X0
>> For I = 3 To (n - 1) Step 2
>> X0 = X0 + X1
>> X1 = X0 + X1
>> Next I
>> FibonacciNumber = IIf(n Mod 2 = 1, X0 + X1, X1)
>> End Function
>>
>> ?FibonacciNumber(139)
>> 50095301248058391139327916261
>>
>> Just for gee-wiz, there are additional neat techniques. For example, if
>> N
>> is an even number, one can cut the number of loops in half again.
>>
>> Function Fibonacci_Even(ByRef N As Long)
>> Dim X As Variant
>> Dim Y As Variant
>> Dim j As Long
>> Dim Half As Long
>>
>> '// For Even numbers only...
>> If N Mod 2 = 1 Then Exit Function
>>
>> Select Case N
>> Case Is < 2, Is > 138: Fibonacci_Even = CVErr(9) 'Subscript out of
>> range
>> Case 2: Fibonacci_Even = 1
>> Case Else
>> Half = N / 2
>> X = CDec(1): Y = X
>> For j = 3 To Half - 1 Step 2
>> X = X + Y
>> Y = X + Y
>> Next j
>>
>> If Half Mod 2 = 0 Then
>> Fibonacci_Even = Y * (2 * X + Y)
>> Else
>> Fibonacci_Even = (X + Y) * (X + 3 * Y)
>> End If
>> End Select
>> End Function
>>
>> ?Fibonacci_Even(138)
>> 30960598847965113057878492344
>>
>>


.

Quantcast