234
правки
Изменения
→Вычисление sketch(x)
Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.
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>;
4) сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.
}}
Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить sketch узла в w-битный тип. Так как <tex>r \leqslant B-1</tex>, то <tex>sketch(node)</tex> будет занимать <tex>B(r^4 + 1) \leqslant B((B-1)^4 + 1) \leqslant B^5 = (w^{1/5})^5 = w </tex> бит.
==Индекс наиболее значащего бита==
Чтобы найти в w-битном числе ''x'' индекс самого старшего бита, содержащего еденицу, разделим ''x'' на <tex>\sqrt{w}</tex> блоков по <tex>\sqrt{w}</tex> бит.
