伎俩一个整数除以常数（两个电源） [英] Trick to divide a constant (power of two) by an integer

问题描述

注意这是一个理论性的问题。我很高兴与我的实际code的性能，因为它是。我只是好奇是否有替代。

有没有窍门做一个恒定值，它本身就是两个的整数次幂，一个整数变量值的整数除法，而无需使用做一个实际的除法运算？

  //固定分子的值
＃定义SIGNAL_PULSE_COUNT 0x4000UL//那可以用一个巧妙的划分。
uint32_t的signalToReferenceRatio（uint32_t的referenceCount）
{
    //促进分子到一个64位的值，移位它由32离开，以便
    //结果具有足够数目precision的比特和除法
    //由分子。
    返回（uint32_t的）（（uint64_t中）SIGNAL_PULSE_COUNT）LT（（;＆LT; 32）/ referenceCount）;
}
 

我已经发现了几个（许多）引用的技巧，以一个常量，整数和浮点做除法。例如，问题什么3是划分一个整数的最快方法？有一些很好的答案，包括其他的引用学术机构和社区的材料。

由于分子是恒定的，它是2的整数幂，是有可能的地方做一个实际的64位师可以使用巧妙的方法;某种位操作（移动，AND，XOR，那种东西）或类似的？

我不想precision的任何损失（由于超出可能的半位整数四舍五入）比，这样做的实际划分时，作为仪器的precision依赖于$ P $这种测量pcision

<子>让编译器决定不是一个答案，因为我想知道是否有一个小窍门。

外，上下文信息

我正在开发的16位数据的驱动器，24位指令字的微控制器。司机做一些魔术与外围模块，以获得一个参考频率的脉冲计数为固定数目的信号频率的脉冲。所需的结果是信号的脉冲的参考脉冲，前pressed为一个无符号的32位值的比值。该函数的运算由用于其中我开发的驱动程序的设备的制造商定义，并且将结果进一步得到浮点真实世界的值进行处理，但是这是这个问题的范围之内。

我使用的微控制器有有一些，我可以用除法运算的数字信号处理器，并且我不害怕，如果必要这么做。会有这种方法来克服，超越一起汇编指令，使其工作，如DSP的推杆被用来做一个BLDC驱动程序ISR一个PID功能一些小的挑战，但没有什么我不能驾驭。

解决方案

您不能用巧妙的数学技巧，不会做一个部门，但你当然可以仍然使用的编程技巧，如果你知道你的引用计数的范围：

• 没有什么比pre计算的查找表在速度方面。


• 有快速近似平方根算法（可能已经在你的DSP），并且可以由一个或两个牛顿迭代改进的迭代逼近。如果做与浮点数的计算是对你不够准确，你也许可以打败64位整数除法在速度方面（而不是在code的清晰度）。

您提到，其结果将在稍后转换为浮点，不计算整数除法可言，但使用浮点硬件可能是有益的。

NOTE This is a theoretical question. I'm happy with the performance of my actual code as it is. I'm just curious about whether there is an alternative.

Is there a trick to do an integer division of a constant value, which is itself an integer power of two, by an integer variable value, without having to use do an actual divide operation?

// The fixed value of the numerator
#define SIGNAL_PULSE_COUNT 0x4000UL

// The division that could use a neat trick.
uint32_t signalToReferenceRatio(uint32_t referenceCount)
{
    // Promote the numerator to a 64 bit value, shift it left by 32 so
    // the result has an adequate number of bits of precision, and divide
    // by the numerator.
    return (uint32_t)((((uint64_t)SIGNAL_PULSE_COUNT) << 32) / referenceCount);
}

I've found several (lots) of references for tricks to do division by a constant, both integer and floating point. For example, the question What's the fastest way to divide an integer by 3? has a number of good answers including references to other academic and community materials.

Given that the numerator is constant, and it's an integer power of two, is there a neat trick that could be used in place of doing an actual 64 bit division; some kind of bit-wise operation (shifts, AND, XOR, that kind of stuff) or similar?

I don't want any loss of precision (beyond a possible half bit due to integer rounding) greater than that of doing the actual division, as the precision of the instrument relies on the precision of this measurement.

_{"Let the compiler decide" is not an answer, because I want to know if there is a trick.}

Extra, Contextual Information

I'm developing a driver on a 16 bit data, 24 bit instruction word micro-controller. The driver does some magic with the peripheral modules to obtain a pulse count of a reference frequency for a fixed number of pulses of a signal frequency. The required result is a ratio of the signal pulses to the reference pulse, expressed as an unsigned 32 bit value. The arithmetic for the function is defined by the manufacturer of the device for which I'm developing the driver, and the result is processed further to obtain a floating point real-world value, but that's outside the scope of this question.

The micro-controller I'm using has a Digital Signal Processor that has a number of division operations that I could use, and I'm not afraid to do so if necessary. There would be some minor challenges to overcome with this approach, beyond the putting together the assembly instructions to make it work, such as the DSP being used to do a PID function in a BLDC driver ISR, but nothing I can't manage.

解决方案

You cannot use clever mathematical tricks to not do a division, but you can of course still use programming tricks if you know the range of your reference count:

• Nothing beats a pre-computed lookup table in terms of speed.
• There are fast approximate square root algorithms (probably already in your DSP), and you can improve the approximation by one or two Newton-Raphson iterations. If doing the computation with floating-point numbers is accurate enough for you, you can probably beat a 64bit integer division in terms of speed (but not in clarity of code).

You mentioned that the result will be converted to floating-point later, it might be beneficial to not compute the integer division at all, but use your floating point hardware.

这篇关于伎俩一个整数除以常数（两个电源）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！