B计划之二进制十进制相互转化算法
部分讨论结果参考http://bbs.emath.ac.cn/thread-521-1-1.html
关于二进制长整数转十进制
今天突然有了新的想法
1、考虑10000
10000 = (10011100010000)2 = 2^4 + 2^8 + 2^9 + 2^10 + 2^13
则乘以10000可以转化成移位和加减法的操作共7步
10000 a
(a << 4) = 2^4a
(a << 4) << 4 = 2^8a
((a << 4) << 4) << 3 = 2^11a
(((a << 4) << 4) << 3) << 2 = 2^13 a
2^13 a + 2^11 a - 2^8 a + 2^4 a = 10000 a
除以10000则有点复杂了
1 / 10000 = 1/2^14 + 1/2^15 + 1/2^17 + 1/2^21 + 1/2^22 + 1/2^24 + 1/2^28 + 1/2^29 + 1/2^31 ... //这里似乎存在问题，要重新演算
每次三个幂n, n + 1, n + 3，n每次递增7
看需要达到多大精度
假设到2^32
则
a / 10000 =
a1 = a >> 14
a2 = a >> 21
a3 = a >> 28
a / 10000 = a1 + a1 >> 1 + a1 >> 3 + a2 + a2 >> 1 + a2 >> 3 + a3 + a3 >> 1 + a3 >> 3
需要17步
可能不如转化成乘法方便
但乘法必须要限定2进制的基的具体数值
而这里的移位是可以直接得到最后结果的 上述算法在大整数中就不适用了，因为a仍需进一步处理成目标进制的数。 先引用 boxer_tony 在 http://topic.csdn.net/u/20081007/20/4c270c1a-d170-4fab-a3f8-7585a7bb86b4.html 贴子中给出的算法。
可以使用类似归并的方法来把2进制转换为10进制：
（1）从低位到高位（以字节位单位或者更多也可以），两两合并成一个十进制数。假设以字节为单位，此时合并的时候，基数是2^8
（2）继续不断合并（当然基数也是不断改变2^16,2^32...），直到最后只剩下一个，转换完成。 :)
先别说否定的话
我这里和那个帖子一个显著的不同就是
不再考虑长整数整体转换
而是把基转换的乘除转换成移位和加减法
所以应该考虑的简单的多了
现在的问题是
基如果是2和10
则不是很优秀的选择
所以我想找到个优化的基选择
比如2^32 和 10^8等等
回复 3# liangbch 的帖子
上述链接的算法与我的基本一致，但首先要实现10进制的大数算法，这也就是双进制内核的优势，在进制转换过程中将大数除法转化为大数乘法，效率高多了。 这里给出我对3楼算法更详细的描述：
算法描述，
step 1. 原始数据以2^8进制存放，低字节在前，高字节在后，n个字节的数组，记作B
step 2. 以下要进行k=log2(n)趟计算，每次两量合并,R初值为2^8,J=1
step 3. 计算B[ i]= b*R + B (i=0..n/2-1),如果n是奇数，B==B,
step 4. n=(n+1)/2, R=R*R, J++
step 5. if (n>1) 转 step 3
step 6: 现在目标数组只剩下一个元素，这个数是一个十进制数，将其输出即可。
注：
1. B表示一个数组，第一趟计算时，原数组是B,计算结果数组是B,第2趟计算时，原数组是B,计算结果数组是B,依次类推。
2. 在运算过程中，需要计算的数始终是10进制或者$10^k$进制，例如10000进制或者1000000000进制。
对于内存管理，实际上并不需要那么多数组，仅仅需要2个数组即可，第一趟，B因为源数组，B 为目标数组。第2趟则正好相反，B 为源数组。B 为目标数组。
对于数的表示，我的做法是，首先将2进制数表示为$2^29$进制，转化后的十进制表示为$10^9$进制，假如这个数的$2^29$进制表示需要m个DWORD,容易得到，在整个转化过程中，源数组和目标数组需要的空间均不会超过m个DWORD.
回复 4# 无心人 的帖子
这个算法（以加代乘）我不是没有考虑过，除了个别的基如$2^16，10$等含有很少的bit1,大部分基都含有较多的1，如此则此种算法需要执行好多指令，效果反而不如直接使用乘法。另外，即使这种算法有效，也只能提高一个很少的常数因子，可以挖掘的潜力十分有限。 :)
比如一个小数字（相对的）
则显然，两两归并并不是一个很好的方法
额外的开销造成了还不如传统的算法
这里有个分界点
我想至少要上千才合适的
那小于这个界限的必须用传统的算法了
但传统的算法也是可以加速的啊
回复 6# liangbch 的帖子
这个算法的最大优势有两点：1、转换过程不用大数除法，而用大数乘法；
2、尽量转化为高等级乘法，以充分享受O(nlogn)级别的快速算法（如不采用分治法，则优势就体现不出来）。 我想得到一个合适的基数对
(2^a, 10^b)
满足
1、2^a > 10^b
2、2^a < 10^(2b)
3、10^b的二进制表示1的数量较少
1/10^b的二进制循环节简单，非0首长度a个连续的二进制串中1的数量较少
4、相对当前32， 64， 128位的计算机能处理的长度来说，a比较合适