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