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进制的基的具体数值 而这里的移位是可以直接得到最后结果的

gxqcn

上述算法在大整数中就不适用了，因为a仍需进一步处理成目标进制的数。

liangbch

先引用 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等等

gxqcn

上述链接的算法与我的基本一致，但首先要实现10进制的大数算法， 这也就是双进制内核的优势，在进制转换过程中将大数除法转化为大数乘法，效率高多了。

liangbch

这里给出我对3楼算法更详细的描述： 算法描述， step 1. 原始数据以$2^8$进制存放，低字节在前，高字节在后，n个字节的数组，记作B[0][0..n-1] step 2. 以下要进行k=log2(n)趟计算，每次两量合并,R初值为$2^8$,J=1 step 3. 计算B[J][ i]= b[J-1][i*2+1]*R + B[J-1][i*2] (i=0..n/2-1),如果n是奇数，B[J][n/2]==B[J0][n-1], step 4. n=(n+1)/2, R=R*R, J++ step 5. if (n>1) 转 step 3 step 6: 现在目标数组只剩下一个元素，这个数是一个十进制数，将其输出即可。 注： 1. B[J]表示一个数组，第一趟计算时，原数组是B[0],计算结果数组是B[1],第2趟计算时，原数组是B[1],计算结果数组是B[2],依次类推。 2. 在运算过程中，需要计算的数始终是10进制或者$10^k$进制，例如10000进制或者1000000000进制。 对于内存管理，实际上并不需要那么多数组，仅仅需要2个数组即可，第一趟，B[0]因为源数组，B[1] 为目标数组。第2趟则正好相反，B[1] 为源数组。B[0] 为目标数组。 对于数的表示，我的做法是，首先将2进制数表示为$2^29$进制，转化后的十进制表示为$10^9$进制，假如这个数的$2^29$进制表示需要m个DWORD,容易得到，在整个转化过程中，源数组和目标数组需要的空间均不会超过m个DWORD.

liangbch

这个算法（以加代乘）我不是没有考虑过，除了个别的基如$2^16，10$等含有很少的bit1,大部分基都含有较多的1，如此则此种算法需要执行好多指令，效果反而不如直接使用乘法。 另外，即使这种算法有效，也只能提高一个很少的常数因子，可以挖掘的潜力十分有限。

无心人

比如一个小数字（相对的） 则显然，两两归并并不是一个很好的方法 额外的开销造成了还不如传统的算法 这里有个分界点 我想至少要上千才合适的 那小于这个界限的必须用传统的算法了 但传统的算法也是可以加速的啊

gxqcn

这个算法的最大优势有两点： 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比较合适