FNT里的取模

l4m2

FNT里面取模很多，你们懂得
那么是不是需要右移变成32位再除（用乘法代替），最后的1再调整
C000 0001>>30=3
1C00 0001>>26=7
0A00 0001>>25=5

liangbch

你是对的。
令c1=0xC0000001,c2=0x1C000001,c3=0x0A000001,则
$1/{c_1}=2863311529.78 / 2^63$
$1/{c_2}=2454267021.06 / 2^60$
$1/{c_3}=3435973816.32 / 2^59$
故，若被除数是a，且右移k1位为32位整数，则在不考虑误差的情况下，有
a/c1 = ( (a >> k1) * 2863311529.78 >> (63-k1) ）
a/c2 = ( (a >> k1) * 2454267021.06 >> (60-k1) ）
a/c3 = ( (a >> k1) * 3435973816.32 >> (59-k1) ）

l4m2

  a % (p+1)
= a % p - (a+1) / (p+1)
有问题吗

liangbch

回2楼，这是标准的做法，所有的以乘代除法，都需要2次乘法，并且需要一次商的调整。2次乘法的花费比1次除法要少，建议你多看看相关的文档，比如http://www.agner.org/optimize。
我10年前看过Apfloat得的中的模运算中的第一次乘法是用浮点乘法做的，误差是小了些，但需要额外的浮点与整数间转换，效率不必直接使用整数快多少。
apfloat的源码可从 http://www.apfloat.org/apfloat/下载.
关于《apfloat源码分析经验交流》请见 http://bbs.csdn.net/topics/60029071

liangbch

Apfloat中的3个模是0x7E000001,0x78000001,0x6C000001
关于以除代乘法，请看本站帖子 http://bbs.emath.ac.cn/thread-521-3-1.html