매우 큰 'n'에 대한 n 번째 피보나치 수 찾기
n의 매우 큰 값인 1000000에 대해 피보나치 수열의 n 번째 항을 어떻게 찾을 수 있는지 궁금합니다. 초등학교 반복 방정식을 사용 fib(n)=fib(n-1)+fib(n-2)하면 50 번째 항을 찾는 데 2-3 분이 걸립니다!
인터넷 검색 후 Binet의 공식에 대해 알게되었지만 여기에서 말한 것처럼 n> 79의 값에는 적합하지 않습니다 .
소수를 찾는 것과 같은 알고리즘이 있습니까?
행렬 지수화 방법 (선형 반복 방법)을 사용할 수 있습니다. 이 블로그 에서 자세한 설명과 절차를 확인할 수 있습니다 . 실행 시간은 O (log n )입니다.
이 작업을 수행하는 더 좋은 방법이 없다고 생각합니다.
메모 기능 을 사용하면 많은 시간을 절약 할 수 있습니다 . 예를 들어, 다음 두 버전 (JavaScript)을 비교하십시오.
버전 1 : 정상 재귀
var fib = function(n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
};
버전 2 : 메모 화
A. 밑줄 라이브러리 사용
var fib2 = _.memoize(function(n) {
return n < 2 ? n : fib2(n - 1) + fib2(n - 2);
});
B. 라이브러리 없음
var fib3 = (function(){
var memo = {};
return function(n) {
if (memo[n]) {return memo[n];}
return memo[n] = (n <= 2) ? 1 : fib3(n-2) + fib3(n-1);
};
})();
첫 번째 버전은 n = 50 (Chrome)에서 3 분 이상 걸리지 만 두 번째 버전은 5ms 미만입니다! jsFiddle 에서 확인할 수 있습니다 .
버전 1의 시간 복잡도가 지수 ( O (2 N / 2 ))이고 버전 2가 선형 ( O ( N )) 이라는 것을 알고 있다면 놀라운 일이 아닙니다 .
버전 3 : 행렬 곱셈
또한 N 행렬 의 곱셈을 계산하여 시간 복잡성을 O (log ( N ))로 줄일 수도 있습니다 .
여기서 F n 은 피보나치 수열 의 n 번째 항을 나타냅니다 .
최적의 솔루션이 O (log n) 단계 에서 완료된다는 Wayne Rooney의 답변에 동의 하지만 전체 런타임 복잡성은 사용 된 곱셈 알고리즘의 복잡성에 따라 달라집니다. 예를 들어 Karatsuba Multiplication을 사용 하면 전체 런타임 복잡성은 O (n log 2 3 ) ≈ O (n 1.585 )가 됩니다. 1
그러나 행렬 지수 화가 반드시 최선의 방법은 아닙니다. Project Nayuki 의 개발자 가 알아 차렸 듯이 행렬 지수는 제거 할 수있는 중복 계산을 수반합니다. 저자의 설명에서 :
F k 와 F k + 1이 주어지면 다음을 계산할 수 있습니다.
이것은 행렬 지수화처럼 8 개가 아니라 분 할당 3 개의 BigInt에서 BigInt 로의 곱셈 만 필요합니다.
그래도 우리는 이것보다 약간 더 잘할 수 있습니다. 가장 우아한 피보나치 아이덴티티 중 하나는 Lucas Numbers와 관련이 있습니다.
여기서 L n 은 n 번째 루카스 번호 입니다. 이 ID는 다음과 같이 더 일반화 될 수 있습니다.
거기에 약간의 다소간 동등한 방법으로 반복적으로 진행하기는하지만, 가장 논리적 인 온 것 같다 F N 과 L N . 아래 구현에 사용 된 추가 ID는 Lucas Sequences 에 대해 나열된 ID에서 찾거나 파생 될 수 있습니다 .
이러한 방식으로 진행하려면 분 할당 BigInt 대 BigInt 곱셈이 두 번만 필요하고 최종 결과에는 하나만 필요합니다. 이는 Project Nayuki ( 테스트 스크립트 )에서 제공하는 코드보다 약 20 % 빠릅니다 . 참고 : 원본 소스 는 공정한 비교를 위해 약간 수정 (개선)되었습니다.
def fibonacci(n):
def fib_inner(n):
'''Returns F[n] and L[n]'''
if n == 0:
return 0, 2
u, v = fib_inner(n >> 1)
q = (n & 2) - 1
u, v = u * v, v * v + 2*q
if (n & 1):
u1 = (u + v) >> 1
return u1, 2*u + u1
return u, v
u, v = fib_inner(n >> 1)
if (n & 1):
q = (n & 2) - 1
u1 = (u + v) >> 1
return v * u1 + q
return u * v
최신 정보
수염이 희끗 희끗 포인트 아웃은 , 상기 결과는 이미 (2000) 다카하시시 개선 된 2 의 BIGINT 제곱합니다 (쇤하게 - 슈트라 센 알고리즘에 대해 구체적으로) 일반적인지의 BIGINT 승산보다 계산 비용 주목하여. 저자 는 다음과 같은 ID를 사용하여 F n 과 L n 에서 분할하는 반복을 제안합니다 .
이러한 방식으로 반복하려면 위와 같이 BigInt 제곱과 BigInt 곱셈이 아닌 분 할당 두 개의 BigInt 제곱이 필요합니다. 예상대로 런타임은 매우 큰 n의 경우 위의 구현보다 훨씬 빠르지 만 작은 값 ( n <25000 )의 경우 다소 느립니다 .
그러나 이것은 약간 개선 될 수 있습니다. 저자는 "Lucas Numbers의 곱 알고리즘이 가장 적은 비트 연산을 사용하여 피보나치 수 F n 을 계산하는 것으로 알려져 있습니다."라고 주장합니다 . 그런 다음 저자는 루카스 수의 곱 알고리즘을 적용하기로 결정했습니다.이 알고리즘은 당시 가장 빠르게 알려진 F n 과 L n으로 분할되었습니다 . 그러나 L n 은 F n + 1 계산에만 사용됩니다 . 다음과 같은 신원을 고려하면 다소 낭비적인 것 같습니다.
첫 번째는 Takahashi에서 직접 가져오고 두 번째는 행렬 지수화 방법 (Nayuki도 언급)의 결과이고 세 번째는 이전 두 개를 더한 결과입니다. 이것은 F n 과 F n + 1 에 대한 명백한 분할을 허용합니다 . 결과는 BigInt를 하나 덜 추가해야하며, 중요한 것은 n 짝수에 대해 하나 더 적은 2로 나누는 것입니다 . 홀수 n의 경우 이익이 두 배가됩니다. 실제로 이것은 작은 n (10-15 % 더 빠름)에 대해 Takahashi가 제안한 방법보다 훨씬 빠르며 매우 큰 n ( 테스트 스크립트 )에 대해 약간 더 빠릅니다 .
def fibonacci(n):
def fib_inner(n):
'''Returns F[n] and F[n+1]'''
if n == 0:
return 0, 1
u, v = fib_inner(n >> 1)
q = (n & 2) - 1
u *= u
v *= v
if (n & 1):
return u + v, 3*v - 2*(u - q)
return 2*(v + q) - 3*u, u + v
u, v = fib_inner(n >> 1)
# L[m]
l = 2*v - u
if (n & 1):
q = (n & 2) - 1
return v * l + q
return u * l
업데이트 2
처음 게시 한 이후 이전 결과도 약간 개선되었습니다. 두 개의 BigInt 제곱을 제외하고 F n 및 F n + 1 에 대한 분할은 분 할당 3 개의 BigInt 추가 및 두 개의 작은 상수 곱셈의 오버 헤드를 갖습니다. 이 오버 헤드는 대신 L n 및 L n + 1 로 분할하여 거의 완전히 제거 할 수 있습니다 .
이러한 방식으로 분할하려면 이전과 같이 두 개의 BigInt 사각형이 필요하지만 BigInt 추가는 하나만 필요합니다. 하지만이 값은 해당 피보나치 수와 다시 관련되어야합니다. 다행히도 이는 5로 단일 분할로 달성 할 수 있습니다.
몫은 정수로 알려져 있기 때문에 GMP와 같은 정확한 나누기 방법을 mpz_divexact_ui사용할 수 있습니다. 가장 바깥 쪽 분할을 풀면 단일 곱셈으로 최종 값을 계산할 수 있습니다.
Python에서 구현 된 것처럼 이는 small n (5-10 % 더 빠름)에 대한 이전 구현보다 눈에 띄게 빠르며 매우 큰 n ( 테스트 스크립트 )에 대해 약간 더 빠릅니다 .
def fibonacci(n):
def fib_inner(n):
'''Returns L[n] and L[n+1]'''
if n == 0:
return mpz(2), mpz(1)
m = n >> 1
u, v = fib_inner(m)
q = (2, -2)[m & 1]
u = u * u - q
v = v * v + q
if (n & 1):
return v - u, v
return u, v - u
m = n >> 1
u, v = fib_inner(m)
# F[m]
f = (2*v - u) / 5
if (n & 1):
q = (n & 2) - 1
return v * f - q
return u * f
1 F n ~ O (n) 의 자릿수 (또는 비트)는 다음과 같이 표시됩니다.
Karatsuba Multiplication을 사용한 런타임 복잡성은 다음과 같이 계산할 수 있습니다.
2 Takahashi, D. (2000), " 큰 피보나치 수를 계산하기위한 빠른 알고리즘 "(PDF), Information Processing Letters 75 , pp. 243–246.
반복 ID http://en.wikipedia.org/wiki/Fibonacci_number#Other_identities 를 사용 n하여 log(n)단계 에서-번째 숫자 를 찾습니다 . 이를 위해 임의의 정밀도 정수를 사용해야합니다. 또는 각 단계에서 모듈러 산술을 사용하여 모듈 로 모듈로 정확한 답을 계산할 수 있습니다 .
그 점 3n+3 == 3(n+1)에 주목하면 각 단계에서 두 개의 연속적인 피보나치 수 를 계산 하고 나머지 값에 따라 적절한 공식을 선택 하는 단일 재귀 함수를 고안 할 수 있습니다 . IOW는 한 쌍 의 쌍 에서 한 쌍 을 계산 하므로 이중 재귀가 없으며 메모가 필요하지 않습니다.n@(3n+r,3n+r+1), r=0,1,2@(n,n+1)
Haskell 코드가 여기 있습니다 .
F(2n-1) = F(n-1)^2 + F(n)^2 === a' = a^2 + b^2
F(2n) = 2 F(n-1) F(n) + F(n)^2 === b' = 2ab + b^2
더 빠른 코드로 이어질 것 같습니다. "Lucas sequence identities"를 사용 하는 것이 가장 빠를 수 있습니다 ( 이것은 이 구현 을 인용 한 사용자 : primo 때문입니다 ).
대부분의 사람들은 이미 N 번째 피보나치 수의 발견을 설명하는 링크를 제공했습니다. Power 알고리즘이 약간만 변경해도 동일하게 작동하는 방식입니다.
어쨌든 이것은 내 O (log N) 솔루션입니다.
package algFibonacci;
import java.math.BigInteger;
public class algFibonacci {
// author Orel Eraki
// Fibonacci algorithm
// O(log2 n)
public static BigInteger Fibonacci(int n) {
int num = Math.abs(n);
if (num == 0) {
return BigInteger.ZERO;
}
else if (num <= 2) {
return BigInteger.ONE;
}
BigInteger[][] number = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };
BigInteger[][] result = { { BigInteger.ONE, BigInteger.ONE }, { BigInteger.ONE, BigInteger.ZERO } };
while (num > 0) {
if (num%2 == 1) result = MultiplyMatrix(result, number);
number = MultiplyMatrix(number, number);
num/= 2;
}
return result[1][1].multiply(BigInteger.valueOf(((n < 0) ? -1:1)));
}
public static BigInteger[][] MultiplyMatrix(BigInteger[][] mat1, BigInteger[][] mat2) {
return new BigInteger[][] {
{
mat1[0][0].multiply(mat2[0][0]).add(mat1[0][1].multiply(mat2[1][0])),
mat1[0][0].multiply(mat2[0][1]).add(mat1[0][1].multiply(mat2[1][1]))
},
{
mat1[1][0].multiply(mat2[0][0]).add(mat1[1][1].multiply(mat2[1][0])),
mat1[1][0].multiply(mat2[0][1]).add(mat1[1][1].multiply(mat2[1][1]))
}
};
}
public static void main(String[] args) {
System.out.println(Fibonacci(8181));
}
}
피보나치 수를 계산할 때 재귀 알고리즘은 최악의 방법 중 하나입니다. for주기 (반복 방법이라고 함)에 이전 두 숫자를 추가하면 50 번째 요소를 계산하는 데 2-3 분이 걸리지 않습니다.
다음은 O (log (n))에서 n 번째 피보나치 수를 계산하는 파이썬 버전입니다.
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
def matmul(M1, M2):
a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
return [[a11, a12], [a21, a22]]
def matPower(mat, p):
if p == 1:
return mat
m2 = matPower(mat, p//2)
if p % 2 == 0:
return matmul(m2, m2)
else:
return matmul(matmul(m2, m2),mat)
Q = [[1,1],[1,0]]
q_final = matPower(Q, n-1)
return q_final[0][0]
피보나치 수열의 임의적으로 큰 요소 를 계산 하려면 폐쇄 형 솔루션 인 Binet의 공식을 사용해야하며, 답을 계산하기에 충분한 정밀도를 제공하기 위해 임의 정밀도 수학을 사용해야합니다.
그냥 점화식을 사용하지만,해야 하지 50 기간을 계산 2-3 분 정도 필요 - 당신은 어떤 현대적인 시스템에서 몇 초 이내에 수십억에서 조건을 계산할 수 있어야한다. 완전 재귀 공식을 사용하는 것처럼 들리는데, 이는 재귀 계산의 조합 폭발로 이어집니다. 간단한 반복 공식이 훨씬 빠릅니다.
재귀 솔루션은 다음과 같습니다.
int fib(int n) {
if (n < 2)
return 1;
return fib(n-1) + fib(n-2)
}
... 앉아서 스택 오버플로를 확인하십시오.
반복 솔루션은 다음과 같습니다.
int fib(int n) {
if (n < 2)
return 1;
int n_1 = 1, n_2 = 1;
for (int i = 2; i <= n; i += 1) {
int n_new = n_1 + n_2;
n_1 = n_2;
n_2 = n_new;
}
return n_2;
}
우리는 기본적으로 다음 학기 계산하는 방법 공지 사항 n_new이전 용어에서를 n_1하고 n_2그 다음 반복에 대한 아래 모든 조건을 "셔플". 의 값에 선형 실행 시간 을 사용하면 최신 기가 헤르츠 머신에서 수십억 단위 (중간 변수의 정수 오버플로 이후) n에 대해 몇 초의 문제 n입니다.
UVA 문제를 해결했습니다 : 495-Fibonacci Freeze
최대 5000 번째까지 모든 피보나치 수를 생성하고 주어진 입력 (범위 1 ~ 5000)에 대한 출력을 인쇄합니다.
런타임 00.00 초로 허용됩니다.
5000의 피보나치 수는 다음과 같습니다.
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125
#include<stdio.h>
#include<string.h>
#define LIMIT 5001
#define MAX 1050
char num[LIMIT][MAX];
char result[MAX];
char temp[MAX];
char* sum(char str1[], char str2[])
{
int len1 = strlen(str1);
int len2 = strlen(str2);
int minLen, maxLen;
int i, j, k;
if (len1 > len2)
minLen = len2, maxLen = len1;
else
minLen = len1, maxLen = len2;
int carry = 0;
for (k = 0, i = len1 - 1, j = len2 - 1; k<minLen; k++, i--, j--)
{
int val = (str1[i] - '0') + (str2[j] - '0') + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
}
while (k < len1)
{
int val = str1[i] - '0' + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
k++; i--;
}
while (k < len2)
{
int val = str2[j] - '0' + carry;
result[k] = (val % 10) + '0';
carry = val / 10;
k++; j--;
}
if (carry > 0)
{
result[maxLen] = carry + '0';
maxLen++;
result[maxLen] = '\0';
}
else
{
result[maxLen] = '\0';
}
i = 0;
while (result[--maxLen])
{
temp[i++] = result[maxLen];
}
temp[i] = '\0';
return temp;
}
void generateFibonacci()
{
int i;
num[0][0] = '0'; num[0][1] = '\0';
num[1][0] = '1'; num[1][1] = '\0';
for (i = 2; i <= LIMIT; i++)
{
strcpy(num[i], sum(num[i - 1], num[i - 2]));
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int N;
generateFibonacci();
while (scanf("%d", &N) == 1)
{
printf("The Fibonacci number for %d is %s\n", N, num[N]);
}
return 0;
}
가장 간단한 Pythonic 구현은 다음과 같이 주어질 수 있습니다.
def Fib(n):
if (n < 0) :
return -1
elif (n == 0 ):
return 0
else:
a = 1
b = 1
for i in range(2,n+1):
a,b = b, a+b
return a
첫째, 알려진 가장 큰 피보나치 용어 에서 가장 높은 용어에 대한 아이디어를 형성 할 수 있습니다 . 또한 재귀 적 피보나치 함수 프리젠 테이션을 통한 단계별 실행을 참조하십시오 . 이 주제에 대한 관심있는 접근 방식 이이 기사에 있습니다. 또한 세계 최악의 알고리즘 으로 읽어 보 시겠습니까? .
나는 GNU를 사용하여 입력 숫자의 규모C 를 지원 하는 구현을 작성했습니다 .gmp
하나의 숫자에 대한 그림 FIB 할 때입니다 O(n)및 캐시를위한 공간입니다 O(1), (실제로 0 ~ N에 대한 모든 악의없는 거짓말을 생각) .
암호
fib_cached_gmp.c :
// fibonacci - cached algorithm - any scale of input with GMP,
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
// a single step,
void fib_gmp_next(mpz_t *cache) {
mpz_add(cache[2], cache[0], cache[1]);
mpz_set(cache[0], cache[1]);
mpz_set(cache[1], cache[2]);
}
// figure fib for a single number, in O(n),
mpz_t *fib_gmp(int n, mpz_t *result) {
// init cache,
mpz_t cache[3]; // number: [fib(n-2), fib(n-1), fib(n)],
mpz_init(cache[0]);
mpz_init(cache[1]);
mpz_init(cache[2]);
mpz_set_si(cache[0], 0);
mpz_set_si(cache[1], 1);
while (n >= 2) {
fib_gmp_next(cache);
n--;
}
mpz_set(*result, cache[n]);
return result;
}
// test - print fib from 0 to n, tip: cache won't be reused between any 2 input numbers,
void test_seq(int n) {
mpz_t result;
mpz_init(result);
for (int i = 0; i <= n; i++) {
gmp_printf("fib(%2d): %Zd\n", i, fib_gmp(i, &result));
}
}
// test - print fib for a single num,
void test_single(int x) {
mpz_t result;
mpz_init(result);
gmp_printf("fib(%d): %Zd\n", x, fib_gmp(x, &result));
}
int main() {
// test sequence,
test_seq(100);
// test single,
test_single(12345);
return 0;
}
먼저 gmp를 설치하십시오.
// for Ubuntu,
sudo apt-get install libgmp3-dev
엮다:
gcc fib_cached_gmp.c -lgmp
실행 :
./a.out
출력 예 :
fib( 0): 0
fib( 1): 1
fib( 2): 1
fib( 3): 2
fib( 4): 3
fib( 5): 5
fib( 6): 8
fib( 7): 13
fib( 8): 21
fib( 9): 34
fib(10): 55
fib(11): 89
fib(12): 144
fib(13): 233
fib(14): 377
fib(15): 610
fib(16): 987
fib(17): 1597
fib(18): 2584
fib(19): 4181
fib(20): 6765
fib(21): 10946
fib(22): 17711
fib(23): 28657
fib(24): 46368
fib(25): 75025
fib(26): 121393
fib(27): 196418
fib(28): 317811
fib(29): 514229
fib(30): 832040
fib(31): 1346269
fib(32): 2178309
fib(33): 3524578
fib(34): 5702887
fib(35): 9227465
fib(36): 14930352
fib(37): 24157817
fib(38): 39088169
fib(39): 63245986
fib(40): 102334155
fib(41): 165580141
fib(42): 267914296
fib(43): 433494437
fib(44): 701408733
fib(45): 1134903170
fib(46): 1836311903
fib(47): 2971215073
fib(48): 4807526976
fib(49): 7778742049
fib(50): 12586269025
fib(51): 20365011074
fib(52): 32951280099
fib(53): 53316291173
fib(54): 86267571272
fib(55): 139583862445
fib(56): 225851433717
fib(57): 365435296162
fib(58): 591286729879
fib(59): 956722026041
fib(60): 1548008755920
fib(61): 2504730781961
fib(62): 4052739537881
fib(63): 6557470319842
fib(64): 10610209857723
fib(65): 17167680177565
fib(66): 27777890035288
fib(67): 44945570212853
fib(68): 72723460248141
fib(69): 117669030460994
fib(70): 190392490709135
fib(71): 308061521170129
fib(72): 498454011879264
fib(73): 806515533049393
fib(74): 1304969544928657
fib(75): 2111485077978050
fib(76): 3416454622906707
fib(77): 5527939700884757
fib(78): 8944394323791464
fib(79): 14472334024676221
fib(80): 23416728348467685
fib(81): 37889062373143906
fib(82): 61305790721611591
fib(83): 99194853094755497
fib(84): 160500643816367088
fib(85): 259695496911122585
fib(86): 420196140727489673
fib(87): 679891637638612258
fib(88): 1100087778366101931
fib(89): 1779979416004714189
fib(90): 2880067194370816120
fib(91): 4660046610375530309
fib(92): 7540113804746346429
fib(93): 12200160415121876738
fib(94): 19740274219868223167
fib(95): 31940434634990099905
fib(96): 51680708854858323072
fib(97): 83621143489848422977
fib(98): 135301852344706746049
fib(99): 218922995834555169026
fib(100): 354224848179261915075
fib(12345): 400805695072240470970514993214065752192289440772063392234116121035966330621821050108284603033716632771086638046166577665205834362327397885009536790892524821512145173749742393351263429067658996935575930135482780507243981402150702461932551227590433713277255705297537428017957026536279252053237729028633507123483103210846617774763936154673522664591736081039709294423865668046925492747583953758325850613548914282578320544573036249175099094644435323970587790740267131607004023987409385716162460955707793257532112771932704816713519196128834470721836094265012918046427449156654067195071358955104097973710150920536847877434256779886729555691213282504703193401739340461924048504866698176130757935914248753973087073009601101912877383634628929467608983980664185363370286731771712542583041365328648124549323878806758395652340861186334027392307091079257180835672989798524084534677252369585918458720952520972332496025465803523315515681084895362126005441170936820059518262349022456888758938672920855739736423917065122816343192172271301981007636070751378441363091187289522144227851382197807194256392294919912037019476582418451273767976783751999133072126657949249799858935787018952232743400610036315564885371356712960608966755186612620425868892621106627825137425386831657368826398245606147944273998498356443362170133234924531673939303668042878258282104212769625245680321344034442698232414181912301904509531018692483863038992377680591406376081935756597411807864832452421993121459549055042253305545594009110753730302061881025182053074077930494574304284381890534053065639084253641881363463311184024281835265103884539012874542416238100890688593076189105555658375552988619203325356676814545718066196038345684671830102920209857682912971565838896011294918349088792184108318689299230788355618638040186790724351073650210514429114905535411044888774713860041341593318365792673354888566799196442017231870631867558530906286613228902689695061557951752309687806567573290910909535395758148994377158637050112347651517847188123790794231572729345617619677555583207012253101701328971768827861922408064379891201972881554890367344239218306050355964382953279316318309272212482218232309006973312977359562553184608144571713073802285675503209229581312057259729362382786183100343961484090866057560474044189870633912200595478051573769889968342203512550302655117491740823696686983281784153050366346823513213598551985596176977626982962058849363351794302206703907577970065793839511591930741441079234179943480206539767561244271325923343752071038968002157889912694947204003637791271084190929058369801531787887444598295425899927970
팁 :
- 그는
test_seq()똑똑하지 않고 2 개의 입력 숫자 사이에 캐시를 재사용하지 않았습니다.
실제로는 단일 호출로fib_gmp()충분하지만 각 단계에서 에 agmp_printf()를 추가fib_gmp_next()하고 i를 제공 하면 충분fib_gmp_next()합니다.
아무튼 데모 용입니다.
3500 번째 피보나치 수를 계산하는 소스 코드가 c에 있습니다.
http://codingloverlavi.blogspot.in/2013/04/fibonacci-series.html
C의 소스 코드 :-
#include<stdio.h>
#include<conio.h>
#define max 2000
int arr1[max],arr2[max],arr3[max];
void fun(void);
int main()
{
int num,i,j,tag=0;
clrscr();
for(i=0;i<max;i++)
arr1[i]=arr2[i]=arr3[i]=0;
arr2[max-1]=1;
printf("ENTER THE TERM : ");
scanf("%d",&num);
for(i=0;i<num;i++)
{
fun();
if(i==num-3)
break;
for(j=0;j<max;j++)
arr1[j]=arr2[j];
for(j=0;j<max;j++)
arr2[j]=arr3[j];
}
for(i=0;i<max;i++)
{
if(tag||arr3[i])
{
tag=1;
printf("%d",arr3[i]);
}
}
getch();
return 1;
}
void fun(void)
{
int i,temp;
for(i=0;i<max;i++)
arr3[i]=arr1[i]+arr2[i];
for(i=max-1;i>0;i--)
{
if(arr3[i]>9)
{
temp=arr3[i];
arr3[i]%=10;
arr3[i-1]+=(temp/10);
}
}
}
여기에 짧은 파이썬 코드가 있으며 최대 7 자리까지 잘 작동합니다. 3 요소 배열 만 필요
def fibo(n):
i=3
l=[0,1,1]
if n>2:
while i<=n:
l[i%3]= l[(i-1) % 3] + l[(i-2) % 3]
i+=1
return l[n%3]
파이썬에서 더 우아한 솔루션
def fib(n):
if n == 0:
return 0
a, b = 0, 1
for i in range(2, n+1):
a, b = b, a+b
return b
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
const long long int MAX = 10000000;
// Create an array for memoization
long long int f[MAX] = {0};
// Returns n'th fuibonacci number using table f[]
long long int fib(int n)
{
// Base cases
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
if (f[n])
return f[n];
long long int k = (n & 1)? (n+1)/2 : n/2;
f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) %MOD
: ((2*fib(k-1) + fib(k))*fib(k))%MOD;
return f[n];
}
int main()
{
long long int n = 1000000;
printf("%lld ", fib(n));
return 0;
}
시간 복잡도 : 모든 재귀 호출에서 문제를 절반으로 나눌 때 O (Log n).
피보나치 수 계산 (Haskell 사용) :
버전 1 : 정의를 코드로 직접 변환 (매우 느린 버전) :
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n =
fib (n - 1) + fib (n - 2)
버전 2 : F_ {n-1} 및 F_ {n-2} (빠른 버전) 을 계산하기 위해 수행 한 작업을 사용합니다 .
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
인덱스가 fibs !! n어디에 있는지 간단히 수행하여 n 번째 피보나치를 얻을 수 있습니다 n.
버전 3 : 행렬 곱셈 기법 사용. (더 빠른 버전) :
-- declaring a matrix
data Matrix = Matrix
( (Integer, Integer)
, (Integer, Integer)
)
deriving (Show, Eq)
-- creating it an instance of Num
-- so that if we implement (*) we get (^) for free
instance Num Matrix where
(*) = mMult
-- don't need these
(+) = undefined
negate = undefined
fromInteger = undefined
abs = undefined
signum = undefined
-- 2-d matrix multiplication
mMult :: Matrix -> Matrix -> Matrix
mMult (Matrix ((a11, a12), (a21, a22))) (Matrix ((b11, b12), (b21, b22))) =
Matrix
( (a11 * b11 + a12 * b21, a11 * b12 + a12 * b22)
, (a21 * b11 + a22 * b21, a21 * b12 + a22 * b22)
)
-- base matrix for generating fibonacci
fibBase :: Matrix
fibBase =
Matrix ((1,1), (1,0))
-- get the large fibonacci numbers
fastFib :: Int -> Integer
fastFib n =
let
getNth (Matrix ((_, a12), _)) = a12
in
getNth (fibBase ^ n)
이산 수학에 대한 지식이 있으면 일정한 시간 O (1)에서 모든 피보나치 수를 찾을 수 있습니다. Linear Homogeneous Recurrence Relation 이라는 것이 있습니다 .
피보나치 수열이 유명한 예입니다.
n 번째 피보나치 수를 찾으려면 다음을 찾아야합니다.
우리는 알고 있습니다
어디
그러면 특성 방정식은 다음과 같습니다.
특성 방정식의 근을 찾아 첫 방정식을 대입 한 후
마지막으로 알파 1과 알파 2의 값을 찾아야합니다.
이제이 방정식을 사용하여 O (1)에서 피보나치 수를 찾을 수 있습니다.
C #을 사용하는 경우 Lync 및 BigInteger를 살펴보십시오. 나는 이것을 1000000 (처음 1000000을 건너 뛰기 때문에 실제로 1000001)으로 시도했으며 2 분 (00 : 01 : 19.5765) 미만이었습니다.
public static IEnumerable<BigInteger> Fibonacci()
{
BigInteger i = 0;
BigInteger j = 1;
while (true)
{
BigInteger fib = i + j;
i = j;
j = fib;
yield return fib;
}
}
public static string BiggerFib()
{
BigInteger fib = Fibonacci().Skip(1000000).First();
return fib.ToString();
}
이 JavaScript 구현은 nthFibonacci (1200)를 문제없이 처리합니다.
var nthFibonacci = function(n) {
var arr = [0, 1];
for (; n > 1; n--) {
arr.push(arr.shift() + arr[0])
}
return arr.pop();
};
console.log(nthFibonacci(1200)); // 2.7269884455406272e+250
대화 형 재귀 방식보다 빠른 피보나치를 계산하는 작은 코드를 작성했습니다.
나는 그것을 다시 계산하는 대신 마지막 피보나치 수를 얻기 위해 암기 기술을 사용하고 있습니다.
public class FabSeries {
private static Map<BigInteger, BigInteger> memo = new TreeMap<>();
public static BigInteger fabMemorizingTech(BigInteger n) {
BigInteger ret;
if (memo.containsKey(n))
return memo.get(n);
else {
if (n.compareTo(BigInteger.valueOf(2)) <= 0)
ret = BigInteger.valueOf(1);
else
ret = fabMemorizingTech(n.subtract(BigInteger.valueOf(1))).add(
fabMemorizingTech(n.subtract(BigInteger.valueOf(2))));
memo.put(n, ret);
return ret;
}
}
public static BigInteger fabWithoutMemorizingTech(BigInteger n) {
BigInteger ret;
if (n.compareTo(BigInteger.valueOf(2)) <= 0)
ret = BigInteger.valueOf(1);
else
ret = fabWithoutMemorizingTech(n.subtract(BigInteger.valueOf(1))).add(
fabWithoutMemorizingTech(n.subtract(BigInteger.valueOf(2))));
return ret;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter Number");
BigInteger num = scanner.nextBigInteger();
// Try with memorizing technique
Long preTime = new Date().getTime();
System.out.println("Stats with memorizing technique ");
System.out.println("Fibonacci Value : " + fabMemorizingTech(num) + " ");
System.out.println("Time Taken : " + (new Date().getTime() - preTime));
System.out.println("Memory Map: " + memo);
// Try without memorizing technique.. This is not responsive for large
// value .. can 50 or so..
preTime = new Date().getTime();
System.out.println("Stats with memorizing technique ");
System.out.println("Fibonacci Value : " + fabWithoutMemorizingTech(num) + " ");
System.out.println("Time Taken : " + (new Date().getTime() - preTime));
}
}
번호 입력
40
암기 기법이있는 통계
피보나치 값 : 102334155
소요 시간 : 5
메모리 맵 : {1 = 1, 2 = 1, 3 = 2, 4 = 3, 5 = 5, 6 = 8, 7 = 13, 8 = 21, 9 = 34, 10 = 55, 11 = 89, 12 = 144, 13 = 233, 14 = 377, 15 = 610, 16 = 987, 17 = 1597, 18 = 2584, 19 = 4181, 20 = 6765, 21 = 10946, 22 = 17711, 23 = 28657, 24 = 46368, 25 = 75025, 26 = 121393, 27 = 196418, 28 = 317811, 29 = 514229, 30 = 832040, 31 = 1346269, 32 = 2178309, 33 = 3524578, 34 = 5702887, 35 = 9227465, 36 = 14930352, 37 = 24157817, 38 = 39088169, 39 = 63245986, 40 = 102334155}
테크닉을 암기하지 않는 통계
피보나치 값 : 102334155
소요 시간 : 11558
나는 프로그램을했다. 값을 계산하는 데 시간이 오래 걸리지 않지만 표시 할 수있는 최대 항은 1477 번째입니다 (double의 최대 범위 때문에). 결과가 거의 즉시 나타납니다. 시리즈는 0부터 시작합니다. 개선이 필요한 부분이 있으면 언제든지 편집 해주세요.
#include<iostream>
using namespace std;
void fibseries(long int n)
{
long double x=0;
double y=1;
for (long int i=1;i<=n;i++)
{
if(i%2==1)
{
if(i==n)
{
cout<<x<<" ";
}
x=x+y;
}
else
{
if(i==n)
{
cout<<x<<" ";
}
y=x+y;
}
}
}
main()
{
long int n=0;
cout<<"The number of terms ";
cin>>n;
fibseries(n);
return 0;
}
정보를 위해 :
The following formula seems working fine but depends on the preciseness of the number used-
[((1+√5)/2)ⁿ- ((1-√5)/2)ⁿ]/√5
Note: Don't round-off the figures for more preciseness.
JS sample code:
let n = 74,
const sqrt5 = Math.sqrt(5);
fibNum = Math.round((Math.pow(((1+sqrt5)/2),n)- Math.pow(((1-sqrt5)/2),n))/sqrt5) ;
As per the Number Precision, it'll work fine on chrome console upto n=74
Open for any suggestion!
Another solution
Follows the steps-
- make a set of index and value and pervious value of fibonacci series at certain intervals. e.g each 50 or each 100.
- Find the nearest lower index of the desired number
nfrom the set of step-1. - Proceed in traditional way by adding the previous value in each subsequent one.
Note: It doesn't seems good, but if you really concern about time complexity, this solution is a hit. The max iterations will be equal to the interval as per step-1.
Conclusion:
- Fibonacci numbers are strongly related to the golden ratio: Binet's formula expresses the nth Fibonacci number in terms of n and the golden ratio, and implies that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as n increases.
- In pure mathematics Binet's formula will give you the exact result every time. In real world computing there will be errors as the precision needed exceeds the precision used. Every real solution has the same problem with exceeding precision at some point.
참고 URL : https://stackoverflow.com/questions/14661633/finding-out-nth-fibonacci-number-for-very-large-n
'Programing' 카테고리의 다른 글
| Golang의 웹 서버가 동시 요청을 처리하지 않는 이유는 무엇입니까? (0) | 2020.12.12 |
|---|---|
| Git 파일을 커밋하려고하지만 :: 치명적 : LF가 CRLF로 대체됩니다. (0) | 2020.12.12 |
| 브라우저 닫기 이벤트 감지 시도 (0) | 2020.12.11 |
| 차이점 ?? (0) | 2020.12.11 |
| 마이그레이션을 사용하여 laravel에서 열의 이름을 어떻게 바꿀 수 있습니까? (0) | 2020.12.11 |