TLDR，在底部：)
简介： 我正在创建一个用于处理大量数字的基本算术库（加法，减法...）。我面临的问题之一是将这些巨大的二进制数打印为十进制。
我在uint64_t数组中存储了巨大的二进制数。例如
uint64_t a[64] = {0};
现在，目标是在控制台/文件中打印64 * 64位二进制数作为其十进制值。
初始工作： 为了阐述这个问题，我想描述如何打印十六进制值。
int i;
int s = 1;
a[1] = (uint64_t)0xFF;
for(i = s; i>= 0; i--)
{
printf("0x%08llX, ", a[i]);
}
输出：
0x000000FF, 0x00000000,
同样，对于打印OCT值，我只能从a [64]中取LSB 3位，打印与这些位等效的十进制数，向右移3位a [64]的所有位，并继续重复直到a [64]的所有值都已打印。（以反转顺序打印，以使第一个十进制数字保持在右侧）
我可以通过重复此单位算法来打印大小不受限制的二进制十六进制和十进制值，但是我找不到/开发一个十进制的值，可以重复一遍以打印a [64]（或更大的值）。
我想到的是： 我最初的想法是继续减去
max_64 =(uint64)10000000000000000000; //(i.e.10^19)
uint64_t内部最大的10的倍数，a直到内部的值a小于max_64（基本上等于rem_64 = a%max_64），然后使用以下命令打印rem_64值
printf("%019llu",rem_64);
这是数字的第19个十进制数字a。
然后执行类似于（不是代码）的算术运算：
a = a/max_64; /* Integer division(no fractional part) to remove right most 19 dec digits from 'a' */ …我目前正在尝试弄清楚如何以定点表示形式将两个数字相乘。
假设我的数字表示如下：
[SIGN][2^0].[2^-1][2^-2]..[2^-14]
就我而言，数字10.01000000000000 = -0.25.
例如我会怎么做0.25x0.25等等-0.25x0.25？
希望您能帮忙！
我最近学会了Karatsuba乘法.为了完全理解这个概念,我试图用Python编写代码,并将运行时间与经典乘法进行比较.虽然结果是相同的,但karatsuba的执行时间仍然是最低的,尽管我使用的是递归调用.我的做法有什么问题？一些帮助肯定会让我更多地了解算法设计.
最好
J.P
print('Karatsuba multiplication in Python')
x=raw_input("first_number=")
y=raw_input("second_number=")
print('------------------------')
x=int(x)
y=int(y)
import math
import time
def karatsuba(x,y):
x=str(x)
y=str(y)
len_x=len(x)
len_y=len(y)
if(int(len_x)==1 or int(len_y)==1):
return int(x)*int(y)
else:
B=10
exp1=int(math.ceil(len_x/2.0))
exp2=int(math.ceil(len_y/2.0))
if(exp1<exp2):
exp=exp1
else:
exp=exp2
m1=len_x-exp
m2=len_y-exp
a=karatsuba(int(x[0:m1]),int(y[0:m2]))
c=karatsuba(int(x[m1:len_x]),int(y[m2:len_y]))
b=karatsuba(int(x[0:m1])+int(x[m1:len_x]),int(y[0:m2])+int(y[m2:len_y]))-a-c
results=a*math.pow(10,2*exp) + b*math.pow(10,exp) + c
return int(results)
start_time=time.time()
ctrl = x*y
tpt=time.time() - start_time
print x,'*',y,'=',ctrl
print("--- %s seconds ---" % tpt)
start_time=time.time()
output=karatsuba(x,y)
tpt=time.time() - start_time
print 'karatsuba(',x,',',y,')=',output
print("--- %s seconds ---" % tpt)
我实现了 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));
// …我想在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)
结果对比如下： …
使用FFT（快速傅立叶变换）乘法会出现一些问题吗？我好奇。谢谢。