找到第一个有1000位的斐波那契数 - Find a very first Fibonacci number which has 1000 digits

Find a very first Fibonacci number which has 1000 digits

本文关键字：第一个 1000位 | 更新日期: 2023-09-27

这是我编码来解决我的问题，它可以快速产生第10位数字，我已经改变了php.ini max- executiontime 到10000仍然没有得到一个小时的答案。我怎样才能快速/快速地运行这段代码?

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>" ;
}

@same slow progress

类似于

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)

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

$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>" ;