我需要编写一个算法(我不能使用任何第三方库,因为这是一个赋值)来划分(整数除法,浮动部分并不重要)非常大的数字,如100 - 1000位数.我找到了http://en.wikipedia.org/wiki/Fourier_division算法,但我不知道这是不是正确的方法.你有什么建议吗？
1) check divisior < dividend, otherwise it's zero (because it will be an int division)
2) start from the left
3) get equal portion of digits from the dividend
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1
5) multiply divisor by 1-9 through the loop
6) when it exceeds the dividend portion, previous multiplier is the answer
7) repeat steps 3 to 5 until reaching to the end
我需要将字节数组中以数字表示的数字除以非标准字节数.它可能是5个字节或1 GB或更多.应使用表示为字节数组的数字进行除法,而不对数字进行任何转换.
我将大整数编码为一个数组size_t.我已经有其他操作工作(加,减,乘); 以及一位数的划分.但是如果可能的话,我想匹配乘法算法的时间复杂度(目前Toom-Cook).
我收集有线性时间算法,用于采用我的红利的乘法逆的各种概念.这意味着我理论上可以在与乘法相同的时间复杂度中实现除法,因为无论如何,线性时间操作通过比较是"无关紧要的".
我的问题是,我该怎么做呢？什么类型的乘法逆在实践中最好？模数64^digitcount？当我将乘法逆乘以我的除数时,我可以推卸计算由于整数截断而丢弃的数据部分吗？任何人都可以提供C或C++伪代码或准确解释应该如何做到这一点？
或者是否存在比基于逆的方法更好的专用除法算法？
编辑:我挖出了上面提到的"反向"方法.在"Art of Computer Programming,Volume 2:Seminumerical Algorithms"的第312页上,Knuth提供了"算法R",它是一种高精度的倒数.他说它的时间复杂度小于乘法的时间复杂度.然而,将它转换为C并测试它并且不清楚将消耗多少开销内存等,直到我对其进行编码,这将花费一些时间,这是非常重要的.如果没有人打败我,我会发布它.
我正在将BigInt课程作为编程练习.它在base-65536中使用2的补码有符号整数的向量(因此32位乘法不会溢出.一旦我完全工作,我将增加基数).
所有基本的数学运算进行编码,其中一个问题:分裂是痛苦的基本算法,我能够创造慢.(对于商的每个数字,它有点像二进制除法......除非有人想看到它,否则我不会发布它.)
而不是我的慢速算法,我想使用Newton-Raphson找到(移位)倒数然后乘以(和移位).我想我已经掌握了基础知识:你给出公式(x1 = x0(2 - x0*除数))一个很好的初始猜测,然后经过一些迭代后,x收敛到倒数.这部分似乎很容易......但是当我尝试将这个公式应用于大整数时,我遇到了一些问题:
问题1:
因为我正在使用整数......好吧......我不能使用分数.这似乎导致x总是发散(x0*除数似乎必须<2)？我的直觉告诉我应该对方程进行一些修改,使其能够整数运算(达到一定的精度),但我真的很难找出它是什么.(我缺乏数学技能在这里打败了我......)我想我需要找到一些等效的等式而不是d有d*[base ^ somePower]？可以有一些方程式(x1 = x0(2 - x0*d))与整数一致吗？
问题2:
当我使用牛顿的公式来找到某些数字的倒数时,结果最终只是一个小部分,低于答案应该是...... ex.当试图找到4的倒数(十进制):
x0 = 0.3
x1 = 0.24
x2 = 0.2496
x3 = 0.24999936
x4 = 0.2499999999983616
x5 = 0.24999999999999999999998926258176
如果我代表基数为10的数字,我希望得到25的结果(并记住将产品右移2).使用一些倒数(例如1/3),您可以在知道足够的准确度后截断结果.但是我怎样才能从上面的结果中得出正确的倒数呢？
对不起,如果这太模糊或者我要求太多了.我查看了维基百科和我在谷歌上可以找到的所有研究论文,但我觉得我正在撞墙.我感谢任何人都能给我的帮助!
...
编辑:算法运行,虽然它比我预期的要慢得多.与我的旧算法相比,我实际上失去了很多速度,即使是数千位的数字......我仍然缺少一些东西.这不是乘法的问题,这是非常快的.(我确实使用Karatsuba的算法).
对于任何感兴趣的人,这是我目前的Newton-Raphson算法的迭代:
bigint operator/(const bigint& lhs, const bigint& rhs) {
if (rhs == 0) throw overflow_error("Divide by zero exception");
bigint dividend = lhs;
bigint divisor = rhs;
bool negative = 0; …请考虑以下代码:
int bn_div(bn_t *bn1, bn_t *bn2, bn_t *bnr)
{
uint32 q, m; /* Division Result */
uint32 i; /* Loop Counter */
uint32 j; /* Loop Counter */
/* Check Input */
if (bn1 == NULL) return(EFAULT);
if (bn1->dat == NULL) return(EFAULT);
if (bn2 == NULL) return(EFAULT);
if (bn2->dat == NULL) return(EFAULT);
if (bnr == NULL) return(EFAULT);
if (bnr->dat == NULL) return(EFAULT);
#if defined(__i386__) || defined(__amd64__)
__asm__ (".intel_syntax noprefix");
__asm__ ("pushl %eax");
__asm__ ("pushl %edx");
__asm__ ("pushf");
__asm__ ("movl %eax, …