[Javascript] - Big Integer

Big Integer (큰 정수)

 

- 자바스크립트에는 64비트 정수가 없다

 

• int64 형은 최대 9223372036854775807 까지의 정수를 담을 수 있는데, 자바스크립트의 Number.MAX_SAFE_INTEGER 범위보다 세자리나 큼
• 자바스크립트의 숫자형은 한개라 새로운 숫자형을 추가하는데에도 문제가 있음 -> 단순성을 잃게되고, 잠재적으로 다른 버그를 초래할 가능성이 커짐
• 만약 64비트 정수형을 추가하더라도 이후 72비트, 96비트, 128비트 등등을 대응할 필요는 없을까? 라는 논쟁이 이어질 수 있습니다.

- 큰 정수를 언어에 추가하는 대신 라이브러리화 하는 것이 적절해 보이며 해당 부분을 이번 내용에서 보도록 하겠습니다.

 

• 큰 정수는 배열 형태로 저장할 것입니다. (크기가 자유롭기에)
• 배열의 각 요소는 큰 정수의 일부 비트에 해당하는 값을 가집니다.
• 배열의 각 요소별로 사용할 비트수에 대해 가장 큰 값은 안전한 양수 범위를 표현할 수 있는 53개지만, 비트 단위 연산자 및 곱하기나 나누기를 고려하면 24비트가 적절합니다.
• 부호를 표시할 수 있는 크기 표현 방식으로 배열의 0번 요소는 숫자의 부호를 나타내며 "+" 또는 "-" / 아래 예시)

9000000000000000000
  = ["+", 8650752, 7098594, 31974]
  = 8650725 + 7098594 * 16777216 ** 1 + 31974 * 16777216 ** 2 // 16777216 = Math.pow(2, 24)

 

- 위의 설계 부분을 바탕으로 큰 정수 라이브러리를 만들어 보겠습니다. 코드의 양이 꽤 길지만 충분한 주석을 추가했습니다.

 

// 상수 정의
const radix = 16777216; // Math.pow(2, 24);
const radix_squared = radix * radix;
const log2_radix = 24;
const plus = "+";
const minus = "-";
const sign = 0;
const least = 1;

const last = (array) => {
  return array[array.length - 1];
};

const next_to_last(array) => {
  return array[array.length - 2];
}

// 코드 가독성을 위해 추가 (꼭 필요하진 않음)
const zero = Object.freeze([plus]);
const one = Object.freeze([plus, 1]);
const two = Object.freeze([plus, 2]);
const ten = Object.freeze([plus, 10]);
const negative_one = Object.freeze([minus, 1]);

// 큰정수인지 판별하는 술어 함수 (= true or false 를 반환하는 함수)
const is_big_integer = (big) => {
  return Array.isArray(big) && (big[sign] === plus || big[sign] === minus);
};

// 부호가 "-" 인지 판별하는 술어 함수
const is_negative = (big) => {
  return Array.isArray(big) && big[sign] === minus;
}

// 부호가 "+" 인지 판별하는 술어 함수
const is_positive = (big) => {
  return Array.isArray(big) && big[sign] === plus;
};

// 0인지 판별하는 술어 함수
const is_zero = (big) => {
  return !Array.isArray(big) || big.length < 2;
};

// 배열의 마지막 요소가 0인 경우 제거하는 함수 (윗자리에 있는 0은 필요없는 숫자이므로)
const mint = (proto_big_integer) => {
  while(last[proto_big_integer) === 0) {
    proto_big_integer.length -= 1;
  }
  
  if (proto_big_integer.length <= 1) {
    return zero;
  }
  
  if (proto_big_integer[sign] === plus) {
    if (proto_big_integer.length === 2) {
      if (proto_big_integer[least] === 1) {
        return one;
      }
      if (proto_big_integer[least] === 2) {
        return two;
      }
      if (proto_big_integer[least] === 10) {
        return ten;
      }
    }
  } else if (proto_big_integer.length === 2) {
    if (proto_big_integer[least] === 1) {
      return nagative_one;
    }
  }
  return Object.freeze(proto_big_integer); // 더 이상 바꿀 것이 없을 시 동결
};

// 부호 바꾸기 함수
const neg = (big) => {
  if (is_zero(big)) return zero;

  let negation = big.slice();
  negation[sign] = (is_negative(big) ? plus : minus);
  
  return mint(negation);
};

// 절댓값 구하는 함수
const abs = (big) => {
  return (is_zero(big) ? zero : (is_negative(big) ? neg(big) : big));
};

// 부호 추출하는 함수
const signum = (big) => {
  return (is_zero(big) ? zero : (is_negative(big) ? negative_one : one));
};

// 두 큰 정수가 동일한 값을 가지는지 확인하는 함수
const eq = (comparahend, comparator) => {
  return comparahend === comparator || (
    comparahend.length === comparator.length && comparahend.every((element, i) => element === comparator[i])
  );
};

// 큰 정수의 절댓값이 다른 큰 정수 절댓값보다 작은지 판별하는 함수
const abs_lt = (comparahend, comparator) => {
  return (
    comparahend.length === comparator.length ? // 길이가 같으면 모든 배열 원소를 비교
      comparahend.reduce((reduction, element, i) => {
        if (i !== sign) {
          const other = comparator[i];
          if (element !== other) {
            return element < other;
          }
        }
        return reduction;
      }, false)
      :
      comparahend.length < comparator.length // 길이가 더 작으면 절댓값이 작은 것
  );
};

// 부호를 포함한 값이 다른 정수값보다 작은지 판별하는 함수
const lt = (comparahend, comparator) => {
  return (
    comparahend[sign] !== comparator[sign] ?
      is_negative(comparahend)
      :
      (
        is_negative(comparahend) ? abs_lt(comparator, comparahend) : abs_lt(comparahend, comparator)
      )
  );
};

// lt 함수를 활용해 다른 비교함수를 만듬, 이름으로 함수의 기능 파악 가능
const ge = (a, b) => !lt(a, b);
const gt = (a, b) => lt(b, a);
const le = (a, b) => !lt(b, a);

// and 비트 연산 함수
const and = (a, b) => {
  if (a.length < b.length) {
    [a, b] = [b, a]; // 더 짧은 배열을 a 로
  }
  return mint(a.map((element, i) => {
    return (i === sign ? plus : element & b[i]);
  }));
};

// or 비트 연산 함수
const or = (a, b) => {
  if (a.length < b.length) {
    [a, b] = [b, a]; // 더 긴 배열을 a 로
  }
  return mint(a.map((element, i) => {
    return (i === sign ? plus : element | (b[i] || 0));
  }));
};

// xor 비트 연산 함수
const xor = (a, b) => {
  if (a.length < b.length) {
    [a, b] = [b, a]; // 더 긴 배열을 a 로
  }
  return mint(a.map((element, i) => {
    return (i === sign ? plus : element ^ (b[i] || 0));
  }));
};

// 숫자와 큰 정수 값을 쉽게 처리하기 위한 함수
const int = (big) => {
  let result;
  
  if (typeof big === "number") {
    if (Number.isSafeInteger(big)) {
      return big;
    }
  } else if (is_big_integer(big)) {
    if (big.length < 2) {
      return 0;
    }
    if (big.length === 2) {
      return (is_negative(big) ? -big[least] : big[least]);
    }
    if (big.length === 3) {
      result = big[least + 1] * radix + big[least];
      return (is_negative(big) ? -result : result);
    }
    if (big.length === 4) {
      result = (big[least + 2] * radix_squared + big[least + 1] * radix + big[least]);
      if (Number.isSafeInteger(result)) {
        return (is_negative(big) ? -result : result);
      }
    }
  }
};

// 최하위 비트를 삭제해 숫자의 크기를 줄이는 함수
const shift_down = (big, places) => {
  if (is_zero(big)) return zero;
  
  places = int(places);
  
  if (Number.isSafeInteger(places)) {
    if (places === 0) return abs(big);
    if (places < 0) return shift_up(big, -places);
    
    let skip = Math.floor(places / log2_radix);
    places -= skip * log2_radix;
    
    if (skip + 1 >= big.length) return zero;
    
    big = (skip > 0 ? mint(zero.concat(big.slice(skip + 1))) : big);
    
    if (places === 0) return big;
    
    return mint(big.map((element, i) => {
      if (i === sign) return plus;
      
      return ((radix - 1) & ((element >> places) | ((big[i + 1] || 0) << (log2_radix - places))));
    }));
  }
};

// 최하위 위치에 0을 넣어 숫자를 증가시키는 함수
const shift_up = (big, places) => {
  if (is_zero(big)) return zero;
  
  places = int(places);
  
  if (Number.isSafeInteger(places)) {
    if (places === 0) return abs(big);
    
    if (places < 0) return shift_down(big, -places);
    
    let blanks  = Math.floor(places / log2_radix);
    let result = new Array(blanks + 1).fill(0);
    
    result[sign] = plus;
    places -= blanks * log2_radix;
    
    if (places === 0) return mint(result.concat(big.slice(least)));
    
    let carry = big.reduce((accumulator, element, i) => {
      if (i === sign) return 0;
      
      result.push(((element << places | accumulator) & (radix - 1));
      
      return element >> (log2_radix - places);
    }, 0);
    
    if (carry > 0) result.push(carry);
    
    return mint(result);
  }
};

// 값이 1인 비트를 지정한 갯수만큼 가진 큰 정수를 만드는 함수
const mask = (bits) => {
  bits = int(bits);
  
  if (bits !== undefined && bits >= 0) {
    let mega = Math.floor(bits / log2_radix);
    let result = new Array(mega + 1).fill(radix - 1);
    result[sign] = plus;
    let leftover = bits - (mega * log2_radix);
    
    if (leftover > 0) result.push((1 << leftover) - 1);
    
    return mint(result);
  }
};

// 모든 비트의 보수를 만드는 not 함수
const not = (a, bits) => xor(a, mask(i));

// 임의의 큰 정수를 생성하는 함수
const random = (bits, random = Math.random) => { // 보안을 신경 써야 한다면 Math.random 보다 더 강력한 난수 생성기를 인잘 전달
  const ones = mask(bits);
  
  if (ones !== undefined) {
    return mint(ones.map((element, i) => {
      if (i === sign) return plus;
      
      const b = random();
      
      return ((b * radix_squared) ^ (b * radix)) & element;
    }));
  }
};

// 더하기
const add = (augend, addend) => {
  if (is_zero(augend)) return addend;
  if (is_zero(addend)) return augend;
  if (augend[sign] !== addend[sign]) return sub(augend, neg(addend)); // 부호가 다르면 뺄셈
  
  if (augend.length < addend.length) [addend, augend] = [augend, addend];
  
  let carry = 0;
  let result = augend.map((element, i) => {
    if (i !== sign) {
      element += (addend[i] || 0) + carry;
      if (element >= radix) {
        carry = 1;
        element -= radix;
      } else {
        carry = 0;
      }
    }
    return element;
  }); // 더 긴 정수쪽에 map 을 쓴 다음 || 연산자를 통해 짧은 쪽에 존재하지 않는 요소에 0을 적용해 덧셈
  
  if (carry > 0) result.push(carry);
  
  return mint(result);
};

// 뺄셈
const sub = (minuend, subtrahend) => {
  if (is_zero(subtrahend)) return minuend;
  if (is_zero(minuend)) return neg(subtrahend);
  
  let minuend_sign = minuend[sign];
  
  if (minuend_sign !== subtrahend[sign]) return add(minuend, neg(subtrahend)); // 부호가 다르면 더하기
  
  // 큰 수에서 작은 수를 뺌
  if (abs_lt(minuend, subtrahend)) {
    [subtrahend, minuend] = [minuend, subtrahend];
    minuend_sign = (minuend_sign === minus ? plus : minus);
  }
  let borrow = 0;
  
  return mint(minuend.map((element, i) => {
    if (i === sign) return minuend_sign;
    
    let diff = element - ((subtrahend[i] || 0) + borrow);
    
    if (diff < 0) {
      diff += 16777216;
      borrow = 1;
    } else {
      borrow = 0;
    }
    return diff;
  }));
};

// 곱셈 -> 각 요소의 곱은 48비트가 될 수 있지만 24비트밖에 담을 수 없으므로 초과할 시 자리올림수 처리
const mul = (multiplicand, multiplier) => {
  if (is_zero(multiplicand) || is_zero(multiplier)) return zero;
  
  let result = [mutiplicand[sign] === multiplier[sign] ? plus : minus]; // 두 수의 부호가 같으면 결과는 양수
  
  // 자리올림수를 계속 전달하면서 multiplicand 의 각 요소와 multiplier 의 각 요소를 곱함
  multiplicand.forEach((multiplicand_e, i) => {
    if (i !== sign) {
      let carry = 0;
      multiplier.forEach((multiplier_e, j) => {
        if (j !== sign) {
          let at = i + j - 1;
          let product = (multiplicand_e * multiplier_e) + (result[at]) || 0) + carry);
          result[at] = product & 16777215;
          carry = Math.floor(product / radix);
        }
      });
      if (carry > 0) result[i + multiplier.length - 1] = carry;
    }
  });
  return mint(result);
};

// 나누기 (몫과 나머지 모두 반환)
const divrem = (dividend, divisor) => {
  if (is_zero(dividend) || abs_lt(dividend, divisor)) return [zero, dividend];
  if (is_zero(divisor)) return undefined;
  
  let quotient_is_negative = dividend[sign] !== divisor[sign];
  let remainder_is_negative = dividend[sign] === minus;
  let remainder = dividend;
  dividend = abs(dividend);
  divisor = abs(divisor);
  
  /*
   * 최상위 비트가 1이 될 때까지 왼쪽으로 시프트
   * 나눠지는 수도 똑같이 길이만큼 시프트
   * 시프트 횟수를 알아내기 위해 첫번째 0을 찾음
   */
  let shift = Math.clz32(last(divisor)) - 8; // clz32 는 32비트내에서 찾는 함수라 8을 뺌 (24비트)
  
  dividend = shift_up(dividend, shift);
  divisor = shift_up(divisor, shift);
  let place = dividend.length - divisor.length;
  let dividend_prefix = last(dividend);
  let divisor_prefix = last(divisor);
  
  if (dividend_prefix < divisor_prefix) {
    dividend_prefix = (dividend_prefix * radix) + next_to_last(dividend);
  } else {
    place += 1;
  }
  divisor = shift_up(divisor, (place - 1) * 24);
  let quotient = new Array(place + 1).fill(0);
  quotient[sign] = plus;
  
  while(true) {
    let estimated = Math.floor(dividend_prefix / divisor_prefix);
    
    // 추정값이 너무 큰 경우 결과가 음수면 줄인 다음 다시 시도, 너무 작은 경우는 없음
    if (estimated > 0) {
      while(true) {
        let trial = sub(dividend, mul(divisor, [plus, estimated]));
        
        if (!is_negative(trial)) {
          dividend = trial;
          break;
        }
        estimated -= 1;
      }
    }
    
    // quotient에 저장하되 마지막 공간이면 다음으로 넘어감
    quotient[place] = estimated;
    place -= 1;
    
    if (place === 0) break;
    
    if (is_zero(dividend)) break;
    
    dividend_prefix = last(dividend) * radix + next_to_last(dividend);
    divisor = shift_down(divisor, 24);
  }
  
  quotient = mint(quotient);
  remainder = shift_down(dividend, shift);
  
  return [
    (quotient_is_negative ? neg(quotient) : quotient),
    (raminder_is_negative ? neg(reminader) : remainder)
  ];
};

// 몫만 반환하는 함수도 제공
const div = (dividend, divisor) => {
  let temp = divrem(dividend, divisor);
  
  if (temp) return temp[0];
};

// 거듭제곱 (제곱과 곱하기를 사용)
const power = (big, exponent) => {
  let exp = int(exponent);
  
  if (exp === 0) return one;
  if (is_zero(big)) return zero;
  if (exp === undefined || exp < 0) return undefined;
  
  let result = one;
  
  while(true) {
    if ((exp & 1) !== 0) result = mul(result, big);
      
    exp = Math.floor(exp / 2);
      
    if (exp < 1) break;
      
    big = mul(big, big);
  }
  return mint(result);
};

// 기약분수로 만들는 함수
const gcd = (a, b) => {
  a = abs(a);
  b = abs(b);
  
  while(!is_zero(b)) {
    let [ignore, remainder] = divrem(a, b);
    a = b;
    b = remainder;
  }
  return a;
};

/*
 * 숫자형이나 문자열을 큰 정수로 변환 후 반대로도 변환할 수 있는 함수가 필요
 * digitset 문자열은 숫자를 문자로 매핑시킬 때 사용
 * charset 객체는 반대로 문자를 숫자로 매핑
 */
const digitset = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ*~$=";
const charset = (object) => {
  digitset.split("").forEach((element, i) => {
    object[element] = i;
  });
  return Object.freeze(object);
}(Object.create(null)));

// 숫자나 문자열, 기수값을 받아 큰 정수로 반환하는 함수
const make = (value, radix_2_37) => {
  let result;
  
  if (typeof value === "string") {
    let radish;
    
    if (radix_2_37 === undefined) {
      radix_2_37 = 10;
      radish = ten;
    } else {
      if (!Number.isInteger(radix_2_37) || radix_2_37 < 2 || radix_2_37 > 37) {
        return undefined;
      }
      radish = make(radix_2_37);
    }
    
    result = zero;
    let good = false;
    let negative = false;
    
    if (value.toUpperCase().split("").every((element, i) => {
      let digit = charset[element];
      
      if (digit !== undefined && digit < radix_2_37) {
        result = add(mul(result, radish), [plus, digit]);
        good = true;
        return true;
      }
      if (i === sign) {
        if (element === plus) return true;
        if (element === minus) {
          negative = true;
          return true;
        }
      }
      return digit === "_";
    }) && good) {
      if (negative) result = neg(result);
      
      return mint(result);
    }
    return undefined;
  }
  
  if (Number.isInteger(value)) {
    let whole = Math.abs(value);
    
    result = [(value < 0 ? minus : plus)];
    
    while(whole >= radix) {
      let quotient = Math.floor(whole / radix);
      result.push(whole - (quotient * radix));
      whole = quotient;
    }
    
    if (whole > 0) result.push(whole);
    
    return mint(result);
  }
  
  if (Array.isArray(value)) return mint(value);
};

// 큰 정수 값을 자바스크립트 수로 바꿈 (값이 안전한 정수 범위내에 있을때만 유효)
const number = (big) => {
  let value = 0;
  let the_sign = 1;
  let factor = 1;

  big.forEach((element, i) => {
    if (i === 0) {
      if (element === minus) the_sign = -1;
    } else {
      value += element * factor;
      factor *= radix;
    }
  });
  return the_sign * value;
};

// 큰 정수값을 문자열로 변환하는 함수
const string = (a, radix_2_thru_37 = 10) => {
  if (is_zero(a)) return "0";
  
  radix_2_thru_37 = int(radix_2_thru_37);
  
  if (!Number.isSafeInteger(radix_2_thru_37) || radix_2_thru_37 < 2 || radix_2_thru_37 > 37) {
    return undefined;
  }
  const radish = make(radix_2_thru_37);
  const the_sign = (a[sign] === minus ? "-" : "");
  
  a = abs(a);
  let digits = [];
  
  while(!is_zero(a)) {
    let [quotient, remainder] = divrem(a, radish);
    digits.push(digitset[number(remainder)]);
    a = quotient;
  }
  digits.push(the_sign);
  return digits.reverse().join("");
};

// 32비트 정수에서 값이 1인 비트의 개수 반환
const population_32 = (int32) => {
  int32 -= (int32 >>> 1) & 0x55555555;
  
  int32 = (int32 & 0x33333333) + ((int32 >>> 2) & 0x33333333);
  
  int32 = (int32 + (int32 >>> 4) & 0x0F0F0F0F;
  
  int32 = (int32 + (int32 >>> 8) & 0x001F001F;
  
  return (int32 + (int32 >>> 16)) & 0x0000003F;
};

// 큰 정수에서 값이 1인 비트개수를 세어서 반환하는 함수 (해밍거리를 계산할 때 유용)
const population = (big) => {
  return big.reduce((reduction, element, i) => {
    return reduction + (i === sign ? 0 : population_32(element));
  }, 0);
};

// 앞쪽의 0을 제외한 전체 비트 수 세어서 반환하는 함수
const significant_bits = (big) => {
  return (
    big.length > 1
    ?
    make((big.length - 2) * log2_radix + (32 - Math.clz32(last(big))))
    :
    zero
  );
};

export default Object.freeze({
  abs,
  abs_lt,
  add,
  and,
  div,
  divrem,
  eq,
  gcd,
  is_big_integer,
  is_negative,
  is_positive,
  is_zero,
  lt,
  make,
  mask,
  mul,
  neg,
  not,
  number,
  or,
  population,
  power,
  random,
  shift_down,
  shift_up,
  significant_bits,
  signum,
  string,
  sub,
  ten,
  two,
  one,
  xor,
  zero
});

 

- 상당히 긴 코드였지만 이렇게 해서 big_integer 객체를 export 시켰습니다.

 

import big_integer from './big_integer';

 

- 위와 같이 해당 모듈을 임포트해서 사용할 수 있으며, 추후에 해당 모듈의 각 함수를 사용한 예시도 다뤄보도록 하겠습니다.