几种取模优化方法(译自 min-25 的博客)

liu_cheng_ao 2018-02-28 13:08:17 2018-04-10 9:43:17

min-25 的博客链接

orz Min_25

嗯 …… 上次开了个 Berlekamp-Massey 算法的坑,稍后再填。

这次来介绍几种取模优化。内容取自上述 min-25 的博客,结合 Wikipedia 做了一些修改。

现在开始正题。

Barrett Reduction(利用乘法计算取模)

基本原理

假设现在我们要计算 a \bmod n

取模的性质很少,我们通常利用 a \bmod n=a-n\cdot \lfloor \frac{a}{n} \rfloor 进行计算。

那么直接的想法是计算一个浮点数 s=n^{-1} ,然后直接计算。那么问题就在于 s 的精度。

要研究这个问题,首先我们要搞清楚浮点数的存储方式和精度。浮点数是用 a\times 2^b 的形式存储的,其中 a 是有效数字不超过若干位(double 是 52 位)的二进制数“阶码”, b 是指数(double 是 11 位)。那么浮点数向下取整的操作实际上就是舍去 a 的最后若干位,并令 b=0

那么我们设浮点数表示 s=m \times 2^{-k} ,最终我们计算的就是 \lfloor \frac{a}{n} \rfloor = \lfloor \frac{ma}{2^k} \rfloor

于是,问题转化为构造一个 m k 使得:

\lfloor \frac{a}{n} \rfloor = \lfloor \frac{ma}{2^k} \rfloor

就有 a % n == a - n * (a * m >> k) 了。

那么 m k 怎样确定呢?我们不妨仍从浮点数除法计算 s ,考虑:

s= m \times 2^{-k} \approx n^{-1}

也即, m\cdot n\approx 2^k ,那么对于某个 k 要么 m=\lfloor \frac{2^k}{n} \rfloor ,要么 m=\lceil \frac{2^k}{n} \rceil

那么现在要解决的问题有两个:

  • k 应该取多大
  • m 到底是向上取整还是向下取整

我们稍微改写目标等式:

\lfloor \frac{a\cdot 2^k}{n\cdot 2^k} \rfloor = \lfloor \frac{nma}{n\cdot 2^k} \rfloor

m 代入得:

\lfloor \frac{a\cdot 2^k}{n\cdot 2^k} \rfloor = \lfloor \frac{na(\frac{2^k}{n}+O(1))}{n\cdot 2^k} \rfloor = \lfloor \frac{a\cdot 2^k+O(na)}{n\cdot 2^k} \rfloor

精度要求 a=O(2^k) ,即 2^k=Ω(a)

我们发现 a 的大小对精度( k )有影响。考虑到实际情况(乘法取模),我们认为 0\le a<n^2

那么 k 至少是 \lceil 2\log_2n\rceil 。我们可以取这个下界,然后计算后进行 O(1) 次调整。但这样效率不是很高。

我们试图找一个不需要调整的做法:

可以看到,等式的左边 \lfloor \frac{a}{n} \rfloor n^{-1} 的整数倍,如果我们能令等式右边不小于左边且差小于 n^{-1} ,就可以保证等式成立。

要让右边不小于左边, m 需要偏大,这就回答了我们的第二个问题。因此, m=\lceil \frac{2^k}{n} \rceil 。并且,由于精度要求从原来下取整的 1 变成了 n^{-1} ,需要 2^k=Ω(na)

我们令 m=\frac{2^k+r}{n}(0\le r<n) ,那么有:

\begin{aligned} & \frac{ma}{2^k} - \frac{a}{n} - \frac{1}{n} \\ = & \frac{nma-a\cdot 2^k-2^k}{n\cdot 2^k} \\ = & \frac{(2^k+r)a-a\cdot 2^k-2^k}{n\cdot 2^k} \\ = & \frac{ra-2^k}{n\cdot 2^k} \end{aligned}

要求其为负,即要求 2^k>ra ,即 2^k>(n-1)a

如果有 0\le a < n^2 ,应取 k=\lceil \log_2((n-1)(n^2-1)+1) \rceil ;若仅有乘法取模 0\le a <(n-1)^2 ,则应取 k=\lceil \log_2((n-1)((n-1)^2-1)+1) \rceil

这就是 Barrett 取模算法

整除判定

有时候我们不需要求出具体的值,只要知道 a 是否是 n 的整数倍。这时我们可以做得更简单一些:

共 8 条回复

Gunbuster

催更催更

kczno1

话说这题https://loj.ac/problem/6466如果用pollard rho的话快速乘好像必须得用min25这篇博客里提到的Montgomery modular multiplication。。

UKE_Automaton

orz

WAAutoMaton

中排%lca && 催更

SHENZHEBEI

前排%lca!

Snakes

下文呢……

bestFy

前排%lca!

skylee

orz