234
правки
Изменения
→Вычисление sketch(x)
1) уберем все несущественные биты <tex>x' = x</tex> ''AND'' <tex>\displaystyle \sum_{i=0}^{r-1}2^{b_i}</tex>;
2) умножением на некоторое заранее вычисленное число <tex>M = \displaystyle\sum_{i=0}^{r-1}2^{m_i}</tex> сместим все существенные биты в блок меньшего размера.
<tex>x'\times M = \displaystyle(\sum_{i=0}^{r-1}x_{b_i}2^{b_i})(\sum_{i=0}^{r-1}2^{m_i}) = \sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}</tex>;
3) применив побитовое ''AND'' , уберем лишние биты, появившиеся в результате умножения;
<tex>\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}</tex> ''AND'' <tex>\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>;
|author=
|about=
|statement=Дана последовательность из <tex>r </tex> чисел <tex>b_0<b_1<\ldots <b_{r-1}</tex>. Тогда существует последовательность <tex>m_0<m_1\ldots <m_{r-1}</tex>, такая что:
1) все <tex>b_i + m_j</tex> различны, для <tex>0\leqslant i,j \leqslant r-1</tex>;
2) <tex>b_1 b_0 + m_2m_0\leqslant b_2 b_1 + m_2m_1\leqslant \ldots \leqslant b_{r-1} + m_{r-1}</tex>;
3) <tex>(b_{r-1} + m_{r-1}) - (b_0 + m_0) \leqslant r^4</tex>.
|proof=
Выберем некоторые <tex>m_i'</tex>, таким образом, чтобы <tex>m_i' + b_k \not\equiv m_j' + b_p</tex>. Предположим, что мы выбрали <tex>m_1' \ldots m_{t-1}'</tex>. Тогда <tex>m_t' \ne m_i' + b_j - b_k \; \forall i,j,k</tex>. Всего <tex>t\times r\times r < r^3 </tex> недопустимых значений для <tex>m_t'</tex>, поэтому всегда можно найти хотя бы одно значение.
Чтобы получить <tex>m_i</tex>, выбираем каждый раз наименьшее <tex>m_i'</tex> и прибавляем подходящее число кратное <tex>r^3</tex>, такое что <tex>m_i+c_i < m_{i+1}+c_{i+1} \leqslant m_i+c_i+r^3</tex>.
