효율적인 곱셈

Question

정말 긴 숫자를 곱하기 위해 몇 가지 코드를 작성했습니다. 이 작업을 수행하는보다 효율적인 방법이 있는지 궁금한가요?

다음은 지금까지 해 보았습니다. 기본적으로 '긴 곱셈'기법을 구현했습니다.

internal enum Digit 
    { 
     Zero = 0, 
     One, 
     Two, 
     Three, 
     Four, 
     Five, 
     Six, 
     Seven, 
     Eight, 
     Nine 
    } 

    public class NumbersWhiz 
    { 
     public string Add(string Augend, string Addend) 
     { 
      string longerNum = (Augend.Length > Addend.Length == true) ? Augend : Addend; 
      string shorterNum = (Addend.Length < Augend.Length == true) ? Addend : Augend; 

      int longerLen = (Augend.Length > Addend.Length == true) ? Augend.Length : Addend.Length; 
      int shorterLen = (Addend.Length < Augend.Length == true) ? Addend.Length : Augend.Length; 

      //Pad the shorter number initially with zeros to match length of longer number 
      int deltaLen = longerLen - shorterLen; 
      string numTwoZeroed = new String('0', deltaLen); 
      string numTwo = numTwoZeroed.Insert(deltaLen, shorterNum); 
      string numOne = longerNum; 

      string result = new String('0', longerLen); 
      StringBuilder resultBuilder = new StringBuilder(result); 

      bool carryForward = false; 
      for (int index = longerLen; index > 0; index--) 
      { 
       int augend = Convert.ToInt32(numOne.Substring(index - 1, 1)); 
       int addend = Convert.ToInt32(numTwo.Substring(index - 1, 1)); 

       int sum = (carryForward == true) ? 1 : 0; 
       sum = sum + augend + addend; 
       carryForward = ((sum > 9) == true) ? true : false; 
       int reminder = sum % 10; 
       resultBuilder[index - 1] = Convert.ToChar(reminder.ToString()); 
      } 

      if(carryForward) 
       resultBuilder.Insert(0, '1'); 

      return resultBuilder.ToString(); 
     } 

     public string Multiply(string Multiplicand, string Multiplier) 
     { 
      int resultLen = Multiplicand.Length + Multiplier.Length; 
      string totalSum = new String('0', resultLen); 
      for (int index = Multiplier.Length; index > 0; index--) 
      { 
       int multiplierDigit = Convert.ToInt32(Multiplier.Substring(index - 1, 1)); 

       string product = Multiply(Multiplicand, (Digit)multiplierDigit); 
       product += new String('0', Multiplier.Length - index); 
       totalSum = Add(totalSum, product); 
      } 
      return totalSum; 
     } 

     string Multiply(string Multiplicand, Digit MultiplierDigit) 
     { 
      int multiplier = (int)MultiplierDigit; 
      if (multiplier == 0) 
       return "0"; 

      int carry = 0; 
      bool carryForward = false; 
      int len = Multiplicand.Length; 

      int productLen = len + 1; 
      string result = new String('0', productLen); 
      StringBuilder resultBuilder = new StringBuilder(result); 

      for (int index = len; index > 0; index--) 
      { 
       int multiplicandDigit = Convert.ToInt32(Multiplicand.Substring(index - 1, 1)); 

       int product = (multiplicandDigit * multiplier) + carry; 
       carryForward = ((product > 9) == true) ? true : false; 
       int reminder = product % 10; 
       carry = (product - reminder)/10; 
       resultBuilder[index] = Convert.ToChar(reminder.ToString()); 
      } 

      if (carryForward) 
       resultBuilder[0] = Convert.ToChar(carry.ToString()); 

      return resultBuilder.ToString(); 
     } 
    } 

Answer 1

예 - 이것은 한 자리 씩 입력하는 작업입니다.

더 빨리 작업을 수행 할 수있는 몇 가지 확실한 옵션이 있습니다. 하나는 2 진수 연산이며, 숫자 중 하나를 2의 거듭 제곱의 합으로 처리하고 그 결과를 2의 거듭 제곱을 곱하여 얻은 부분 결과의 합계로도 처리합니다.

예를 들어, 17x11 (181을 제공해야 함)이라고 가정 해 보겠습니다.

은 그래서, 그것은 2 + 2 ⁴⁰있어 2의 멱수로 (17)를 생각하자 (즉, 1 + 16). 그래서 우리가 취할 수 11 * 1 + * (16) 우리는 변화와 승산의 각을 할 수있는, 그래서 11 < < 0 + 11 < < 4.

사물을 보는 또 다른 방법은 (즉, 리드의 (11) 일을하는 다소 다른 방식)은 큰 수에 유용합니다. 논증의 목적으로 4 비트 연산 만 수행 할 수 있다고 가정 해 봅시다. 이 경우 각 숫자를 4 비트 조각으로 생각하고 곱셈의 분배 속성을 사용하여 결과를 얻습니다. 즉, 각 큰 숫자를 취해서 숫자의 합계로 나눕니다. 각 숫자는 정수를 구성하는 비트의 "슬라이스"를 나타냅니다. 예를 들어, 0x1234 * 0x4321과 같은 것을 고려해보십시오. (단순함과 동일하게) 두 개의 8 비트 피연산자를 곱하여 16 비트 결과를 생성 할 수있는 CPU를 곱하는 것으로 가정합니다. 그래서,

0x1200 * 0x4300 + 0x1200 * 0x21 + 0x34 * 0x4300 + 0x34 * 0x21 

이들 각각 (분명히 충분히)은 8 유효 비트가 있습니다

(0x1200 + 0x34) * (0x4300 + 0x21) 

그런 다음 우리는 분배 속성을 사용할 수 있습니다 : 그래서, 우리는 8 비트 조각으로 그 최대의 각각의 휴식 우리는 8 비트 CPU에서 각각의 연산을 수행 할 수 있습니다. 그런 다음 기본적으로 4 개의 중간 결과를 가져와 함께 추가해야합니다. 합리적인 CPU에는이 다중 정밀 작업을 처리하는 데 사용할 수있는 carry-bit 및 add-with-carry 명령이 있습니다.

여기에 8 비트 연산이 나와 있지만, 32 비트 또는 64 비트 CPU에서 256 비트 피연산자가 어떻게 확장되는지는 분명합니다.

Answer 2

글쎄, 네. 보다 진보 된 곱셈 방법이 있습니다.

알고리즘 속도를 높이는 빠르고 쉬운 방법은 컴퓨터에 더 적합한 숫자 체계로 10 진수 자리 (소수 자리)부터 이동하는 것입니다. 2 기수에 32 비트 또는 64 비트 정수로 작업하는 것이 훨씬 빠릅니다. 계산 당 더 많은 작업을 수행하고 모든 모듈러스 계산을 제거합니다.

너머에서 (사소한) 곱셈 알고리즘을 더 나은 것으로 대체 할 수 있습니다. 숫자가 너무 커지면 다른 복잡성 영역으로 이동하여 엄청난 속도 향상을 얻을 수 있습니다. 알고리즘의 복잡성은 O (n * m)입니다. 여기서 n과 m은 두 요소의 자릿수입니다.

고속 푸리에 변환은 O (n log n)에서 훨씬 빠른 거대한 곱셈을 수행하는 데 사용할 수 있습니다.언급 할 가치가있는 것은 Number Theoretic Transform으로이 작업에 훨씬 더 적합합니다.

큰 정수 산술의 주제에서 배우고 탐구해야 할 것이 많습니다. 그러나 숫자를 곱하기를 원하고 어떻게 완료되었는지 신경 쓰지 않으면 테스트되고 빠른 bignum 라이브러리를 사용하는 것이 좋습니다.