FIBONACCI SERIES

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
bluekhille
Forum Commoner
Posts: 25
Joined: Thu Jul 16, 2009 6:49 am

FIBONACCI SERIES

Post by bluekhille »

Can any body help me with this one?

i need a program.

sample output

if i input 5 then the output must be

1
1
2
3
5


my input is the number of alteration
then the output is the sum of two numbers above it. out depends on number of alteration.

pls help me thanks!
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: FIBONACCI SERIES

Post by VladSun »

Google is your friend :)
http://www.google.com/search?client=ope ... 8&oe=utf-8

Though, I really think you should try to implement it by yourself.
Last edited by VladSun on Mon Jul 27, 2009 8:02 am, edited 1 time in total.
There are 10 types of people in this world, those who understand binary and those who don't
bluekhille
Forum Commoner
Posts: 25
Joined: Thu Jul 16, 2009 6:49 am

Re: FIBONACCI SERIES

Post by bluekhille »

thanks vlad! :D
User avatar
jackpf
DevNet Resident
Posts: 2119
Joined: Sun Feb 15, 2009 7:22 pm
Location: Ipswich, UK

Re: FIBONACCI SERIES

Post by jackpf »

Just to let everyone know that I'm such mathematical genius :P

Code: Select all

<?php
        //the initial number :)
        $number = 40;
       
        //the two integers required for the fibonacci sequence
        $i  = 0;
        $ii = 1;
        //the counter to alternate sums
        $counter = 0;
        //init the sequence
        $sequence = array(0, 1);
       
        //while the sum of each fibonacci number is less than the initial number...
        while($i + $ii <= $number)
        {
                //just to save me some typing
                $_i = $i + $ii;
               
                //append to the sequence
                array_push($sequence, $_i);
               
                //alternate which integer has the previous added to it (must start with 0 + 1 since 1 + 0 will cause an infinite loop)
                if($counter % 2 == 0)
                        $i  += $ii;
                else
                        $ii += $i;
               
                //increment counter
                $counter++;
        }
       
        echo implode(', ', $sequence);
?>
User avatar
jayshields
DevNet Resident
Posts: 1912
Joined: Mon Aug 22, 2005 12:11 pm
Location: Leeds/Manchester, England

Re: FIBONACCI SERIES

Post by jayshields »

Basically stay away from recursion with this algorithm, although the code is much more concise the performance degrades hugely when the number is anything substantial.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: FIBONACCI SERIES

Post by VladSun »

jackpf wrote:

Code: Select all

 
                $_i = $i + $ii;
               
                array_push($sequence, $_i);
               
                if($counter % 2 == 0)
                        $i  += $ii;
                else
                        $ii += $i;
               
                $counter++;
 
Why do you need this?
According to Fibonacci series definition, it should be:

Code: Select all

 
                $_i = $i + $ii;
               
                array_push($sequence, $_i);
           
                $i  = $ii;
                $ii = $_i;
               
There are 10 types of people in this world, those who understand binary and those who don't
bluekhille
Forum Commoner
Posts: 25
Joined: Thu Jul 16, 2009 6:49 am

Re: FIBONACCI SERIES

Post by bluekhille »

so which is the right one? :?
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: FIBONACCI SERIES

Post by VladSun »

VladSun wrote:Though, I really think you should try to implement it by yourself.
There are 10 types of people in this world, those who understand binary and those who don't
User avatar
jackpf
DevNet Resident
Posts: 2119
Joined: Sun Feb 15, 2009 7:22 pm
Location: Ipswich, UK

Re: FIBONACCI SERIES

Post by jackpf »

jayshields wrote:Basically stay away from recursion with this algorithm, although the code is much more concise the performance degrades hugely when the number is anything substantial.
How are you supposed to do this without recursion?

And I doubt that. With the number 23452346234623464294967296 it takes 0.00018310546875 seconds to execute on my PC.
VladSun wrote:According to Fibonacci series definition, it should be:

Code: Select all

 
                $_i = $i + $ii;
               
                array_push($sequence, $_i);
           
                $i  = $ii;
                $ii = $_i;
               
And yeah, you're right. Although they both work. I haven't studied the fibonacci sequence for years though :P
User avatar
jayshields
DevNet Resident
Posts: 1912
Joined: Mon Aug 22, 2005 12:11 pm
Location: Leeds/Manchester, England

Re: FIBONACCI SERIES

Post by jayshields »

Your version isn't recursive.

The recursive version is the most concise version, which seems to be the version most people are introduced to. It looks like this:

Code: Select all

function fib($num)
{
  //Base case
  if($num < 2)
    return $num;
 
  return fib($num - 1) + fib($num - 2);
}
OP: The first Google result for "fibonacci php" gives http://snipplr.com/view/1993/php-fibonacci-sequence/ which seems a pretty good solution to me.
User avatar
jackpf
DevNet Resident
Posts: 2119
Joined: Sun Feb 15, 2009 7:22 pm
Location: Ipswich, UK

Re: FIBONACCI SERIES

Post by jackpf »

Oh right, I thought you were referring to my while() loop as recursion :) Yeah, that probably would be slower.

And yeah, there are loads on google. Still, it was a nice challenge though :P
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: FIBONACCI SERIES

Post by VladSun »

Also, a full version should implement calculation of Fibonacci series with negative numbers:

F(-n) = F(n)(-1)^(n+1)
There are 10 types of people in this world, those who understand binary and those who don't
Post Reply