标签: karatsuba

我实现了 karatsuba 乘法算法。我想以这种方式改进它，我可以将 2 个 64 位数字相乘，但我不知道该怎么做。我得到了一个提示，两个数字都包含一个 2 的幂的位数，但这对我没有任何暗示。你能给出任何其他提示吗？数学提示或算法改进提示。

#include <iostream>
#include <math.h>
using namespace std;

int getLength(long long value);
long long multiply(long long x, long long y);

int getLength(long long value)
{
    int counter = 0;
    while (value != 0)
    {
        counter++;
        value /= 10;
    }
    return counter;
}

long long multiply(long long x, long long y)
{
    int xLength = getLength(x);
    int yLength = getLength(y);

    // the bigger of the two lengths
    int N = (int)(fmax(xLength, yLength));

    // …

我最近实施了Karatsuba Multiplication作为个人练习.我按照维基百科上提供的伪代码在Python中编写了我的实现:

procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* calculates the size of the numbers */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* split the digit sequences about the middle */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 calls made to numbers approximately half the size */
  z0 = karatsuba(low1, low2)
  z1 = karatsuba((low1+high1), (low2+high2))
  z2 = karatsuba(high1, high2)
  return (z2*10^(2*m2)) + ((z1-z2-z0)*10^(m2)) …

我想在python中实现Karatsuba乘法。

但是当数字很大时，我得到了正确的答案。

谁能告诉我我的代码哪里错了？

当 x 非常大时，唐叶乘法实现是不正确的。

import math
def fun1(x,y):
    if x <= 100  or y<=100:
        return x*y
    else:
        n = int(math.log10(x)) + 1
        print(n)
        #split x
        a = int(x//(10**int(n/2)))
        b = int(x%(10**int(n/2)))
        #split y
        c = int(y//(10**int(n/2)))
        d = int(y%(10**int(n/2)) )
        print('=======')
        print(a,b,c,d)
        s1 = fun1(a,c)
        s2 = fun1(b,d)
        s3 = fun1(a+b, c+d) - s1 -s2

        return 10**(n) * s1 + 10**int(n/2) * s3 + s2
x = 3141592653589793238462643383279502884197169399375105820974944592
y = 3141592653589793238462643383279502884197169399375105820974944592
res = fun1(x,y)
print(res)

结果对比如下： …

我花了一段时间尝试在 Python 中实现 Karatsuba 的算法，虽然当我尝试将两个较大的数字（超过 ~10^15）相乘时，我的结果开始变得不准确，但我已经很接近了。我不明白为什么。

附带问题：是否有办法让我的基本情况“x 和 y 都（而不是其中之一）严格小于（而不是小于）10”

def karatsuba(x, y):
    # 1. Split ints

    if x <= 10 or y <= 10:
        #Base case
        return x * y

    n_x = ceil(log(x, 10))  # Nb of digits in x
    n_y = ceil(log(y, 10))

    n = max(n_x, n_y)

    b = int(x % (10 ** (n // 2)))
    a = int(x / (10 ** (n // 2)))
    d = int(y % (10 ** (n // 2)))
    c = int(y / …