找到第一个有 1000 位数字的斐波那契数

Question

这是我为解决我的问题而编写的代码，它可以快速生成第 10 位数字，我已将 php.ini max-execution-time 更改为 10000 一小时内仍然没有得到答复。我如何运行此代码 quickly/sppedly .

function fabNumber($n){
    if($n==1 || $n==2) {
        return 1;
    }
    return fabNumber($n-2) + fabNumber($n-1);
}

function count_digit($number){
    return strlen($number);
}


$i = 1;
$count = 1;
while( $count != 1000){

    $fab_number = fabNumber($i);
    $count =  count_digit($fab_number);
    //var_dump($fab_number ,$count)."<br>";
    ++$i;
    echo $fab_number . "  index of ". $i ."<br>" ;
}

我应该使用 GMP 库

Edit 1:


  function fabNumber($n){
    if($n==1 || $n==2) {
        return 1;
    }
    return gmp_strval( fabNumber($n-2) )+ gmp_strval(fabNumber($n-1) );
}

function count_digit($number){
    return strlen($number);
}


$i = 1;
$count = 1;
while( $count != 100){

    $fab_number =gmp_strval( fabNumber($i));
    $count =  count_digit($fab_number);
    //var_dump($fab_number ,$count)."<br>";
    ++$i;
    echo gmp_strval($fab_number) . "  index of ". $i ."<br>" ;
}

@同样缓慢的进展

Answer 1

类似于：

function getFibonacci() {
    $i = '0';
    $k = '1'; //first fibonacci value
    yield $k;
    while(true) {
        $k = gmp_add($i, $k);
        $i = gmp_sub($k, $i);
        yield $k;
    }
}

foreach(getFibonacci() as $value) {
    if (strlen($value) == 1000) {
        break;
    }
}
echo $value, PHP_EOL;

(PHP >= 5.5.0)

Answer 2

您可以缓存数字以节省时间，因为在您的版本中，您会在每次迭代时重新计算所有数字

$GLOBALS["fabTab"] = array();


function fabNumber($n){
    if($n==1 || $n==2) {
        return "1";
    }

    if (!isset($GLOBALS["fabTab"][$n])) {
        $GLOBALS["fabTab"][$n] = bcadd(fabNumber($n-2), fabNumber($n-1));
    }

    return $GLOBALS["fabTab"][$n];
}

function count_digit($number){
    return strlen($number);
}

$start = time();

$i = 1;
$count = 1;
while( $count != 1000) {
    $fab_number = fabNumber($i);
    $count =  count_digit($fab_number);
    //var_dump($fab_number ,$count)."<br>";
    ++$i;
} 

echo "$fab_number<br/>index of ". $i ."<br>" ;
echo $count . " digits<br>" ;
echo (time() - $start) . " seconds<br>" ;

找到第一个有 1000 位数字的斐波那契数

Find a very first Fibonacci number which has 1000 digits

php

ini