317
правок
Изменения
м
→Вычисление sketch(x)
# Уберем все несущественные биты <tex>x' = x \& \displaystyle \sum_{i=0}^{r-1}2^{b_i}</tex>.
# Умножением на некоторое заранее вычисленное число <tex>M = \displaystyle\sum_{i=0}^{r-1}2^{m_i}</tex> сместим все существенные биты в блок меньшего размера: <tex>x'\times M = \displaystyle\left(\sum_{i=0}^{r-1}x_{b_i}2^{b_i}\right)\left(\sum_{i=0}^{r-1}2^{m_i}\right) = \sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}</tex>.
# Применив побитовое <tex>\&</tex>, уберем лишние биты, появившиеся в результате умножения: <tex>\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j} \& \displaystyle\sum_{i=0}^{r-1}2^{b_i+m_i} = \sum_{i=0}^{r-1}x_{b_i}2^{b_i+m_i}</tex>.
# Сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.
