最优化的方式在C模数计算 [英] Most optimized way to calculate modulus in C
问题描述
我已经尽量减少C.计算模成本
说我有一个数x，n是将分X
I have minimize cost of calculating modulus in C. say I have a number x and n is the number which will divide x
当n = = 65536（这恰好是2 ^ 16）：
when n == 65536 (which happens to be 2^16):
模= X％N（11汇编指令，由GCC生产）
或结果
MOD = X＆放大器;为0xFFFF，它等于模= X＆放大器; 65535（4汇编指令）
mod = x % n (11 assembly instructions as produced by GCC)
or
mod = x & 0xffff which is equal to mod = x & 65535 (4 assembly instructions)
所以，GCC不优化就到这个程度。
so, GCC doesn't optimize it to this extent.
在我的情况下，n是不是X ^（INT），但最大的素数小于2 ^ 16这是65521
In my case n is not x^(int) but is largest prime less than 2^16 which is 65521
我表现出对n == 2 ^ 16位运算可以优化计算。什么位运算可我preform当n == 65521计算模量。
as I showed for n == 2^16, bit-wise operations can optimize the computation. What bit-wise operations can I preform when n == 65521 to calculate modulus.
推荐答案
首先，确保你在寻找优化code绘制的结论什么GCC是生产前（并确保这个特殊的前pression真正需要优化）。最后 - 不计的指示提请你的结论;它可能是一个11指令序列可以预期比更短序列，其包括一个div指令执行更好
First, make sure you're looking at optimized code before drawing conclusion about what GCC is producing (and make sure this particular expression really needs to be optimized). Finally - don't count instructions to draw your conclusions; it may be that an 11 instruction sequence might be expected to perform better than a shorter sequence that includes a div instruction.
此外，您还不能断定因为
Also, you can't conclude that because x mod 65536 can be calculated with a simple bit mask that any mod operation can be implemented that way. Consider how easy dividing by 10 in decimal is as opposed to dividing by an arbitrary number.
与所有出的方式，你可以使用一些神奇数字技术，从亨利·沃伦的黑客的喜悦书：
With all that out of the way, you may be able to use some of the 'magic number' techniques from Henry Warren's Hacker's Delight book:
- http://www.hackersdelight.org/
- http://www.hackersdelight.org/magic.htm
有是一个补充章节包含计算所得的余数，而不计算商的两种方法的网站！ ，你可能会发现一些使用。首届技术只适用于一组有限的除数，所以不会为你的特定实例的工作。我没有真正看了网上的一章，所以我完全不知道其他技术可能如何适用适合你。
There's an added chapter on the website that contains "two methods of computing the remainder of division without computing the quotient!", which you may find of some use. The 1st technique applies only to a limited set of divisors, so it won't work for your particular instance. I haven't actually read the online chapter, so I don't know exactly how applicable the other technique might be for you.
这篇关于最优化的方式在C模数计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
