JS：フィボナッチシーケンスに番号が含まれているかどうかを調べる（ループなし）

Question

フィボナッチシーケンスに番号が含まれているかどうかを確認する効率的な方法はありますか？

配列内にシーケンスを作成し、新たに生成されたシーケンス番号が入力番号と等しいかどうかを確認するループを使用した例が多数あります。別の方法がありますか？

Answer 1

http://www.geeksforgeeks.org/check-number-fibonacci-number/

及び一つ又は（5 * N2 + 4）または（5 * N2の両方もしあれば数がフィボナッチであることを意味するフィボナッチ数約特別な品質があると、このリンクの詳細 - 4 ）は完璧な広場です。

ので、

function (num) { 
    if (isSquare(5*(num*num)-4) || isSquare(5*(num*num)+4) { 
     return true; 
    } else { return false; } 
} 

はその後isSquareは単純なチェック機能になります。

編集：フィボナッチ数を見つけるのにはるかに効率的で簡単な方法ですが、上限があります。約70フィボナッチ数以上では、数値が大きすぎるために問題が発生することがあります。

Answer 2

def is_squared(number): 
    temp_root = math.sqrt(number); 
    temp_root = int(temp_root); 
    return (temp_root * temp_root == number); 

def check_all_fibo(test_number_list): 
    result_fibo_list = []; 
    for item in test_number_list: 
     if item==0 or item == 1 or item == 2: 
      result_fibo_list.append(item); 
      continue; 
     if is_squared(5 * item * item - 4) or is_squared(5 * item * item + 4): 
      result_fibo_list.append(item); 
    return result_fibo_list; 

これは私のpython実装です。しかし、この式は、フィブスがあまりにも大きくない場合にのみ機能することに注意してください。

Answer 3

function isSquare(n) { 
    return n > 0 && Math.sqrt(n) % 1 === 0; 
}; 

//Equation modified from http://www.geeksforgeeks.org/check-number-fibonacci-number/ 
function isFibonacci(numberToCheck) 
{ 
    // numberToCheck is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both 
    // is a perferct square 
    return isPerfectSquare(5*numberToCheck*numberToCheck + 4) || 
      isPerfectSquare(5*numberToCheck*numberToCheck - 4); 
} 


for(var i = 0; i<= 10000; ++i) { 
    console.log(i + " - " + isFibonacci(i)); 
} 

これは、大規模な数字の場合でも失敗する可能性が高いです。