Fibonacci Algo

Psychophanta · Post by **Psychophanta** » Thu Sep 21, 2006 10:10 am

Code updated For 5.20+

    ;Leonardo de Pisa (aka Fibonacci) PB algorithm (2006-09) by Albert (Psychophanta)
    Define.q
    Procedure.q fib(n)
      Protected r=1,r1=0,negflag=1
      If n<0:n=-n:negflag=-(~n&1):negflag*2+1:EndIf
      Repeat
        If n=0:r=r1:Break:EndIf:r1+r:n-1
        If n=0:Break:EndIf:r+r1:n-1
    ;     Delay(20)  ; <- lets CPU to take a breath (if you want :-P )
      ForEver
      ProcedureReturn r*negflag
    EndProcedure
    ;
    ;prove it:
    For t.l=-92 To 92
      Debug Str(t)+" -> "+StrU(fib(t),#PB_Quad)
    Next
    ;
    If OpenConsole()
      Repeat
        Print("Enter number to find at fringe [-92,92]: ")
        n=Val(Input())
      Until n<=92 And n>=-92
      answer=fib(n)
      PrintN(""):PrintN(StrU(answer,#PB_Quad)+" is the "+StrU(n,#PB_Quad)+"th Fibonacci number."):PrintN("")
      PrintN("Press ESC to continue."):PrintN("")
      Repeat:key.s=Inkey():Delay(20):Until key=Chr(#ESC) ; catch ESC
      CloseConsole()
    EndIf

Suggest: Never use recursivity for these kind of things.

EDIT: also with negative values support.

NoahPhense · Post by **NoahPhense** » Thu Sep 21, 2006 12:24 pm

I don't know who did it.. But I posted this algo last night. Of course it
has been modified. But I know it was mine because of some lines. Like
the Catch ESC..

Moderator or not.. next time you move or delete a post. It would be
respectful to, in someway, notify the poster.

Thanks!

This is what I had posted, and I posted it in Off Topic.

Code: Select all

; /* Fibonacci Algo (converted from C++) bored
; Noah Phense */

; // init
Declare.l fib(n.l)
Define.l n, answer

; // main
If OpenConsole()
  Print("Enter number to find: ")
  n = Val(Input())
  answer = fib(n)
  PrintN("") : PrintN(Str(answer) + " is the " + Str(n) + "th Fibonacci number.") : PrintN("")
  PrintN("Press ESC to continue.") : PrintN("")
  Repeat : key.s = Inkey() : Delay(1) : Until key = Chr(27) ; catch ESC
  CloseConsole()
EndIf

End

; // fib algo
Procedure.l fib(n.l)
  If (n < 3)
    ProcedureReturn 1
  Else
    ProcedureReturn (fib(n-2) + fib(n-1))
  EndIf
EndProcedure

- np

Psychophanta · Post by **Psychophanta** » Thu Sep 21, 2006 12:43 pm

Yes, you are right, the moderator has deleted your post because it was not offtopic.
I agree with you that moderators should notify user when delete posts.

NoahPhense · Post by **NoahPhense** » Thu Sep 21, 2006 12:50 pm

Psychophanta wrote:Yes, you are right, the moderator has deleted your post because it was not offtopic.
I agree with you that moderators should notify user when delete posts.

Wonderful. Next time, I'll make it worth their while. I will be
sure to post it SEVERAL times. In several locations.

- np

rsts · Post by **rsts** » Thu Sep 21, 2006 6:33 pm

Yours may have accidentally been deleted as part of some clean up from some bot posts that occurred last night.

Or maybe they're out to get you

cheers

NoahPhense · Post by **NoahPhense** » Thu Sep 21, 2006 7:40 pm

rsts wrote:Yours may have accidentally been deleted as part of some clean up from some bot posts that occurred last night.

Or maybe they're out to get you

cheers

It's all good, I read those posts about the bot.

No Offense ...

= Noah Phense

- np

*ps -- they are out to get me.. but they'll never catch me

citystate · Post by **citystate** » Fri Sep 22, 2006 6:09 am

you could always just use Binet's fomula:

Code: Select all

Procedure.d Fib(n.l)
  sqr5.d = pow(5,0.5)
  result.d = (pow(0.5+sqr5/2,n)-pow(0.5-sqr5/2,2))/sqr5
  ProcedureReturn result
EndProcedure

no need for loops or recursion

Cheers,
Matt

Psychophanta · Post by **Psychophanta** » Fri Sep 22, 2006 9:21 am

citystate wrote:you could always just use Binet's fomula:
Code: Select all
Procedure.d Fib(n.l)
  sqr5.d = pow(5,0.5)
  result.d = (pow(0.5+sqr5/2,n)-pow(0.5-sqr5/2,2))/sqr5
  ProcedureReturn result
EndProcedure
no need for loops or recursion

Cheers,
Matt

EDIT:
Nope

That method is not good, there is an error caused at point when n=70.
That error begins at n=71, and the error is dragged and it grows while n is incremented.
Test yourself.

Perhaps the error is due to floats resolution, but i dont know, because windows calculator gives 308061521170128,82917960675006244 for n=71 with Binet's formula, and your PB funtion gives: 308061521170129.56 :roll:

Useful info for trip more about this matter:
http://members.aol.com/kwpapke/Binet.html

citystate · Post by **citystate** » Sat Sep 23, 2006 8:30 am

bugga
got the formula wrong - that's what I get from working from memory

Procedure.d Fib(n.l)
sqr5.d = pow(5,0.5)
result.d = (pow(0.5+sqr5/2,n)-pow(0.5-sqr5/2,n))/sqr5 ; changed '2' to 'n'
ProcedureReturn result
EndProcedure

this one should work - thanks for the feedback Psychophanta

Cheers

Psychophanta · Post by **Psychophanta** » Sat Sep 23, 2006 10:35 am

Yes, i saw there was that mistake in your function.
But with the fixed mistake, the error persists because of floats and doubles have not enough precission for this matters.

Besides of that, with your corrected function there is one more error respect the mine of the first post:
it doesn't allow negative values.

And besides of all that, nor my function neither yours accept real numbers (floats) 'n', and neither accepts complex numbers as 'n'.

So here is the algorithm i made for accept real, and also complex numbers for 'n'.
(Notice the results have an error which is bigger as long 'n' grows because the Binet's formula uses floats. This doesn't happen with my function in the first post coz it uses only integers for 'n'):

Code: Select all

;Binet's formula got from Leonardo de Pisa (aka Fibonacci) sequence. PB algorithm (2006-09) by Albert (Psychophanta)
Structure ComplexNumber
  RealPart.d
  ImagPArt.d
EndStructure
Global Result.ComplexNumber,SQRT5.d=Sqr(5),Phi.d=(1+SQRT5)/2,LogPhi.d=Log(Phi)
#e=2.718281828459045235;3602874713527
Procedure Fib(RealPart.d,ImagPart.d=0.0); <- Binet's formula (valid for real numbers and also for complex numbers)
  Protected PhiPowRealPart.d=Pow(Phi,RealPart),PhiPowRealParte.d=PhiPowRealPart*Pow(#e,ImagPart*#PI)
  Result\RealPart=(PhiPowRealPart*Cos(ImagPart*LogPhi)-Cos(RealPart*#PI-ImagPart*LogPhi)/PhiPowRealParte)/SQRT5
  Result\ImagPart=(PhiPowRealPart*Sin(ImagPart*LogPhi)-Sin(RealPart*#PI-ImagPart*LogPhi)/PhiPowRealParte)/SQRT5
EndProcedure

;prove Fib:
Realcounter.d=-5
While Realcounter.d<5
  Imagcounter.d=-5
  While Imagcounter.d<5
    Fib(Realcounter,Imagcounter)
    Debug StrD(Realcounter)+", "+StrD(Imagcounter)+"i  => "+StrD(Result\RealPart)+", "+StrD(Result\ImagPart)+"i"
    Imagcounter+0.5
    Delay(20)
  Wend
  Realcounter+1.0
Wend

PureBasic Forums - English

Fibonacci Algo

Fibonacci Algo

Re: Fibonacci Algo