找回密码
 欢迎注册
查看: 17335|回复: 29

[原创] B计划之二进制十进制相互转化算法

[复制链接]
发表于 2008-10-16 19:49:30 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
部分讨论结果参考
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进制的基的具体数值
而这里的移位是可以直接得到最后结果的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-16 20:52:42 | 显示全部楼层
上述算法在大整数中就不适用了,因为a仍需进一步处理成目标进制的数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-16 21:01:30 | 显示全部楼层
先引用 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...),直到最后只剩下一个,转换完成。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-16 21:08:02 | 显示全部楼层


先别说否定的话
我这里和那个帖子一个显著的不同就是
不再考虑长整数整体转换
而是把基转换的乘除转换成移位和加减法

所以应该考虑的简单的多了
现在的问题是
基如果是2和10
则不是很优秀的选择
所以我想找到个优化的基选择
比如2^32 和 10^8等等
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-16 21:09:16 | 显示全部楼层

回复 3# liangbch 的帖子

上述链接的算法与我的基本一致,但首先要实现10进制的大数算法,
这也就是双进制内核的优势,在进制转换过程中将大数除法转化为大数乘法,效率高多了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-16 21:09:28 | 显示全部楼层
这里给出我对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.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-16 21:17:54 | 显示全部楼层

回复 4# 无心人 的帖子

这个算法(以加代乘)我不是没有考虑过,除了个别的基如$2^16,10$等含有很少的bit1,大部分基都含有较多的1,如此则此种算法需要执行好多指令,效果反而不如直接使用乘法。
  另外,即使这种算法有效,也只能提高一个很少的常数因子,可以挖掘的潜力十分有限。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-16 21:24:30 | 显示全部楼层


比如一个小数字(相对的)
则显然,两两归并并不是一个很好的方法
额外的开销造成了还不如传统的算法
这里有个分界点
我想至少要上千才合适的

那小于这个界限的必须用传统的算法了
但传统的算法也是可以加速的啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-16 21:24:59 | 显示全部楼层

回复 6# liangbch 的帖子

这个算法的最大优势有两点:
1、转换过程不用大数除法,而用大数乘法;
2、尽量转化为高等级乘法,以充分享受O(nlogn)级别的快速算法(如不采用分治法,则优势就体现不出来)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-16 21:28:43 | 显示全部楼层
我想得到一个合适的基数对
(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比较合适
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 16:34 , Processed in 0.052040 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表