不用除法怎么求A/3

fallening_cu

Ager 发表于 2012-10-22 02:03
友情提醒

楼主在一楼其实只说了不能用除法；
至于乘法和除法的实现是另外一个问题了。

fallening_cu

Ager 发表于 2012-10-22 02:03
友情提醒

顺便问下，昨天是什么节日啊？在超市有奇怪的松树买，而且晚上邻居在唱歌闹腾了好一阵，不像是普通的周末。

_Rayx

回复 6# Ager


    这个只能算整除的吧？

safedead

GMP有段很NB的代码，求取64位无符号整数对2 ^ 64的乘法逆元
GMP里面涉及除法运算一般都引用这段代码，商就是被除数乘以除数的乘法逆元的结果的高64位
下面这段就是引自mpn/invert_limb.asm的一段注释，数字单位是指令周期，越小越快

C            cycles/limb (approx)       div
C K8,K9:         48                      71
C K10:           48                      77
C P4:           135                     161
C P6 core2:      69                     116
C P6 corei7:     55                      89
C P6 atom:      129                     191

比CPU内置的除法器要快20% ~ 50%左右，详细代码我就不贴了，下载GMP的代码自己看去
涉及的运算是：位移，查表(引用数组)，加法，乘法

mci2004

Ager 发表于 2012-10-21 22:48
经过优化，还可以有一个超级简单的，更加清爽。同上面那个一样，也是用到了一些数学知识，呵呵……经过32-b ...

不懂这个数学知识，能否解释下？

BTW: 大神，你确定这能得到正确的结果吗？

Ager

_Rayx 发表于 2012-10-22 10:19
回复 6# Ager

这个只能算整除的吧？

是唉。

asdmonster

mark liuming

发仔很忙

回复 6# Ager

额，这个代码虽然很简单，但是我没看懂


   

Ager

@mci2004
@发仔很忙

发仔很忙 发表于 2012-10-22 23:26
回复 6# Ager

额，这个代码虽然很简单，但是我没看懂

这样吧 。。。你不妨把这个函数，跟C语言本身所提供的除法运算符（作用在整数上），（将运行结果）比较一下。

在你的平台环境中，实实在在地跑一下，看看结果的正确度到底几何。

确定在结果的正确性上没问题之后，我再来解释原理。这样，你看妥否？

呵呵 ：）

发仔很忙

回复 6# Ager

额，这个数据出错的

，

结果如下：