317
правок
Изменения
м
1) # уберем все несущественные биты <tex>x' = x </tex>&<tex> \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(\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>,# применив побитовое &, уберем лишние биты, появившиеся в результате умножения: <tex>\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j} </tex>&<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>,# сделаем сдвиг вправо на <tex>m_0 + b_0</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) применив побитовое &, уберем лишние биты, появившиеся в результате умножения,
<tex>\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j} </tex>&<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>,
4) сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.
→Вычисление sketch(x)
Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.
{{Утверждение
|id=
