Изменения

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