피보나치 문제 풀 때 왜 1234567로 나눈 나머지를 사용해야 하는가

프로그레머스 Lv.2 피보나치 수 문제다. 

피보나치 n번째 자리 수를 1234567로 나눈 나머지 값을 구하라는 문제였다 (n은 2 이상).

 

왜 나누어야 하는걸까?

힌트를 보니 n이 커질수록 리턴해야 하는 값도 커지고 47번째 피보나치 수는 2,971,215,073이라고 한다. 이 수가 32비트 정수(ex.int)의 범위를 넘고, 100,000번째 피보나치 수는 자릿수가 20,000을 넘겨 64비트 정수(ex.long)의 범위를 넘어 오버플로우가 난다고 되어있다. 그렇기 때문에 1234567로 나누어야 하고 사용법은 아래와 같다.

F(n) % m 
= (F(n-1) + F(n-2)) % m
= (F(n-1) % m + F(n-2) % m) % m

 

무슨 말인지 대충은 알겠는데 정확하게 모르겠는 사람도 있을거다. 

 

일단 C언어로 생각해보면 이해가 간다. int 자료형은 4바이트를 지원하고 64비트 CPU 환경에서는 -2,147,483,648 ~ 2,147,483,647 사이의 정수를 사용할 수 있다. 확실히 47번째 피보나치 수는 int 자료형의 최대값보다 크다. 

또 long 의 경우는 OS에 따라 4 또는 8바이트를 지원한다. 이 블로그에 자세히 설명되어있다.

 

하지만 난 javascript로 문제를 풀고 있었는데 이 경우는 어떨까. 

js의 number가 지원하는 범위 아래와 같이 알 수 있고 이런 값이 나오는 이유는 js가 double-precision 64-bit 형식으로 수를 표현하기 때문이라고 한다 (출처: https://80000coding.oopy.io/5226d086-ed18-482c-a58b-fe65f040a82e). 설명이 아주 자세하게 되어있는 게시물이다. 

console.log(Number.MAX_VALUE); //1.7976931348623157e+308 (최댓값)
console.log(Number.MIN_VALUE); //5e-324 (최솟값)

 

MAX_SAFE_INTEGER로 찍어보면 9007199254740991의 값이 나온다고 한다.

js는 -9007199254740991 ~ 9007199254740991 범위의 숫자를 사용할 수 있다.

 

핵심은 피보나치 값이 컴퓨터가 읽을 수 있는 최대 수를 넘어버린다는 것.

 

왜 1234567인가

사실 위 내용은 딱 보는 순간 대충 감 잡았었고 진짜 궁금했던 부분은 이것이다. 문제에서 1234567로 나눈 나머지 값으로 저장하라고 했는데 왜 1234567인가. 다른 숫자는 안 되는가.

근데 이건 그냥 임의의 수인듯 하다. 다른 수도 상관 없는. 

chatGPT의 말을 빌리자면 그냥 '오버플로를 방지할 수 있을 만큼 크지만 계산 효율성이 있을 만큼 작은 소수' 인 것이다. 

뭔가 의미가 있는 줄 알았는데 다소 허무하게도 프로그레머스에서 정한 수일 뿐인 듯.