JavaScript 대수 곱 하기 실현 방법 인 스 턴 스

머리말
JavaScript 의 최대 안전 정 수 는 2^{53}C 1,즉 9007199254740991 입 니 다.우리 가 이 범 위 를 초과 한 수 치 를 계산 할 때 정확 한 값 을 얻 지 못 하고 근사치 입 니 다.예 를 들 어 우리 가 9007199254740991+10 을 계산 한 결 과 는 9007199254741000 입 니 다.이 글 은 자바 스 크 립 트 에서 문자열 을 어떻게 이용 하여 대수 적 곱 하기 를 실현 하 는 지 설명 한다.
더 하 다
문자열 로 곱 하기 기본 적 인 사 고 는 우리 가 종이 위 에서 수직 연산 을 하 는 것 과 같다.덧셈 에 대해 우 리 는 두 개의 숫자 num 1 과 num 2 를 상하 로 정렬 한 다음 에 한 자리 부터 두 개의 숫자 가 대응 하 는 비트 의 합 을 계산 하고 가장 높 은 위치 로 순환 하여 모든 연산 결 과 를 하나의 배열 result 에 저장 한 다음 에 Array.prototype.join()방법 으로 하나의 배열 로 복원 해 야 한다.
여기 서 순환 이 정상적으로 진행 되 기 위해 서 는 두 문자열 의 자릿수 가 같 아야 합 니 다.따라서 우 리 는 String.prototpye.padstart()방법 으로 자릿수 가 비교적 작은 문자열 의 앞 을'0'으로 보완 해 야 합 니 다.
위치 에 따라 문 제 는 진 위 를 어떻게 보존 하 느 냐 하 는 것 이다.나의 생각 은 이렇다.우리 가 num 1[i]와 num 2[i]를 더 할 때 가장 많은 두 자릿수 를 얻 을 수 있 습 니 다.이것 은 result 의 두 자리,즉 현재 result[0]위치 와 곧 unshift 가 result 중의 한 사람 에 게 영향 을 줄 것 입 니 다.현재 result[0]위치의 수 는 계산[i-1]이 얻 은 수의 높 은 위치(즉 진 위)입 니 다.우 리 는 우리 가 계산 한 값 을 진 위 를 더 하고 얻 은 수 는 두 자리 로 나 누 어 result 에 넣 습 니 다.
그래서 요약 하면 우리 가 num 1[i]+num 2[i]를 계산 하여 두 자릿수 를 얻 는 것 이다.이 두 자릿수 는 먼저 num1[i-1]+num 2[i-1]의 결과 의 진 위(즉 result[0]를 더 한 다음 에 high 와 low 두 자리 로 나 누 어 result[0]의 값 을 low 비트 로 교체 한 다음 에 high 비트 unshift 를 result 맨 앞 에 가 져 가 야 한다.아래 그림 을 참고 하여 이해 할 수 있다.

그래서 우 리 는 매번 계산 할 때마다 한 사람과 다음 의 진 위 를 확인한다.마지막 코드 는 다음 과 같 습 니 다.

let add = function (num1, num2) {
 if (isNaN(num1) || isNaN(num2)) return '';
 if (num1 === '0' || num2 === '0') return (num1 === '0' ? num2 : num1);

 let len = Math.max(num1.length, num2.length);
 num1 = num1.padStart(len, '0');
 num2 = num2.padStart(len, '0');

 let result = [];

 for (let i = len - 1; i >= 0; i--) {
  let sum = Number(num1[i]) + Number(num2[i]) + (result[0] || 0);
  let low = sum % 10;
  let high = Math.floor(sum / 10);

  result[0] = low;
  result.unshift(high);
 }
 return result.join('');
}

console.log(add('10', '9007199254740991')) //09007199254741001

코드 에서 우 리 는 두 개의 판단 을 추가 하여 두 개의 매개 변수 가 합 법 적 인 숫자 형식 인지 판단 하고 한 개의 숫자 가'0'이면 다른 수 를 직접 되 돌려 줍 니 다.
곱 하 다
상승의 논 리 는 상승의 논리 보다 좀 복잡 하지만 전체적인 사고방식 은 세로 식 에 따라 알고리즘 을 실현 한다.나 는 그림 을 한 장 그 렸 는데 우 리 는 그림 을 빌려 설명 한다.

상승 은 하나의 2 층 순환 이다.우 리 는 하나의 수의 위 치 를 순환 하고 모든 사람 은 다른 수의 순환 하 는 모든 사람과 곱 해 야 한다.우리 가 매번 곱 한 결 과 는 기껏해야 두 자릿수 이다.그러나 더하기 와 달리 하 이 는 매번 unshift 로 들 어가 면 되 고,곱 한 높 은 자리 도 result 의 위치 와 연산 해 야 한다.
우 리 는 상승 하 는 규칙 을 살 펴 보 자.우리 가 num 1[i]*num 2[j]를 사용 할 때 두 자릿수 를 얻 을 수도 있 고 한 자릿수 를 얻 을 수도 있다.우 리 는 모두 두 자릿수 로 계산 하고 높 은 자리 에 없 는 것 은 0 으로 보충 하면 마지막 으로 우리 가 얻 은 결 과 는 i+j 자리 의 수(처음에 보충 하 는 0 이 있 을 수 있다)가 될 것 이다.그리고 우리 가 매번 num1[i]*num 2[j]를 계산 할 때마다 영향 을 주 는 것 은 result 중의 i+j 와 i+j+1 이다.
덧셈 의 논리 와 마찬가지 로 우 리 는 num1[i]*num 2[j]의 결과 와 result[i+j+1]을 더 하여 얻 은 결 과 를 low 와 high 로 나 누 어 reslut 의[i+j+1]과[i+j]에 각각 저장 합 니 다.그러나 여기 서 주의해 야 할 것 은 덧셈 과 달리 덧셈 의 높 은 위 치 를 직접 저장 하면 됩 니 다.여기 있 는 high 에 대응 하 는 result[i+j]는 이미 가치 가 있 을 수 있 습 니 다.우 리 는 이미 존재 하 는 값 을 더 해 야 합 니 다.
high 와 result[i+j]의 더하기 가 존재 할 수 있 습 니 다.어떻게 해 야 합 니까?그림 오른쪽 에 있 는 현재 result 값 을 보면 한 자릿수 가 아 닌 비트 가 저 장 된 것 을 볼 수 있 습 니 다.우 리 는 high+result[i+j]의 값 을 직접 연결 하여 result[i+j]에 저장 합 니 다.왜 이렇게 할 수 있 습 니까?다음 에 num 1[i]*num 2[j-1]를 계산 할 때(우 리 는 뒤에서 앞으로 옮 겨 다 니 는 것 을 주의 하 세 요)result[i+j]와 low 를 더 하면 자 연 스 럽 게 진 위 를 처리 할 수 있 기 때 문 입 니 다.이것 도 이 알고리즘 이 비교적 중요 한 부분 입 니 다.
마지막 코드:

let multiply = function (num1, num2) {
  if (isNaN(num1) || isNaN(num2)) return '';
  if (num1 === '0' || num2 === '0') return '0';

  let l1 = num1.length,
    l2 = num2.length;

  let result = [];

  for (let i = l1 -1; i >= 0; i--) {
    for (let j = l2 - 1; j >= 0; j--) {
      let index1 = i + j;
      let index2 = i + j + 1;

      let product = num1[i] * num2[j] + (result[index2] || 0);
      result[index2] = product % 10;
      result[index1] = Math.floor(product / 10) + (result[index1] || 0);
    }
  }
  return result.join('').replace(/^0+/, '');
}

console.log(multiply('123', '234')) //28782

코드 에 두 가지 판단 이 추가 되 었 습 니 다.합 법 적 인 숫자 인지,한 값 이 0 이면 바로 0 으로 돌아 갑 니 다.마지막 으로 얻 은 결과 의 시작 이 0 인지 아 닌 지 를 판단 하고 있 으 면 지 워 야 합 니 다.여기 서 사용 하 는 정규 표현 식 입 니 다.
총결산
자 바스 크 립 트 의 대수 적 곱 하기 실현 방법 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.자 바스 크 립 트 의 대수 적 곱 하기 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!