擂台：超大整数高精度快速算法-4 （快速计算千万阶乘）
近几个月来，我把精力主要集中于改进大数算法核心乘法部分，终于取得了令人欣喜的进展，
将最最核心的顶级大数乘法算法效率提高了近一倍左右！（代价是手工编写了大量汇编代码）
从现有的数款 CPU 及不同的操作系统的测试来看，在计算“1千万的阶乘”时均提速了 50% 以上，
如10000000!： Factorial_old(t0/s) Factorial_new(t1/s) (t0 - t1)/t1 * 100%
机台A 68.929053 43.584557 58.15%
机台B 48.787876 31.227357 56.23%
机台C 65.850629 42.810574 53.82%
机台D 41.436746 25.617276 61.75%
其中，
机台A —— Windows XP SP2，Intel Pentium 4 CPU 2.93GHz，512MB DDR - 133MHz
机台B —— Windows XP SP2，AMD Athlon 64 Processor 3200+，1GB DDR - 200MHz
机台C —— Windows Vista 64，Intel Pentium 4 CPU 3.00GHz，1GB DDR - 200MHz
机台D —— Windows XP SP2，AMD Athlon 64 X2 Dual Core Processor 4800+，2GB DDR2 - 800MHz
如果大家感兴趣，请从下列两个站点之一下载（169 KB，本链接仅在正式发布前有效）：
http://hugecalc.ik8.com/download/Factorial.rar
http://www.freewebs.com/maths/download/Factorial.rar
欢迎您将测试结果直接发布出来，或填表（我已制作好了 Excel 表）后反馈给我。。。
如果您发现计算“1千万的阶乘”还有更快的程序，请告诉我，必将千分相赠！
//=============================================================================
这是我继2004年连摆的三场“擂台”后，第四次摆“擂台”，
前几次无论是网友还是本人都收获颇丰，但愿这次也会有不俗的效果。
注：前几次“擂台”的链接如下：
http://topic.csdn.net/T/20040510/14/3049738.html
http://topic.csdn.net/T/20040721/19/3197332.html
http://topic.csdn.net/T/20041010/17/3441530.html
近期还有个帖子也非常值得看，是关于汇编优化的，也是这次升级的技术储备之一：
http://community.csdn.net/Expert/TopicView.asp?id=5505130
[解决办法]
恭喜搂主！！！
本来一直有改进大数乘法的想法，无奈精力有限，新的程序始终没有做出来。我的算法出来以后，是否可胜楼主，没有确切把握。但在小规模的情况下，预计应该和楼主相当，没准还能超越楼主。小规模指在计算乘法时，由于被乘数，乘数相对较短，FFT,FNT无法发挥作用的情况下。典型值为：如计算1万的阶乘。
另外，请问搂住，据你的经验，在计算大数阶乘时，基于10^9的算法和基于2^32的乘法，哪一更有优势。
[解决办法]
都是高手，占个楼学习
[解决办法]
mark
[解决办法]
ren guo liu ming
[解决办法]
建议楼主把阶乘化为幂运算，其公式随便一本数论书上都有，我曾经做过，速度能极大幅度的提高
[解决办法]
现在的显卡上的GPU运算性能超过CPU很多；不知道有没有人研究一下大整数乘法移植到GPU的实现；
当前快速傅立叶变换(FFT)已经有人移植到了GPU上(见《GPU精粹2》或者http://gamma.cs.unc.edu/GPUFFTW/ 等等)，那么大整数乘法运
算移植到GPU也就有了可能；
但也有一些问题待求证:
1.当前GPU支持的最高的精度是32bit单精度浮点数运算，对于大整数乘法是否精度足够；
2.GPU是否能够正确计算(按精度要求，或者符合IEEE标准)，GPU计算颜色时如果有小的误差，不会有什么问题，但对于大整数乘法
运算却可能有很大的问题(问题2应该不严重，因为GPU厂商也正在争夺通用计算领域)；
3.是否能减小输入的数据的值域范围使32bit浮点计算也精度足够；
或者能否开发一个算法来用多次单精度浮点运算模拟出更高精度的浮点运算；
另外，把数论变换移植到GPU不知道是否可行
（瞎扯：随着能够集成的晶体管越来越多，而CPU频率提升的停滞不前，流式计算一定会在CPU里占有重要地位；对于性能提升，流式核心比多x86核心能更好地利用晶体管）
[解决办法]
曾经有人给我一个网站，专门研究计算的，可惜忘记了，速度就超快。
[解决办法]
n!=(p1^[n/p1])*(p2^[n/p2])*.....*(pm^[n/pm]),公式大致是这个样子，p1,....,pm依次为小于n的素数，用这个公式算很快，乘法的次数会大幅度的减少
[解决办法]
Y___Y(一叶障目) ( ) 信誉：100 Blog 加为好友 2007-07-12 10:36:17 得分: 0
建议楼主把阶乘化为幂运算，其公式随便一本数论书上都有，我曾经做过，速度能极大幅度的提高
==哪个公式？
[解决办法]
据我所知，搂主在很早以前,就提到了Y___Y(一叶障目) 的那个算法,即将n!分解质因素再相乘.这个算法能够提升的速度大约在2倍以上,但应该不超过4倍.
[解决办法]
学习
[解决办法]
我在《千分求汇编优化：UInt96x96To192(...)》帖子回复了一段，这里拷贝过来,希望有用：
====================================================================================================
这里的函数还没有考虑优化内存预读和禁止写缓存；
这两个优化对于大数乘法应该有用(我没有测试过)；对于这里的简单测试缓存优化几乎没有
用，因为这里的测试方式CPU默认缓存策略很适合，但在操作大量内存的大数乘法中，应该
考略缓存策略；
具体实现方法：
预读： 在真正使用到源数据之前几百个ＣＰＵ周期之前（时间由内存和ＣＰＵ的速度差异
决定）手工读一次其内存数据，也就是将间隔６４字节（当前CPU的缓存行大小）内存数据
其中的一个加载一次；
实现方式： a: 手工预读伪代码 (假设源数据在esi寄存器)
for (i;i <BestBufSize;i+=64） //预读数据总大小应该小于CPU的缓存
mov eax,[esi+i]
开始处理esi到esi+BestBufSize的源数据
b:使用专用CPU预读指令prefetch*替换mov eax,[esi+i]
这类指令prefetchnta、prefetcht0、prefetcht1、prefetcht2等作
用是让CPU默认预读、或者指定预读数据到一级缓存或二级缓存...
a的方案比较通用，不需要CPU支持专用的预读指令，而且在我以前的P4核心赛扬
上a方案比b方案还快；
b方案对后来的CPU更友好一些，在我的AMD64X2上b比a快；
禁止写缓冲：当需要写入内存的数据比较多，或不需要立即再次访问写的数据的时候；可
以使用禁止写缓冲优化策略，减少缓冲区污染；
实现方式：使用CPU提供的流式写内存指令MOVNT*
这些指令包括:MOVNTQ、MOVNTI（SSE3）、MOVNTDQ、MOVNTPD,MOVNTPS,
（MOVNTSD、MOVNTSS在SSE4指令集支持）等等
这些指令针对了不同的寄存器类型或者寄存器里的不同数据类型
(sfence指令配合用于刷新写缓存，一般在处理完一块数据以后使用)
完整的缓存优化还包括 把函数内的局部数据布局到64byte的缓存行，寄存器不够用时可以使用
局部堆栈变量(局部变量)来代替(特别是对于常量)
不建议使用各处分布的全局变量，建议可以集中放到一个结构里，从而使他们占用相同的缓存行。。。
(对于内存地址数值给缓存时造成的hash碰撞（CPU的缓存行路数有限），如果发生也要考略避过(发生的情况比较少)，...)
大整数运算中乘法是最核心的部分，而大整数乘法复杂度为O(N*log(N))，缓存优化所能起的效果需要楼主测试一下
======================================================================================================
另外，对于动态内存，建议自己写一个内存池的内存分配器
看了楼主的程序，发现还没有针对多核CPU做优化，可以考略加进去 (简单实现的话我的blog里有一个把任务动态分配到多CPU并行执行的C++类)
建议楼主用这套库实现计算PI (使用4次收敛的博尔温迭代式、或者2次收敛的几何迭代式，我可以提供公式)
这样应该很有意义，很可能大家会把你的程序作为测试CPU能力的一个衡量标准和基准测试
[解决办法]
其实在计算的过程中采取内存一次分配，不必多次分配释放来浪费时间，因为可以运用斯特林公式准确计算出最终的位数，但这种方法对速度提升的幅度有限
[解决办法]
m
[解决办法]
好的。
[解决办法]
阶乘有个估算公式吧？我去找找！
[解决办法]
以下我Factorial7(noFFT)和我同算法版本calcFac35(2004年编译）的速度对比,可以看出,在计算5000!到200000!时,gxq的程序分别比我的程序快 15%,22%,28%,51%,65%.
program 5000! 10000! 20000! 50000! 100000!200000!
calcFac350.00655 0.022364 0.076063 0.373486 1.2580544.174346
Factorial7(noFFT) 0.005665 0.018344 0.059229 0.26871 0.8317842.5311
1.151.219 1.284 1.389 1.5121.649
BS自己一下,我先前以为Factorial7(noFFT)这个程序使用了SSE2指令优化了呢,不使用SSE2指,竟比我的程序快这么多,的确很厉害,这段时间也将尝试重新编写乘法内核,看看能否达到或超越了楼主的程序.顺便也尝试使用SSE2指令优化,看看速度可以提高多少.
[解决办法]
我不这么认为：你所说的常规算法大概指硬乘法，它是分治法的基础，如果硬乘法速度改进了，将根本性的改变大数乘法的速度。
在硬乘法中，我估计，使用SSE2指令在PIV电脑上，可提速约100%左右。
字节对齐问题，可使用非对齐的指令，将数装入到XMM寄存器，然后使用 PSHUFD指令重排。
整数除法问题，除法指令的使用频度时很低的，保持原来的算法即可，重要的是：调用一次SSE2指令可执行2组 32bit*32bit=64bit的乘法，或者 2组64bit的加法。
估计仅仅是估计，实际效果如何还不好说，等我做出来后，就知道了（速度提升的幅度究竟有多大）。
[解决办法]
For numIndex As Integer = 2 To number
carry = 0
For arrayIndex = 0 To arrayTail
midProduct = product(arrayIndex) * numIndex + carry
carry = midProduct \ DIVISOR
product(arrayIndex) = midProduct - DIVISOR * carry
' Console.WriteLine(product(arrayIndex))
Next arrayIndex
Do While carry <> 0
product(arrayIndex) = carry Mod DIVISOR
carry = carry \ DIVISOR
arrayIndex += 1
Loop
arrayTail = arrayIndex - 1
Next numIndex
我的代码 想让大家能多多修改指正 时间与搂住的比天壤之别 只不过要交作业 就想求求大家帮忙
[解决办法]
运行时间： v7版双核 : v7版四核 = 2 : 1
运行时间： v7版单核 : v7版双核 = 3 : 2
双核到四核提升100%，而单核到双核才提升50% 这里面的原因是什么？ 有没有分析？
是算法原因?(从上面的比值看不像啊) 还是并行任务粒度太小的原因?
我测试过在我的AMDx2 3600+(双核)上一次并行执行的开销平均在1.3万个CPU周期左右，也就是分割的最小任务量至少要大于1.3万个CPU周期以上才能开始从双核并行上获益
(最小任务量时间估计=13000/2G 秒 =0.0065ms =6.5us 建议的最小单个任务量需要比这个估计值大很多才能获得最大的收益)
[解决办法]
1. 我分析了一下Calcfac35(2004年）较 Factorial7(noFFT) 速度较慢的几点原因：
1) 乘法核心汇编优化深度不够。
2) 通过积累加和 除以 1000000000，求 本位 和 进位时，效率不高。
3) 阶乘算法的效率不高，主要是没有尽可能做到 相乘的两个数尽可能长度相当。
4) 没有正对大数的平方作优化。
2. 通过改进这4点，我相信，我应该能都做到使用同等的算法，速度达到或超过 Factorial7(noFFT)。
3。目前已经完成的工作:
1)深度优化乘法核心，采用循环展开的方法，大大减小了跳转指令的执行。以 18 * 18 (被乘数的长度是18，乘数的长度是18）为例，采用传统方法需要 18*18（内循环）+18（外循环），而我现在的程序大约只需要20次左右的跳转指令。采用这种方法优化，使得代码很多，因此 手写代码 很麻烦，我采用了程序（自己编写）生成汇编代码的方法。在采用深度汇编优化时，尽量少访问RAM,一个形象的叫法是 "数据不落地 ",(数据在较长的一段时间,仅仅在寄存器中传递,我称之为 "数据在天上飞 " ,将寄存器中的数据保存到RAM(非必须的),我称之为数据落到地上)
2)采用查表法 和 除法指令相结合的方法， 计算 1个64bit 或者多至67bit的数 除以1000000000的商和余数，仅仅需要一次查表和一次除法，速度提高将近一倍。
4.进一步,可用SSE2指令重写乘法的核心部分,预计对于PIV CPU,速度可再提高一倍.
------解决方案--------------------
留个名, 另外, 《千分求汇编优化：UInt96x96To192(...)》那个帖子我也看过了, 曾经试图对指令配对和优化, 似乎都没有楼主的快, 不知何解?
[解决办法]
我玩了2年(中间上班大概1年)的WoW, 最近抛开了游戏, 是你的《千分求汇编优化：UInt96x96To192(...)》那个帖子让我重新燃起了写代码的激情, 最近在写黑白棋方面的程序, 一直以来我也想用SSE, SSE2优化黑白棋BitBoard的运算, 但最近发现效果不太明显
我下了你的程序, 非常快, 千分优化那个帖子我大概是6月中旬从你给的我email里看到的(email很少看, 抱歉), 今天也不小心也进到了liangbch的blog, 很高兴你们能取得如今的成绩, 从那个帖子来看, 你学习新东西的能力和运用新知识的能力都是超强的, 相当佩服
UInt96x96To192那段代码, 不过我是手工调整(微调), 或是用软件优化(不过是个Demo, 只能针对Pentium III优化), 速度都及不上你的那段代码, 从某种角度来说, 我觉得总还是可以优化一下的, 下面贴某软件优化的结果, 也许不适合现在的CPU, 仅供参考:
//
// Target CPU: Intel Pentium III
// Optimization: Accurate
// Target Compiler: Microsoft Visual C++ 6 with Processor Pack
//
/*
V5:V4:V3:V2:V1:V0
-----------------------------
L2*R0:L0*R0 <-- xmm0
L2*R1:L0*R1 <-- xmm1
L2*R2:L0*R2 <-- xmm2
L1*R2:L1*R0 <-- xmm3
L1*R1 <-- xmm4
*/
_declspec(naked) /* 该版算法可能有点诡异哦:) */
void UInt96x96To192_SSE2_GxQ_org3( UINT32 *p, const UINT32 *pL, const UINT32 *pR )
{
__asm {
mov EDX, dword ptr[esp + 0Ch] // EDX = dword ptr[esp + 0Ch]
mov EAX, dword ptr[esp + 08h] // EAX = dword ptr[esp + 08h]
movq mm0, dword ptr[edx] // pRight = memory dword ptr[edx]
movq mm1, dword ptr[eax] // pLeft = memory dword ptr[eax]
pshufw mm2, mm0,0x55 // Shuffle pRight into xmm1
mov ECX, dword ptr[esp + 04h] // ECX = dword ptr[esp + 04h]
movq mm3, mm2 // xmm4 = xmm1
pmuludq mm2, mm1 // xmm1 = xmm1 * pLeft
pshufw mm4, mm0,0x00 // Shuffle pRight into xmm0
pmuludq mm4, mm1 // xmm0 = xmm0 * pLeft
pshufw mm5, mm0,0xAA // Shuffle pRight into xmm2
pmuludq mm5, mm1 // xmm2 = xmm2 * pLeft
pshufw mm6, mm1,0x55 // Shuffle pLeft into xmm3
pmuludq mm3, mm6 // xmm4 = xmm4 * xmm3
pmuludq mm6, mm0 // xmm3 = xmm3 * pRight
movq dword ptr[ecx], mm4 // memory dword ptr[ecx] = xmm0
psrlq mm4, 4 // Shift xmm0 right by 4
movq mm0, mm2 // pV4_1 = xmm1
psrlq mm2, 4 // Shift xmm1 right by 4
paddq mm0, mm4 // pV4_1 = pV4_1 + xmm0
psrlq mm4, 4 // Shift xmm0 right by 4
paddq mm4, mm2 // xmm0 = xmm0 + xmm1
paddq mm4, mm5 // xmm0 = xmm0 + xmm2
psllq mm5, 4 // Shift xmm2 left by 4
paddq mm0, mm6 // pV4_1 = pV4_1 + xmm3
paddq mm5, mm0 // xmm2 = xmm2 + pV4_1
psrlq mm6, 4 // Shift xmm3 right by 4
paddq mm4, mm6 // xmm0 = xmm0 + xmm3
paddq mm4, mm3 // xmm0 = xmm0 + xmm4
psllq mm3, 4 // Shift xmm4 left by 4
paddq mm5, mm3 // xmm2 = xmm2 + xmm4
movq dword ptr[ecx + 04h], mm5 // memory dword ptr[ecx + 04h] = xmm2
psrlq mm5, 4 // Shift xmm2 right by 4
movq mm0, mm5 // temp = xmm2
psubq mm0, mm4 // temp = temp - xmm0
pslld mm0, 32 // Shift temp left by 32
psrld mm0, 32 // Shift temp right by 32
paddq mm4, mm0 // xmm0 = xmm0 + temp
psubd mm5, mm4 // xmm2 = xmm2 - xmm0
psrlq mm5, 63 // Shift xmm2 right by 63
psllq mm5, 8 // Shift xmm2 left by 8
paddq mm4, mm5 // xmm0 = xmm0 + xmm2
movq qword ptr[ecx + 08h], mm4 // memory qword ptr[ecx + 08h] = xmm0
emms // Empty MMX state
}
}
[解决办法]
晕, 上面那个不对, SSE的版本是这个, 他是针对MMX的优化, 也许真的不适合, 参考
_declspec(naked) /* 该版算法可能有点诡异哦:) */
void UInt96x96To192_SSE2_GxQ_org3( UINT32 *p, const UINT32 *pL, const UINT32 *pR )
{
__asm
{
mov edx, dword ptr[esp + 0Ch] // EDX = dword ptr[esp + 0Ch]
mov eax, dword ptr[esp + 08h] // EAX = dword ptr[esp + 08h]
movdqa xmm0, dword ptr[edx] // pRight = memory dword ptr[edx]
movdqa xmm1, dword ptr[eax] // pLeft = memory dword ptr[eax]
pshufd xmm2, xmm0, 0x55 // Shuffle pRight into xmm1
mov ecx, dword ptr[esp + 04h] // ECX = dword ptr[esp + 04h]
movq xmm3, xmm2 // xmm4 = xmm1
pmuludq xmm2, xmm1 // xmm1 = xmm1 * pLeft
pshufd xmm4, xmm0, 0x00 // Shuffle pRight into xmm0
pmuludq xmm4, xmm1 // xmm0 = xmm0 * pLeft
pshufd xmm5, xmm0, 0xAA // Shuffle pRight into xmm2
pmuludq xmm5, xmm1 // xmm2 = xmm2 * pLeft
pshufd xmm6, xmm1, 0x55 // Shuffle pLeft into xmm3
pmuludq xmm3, xmm6 // xmm4 = xmm4 * xmm3
pmuludq xmm6, xmm0 // xmm3 = xmm3 * pRight
movd dword ptr[ecx], xmm4 // memory dword ptr[ecx] = xmm0
psrldq xmm4, 4 // Shift xmm0 right by 4
movdqa xmm0, xmm2 // pV4_1 = xmm1
psrldq xmm2, 4 // Shift xmm1 right by 4
paddq xmm0, xmm4 // pV4_1 = pV4_1 + xmm0
psrldq xmm4, 4 // Shift xmm0 right by 4
paddq xmm4, xmm2 // xmm0 = xmm0 + xmm1
paddq xmm4, xmm5 // xmm0 = xmm0 + xmm2
pslldq xmm5, 4 // Shift xmm2 left by 4
paddq xmm0, xmm6 // pV4_1 = pV4_1 + xmm3
paddq xmm5, xmm0 // xmm2 = xmm2 + pV4_1
psrldq xmm6, 4 // Shift xmm3 right by 4
paddq xmm4, xmm6 // xmm0 = xmm0 + xmm3
paddq xmm4, xmm3 // xmm0 = xmm0 + xmm4
pslldq xmm3, 4 // Shift xmm4 left by 4
paddq xmm5, xmm3 // xmm2 = xmm2 + xmm4
movd dword ptr[ecx + 04h], xmm5 // memory dword ptr[ecx + 04h] = xmm2
psrldq xmm5, 4 // Shift xmm2 right by 4
movdqa xmm0, xmm5 // temp = xmm2
psubd xmm0, xmm4 // temp = temp - xmm0
psllq xmm0, 32 // Shift temp left by 32
psrlq xmm0, 32 // Shift temp right by 32
paddq xmm4, xmm0 // xmm0 = xmm0 + temp
psubusb xmm5, xmm4 // xmm2 = xmm2 - xmm0
psrlq xmm5, 63 // Shift xmm2 right by 63
pslldq xmm5, 8 // Shift xmm2 left by 8
paddq xmm4, xmm5 // xmm0 = xmm0 + xmm2
movdqu qword ptr[ecx + 08h], xmm4 // memory qword ptr[ecx + 08h] = xmm0
ret // Empty MMX state
}
}
[解决办法]
wa
[解决办法]
mark
[解决办法]
Windows XP SP2 是 32bit 还是 64bit ?
[解决办法]
好久没人回复了，顶一个。
我前面提到 "4.进一步,可用SSE2指令重写乘法的核心部分,预计对于PIV CPU,速度可再提高一倍 "
现在总算有了一个实际的数据，我将我的硬乘法函数中的 92%的乘法和累加部分 用SSE2改写后，在PIV2.6上运行,速度提高了75%，估计若将所有的乘法和累加部分改写后，速度可达到ALU版本的188%.
不幸的是:SSE2版本在PM1.7上运行,速度反而比ALU版本慢20%.
附 函数原型：
void Dec_BaseMul_SSE2(DWORD *p,DWORD *a,DWORD *b,int a_len,int b_len);
数组a[]表示被乘数，长度为a_len
数组b[]表示 乘数， 长度为b_len
数组p[]表示 积， 长度为a_len+b_len
数的表示采用10^9进制(即a[],b[],p[]中的每个元素e,总是满足 0 <=e <1000000000)，高位在前，低位在后
[解决办法]
下面给出我用SSE2指令优化大数乘法的结果，
1。函数原形：
struct _mulPara_ST
{
DWORD *p;
DWORD *a;
DWORD *b;
DWORD a_len;
DWORD b_len;
DWORD carry[3];
};
void _DEC_BaseMul_ALU(struct _mulPara_ST *p);
void _DEC_BaseMul_SSE2(struct _mulPara_ST *p);
2。速度提升结果：
测试时选取a_len 等于 b_len,
当a_len 接近64 且为奇数时：_DEC_BaseMul_SSE2 的速度是 _DEC_BaseMul_ALU 的189%。
当a_len 接近64 且为偶数时：_DEC_BaseMul_SSE2 的速度是 _DEC_BaseMul_ALU 的199%。
3。接下来我将要做一个测试，看看这两个函数比我 2004年版的calcfac35.exe 中使用的那个硬乘法函数快多少，测试结果将在1周内给出。
[解决办法]
mark
[解决办法]
首页看不到这个帖子了，顶一个。
通报一下进展情况：
1。硬乘法版本已定稿（包括ALU版本和SSE2版本）从2005年到现在，写了12个使用硬乘法的大数乘法版本，最新的版本作了彻底的优化，已接近极限，其速度和代码量达到一个平衡，宣布定稿。硬乘法ALU版本的函数的速度 较2004年calcfac35.exe使用的那个有了明显的提高(当时的那个版本也是竭尽全力搞出来的，100%的汇编代码,在当时看来已经很满意)。
1。测试表明，在PIV2.6G 上运行, 目前的ALU版本较2004年版的那个快 23%左右; 在PM1.6G 上运行，目前的版本比2004年版的快了40%。下面是测试数据。
速度比1：指PIV 2.6电脑上，现有的ALU版本与2004年版本的速度关系
速度比2：指PM 1.7电脑上， 现有的ALU版本与2004年版本的速度关系
乘数长度 速度比1 速度比2
16 1.278 1.418
32 1.227 1.398
48 1.232 1.395
64 1.238 1.401
2.硬乘法的计算平方的ALU版本已完成,测试表明,在计算长度为18-128时,可比普通的算法快20%-50%.令人不解的是我的算法从理论上应该比使用普通算法计算近100%,但实际表现却差很多,计算长度达到128,也仅比普通算法快55%左右.
3.目前正在做 使用分治法的乘法函数,受GMP启发,新的版的功能将有所增强,对参加运算的两个数的长度限制更少.
[解决办法]
都是高手~，进来学习~！
[解决办法]
楼主过奖了，2004/2005年版本的乘法核心的优化并未达到极限，只是当时较满意而已。2006年写的大数乘法核心(我从未发表)和现在的版本性能没有多大的区别，但是当时那个版本代码量很大，我不是很满意。现在终于找到了一个即让程序跑得快又让代码量不至于太大的方法，遂宣布定稿。今年另一个重要的收获是学会了用 SSE2 指令计算大数乘法，这得益于楼主的那个“ 千分求汇编优化：UInt96x96To192”的帖子。
相比2004年的大数乘法核心，当前版本的汇编优化的主要方法是循环展开，通过循环展开减少了指令执行的次数，也减少了跳转指令的执行，这个技术并不是很复杂，不涉及算法和数学理论。除了规约(求本位和进位)以外,所用的指令基本和以前一样，并未使用其它等价的指令.不过,规约这块儿并非瓶颈.
By the way, 楼主和shines对我的博客给予了肯定,不胜荣幸,这里表示感谢,不过我的博客对这一专题只是开了个头,等这个擂台结束了,我的算法也更加成熟了,我会继续后续的文章.
[解决办法]
楼主牛B斯,赞一个,不知道俺这本科小鸟啥时候能达这级别
[解决办法]
to: gxqcn
这个多线程错误比较奇怪了，我也有一些用它的并行程序，在多核(AMD64x2和酷睿2)上都没有遇到问题；
也许是我的应用中测试时间或次数不够；不过我自己后来用的代码改成了临界区的实现，应该不会有这个问题了;
根据你的测试情况，我把blog上的代码也更新一下，避免其他人也遇到这问题；
[解决办法]
你的软件不是免费的吗？:)
[解决办法]
写成一篇《大整数算法的计算机实现》应该可以在二级学术期刊上发表，
诸如《计算机工程与科学》、《计算机工程与应用》、《计算机应用与软件》等等。
如果理论上没有新颖之处，想在一级学术期刊上发表是比较困难的，
不过也可以试试，《计算数学》、《计算机学报》等。
[解决办法]
可以看看这个： 那些杂志好发文章（计算机类）？_百度知道 (http://zhidao.baidu.com/question/16682306.html)
[解决办法]
道一声，楼主辛苦了。
搂主可将这个帖子续下去。我等可以继续通报进展情况。
