coffee的日常吧 关注:25贴子:2,218
  • 13回复贴,共1

2015.08.22:决定给对数器换个算法,以前的太慢了

只看楼主收藏回复

为了新算法,啃了一段时间cordic算法,终于搞懂了。结合一些资料,琢磨出了以下的算法
根据欧拉公式有

将求自然对数的问题转换成求反双曲正切
那么就可以用cordic算法算出反双曲正切
设置x1=1, y1=(q-1)/(q+1), z1=0
代入一下方程进行旋转

多次旋转后,
arctanh((q-1)/(q+1))≈z
则lnq≈2z
因为arctanh(2^-0)=∞,所以n就从1开始了。因此z只能收敛到1左右。。也就是说
计算lnq, q只能小于e。。
根本不能满足。。
然后我发现如果在二进制的背景下将公式改写成求log2(q)的公式,z的值就可以轻易扩展。
将q向小方向移m位得到q', 使q'小于2大于等于1
同样
设置x1=1, y1=(q'-1)/(q'+1), z1=0

log(2)(q')≈2z
log(2)(q)≈2z+m
这样就可以轻易扩展。
that's all
通过一次除法,和一堆加减法即可计算出任意位数的log(2)(x)
我脑补了下这个对数器在mc中的样子,感觉形状绝对很不友好
然而我弟最近这几天老缠着我,根本没法做。所以我就先把算法放出来造福社会。
以前那个算法是用初中知识做的。。延迟略大,以后有机会在讲


IP属地:北京1楼2015-08-22 22:11回复
    对了,还有根据换底公式,又可以计算任意底的对数


    IP属地:北京2楼2015-08-22 22:14
    收起回复
      如果再突破了2^x或是e^x的运算,就可以攻克下开任意方了
      因为 log(2)(n√x)=log(x)/n
      所以 n√x=2^(log(x)/n)
      我记得有e^x的cordic算法,因为e^x=sinh(x)+cosh(x),但是还没有深入研究。。但是估计会受到收敛的限制


      IP属地:北京3楼2015-08-22 22:21
      回复
        发现公式写错了orz....
        修改:
        如果y大于0 d=-1
        如果y小于0 d=1
        其余不变


        IP属地:北京4楼2015-08-24 17:04
        收起回复
          卧槽。。。突然发现y(n+1)和x(n+1)写反了。。


          IP属地:北京5楼2015-08-24 17:24
          收起回复
            是yn 与xn的位子写反。。


            IP属地:北京6楼2015-08-24 23:10
            回复
              补充:去找了下,cordic反曲三角函数里的增益因子约为0.8297816,校模因子为它的倒数。(我自己懒得算了


              IP属地:北京7楼2015-08-24 23:17
              回复
                楼主我觉得你有能力加入这个群


                IP属地:福建8楼2015-08-25 10:29
                收起回复
                  我其实不知道双曲三角有什么用...


                  IP属地:上海9楼2015-09-20 16:43
                  回复
                    http://tieba.baidu.com/p/4075916283改进后的算法


                    IP属地:北京12楼2015-10-01 17:02
                    回复