我有一个128位无符号整数A和一个64位无符号整数B.什么是最快的计算方法A % B- 即将A除以B的(64位)余数？
我希望用C或汇编语言来做这件事,但我需要针对32位x86平台.遗憾的是,我无法利用编译器对128位整数的支持,也无法利用x64架构在单条指令中执行所需操作的能力.
编辑:
谢谢你到目前为止的答案.但是,在我看来,建议的算法会非常慢 - 执行128位到64位除法的最快方法是利用处理器对64位乘32位除法的原生支持吗？有没有人知道是否有办法在一些较小的部门中执行更大的划分？
回复:B多久换一次？
主要是我对一般解决方案感兴趣 - 如果A和B每次都可能不同,你会进行什么计算？
然而,第二种可能的情况是B不会像A那样经常变化 - 每个B可能有多达200个As除以.在这种情况下,你的答案有何不同？
这是(AFAIK)这个一般主题中的一个具体问题.
情况如下:
我有一个基于32位RISC微控制器(NEC V810的变体)的嵌入式系统(视频游戏控制台).我想写一个定点数学库.我读过这篇文章,但随附的源代码是用386汇编编写的,所以它既不能直接使用也不能轻易修改.
V810有内置的整数乘法/除法,但我想使用上面文章中提到的18.14格式.这需要将64位int除以32位int,而V810仅执行(有符号或无符号)32位/ 32位除法(产生32位商和32位余数).
所以,我的问题是:如何使用32位/ 32位模拟64位/ 32位除法(以允许红移的预移位)？或者,从另一种方式来看问题,使用标准的32位算术/逻辑运算将18.14定点除以另一种定义的最佳方法是什么？("最好"意味着最快,最小或两者兼而有之).
代数,(V810)汇编和伪代码都很好.我将从C调用代码.
提前致谢!
编辑:不知怎的,我错过了这个问题 ...但是,它仍然需要一些修改才能超级高效(它必须比v810提供的浮点div快,尽管它可能已经......),因此,我可以随意为我工作,以换取声望点;)(当然,我的图书馆文档中也有用).
我需要的形式的执行计算a 2^m / b,其中a/b接近1,a和b接近2^m和m较大(大于1000).我需要商和余数.我可以用Java做到这一点
BigInteger[] computeScaledRatio(BigInteger a, BigInteger b, int m) {
return a.shiftLeft(m).divideAndRemainder(b);
}
成本大约是将2m位数除以m位数的成本.
有没有办法让这更快？
如果可能的话,我想将成本降低到大约分割两个m位数的成本.
我不在乎结果代码是否更复杂和/或是否需要一些外部库.
我绝望地尝试了以下代码.毫不奇怪,这种表现令人沮丧.
static final double LOG2_10 = Math.log(10) / Math.log(2);
static final BigDecimal TWO = BigDecimal.valueOf(2);
BigInteger[] computeScaledRatio(BigInteger a, BigInteger b, int m) {
int percession = (int) Math.ceil((2 * m) / LOG2_10);
BigDecimal t = new BigDecimal(a).divide(new BigDecimal(b),
new MathContext(percession));
t = t.multiply(TWO.pow(m));
BigInteger q = t.toBigInteger();
BigInteger r …