Karatsuba实现C++
Karatsuba是一种用于高精度乘法的算法，它通过将乘法问题分解为更小的子问题来提高计算效率。该算法由安德烈·卡拉茨巴于1960年提出，是分治算法的一个典型应用。
Karatsuba算法的核心思想是将两个大整数相乘的问题转化为三个小整数相乘的问题，并通过递归的方式解决。具体步骤如下：
- 将两个大整数x和y分别拆分为两部分，使得x = a * B^m + b和y = c * B^m + d，其中B是基数（通常为10或2），m是x和y的位数的一半。
- 计算三个小整数的乘积，即ac、bd和(ad + bc)。
- 使用递归的方式计算(ad + bc) = (a + b)(c + d) - ac - bd。
- 将上述结果组合起来得到最终的乘积。
Karatsuba算法相对于传统的乘法算法具有更高的效率，尤其在处理大整数乘法时表现出色。它的时间复杂度为O(n^log2(3))，而传统的乘法算法的时间复杂度为O(n^2)。
在实际应用中，Karatsuba算法可以用于密码学、多项式乘法、大整数计算等领域。例如，在密码学中，大素数的生成和RSA加密算法中的模幂运算都需要进行大整数乘法运算，Karatsuba算法可以提高计算效率。
腾讯云提供了一系列云计算相关产品，其中包括云服务器、云数据库、云存储、人工智能服务等。然而，腾讯云并没有特定针对Karatsuba算法的产品或服务。对于实现Karatsuba算法的C++代码，您可以参考以下链接：
https://github.com/topics/karatsuba
这是一个GitHub上的Karatsuba算法相关项目列表，您可以在其中找到各种实现Karatsuba算法的C++代码示例和开源项目。请注意，这些代码示例和项目并非由腾讯云提供，仅供参考和学习之用。
相关·内容
我正在尝试使用Devcpp在Windows10上的c++中实现Karatsuba乘法算法。下面是相同的代码：
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int karatsuba(int x, int y){
string sx = to_string(x);
string sy = to_string(y);
int len_x = strlen(sx);
int len_y = strlen(sy);
i
浏览 2提问于2018-04-16得票数 0
因此，在“分而治之”课程中，我们被教导：
Karatsuba增殖
快速指数
现在，给定两个正整数a和b比operator::*快于karatsuba(a,b)或pow(a,b)快于
int fast_expo(int Base, int exp)
{
if (exp == 0) {
return 1;
}
if (exp == 1) {
return Base
}
if (exp % 2 == 0) {
return fast_expo(Base, exp / 2) * fast_expo(
浏览 6提问于2016-06-24得票数 0
回答已采纳
我试图在c++中实现bigint类，它还没有完成，我遇到了一些我无法理解的错误。
我删除了所有其他函数(因为在本例中它们是不必要的)，karatsuba还没有完成(但在本例中不应该造成问题)。
在乘法函数(重载*)中，我的编译器给出了一个错误：
传递'const BigInt‘作为'this’参数丢弃限定符-fpermissive
在线
ans.a = karatsuba(n,m);
我知道，当我试图改变传递给常数函数的常量对象或对象时，就会发生这种情况。在我的例子中，我只是创建一个新的向量，并将它传递给karatsuba函数。从过多的*中删除const将消除此错误。
浏览 0提问于2019-08-18得票数 0
回答已采纳
1回答
我在试着理解Karatsuba乘法算法。我编写了以下代码：
def karatsuba_multiply(x, y):
# split x and y
len_x = len(str(x))
len_y = len(str(y))
if len_x == 1 or len_y == 1:
return x*y
n = max(len_x, len_y)
n_half = 10**(n // 2)
a = x // n_half
b = x % n_half
c = y // n_half
d =
浏览 5提问于2020-06-18得票数 1
回答已采纳
1回答
以前我发了一个关于这个问题的问题，得到了很好的回答。，然而，对于类中的递归，我仍然有一些不理解的地方。在上面的链接问题中，如果我将prefixive self.添加到递归子例程中，就会得到与下面类输出中产生的错误完全相同的错误(本文中的第三个代码块)。我理解为什么会发生这种情况；object.karatsuba()只接受self作为它的输入，但是编码的方法要求2，因此出现了错误。
，请检查下面的代码，然后看到我对第三个代码块之后的解决方案的直觉。
例如:我有一个不想在类中工作的karatsuba乘法的工作实现。标准的课堂乘法在课堂上效果很好，但是.
这是类之外的工作代码：
def zeroPa
浏览 0提问于2018-06-09得票数 0
回答已采纳
1回答
因此，我决定尝试用C++实现Karatsuba的算法(自从我上第二节编程课以来，我就再也没有用过这种语言了，所以我非常非常生疏)。不管怎样，我相信我已经逐行跟踪了伪代码，但我的算法仍然不断地弹出错误的答案。 x = 1234, y = 5678
Actual Answer: x*y ==> 7006652
Program output: x*y ==> 12272852 *注意:我在mac上运行，并使用以下代码创建运行c++ -std=c++11 -stdlib=libc++ karatsuba.cpp的可执行文件 不管怎样，这是我起草的代码，你可以随意指
浏览 50提问于2020-07-12得票数 0
回答已采纳
我正在尝试用Python实现
这是我的密码
import math
# Base
B=10
# No. of digits
n=4
# Numbers
x=1234
y=5678
def karatsuba(x,y,d):
if (x < 10 o r y < 10):
return x*y
# Partition
m=math.floor(d/2)
n=math.ceil(d/2)
x1=x//B**n
x2=x%B**n
y1=y//B**n
y2=y%B**n
a=karatsu
浏览 2提问于2015-08-24得票数 2
回答已采纳
我用Python实现了一个Karatsuba算法，但它并没有给出确切的答案。
def karatsuba(x, y):
if x < 10 or y < 10:
return x*y
#making the two numbers strings here
str_x = str(x)
str_y = str(y)
#finding the mid point for each number here
n = max(len(str(x)), len(str(y)))
n_2 = int(n / 2)
浏览 0提问于2017-06-07得票数 3
回答已采纳
在Karatsuba算法的实现中，该方法只计算小数目的真数，但是大的答案是不正确的，问题是什么？
var x = "1685287499328328297814655639278583667919355849391453456921116729";
var y = "7114192848577754587969744626558571536728983167954552999895348492";
function karatsuba(x, y) {
if (x.length < 2 && y.length < 2) {
浏览 0提问于2019-01-15得票数 2
回答已采纳
以下是karatsuba算法的伪代码：
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 = sp
浏览 0提问于2018-10-03得票数 0
回答已采纳
我得到这个错误= Unhandled exception at 0x7A5B1088 (ucrtbased.dll) in algorthmprokect1.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x006B2FF4). occurred
我不知道我在使用字符串时哪里出了错，因为我需要从文件中获取整数，而它们有1000位
更新:在调试之后，我意识到else语句运行了无数次，但是我仍然没有找到解决方案。
string karatsuba(string X,string Y) {
if (X.length()==1 ||
浏览 0提问于2020-04-05得票数 0
2回答
我最近学习了Karatsuba乘法。为了完全理解这个概念，我尝试用Python编写代码，并将运行时间与经典乘法进行了比较。尽管结果是相等的，但karatsuba的执行时间仍然是最低的，尽管我使用的是递归调用。我的方法有什么问题？一些帮助肯定会让我对算法设计有更多的了解。
最好的
JP
print('Karatsuba multiplication in Python')
x=raw_input("first_number=")
y=raw_input("second_number=")
print('-------------------
浏览 0提问于2014-07-14得票数 3
已知具有时间复杂度~O(n^log2(3))的递归Karatsuba乘法算法比具有复杂度O(n^2)的简单乘法算法快。
但是，它使用的内存空间比“年级”算法-- O(n log(n))而不是O(n)内存--要大得多，对于拥有少量内存的控制器或非常小的计算机来说，这是非常关键的。
所以，我的问题是：
在karatsuba算法中有实现O(n)内存空间的方法吗？
PS:我知道使用快速傅立叶变换你可以获得更快的速度O(n log(n))和更好的内存使用O(n)，但是我只是对Karatsuba很好奇。
浏览 9提问于2015-05-04得票数 2
回答已采纳
1回答
嗨，我正在尝试在Javascript中实现karatsuba算法。到目前为止，该算法在某些情况下工作得很好，例如当整数长度为4或8时，当整数长度为6时，它会打印出错误的结果 例如: 3141*2718=>8537238 (正确的结果) 例如: 314*271=>84981.37398106341 (结果错误) 例如: 3141592653589793238462643383279502884197169399375105820974944592 * 2718281828459045235360287471352662497757247093699959574966967627 =
浏览 11提问于2020-05-03得票数 1
1回答
我用BigInteger编写了一个C++类，它应该能够对任意大小的所有数字进行操作。目前，我正试图实现一种非常快速的乘法方法，通过比较现有的算法并测试它们对哪一种数字最有效，我遇到了非常意想不到的结果。我尝试了20次500位数的乘法，并对它们进行了计时。结果是：
karatsuba:
14.178 seconds
long multiplication:
0.879 seconds
维基百科告诉我
因此，对于足够大的n，Karatsuba算法将执行比长和乘法更少的移位和一位数的加法，尽管它的基本步骤使用的加法和移位比简单的公式要多。然而，对于n的小值，额外的shift和add操作可
浏览 1提问于2014-05-31得票数 4
2回答
我在实现Karatsuba算法时遇到了一些问题。我的项目限制了我使用以下库: iostream、iomanip、cctype、cstring。此外，我只能使用整数内置类型和数组/动态数组来处理数字(只会输入无符号整数)。我使用动态数组构建了一个类来处理任意大小的整数。我需要实现一个乘以大整数的函数，如果可能的话，我想使用Karatsuba。我遇到的麻烦是如何分解大整数并执行算法中要求的乘法。我假设这应该是递归完成的。我希望有人能给我一个如何做到这一点的例子。
例如：
我有两个数字存储在动态数组中。让我们假设它们是：
X= 123456789123456789123456789 Y= 98765
浏览 1提问于2013-11-08得票数 1
回答已采纳
1回答
我花了一段时间用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(l
浏览 11提问于2022-02-05得票数 1
回答已采纳
我正在尝试使用karatsuba乘法将两个数字相乘。我的java代码不工作了。我使用字符串作为参数和参数，这样我们就可以将两个n位数相乘(n是偶数)。另外，我不想使用long或BigInteger。请帮我找出我的代码错误。
class karat{
public static String karatsuba(String first, String second){
if(first.length() <= 1 || second.length() <= 1)
return String.valueOf(Long.parseLong(first)*Lo
浏览 18提问于2017-08-20得票数 0
import java.math.BigInteger;
import java.util.Random;
class Karatsuba {
private final static BigInteger ZERO = new BigInteger("0");
public static BigInteger karatsuba(BigInteger x, BigInteger y) {
// cutoff to brute force
int N = Math.max(x.bitLength(), y.bitLength());
if (N &
浏览 1提问于2016-12-24得票数 1
2回答
我已经实现了两个字节数组的乘法，它工作得很好。更准确地说，我需要将64字节的操作数乘以32字节的操作数。
我用最简单的方法实现了它:我做了一个双循环，并计算每个数组中每个字节的乘积。因此，对于特定的值，它采取64 * 32 = 2048步骤。
我尝试使用Karatsuba方法优化它。因此，我按以下方式进行：
a的长度为64字节，b的长度为32字节。
我们将a拆分为：a = p * 16^(32) + q (所以p和q都有32个字节)和计算：a * b = p * b * 16^(32) + q * b (产品是用前面描述的函数计算的)。
我得到了正确的结果，但计算时间相同:两个32字节数组的2
浏览 4提问于2015-05-04得票数 3
回答已采纳
2回答
这里的初学者。我花了一天的大部分时间研究Karatsuba算法，只是因为我认为它会很有成效。我在这里看到过类似的问题，但它们都是用其他语言写的，而且看起来异常复杂。下面是我的代码。一旦它碰到了对ac的递归调用，它就会继续递归。就好像它从来不符合基本的情况一样。如果有人能提供一些关于哪里出了问题的见解，我们将不胜感激。对于这段代码，你应该假设我乘以2，基数-10，四位数。
def karatsuba(x, y):
if len(str(x)) == 1 or len(str(y)) == 1:
return (x * y)
else:
n = (
浏览 3提问于2016-10-08得票数 1
回答已采纳
我正在写自己的卡拉特赛变体，但不能使它与真实的大整数一起工作
'use strict';
const karatsuba = function (x, y) {
if (x < 10 || y < 10) return x * y;
const strX = String(x);
const strY = String(y);
const n = Math.min(strX.length, strY.length);
const m = Math.ceil(n / 2);
const leftX = strX.slice(0, str
浏览 4提问于2016-11-21得票数 1
回答已采纳
1回答
我正在为在线课程在Scala中实现 (我的选择)。考虑到算法是用来乘大数的，我选择了由Java支持的BigInt类型。我希望高效地实现该算法，使用基本10的算法从维基百科复制如下：
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 = floor(m/2)
/* spli
浏览 0提问于2018-11-04得票数 0
回答已采纳
我一直试图在java中实现Karatsuba算法，而不使用BigInteger。我的代码只适用于两个整数相同的情况&具有相同的数字数。我没有得到正确的答案，但是我得到的答案非常接近正确的答案。例如，我在12*12的时候得到149，我不知道我的代码有什么问题，因为我相信我做的一切都是正确的(按书)。这是我的密码。
public static void main(String[] args) {
long ans=karatsuba(12,12);
System.out.println(ans);
}
private static long karatsuba(long
浏览 8提问于2013-07-08得票数 10
下面是我对Karatsuba乘法算法的python实现。此代码似乎适用于大多数输入，但在数字变得太大后开始失败。例如，对于64位输入x = 3141592653589793238462643383279502884197169399375105820974944592 y = 2718281828459045235360287471352662497757247093699959574966967627，算法失败。但是，当我只使用前35位数字时，算法可以工作。谁能解释一下这个实现的不足之处？ from math import floor, ceil
def karatsuba(x, y):
浏览 48提问于2020-05-03得票数 0
回答已采纳
3回答
在不使用位移位的情况下，有没有办法在O(n)时间内计算2^n？
我正在考虑一个使用回忆录的解决方案，因为我总是先从较低的n开始计算。即
d = dict()
def pwr2(n):
if n == 0:
return 1
if n == 1:
return 2
if n in d:
return d[n]
d[n] = 2 * pwr2(n-1)
return d[n]
但我不太确定会有多复杂。
编辑:我应该补充说，我正在使用这个算法的一部分，以便在比O(n^2)更快的时间内将二进制转换为十进制。作为我的分而治
浏览 10提问于2015-04-22得票数 4
我用ADA编写了这样一个Karatsuba算法实现。
procedure Karatsuba (Factor_1, Factor_2 : in Number; Product : out Number) is
m : Integer;
m2 : Integer;
low1 : Number := (0,1);
high1 : Number := (0,1);
low2 : Number := (0,1);
high2 : Number := (0,1);
z0 : Index;
z1 : In
浏览 11提问于2015-03-13得票数 0
回答已采纳
3回答
我正在寻找一个c++类/库，它提供1024bit和更大的整数和位操作，比如：-位移位，-位OR/ and，-定位第一个零位
速度至关重要，因此必须使用一些SIMD程序集来实现。
浏览 0提问于2009-06-28得票数 16
回答已采纳
我没有得到任何结果，我的程序被困在无限循环中。，我用相同的逻辑为四个值编写了一个程序，这个程序工作得很好，但是有三个值，这是行不通的。
def Karatsuba_Recursive(a, b):
if not a or not b:
return "0"
if len(a) == 1 or len(b) == 1:
return str(int(a)*int(b))
else:
m = max(len(a),len(b))
m2 = m // 2
A = a[0:-m2]
浏览 4提问于2022-09-27得票数 -1
回答已采纳
我不明白我的代码出了什么问题。我应该如何修复Karatsuba乘法中的这个递归错误？
def karatsuba(x,y):
if len(str(x))==1 or len(str(y))==1:
return int(x)*int(y)
else:
n=max(len(str(x)),len(str(y)))
nby2=n//2
a=x/(10**nby2)
b=x%(10**nby2)
c=y/(10**nby2)
d=y%(10**nby2)
浏览 7提问于2019-08-19得票数 0
2回答
我正在处理一个本地C++/CLI类，它使用多精度值执行整数运算。单个整数由64位无符号整数数组表示.符号用布尔值表示，负值是用它们的绝对值存储的，而不是作为两个的补充。这使得处理符号问题变得容易多了。目前我正在优化乘法运算。我已经做了几次优化循环，但是函数仍然需要是两个.NET BigInteger值的*操作符的两倍，这表明还有很大的进一步优化的潜力。
在寻求帮助之前，让我向你展示我已经尝试过的东西。我的第一次尝试是一种天真的方法:使用一个基本的64位到128位乘法对所有64位项的对，并移动/添加结果。我没有在这里显示代码，因为它太慢了。下一次尝试是递归分而治之算法，结果证明它要好得多。在我的
浏览 1提问于2019-03-25得票数 0
回答已采纳
1回答
我写了一个名为的类，它可以处理任意位大小的整数，而且我似乎已经完成了所有的工作，只有一件事例外，尽管我做了很多事情来修复它，但它拒绝正常工作：
std::ostream & operator<<(std::ostream & stream, integer rhs){
std::string out = "";
if (rhs == 0)
out = "0";
else {
int div = 10;
if (stream.flags() & stream
浏览 2提问于2011-08-15得票数 3
我一直试图以以下方式在中实现Python3：
def karatsuba(num1,num2):
n_max = max(len(str(int(num1))), len(str(int(num2))))
if n_max == 1:
return int(num1*num2)
n = n_max + n_max%2
a = num1//10**(n/2)
b = num1%10**(n/2)
c = num2//10**(n/2)
d = num2%10**(n/2)
t1 = karatsuba(a,c)
浏览 7提问于2022-02-08得票数 0
回答已采纳
在我的python代码中，使用Karatsuba的算法[，]输出2个数字的乘法值时遇到了最困难的问题。这是我的代码：
def mult(num1,num2):
if num1 < 10 or num2 < 10:
return int(num1*num2)
else:
n = len(str(num1))
a = int(str(num1)[:-(int(n/2))])
#print(a)
c = int(str(num2)[:-(int(n/2))])
浏览 0提问于2018-08-20得票数 0
我正在尝试用Java实现karatsuba算法，我起诉BigInteger，我遵循了所有的步骤，但我没有得到正确的结果，是什么让我发疯。
下面是我的代码：
public BigInteger karatsuba(BigInteger a, BigInteger b, int base) {
if (a.compareTo(BigInteger.TEN) == -1 || b.compareTo(BigInteger.TEN) == -1 ) {
return a.multiply(b);
}
/* calculates the size of the
浏览 7提问于2017-02-04得票数 2
回答已采纳
1回答
我将两个n位正整数与n位Karatsuba乘法器相乘。但在大多数情况下，子问题仍然需要处理两个n位数字。那么，我是否应该再次递归地使用n位Karatsuba算法来解决子问题？这种方法中是否存在冗余？它会以任何方式影响计算时间(O(n^1.5))吗？
浏览 0提问于2013-01-11得票数 0
我对编程相对来说还是比较新的，在运行时间方面，我并不希望这个算法特别高效，而只是试图复制Karatsuba算法并使其工作。
我尝试了许多数字和小数字(如y= 40004009343254，x= 40004001343234)，当数字增加时(如y= 4000400934325423423，x=40004001343232423)，算法停止工作，返回类似但不正确的答案。
任何可能是错误的线索都会非常感谢！
注意到：这个线程不是关于效率，而是关于获得正确的结果。尽管如此，有关效率的评论也将得到考虑和赞赏。
码
y = 4000400934325423423
x = 40004001343234324
浏览 3提问于2016-12-09得票数 1
回答已采纳
今天，我听说了Karatsuba算法，一种快速乘法算法。我很好奇，这个“快”在哪种意义上是指？
通常，当计算一段代码的时间复杂度时，我们考虑使用*运算符的乘法运算作为O(1)，如果它总是正确的，为什么我们有一个关于渐近符号的更快的算法？或者*在非常大的数字上执行时不应该被认为是O(1)，其中Karatsuba算法是有用的？
在机器级别，编译器总是在*上做一些优化。例如，使用逐位运算将一个数乘以2^n。Karatsuba算法在实际运行时间内是否优于*？
浏览 0提问于2012-03-19得票数 4
回答已采纳
试着用Karatsuba乘法器将两个二进制数相乘，下面的逻辑对无符号数很好，但是当我将输入之一改为负数时，得到的答案却是错误的。在下面的示例中，a=1010011111000000(等于-88.25)和b= 0001010001000000(等于20.25)。答案应该是11111001000001001111000000000000(equals:-1787.0625)but，我最终得到的答案是。采用定点逻辑，输入16位，分数8位，输出32位和16位。
module karatsuba( input signed [15:0] a,
input signed [15:0] b,
浏览 22提问于2022-11-11得票数 -1
我正在实现一个Karatsuba算法，并且遇到了这个异常。
一些相关代码(如果需要，我可以发布更多代码)：
来自main：
int degree = (input.nextInt() + 1);
int A[] = new int[degree];
int B[] = new int[degree];
for(int i = 0; i < degree; i++)
A[i] = input.nextInt();
for(int i = 0; i < degree; i++)
B[i] = input.nextInt();
product = karatsuba(A
浏览 2提问于2018-12-15得票数 0
回答已采纳
1回答
我试图在c中实现kartsuba的算法，我遵循了，但问题是我并不总是得到正确的结果。
以下是实现：
long long karatsuba(char* a,char* b){
if (atoi(a)<10 || atoi(b)<10)
return atoi(a)*atoi(b);
int m = ((strlen(a)<strlen(b))?strlen(a):strlen(b))/2;
char* high1 = slice(a,0,m);
char* low1 = slice(a,m,strlen(a)-m);
char* high2 = slice(b,0,
浏览 1提问于2019-03-24得票数 1
回答已采纳
这段代码没有通过所有的测试用例，有人能帮上忙吗？我只是通过了直截了当的测试，然后它就失去了精度。
import math
import unittest
class IntegerMultiplier:
def multiply(self, x, y):
if x < 10 or y < 10:
return x * y
x = str(x)
y = str(y)
m_max = min(len(x), len(y))
x = x.rjust(m_max, &#
浏览 5提问于2019-07-21得票数 0
2回答
我试图将整数长度与数字长度进行比较，并将最小的长度与0的长度相加，从而使两者的大小相同，即：
6 and 1500
变成了
0006 and 1500
我无法得到std::stoi的工作，然后检查每个数字的长度。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int schoolMethod(int a, int b, int base){
if(std::stoi(a)<std::stoi(b)){
//do stuff
re
浏览 4提问于2015-08-10得票数 0
3回答
我想用Python语言实现。但是，在表单中写入数字
A=c*x+d
其中x是接近sqrt(A)的基(令x=b^m)的幂。
如果我连除法和乘法都不会，我怎么找到x呢？我是否应该计算位数并将A向左移位位数的一半？
谢谢。
浏览 1提问于2011-09-18得票数 6
回答已采纳
我首先用long编写了Karatsuba算法的代码。我觉得效果很好。使用相同的逻辑，我将代码转换为BigInteger，但出于某些原因，它给了StackOverflowError。
我不知道为什么。请帮帮忙。
EDIT1:长时间的代码也有一个逻辑缺陷。我不知道是什么。
EDIT2: long的代码现在起作用了。我误把"%“操作符换成了"/”。
EDIT3:现在一切都好。我将.xor更改为.pow，将==更改为.equals，并修复了返回语句中的一些括号问题。谢谢大家的帮助！
以下是正确的代码：
public static BigInteger karatsuba3(BigI
浏览 2提问于2016-10-19得票数 4
我正在学习Karatsuba，并且很好奇Python实际上是如何实现乘法运算的。对不起，我找不到这方面的文件。
浏览 2提问于2022-06-22得票数 0
回答已采纳
1回答
我想在这里做卡拉特赛乘法。下面的代码适用于两位数的数字(例如78 * 34)，但对于数字大于2的数字(例如5678 * 1234)，则给出错误的结果。我已经附加了调试日志。在某一点之后，计算是错误的。有人能看看我对算法的理解是否不正确吗？
static BigInteger karatsuba(BigInteger no1, BigInteger no2){
BigInteger result = null;
//Both numbers less than 10
if(no1.compareTo(new BigInteger("9")) !=
浏览 3提问于2021-04-16得票数 1
回答已采纳
3回答
我正在尝试用c++实现Karatsuba乘法算法，但现在我只是想让它在python中工作。
下面是我的代码：
def mult(x, y, b, m):
if max(x, y) < b:
return x * y
bm = pow(b, m)
x0 = x / bm
x1 = x % bm
y0 = y / bm
y1 = y % bm
z2 = mult(x1, y1, b, m)
z0 = mult(x0, y0, b, m)
z1 = mult(x1 + x0, y1 + y0, b, m
浏览 1提问于2011-08-15得票数 6
回答已采纳
首先是一些背景知识：
我的编程经验包括一个学期(3个月)的C++和一些高中的QBasic。是的，我看过GMP和Bignum库；从原始代码中很难学到东西，尤其是在不了解程序员意图的情况下。此外，我想学习如何为自己做这件事。
我正在编写一个任意大整数的乘法函数。我使用字符数组来表示这些数字，并在末尾使用+或-作为标记(例如。"12345+"，"31415-")。
我目前正在实现Karatsuba算法。问题是，使用递归和动态内存分配时，该函数比naive方法慢5倍。
我可以使用一些关于如何减少运行时间的提示。
char* dam(char* one, char* tw
浏览 1提问于2011-11-03得票数 6
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
