代码之家 › 专栏 › 技术社区 › Valdemarick

非常长整数的乘法

64bit math algorithm

Valdemarick · 技术社区 · 18 年前

有没有精确地将两个任意长整数相乘的算法?我使用的语言限制为64位无符号整数长度(最大整数大小为18446744073709551615)。实际上,我希望能够通过分解每个数字,以某种方式使用无符号64位整数处理它们,然后将它们放回到一个字符串中(这将解决乘法结果存储的问题)。

有什么想法吗?

7 回复 | 直到 7 年前

Paige Ruten 18 年前

大多数语言都有这样做的函数或库,通常称为bignum库。( GMP 是好的。

如果你想自己做,我会像人们在纸上做长乘法那样做。要做到这一点,您可以使用包含数字的字符串,也可以使用二进制位操作。

例子:

  45
 x67
 ---
 315
+270
----
 585

或二进制的:

   101
  x101
  ----
   101
  000
+101
------
 11001

编辑: 在使用二进制代码之后,我意识到使用位操作而不是包含以10为基数的字符串来编码要简单得多(当然也要快得多)。我已经编辑了我的二进制乘法示例来显示一个模式:对于底部数字中的每个1位,添加顶部数字,位左移。 1位的位置 乘以一个变量。最后,该变量将包含产品。

要存储产品,您必须有两个64位数字,并设想其中一个是产品的前64位,另一个是产品的第二个64位。您必须编写代码,将第二个数字的第63位的加法运算到第一个数字的第0位。

Nick Johnson 18 年前

如果您不能使用现有的bignum库(如gmp),请签出 Wikipedia's article on binary multiplication with computers . 有许多好的,有效的算法。

Procedural Throwback 18 年前

最简单的方法是使用教科书机制,将任意大小的数字分成32位的块。

给定一个b c d*e f g h(每个块32位,总共128位)
您需要一个9个双字宽的输出数组。将[0..8]设置为0

您将首先执行:h*d+out[8]=>64位结果。
将低32位存储在输出[8]中,并将高32位作为进位。
下一步:(H*C)+出[7]+进位
同样,将低32位存储在输出(7)中,使用高32位作为进位。
完成h*a+出[4]+进位后,您需要继续循环直到没有进位。

然后用g,f,e重复。
对于G来说,你应该从7开始而不是从8开始,以此类推。

最后,遍历并将大整数转换为数字(这需要一个“将大数字除以一个单词”的例程)

Draemon 18 年前

是的,您使用的数据类型实际上是一个数字字符串(就像普通的“字符串”是一个字符串一样)。你如何做到这一点是高度依赖语言的。例如,Java使用BigDeCimple。你用什么语言?

ejgottl 18 年前

这通常作为家庭作业来做。你在小学学到的算法会奏效的。如果您需要一个真正的应用程序,请使用一个库(其他文章中提到了几个库)。

phuclv 7 年前

这是我用C编写的代码。好的旧乘法方法

char *multiply(char s1[], char s2[]) {
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    int i, j, k = 0, c = 0;
    char *r = (char *) malloc (l1+l2+1); // add one byte for the zero terminating string
    int temp;

    strrev(s1);
    strrev(s2);
    for (i = 0;i <l1+l2; i++) {
        r[i] = 0 + '0';
    }

    for (i = 0; i <l1; i ++) {
        c = 0; k = i;
        for (j = 0; j < l2; j++) {
            temp = get_int(s1[i]) * get_int(s2[j]);
            temp = temp + c + get_int(r[k]);
            c = temp /10;
            r[k] = temp%10 + '0';

            k++;
        }
        if (c!=0) {
            r[k] = c + '0';
            k++;
        }
    }

    r[k] = '\0';
    strrev(r);
    return r;
}

Pianistprogrammer 7 年前

    //Here is a JavaScript version of an Karatsuba Algorithm running with less time than the usual multiplication method
    
    function range(start, stop, step) {
        if (typeof stop == 'undefined') {
            // one param defined
            stop = start;
            start = 0;
        }
        if (typeof step == 'undefined') {
            step = 1;
        }
        if ((step > 0 && start >= stop) || (step < 0 && start <= stop)) {
            return [];
        }
        var result = [];
        for (var i = start; step > 0 ? i < stop : i > stop; i += step) {
            result.push(i);
        }
        return result;
    };
    function zeroPad(numberString, zeros, left = true) {
        //Return the string with zeros added to the left or right.
        for (var i in range(zeros)) {
            if (left)
                numberString = '0' + numberString
            else
                numberString = numberString + '0'
        }
    
        return numberString
    }
    function largeMultiplication(x, y) {
        x = x.toString();
        y = y.toString();
    
        if (x.length == 1 && y.length == 1)
            return parseInt(x) * parseInt(y)
    
        if (x.length < y.length)
            x = zeroPad(x, y.length - x.length);
    
        else
            y = zeroPad(y, x.length - y.length);
    
        n = x.length
        j = Math.floor(n/2);
    
        //for odd digit integers
        if ( n % 2 != 0)
            j += 1    
        var BZeroPadding = n - j
        var AZeroPadding = BZeroPadding * 2
    
        a = parseInt(x.substring(0,j));
        b = parseInt(x.substring(j));
        c = parseInt(y.substring(0,j));
        d = parseInt(y.substring(j));
    
        //recursively calculate
        ac = largeMultiplication(a, c)
        bd = largeMultiplication(b, d)
        k = largeMultiplication(a + b, c + d)
        A = parseInt(zeroPad(ac.toString(), AZeroPadding, false))
        B = parseInt(zeroPad((k - ac - bd).toString(), BZeroPadding, false))
        return A + B + bd
    }
    //testing the function here
    example = largeMultiplication(12, 34)
    console.log(example)