高效乘法

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

嗯，是的。还有更高级的乘法方法。

一个快速而简单的方法是将你的算法从基数10(也就是小数位)转移到一个更适合计算机的数字系统中。在基数2中处理32位或64位整数的速度会快得多。你每次计算都要做更多的工作，同时也摆脱了所有的模运算。

除此之外，您还可以用更好的算法替换(简单的)乘法算法。如果你的数字开始变得很大，你可以通过移动到一个不同的复杂区域来获得巨大的加速。您的算法的复杂度为O(n*m)，其中n和m是两个因子的位数。

快速傅立叶变换可以在O(n log n)内更快地进行大数乘法。值得一提的是数论变换，它更适合于这项任务。

在大整数算术的主题中有很多需要学习和探索的东西。但是，如果你只想做数字乘法，而不关心它是如何完成的，我建议你只使用一个经过测试的快速bignum库。