Page 1 of 1
Fibonacci Algo
Posted: Thu Sep 21, 2006 10:10 am
by Psychophanta
Code updated For 5.20+
Code: Select all
;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.
Re: Fibonacci Algo
Posted: Thu Sep 21, 2006 12:24 pm
by NoahPhense
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
Posted: Thu Sep 21, 2006 12:43 pm
by Psychophanta
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.
Posted: Thu Sep 21, 2006 12:50 pm
by NoahPhense
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
Posted: Thu Sep 21, 2006 6:33 pm
by rsts
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
Posted: Thu Sep 21, 2006 7:40 pm
by NoahPhense
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
Posted: Fri Sep 22, 2006 6:09 am
by citystate
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
Posted: Fri Sep 22, 2006 9:21 am
by Psychophanta
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
Posted: Sat Sep 23, 2006 8:30 am
by citystate
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
Posted: Sat Sep 23, 2006 10:35 am
by Psychophanta
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