C - 针对模数的按位运算的算法,对于非2的幂次数

#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct bitfield64_t {
  uint64_t b0 : 4;
  uint64_t b1 : 4;
  uint64_t b2 : 4;
  uint64_t b3 : 4;
  uint64_t b4 : 4;
  uint64_t b5 : 4;
  uint64_t b6 : 4;
  uint64_t b7 : 4;
  uint64_t b8 : 4;
  uint64_t b9 : 4;
  uint64_t b10 : 4;
  uint64_t b11 : 4;
  uint64_t b12 : 4;
  uint64_t b13 : 4;
  uint64_t b14 : 4;
  uint64_t b15 : 4;
} bitfield64_t;

typedef union pun64_t {
  uint64_t u;
  bitfield64_t b;
} pun64_t;

/* i%5 for i in [0,19].  The upper bound guarantees that nibble_mod5[a+b] is
 * valid whenever a<16 and b<5.
 */
const unsigned nibble_mod5[20] = {
  0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4
};

unsigned add_mod5( const unsigned a, const unsigned b )
/* Returns (a + b) % 5, where
 *   a < 16
 *   b < 5
 */
{
  assert(a < 16);
  assert(b < 5);
  return nibble_mod5[a + b];
}

int main( const int argc, const char* argv[] )
{
  int64_t n;

  if ( argc != 2 ) {
    fprintf( stderr,
             "Call this program with an unsigned number as its argument.\n" );
    return EXIT_FAILURE;
  }

  if ( 1 != sscanf( argv[1], "%lld", &n ) || n < 0 ) {
    fprintf( stderr,
             "The argument must be an unsigned number.\n" );
    return EXIT_FAILURE;
  }

  const pun64_t p = { .u = (uint64_t)n };
  const unsigned result =
    add_mod5( p.b.b15,
    add_mod5( p.b.b14,
    add_mod5( p.b.b13,
    add_mod5( p.b.b12,
    add_mod5( p.b.b11,
    add_mod5( p.b.b10,
    add_mod5( p.b.b9,
    add_mod5( p.b.b8,
    add_mod5( p.b.b7,
    add_mod5( p.b.b6,
    add_mod5( p.b.b5,
    add_mod5( p.b.b4,
    add_mod5( p.b.b3,
    add_mod5( p.b.b2,
    add_mod5( p.b.b1,
    nibble_mod5[p.b.b0] )))))))))))))));

   printf( "%u\n", result );
   assert( result == n % 5 );
   return EXIT_SUCCESS;
}

Run Code Online (Sandbox Code Playgroud)

为了找到一个BIGNUM的模量,可以采取的一个事实,即16的任何权力是一致的,以1个模5.因此,你的字大小是否优势W¯¯是2⁸,2ⁱ⁶,2³²或2⁶⁴,你可以写你的BIGNUM为a₀w⁰ + a 1w 1 + a 2w 2 + ... a a1 1 + a 1 11 + a 21 2 + ...≡a0+ a 1 + a 2 + ...(mod 5).这也是为什么任何数字的十进制数字的总和与模数3或9的原始数字一致:10≡1(mod 3).

这也适用于3字节,5字节,15字节和17字节,16位字的因子为255和257,32位字的因子为65,535和65,537.如果您注意到该模式,那是因为b²ⁿ=(bⁿ+ 1)(bⁿ-1)+ 1,其中b = 2且n = 2,4,8或16.

您可以将此方法的变体应用于任何n,使得块大小与-1(mod n)一致:交替加法和减法.它的工作原理是因为a0w⁰+a1w¹+ a2w2 + ...≡a0(-1)⁰+ a 1(-1)¹+ a 2(-1)²+ ...≡a0 - a 1 + a 2 - ...(mod n ),但是没那么有用,因为许多这样的n值都是梅森素数.它类似于你如何通过从右到左并加上,减去,加上和减去数字来获取任何小数的mod 11,例如144≅4 - 4 +1≡1(mod 11).就像数字一样,你可以使用五位块执行相同的技巧,因为32(如10)也与-1 modulo 11一致.

另一种有用的特殊情况发生时瓦特 ≡ 瓦特 ²≡C(MOD B).然后你有一个δw⁰+ a1w1 + a2w2 + ......≡ac+ a 1c + a 2c + ...≡a0+ c(a 1 + a 2 + ...)(mod b).这类似于10≡100≡1000≡...≡4(mod 6),所以任何数字都与其最后一位数加上其余数位之和的四倍,模数为6.计算可以是查找和每个字节加一个,乘以一个小常数乘以一个或两个位移.例如,要采用mod 20,您可以添加除最低位字节mod 20之外的所有字节,将和乘以256 mod 20 = 16,这只是左移4,然后添加最后一个字节.这可能非常方便:不计算给出1或0的余数的数字,这适用于模数为6,10和12的半字节,以及以这些值为模的字节和20,24,30,34,40,48,60,68 ,80,96,102,120,136,160,170,192,204和240.

如果数字可以表示为特殊情况的乘积,则可以使用中国剩余定理求解.例如,77 = 11×7,32≡-1 mod 11和8≡1mod 7,因此你可以找到余数除以11和7,它们确定余数除以77.大多数小素数落入一个以前讨论过的特殊情况.

许多后来的RISC架构具有硬件鸿沟但没有模数,并告诉程序员通过计算a%b进行计算a-(a/b)*b.ARM A64是目前使用最多的产品.如果您没有硬件部门,请查看此答案.这里给出了当基数是小常数时的另一种方法的示例,并且广泛用于CISC架构.

Sean Anderson在2001年也编写了一个算法,但可能早些时候发现它的计算模数比2的幂小1.它类似于我上面使用的技术,但依赖于位移,可以扩展到任何因素(1<<s)-1.这几乎就是你要找的!

通常,优化编译器应该使用最有效的方法%在硬件上实现.在你的例子中,任何体面的编译器只会折叠常量并优化7%5为2.

归档时间：	7 年，6 月前
查看次数：	667 次
最近记录：	6 年，5 月前