(번역) Adding Extremely Large Numbers and Extra Long Factorials.

[번역] Adding Extremely Large Numbers and Extra Long Factorials.

원문 Link

자바스크립트에서 우리는 53 bits까지만 숫자를 저장할 수 있습니다. 바꿔 말하면, 가장 안전하게 저장 가능한 큰 수는 9007199254740991입니다. Number.MAXSAFEINTEGER 참고

이러한 자바스크립트의 성질은 매우 큰 숫자를 연산하거나 factorial과 같은 수를 연산해야 할 때 문제가 발생합니다. 저 또한 큰 수의 Factorial을 계산할 때 이 같은 문제를 겪었습니다. Extra Long Factorial Problem

그러면 어떻게 이 문제를 해결할 수 있을까요? 먼저 문제를 세부적으로 살펴봅시다. factorial을 구하기 위해서 우리는 어떻게 하면 매우 큰 수를 자바스크립트를 이용해 연산할 수 있을지 알아내야 합니다. 그리고 그렇게 하기 위해서는 우선, 어떻게 매우 큰 수의 덧셈을 할 수 있을지 파악해야 합니다.

Step 1 : Addition

덧셈을 하기 위해서, 초등학교 때 배웠던 덧셈을 하는 방식을 사용해야합니다. 우리는 모두 이러한 기본적인 덧셈을 할 수 있습니다. 하지만, 문제가 되는 부분은 이러한 알고리즘을 코드로 구현해야 한다는 것입니다.

우선, 큰 숫자를 자바스크립트가 다루지 못 하기 때문에, 우리는 문제를 피하기 위해 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'이 도출됨.

설명 :

  1. 인자로 전달받은 문자 타입의 수를 변수에 저장함.
  2. 두 문자열 중 긴 문자열이 덧셈 연산에서 위로 올 수 있도록 어떠한 문자열이 더 긴지 파악해야 함.
  3. 두 문자열의 각 문자를 돌며 자릿수마다 덧셈을 하고, 올림 할 수는 따로 저장함.
  4. 덧셈을 한 수의 맨 오른쪽 수를 sum의 문자열에 합침.
  5. 함수에 전달받은 인자의 맨 왼쪽의 수를 더할 때는, 다음 연산할 수가 없기 때문에 올림 할 수를 함께 결과에 포함 시켜야 함.

Github Link

위의 반복문이 완료되면, 두 수의 합을 수의 길이에 상관없이 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를 구현했습니다. 이후 큰 숫자를 처리하기 위한 코드를 추가했습니다. 추가된 부분에 대한 설명은 아래와 같습니다.

  1. isSafeInterger() 메소드로 일반적인 숫자의 곱을 했을 때 안전하게 사용 가능한 숫자가 도출되는지 확인합니다. 문제가 없다면 숫자의 곱을 진행합니다.
  2. 그렇지 않다면, 우리가 이전에 작성한 add 함수를 호출해 곱셈을 구현해야 합니다. (곱셈은 단순히 덧셈의 반복이기 때문입니다. 덧셈을 반복함으로써 어떠한 수의 곱을 값으로 얻을 수 있습니다.)
  3. 결과값을 반환합니다.

GitHub Link: https://github.com/niinpatel/extra-long-factorials

여기까지입니다. 꽤 까다로운 알고리즘이지만, 즐겁게 읽으셨으면 좋겠습니다.