我想找到一种方法知道整数是否被3或7除而不使用除法,因为它在MIPS汇编中非常慢.
I want to find a way to know if an integer is divided by 3 or 7 without using division, because it is very slow in MIPS assembly.
我做了很多研究,但一无所获.
I have done a lot of research but found nothing.
推荐答案格兰伦德蒙哥马利(Montgomery)要求除数模(c0)为(奇)除数的模/乘逆. (本文的某些部分已得到改进,最近)
There's a method described by Granlund & Montgomery that requires the modular / multiplicative inverse of the (odd) divisor modulo 2**b. (Some parts of this paper have been improved recently)
除数:(d) = 3, 7(奇数)是一个简单的例子.假设使用32位(无符号)算术,取模2**32的反数分别产生2863311531 (0xAAAAAAAB)和3067833783 (0xB6DB6DB7). 此处.
The divisors: (d) = 3, 7 (odd numbers) are an easy case. Assuming 32 bit (unsigned) arithmetic, the inverses modulo 2**32 yield 2863311531 (0xAAAAAAAB) and 3067833783 (0xB6DB6DB7) respectively. There's an online calculator here.
我们还需要qmax = (2**32 - 1) / d值:0x55555555和0x24924924分别.
We also need the qmax = (2**32 - 1) / d values: 0x55555555 and 0x24924924 resp.
要测试32位(无符号)数字(n),请执行一个字乘法-即,丢弃完整64位结果的高位字:q = dinv * n
To test a 32 bit (unsigned) number (n), perform a single word multiply - that is, discard the high word of the full 64 bit result: q = dinv * n
如果(n)可被(d)整除,则(q)必须满足:q * d == n 和 q <= qmax.例如,
If (n) is divisible by (d), then (q) must satisfy: q * d == n and q <= qmax. e.g.,
int is_divisible_by_3 (uint32_t n) { uint32_t q = n * 0xAAAAAAAB; return (q <= 0x55555555 && (q * 3 == n)) }用两个单字乘法替换除法/余数.
Which replaces a division / remainder with a couple of single word multiplications.
并且对于d = 7同样.另外,像gcc这样的现代编译器也会在为MIPS等生成的程序集中对常数除数/模量(例如if (n % 3 == 0) ...)执行类似的优化.
And similarly for d = 7. Alternatively, a modern compiler like gcc will perform a similar optimization for a constant divisor / modulus, e.g., if (n % 3 == 0) ... - in the assembly generated for MIPS, etc.
更多推荐
如何在MIPS汇编中找到无除法或取模运算符的余数
发布评论