Skip to content

Fibonacci

10 messages · Erich Neuwirth, Petr Savicky, Nutter, Benjamin +6 more

Original
Erich Neuwirth
# 
The "easy" solution to compute the Fibonacci numbers is
 
fibo <- function(n,a=1,b=1){
 if (n == 1) return(a)
 if (n == 2) return(b)
 return(fibo(n-1,b,a+b)) 
}

It avoids double recursion.
It is, however, not as resource efficient as a loop since R does not do
tail recursion elimination.
On Apr 20, 2011, at 11:42 AM, Georgina Imberger wrote:

            

      
      
      
    

        

      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Petr Savicky
    

    

      
      #
    

  


  

      
On Wed, Apr 20, 2011 at 11:42:38AM +0200, Georgina Imberger wrote:

            

      
      
      
    

        
Is it allowed to use length() function? If so, then try
the following

  Fibonacci<-c(1,1)
  while (max(Fibonacci)<500){
      Fibonacci<-c(Fibonacci, Fibonacci[length(Fibonacci) - 1] + Fibonacci[length(Fibonacci)])
  }

Petr Savicky.

  
  


  


      

    

    

      
      

        


  

        

      Nutter, Benjamin
    

    

      
      #
    

  


  

      
Fibonacci <- c(1, 1)
while (max (Fibonacci) < 500){
  Fibonacci <- c(Fibonacci, sum(tail(Fibonacci, 2))) } 

-----Original Message-----
From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org]
On Behalf Of Georgina Imberger
Sent: Wednesday, April 20, 2011 5:43 AM
To: r-help at r-project.org
Subject: [R] Fibonacci

Hi!

I am trying to work out the code to get a Fibonacci sequence, using the
while() loop and only one variable. And I can't figure it out.

Fibonacci<-c(1,1)
while (max(Fibonacci)<500){
Fibonacci<-c(Fibonacci, (max(Fibonacci) + ?(Fibanacci))) }


How can I tell R to take the value one before the max value? (Without
defining another variable)

(Probably super easy... I am a beginner...)

Thanks,
Georgie


______________________________________________
R-help at r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.


===================================

 Please consider the environment before printing this e-mail

Cleveland Clinic is ranked one of the top hospitals
in America by U.S.News & World Report (2010).  
Visit us online at http://www.clevelandclinic.org for
a complete listing of our services, staff and
locations.


Confidentiality Note:  This message is intended for use\...{{dropped:13}}

  
  


  


      

    

    

      
      

        


  

        

      Bart Joosen
    

    

      
      #
    

  


  

      
Another solution:

while (Fibonacci[1] < 500)  Fibonacci <- c(sum(Fibonacci[c(1,2)]),
Fibonacci)

While this adds the sum before the existing values, the length or tail
function or avoided, but even with reordering, its faster
(Fibonacci[length(Fibonacci):1])

Best regards

Bart


--
View this message in context: http://r.789695.n4.nabble.com/Fibonacci-tp3462636p3463050.html
Sent from the R help mailing list archive at Nabble.com.

  
  


  


      

    

    

      
      

        
      

    

    

      
      

        


  

        

      Michael Dewey
    

    

      
      #
    

  


  

      
At 10:42 20/04/2011, Georgina Imberger wrote:

            

      
      
      
    

        
> phi <- 0.5 * (1 + sqrt(5))
 > phi
[1] 1.618034
 > fib <- function(n) {(phi ^ n - (1 - phi) ^ n) / sqrt(5)}
 > fib(1:10)
  [1]  1  1  2  3  5  8 13 21 34 55
 >

Admittedly this does not use a while loop as you requested

Courtesy of Wikipedia

            

      
      
      
    

        
Michael Dewey
info at aghmed.fsnet.co.uk
http://www.aghmed.fsnet.co.uk/home.html

  
  


  


      

    

    

      
      

        


  

        

      David Winsemius
    

    

      
      #
    

  


  

      
On Apr 21, 2011, at 9:04 AM, Michael Dewey wrote:

        

            

      
      
      
    

        
I like it!

 > test <-c(  1,  1,  2,  3,  5,  8, 13, 21, 34, 55)
 > test == fib(1:10)
  [1]  TRUE  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE

To avoid such FAQ-tual puzzlement, it might be better to round to zero  
digits:

fib2 <- function(n) {round( (phi ^ n - (1 - phi) ^ n) / sqrt(5) ) }

 > test == fib2(1:10)
  [1] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE


There are several packages that offer fib() functions of one name or  
another, including the gmp package which always seems to "think  
bigger" than I do. I cannot (trivially) see how that author does it  
with fibnum(), because it is in a .Call()

  
    

      
      
    

  


  


      

    

    

      
      

        


  

        

      Nordlund, Dan (DSHS/RDA)
    

    

      
      #
    

  


  

          

      
      
      
    

        
I, too, like the Michael/David/Wikipedia solution.  But if this is homework, I would recommend using length() instead of max() for getting the last two items of the vector.

Hope this is helpful,

Dan

Daniel J. Nordlund
Washington State Department of Social and Health Services
Planning, Performance, and Accountability
Research and Data Analysis Division
Olympia, WA 98504-5204

  
  


  


      

    

    

      
      

        


  

        

      William Dunlap
    

    

      
      #
    

  


  

          

      
      
      
    

        
If you are going to round anyway, you can save time and
add puzzlement by leaving out the (1-phi)^n term:
  
  > fib3 <- function(n) {round( (phi ^ n) / sqrt(5) ) }
  > all(fib2(0:100) == fib3(0:100))
  [1] TRUE

Bill Dunlap
Spotfire, TIBCO Software
wdunlap tibco.com