尝试仅使用整数数学将0..4096之间的数字乘以0.3

Question

我试图围绕如何将一个数字从0..4096乘以0.3,只使用带有移位操作和缩放的整数,而不是在C中分割.我是这个东西和任何输入或步骤的新手一步一步的建议会非常有帮助.

Answer 1

乘以0.3与乘以相同(0.3*2^n),然后除以2^n.第二阶段相当于右移n.

但最有价值的是n什么？

要找到这个,请获取最大的整数并找到最大值,n以便在(0.3*2^n)没有溢出的情况下乘以.使用64位无符号整数和4096作为最大值

0.3*2^n <= 2^(64-12)

要么

0.3 <= 2^(64-12-n)

n当RHS等于0.5时,不平等最大

2^-1 = 2^(64-12-n)

所以-1 = 64-12-n,n = 64-12+1 = 53.

所以答案是乘以2^53*0.3然后右移53,即

/* designed to work with input values 0 .. 4096 only */
uint64_t
multiplyby0_3 (uint64_t x)
{
    return (x * 2702159776422297ULL) >> 53;
}

要检查是否没有溢出,我们已经得到了最好的n,来自bc:

2702159776422297*4096 = 11068046444225728512
2^64                  = 18446744073709551616

IE它不会溢出,但如果我们再次乘以2,它就会.

对于32位整数,答案乘以2^21*0.3然后右移21,即

/* designed to work with input values 0 .. 4096 only */
uint32_t
multiplyby0_3 (uint32_t x)
{
    return (x * 629146U) >> 21;
}

最后,通过查看1乘数中的二进制数,可以将任意乘法分解为多个加法.因此,您允许"缩放",我认为这意味着成倍增加.如果不是,这里是32位版本开发的事实,(64位作为练习留给读者版本)629146是10011001100110011010(一个整洁的模式,由于重复二进制小数).我们将绕过另一条路并10011001100110011001改为使用.

/* designed to work with input values 0 .. 4096 only */
uint32_t
multiplyby0_3 (uint32_t x)
{
    uint32_t y;
    x += x<<3;    /* * 1001 */
    y = x<<4 + x; /* * 10011001 */
    y += y<<8;    /* * 1001100110011001 */
    y += x<<16;   /* * 10011001100110011001 */
    return y >> 21;
}

Answer 2

如果你有快速整数乘法,但你没有整数除法,你可以通过乘以1229得到合理的近似值,然后向右移12位.例如:

>> 100 * 1229
122900
>> 122900 >> 12
30

这是有效的,因为1229是关于0.3 * 1 << 12."实际"值为1228.8,因此在某些情况下估计值将高1(4097值中的68个).但它永远不会超过1.

Answer 3

使用divu10()下面的经典黑客.我更喜欢*n和shift方法,但我认为我提供了另一个POV.

unsigned mult3tenths(unsigned x) {
  return divu10(x*3);
}

unsigned divu10(unsigned n) {
  unsigned q, rem;
  q = (n >> 1) + (n >> 2);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
  q = q >> 3;
  rem = n - q*10;
  return q + ((rem + 6) >> 4);  
}