Actually the essence of the competition in the title.

Rules:

  • the organizer of the competition does not participate in it
  • Php programming language

Victory criteria

  • Wins the algorithm that calculates the longest sequence

Testing

Closed due to the fact that off-topic participants are Visman , aleksandr barakin , user194374, fori1ton , Kromster Jul 5 '16 at 7:46 .

  • Most likely, this question does not correspond to the subject of Stack Overflow in Russian, according to the rules described in the certificate .
If the question can be reformulated according to the rules set out in the certificate , edit it .

  • Strange criterion of victory. The sequence of Fibonacci numbers is infinite. - AK ♦
  • four
    Not like the question never, like this. - Visman
  • @Visman Does the competition tag mean anything to you? - Naumov
  • 2
    The longest non-library sequence for large numbers is limited to the largest number in pure PHP. When attracting - the same picture, the largest number in the library. In any case, the running time of the algorithm will obviously be longer than the timeout for launching the online script. - PinkTux
  • 2
    @Naumov, in the conditions of such a service, many factors affect the purity of the time measurement. And here, plus or minus a millisecond is the difference in the result. In general, nonsense. Considering that 99% of the tested code will match almost byte-by-byte. - PinkTux

2 answers 2

There are many ways to calculate the Fibonacci number, you can use the definition and calculate them sequentially. However, it seems to me the most productive approach is to first create the function fibanchi() , which calculates an arbitrary Fibonacci number by its number in the sequence. The fastest way to solve this particular problem is the Binet formula.

 <?php function fibanchi($n) { return round((((1 + sqrt(5)) / 2) ** $n - ((1 - sqrt(5)) / 2) ** $n) / sqrt(5)); }

However, not only is the formula itself approximate, for large values ​​of the Fibonacci number, you can quickly go beyond the boundaries of both integer and floating point numbers. If the goal is the highest values ​​of Fibonacci numbers and accuracy, you can organize calculations in the array directly by definition - long, but the values ​​obtained will be very accurate (in this case, you can wipe numbers 2000 and higher, which are obviously not available when calculating using the Binet formula using scalar types).

 <?php function fibanchi($n) { // К-во разрядов $digit = intval($n / 4) + 5; $result = ''; $a1 = []; $a2 = []; $a3 = []; $a1[0] = 1; $a2[0] = 1; for($j = 2; $j < $n; $j++) { for($i = 0; $i < $digit; $i++) { $a1[$i] = isset($a1[$i]) ? $a1[$i] : 0; $a2[$i] = isset($a2[$i]) ? $a2[$i] : 0; $b = intval(($a1[$i] + $a2[$i])/10); $a3[$i] = $a1[$i] + $a2[$i] - $b * 10; isset($a1[$i + 1]) ? $a1[$i + 1] += $b : $a1[$i + 1] = $b; } for($i = 0; $i < $digit; $i++) { $a1[$i] = $a2[$i]; $a2[$i] = $a3[$i]; $a3[$i] = 0; } } $flg = false; for($i = count($a2) - 1; $i >= 0; $i--) { if($a2[$i] >= 1) $flg = true; if($flg) $result .= $a2[$i]; } return $result; }

To output a sequence, you can use the loop

 <?php for($i = 0; $i < 20; $i++) { echo fibanchi($i)."<br />"; }

    Each subsequent number of the Fibonacci series is the sum of the two previous numbers. 0 1 1 2 3 5 8 13 21 34 ...

    Probably the easiest algorithm.

     $end = 25; $j = 1; for($i=1; $i<$end; $i+=$j) { echo $i, ' '; $j = $i - $j; }

    1 1 2 3 5 8 13 21

    • The sequence starts at 0, but in principle it will come down. - Naumov