c - 在数组表示和除数中查找数字的模数

Question

我有一个无符号整数数组，如下所示

unsigned coeffs[] = { x_(n-1), ... , x_1, x_0 }

表示以 10 为底的数字 < x_(n-1) ... x_1 x_0 >。

现在我想在给定一个除数(无符号整数)的情况下找出这个数的模数，并想出了以下使用霍纳规则用 C 语言编写的函数。

unsigned modulo(unsigned coeffs*, unsigned degree, unsigned divisor)
{
    int r = 0;
    for(int i = 0; i < degree; ++i)
        r = (r * 10 + coeffs[i]) % divisor;
    return r;
}

这是正确的还是我做错了什么？ x)

Answer 1

Find modulus of a number in array representation and a divisor
Is this correct or am I doing something wrong here?

使用小的除数，没问题。

@Klas Lindbäck当一个大的 divisor 未能通过代码时识别。 (假定使用 unsigned r 而不是 int r)。我得出了一个稍微不同的限制

divisor <= (UINT_MAX - 9)/10 + 1

如果代码需要处理大的除数，那么有两种方法:

1) 使用更宽的类型:

// Consider some wider type like unsigned long long or uintmax_t
_Static_assert(ULLONG_MAX > UINT_MAX, "Oops");
typedef unsigned long long unsigned2x;

// Might as well make `unsigned coeffs*` `const`  and `size_t` for indexing.
unsigned modulo(const unsigned coeffs*, size_t degree, unsigned divisor) {
  unsigned2x r = 0;
  for(size_t i = 0; i < degree; ++i) {
    r = ((r * 10) + coeffs[i]) % divisor;
  }
  return (unsigned) r;
}

2) 分部分执行mod:

提供的方法:@Micrified当 r * 10 溢出时失败。

为了应对不存在更宽的无符号整数并且代码必须处理较大的除数的情况，请使用以下代码，该代码来自Modular exponentiation without range restriction。

// when `unsigned` potentially as wide as `uintmax_t`
unsigned modulo(const unsigned coeffs*, size_t degree, unsigned divisor) {
  unsigned r = 0;
  for(size_t i = 0; i < degree; ++i) {
    r = mulmodmax(r, 10, divisor);
    r = addmodmax(r, coeffs[i], divisor);
  }
  return r;
}