相关疑难解决方法(0)

为了加快我的bignum除数,我需要加速y = x^2bigints的操作,bigints被表示为无符号DWORD的动态数组.要明确:

DWORD x[n+1] = { LSW, ......, MSW };

• 其中n + 1是使用的DWORD的数量
• 所以数量的价值 x = x[0]+x[1]<<32 + ... x[N]<<32*(n)

问题是:如何在y = x^2没有精度损失的情况下尽快计算？ - 使用C++和整数算术(32位带Carry)处理.

我目前的方法是应用乘法y = x*x并避免多次乘法.

例如:

x = x[0] + x[1]<<32 + ... x[n]<<32*(n)

为简单起见,让我重写一下:

x = x0+ x1 + x2 + ... + xn

其中index表示数组内的地址,因此:

y = x*x
y = (x0 + x1 + x2 + ...xn)*(x0 + x1 + x2 + ...xn)
y = x0*(x0 …

我最近实施了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)) …