September 11th 2018
자바스크립트에서 우리는 53 bits까지만 숫자를 저장할 수 있습니다. 바꿔 말하면, 가장 안전하게 저장 가능한 큰 수는 9007199254740991입니다. Number.MAXSAFEINTEGER 참고
이러한 자바스크립트의 성질은 매우 큰 숫자를 연산하거나 factorial과 같은 수를 연산해야 할 때 문제가 발생합니다. 저 또한 큰 수의 Factorial을 계산할 때 이 같은 문제를 겪었습니다. Extra Long Factorial Problem
그러면 어떻게 이 문제를 해결할 수 있을까요? 먼저 문제를 세부적으로 살펴봅시다. factorial을 구하기 위해서 우리는 어떻게 하면 매우 큰 수를 자바스크립트를 이용해 연산할 수 있을지 알아내야 합니다. 그리고 그렇게 하기 위해서는 우선, 어떻게 매우 큰 수의 덧셈을 할 수 있을지 파악해야 합니다.
덧셈을 하기 위해서, 초등학교 때 배웠던 덧셈을 하는 방식을 사용해야합니다. 우리는 모두 이러한 기본적인 덧셈을 할 수 있습니다. 하지만, 문제가 되는 부분은 이러한 알고리즘을 코드로 구현해야 한다는 것입니다.
우선, 큰 숫자를 자바스크립트가 다루지 못 하기 때문에, 우리는 문제를 피하기 위해 String 타입으로 숫자를 저장해야 합니다. 덧셈에 대한 합 또한 string으로 반환을 해야 합니다. 아래와 같이 덧셈을 구현할 수 있습니다.
/**
* 큰 수를 다루기 위해서, 숫자는 string으로 주어져야 합니다.
* example -
* add("15", "15"); // returns "30"
*/
function add(str1, str2) {
let sum = ''; // 최종 값은 여기에 저장됨.
// 아래 프로그램에서 많이 사용하는 것을 변수로 묶음.
let str1Length = str1.length;
let str2Length = str2.length;
// string 중 길이가 긴 쪽이 str1이 되도록 설정함.
if (str2Length > str1Length) {
let temp = str1;
str2 = str1;
str1 = temp;
}
let carry = 0; // 덧셈 후 올림할 숫자를 저장할 변수.
let a;
let b;
let temp;
let digitSum;
for (let i = 0; i < str1Length; i++) {
a = parseInt(str1.charAt(str1Length - 1 - i)); // str1의 i 번째 숫자(맨 처음은 1의 자리 숫자)의 문자를 숫자로 변경함.
b = parseInt(str2.charAt(str2Length - 1 - i)); // str2의 i 번째 숫자(맨 처음은 1의 자리 숫자)의 문자를 숫자로 변경함.
b = b ? b : 0; // b가 숫자가 아닌 경우 b = 0으로 설정함. str2의 길이가 str1보다 작은 경우를 대비함.
temp = (carry + a + b).toString(); // a + b + carry를 더한 후 temp에 저장함.
digitSum = temp.charAt(temp.length - 1); //
carry = parseInt(temp.substr(0, temp.length - 1)); // carry 와 digitSum을 구분함. 두 수의 덧셈이 10을 넘긴 경우 10의 자리 수를 carry로 할당함.
carry = carry ? carry : 0; // carry가 숫자가 아닌 경우, 0으로 설정함.
sum = i === str1Length - 1 ? temp + sum : digitSum + sum; // digitSum과 sum을 합침. 마지막 연산의 경우 carry까지 합치기 위해서 temp와 sum을 합침.
}
return sum; // 결과값을 반환함.
}
console.log(add('2750', '3750')); // '6500'이 도출됨.
위의 반복문이 완료되면, 두 수의 합을 수의 길이에 상관없이 string으로 반환받을 수 있습니다. String은 저장한 문자 수의 제한이 없기 때문입니다.
이제 위의 함수를 통해 우리는 큰 수의 덧셈을 할 수 있기 때문에, 이번에는 매우 큰 수의 factorial을 구해보도록 하겠습니다.
Code Snippet
function extraLongFactorials(n) {
let fact = 1;
for (let i = 2; i <= n; i++) {
if (Number.isSafeInteger(fact * i)) {
fact = fact * i;
} else {
//fact = fact + fact + .. i times
let factxi = '0'; // 큰 수의 factorial 곱을 저장할 변수
for (let j = 0; j < i; j++) {
factxi = add(factxi, fact.toString());
}
fact = factxi; // 다음 loop를 돌기 전 fact를 저장함.
}
}
return fact;
}
console.log(extraLongFactorials(25)); // prints 15511210043330985984000000
console.log(extraLongFactorials(34)); // prints 295232799039604140847618609643520000000
먼저 일반적인 factorial number를 구하는 loop를 구현했습니다. 이후 큰 숫자를 처리하기 위한 코드를 추가했습니다. 추가된 부분에 대한 설명은 아래와 같습니다.
GitHub Link: https://github.com/niinpatel/extra-long-factorials
여기까지입니다. 꽤 까다로운 알고리즘이지만, 즐겁게 읽으셨으면 좋겠습니다.