diff options
| -rw-r--r-- | ps1/main.tex | 10 |
1 files changed, 6 insertions, 4 deletions
diff --git a/ps1/main.tex b/ps1/main.tex index a2646e3..65c7707 100644 --- a/ps1/main.tex +++ b/ps1/main.tex @@ -44,6 +44,8 @@ necessarily equal to the number of elements. Indeed, inserting an element can possibly require creating a min pointer in its cluster and recursively inserting its cluster id into the summary. +\paragraph{(b)} See \textbf{(c)}. + \paragraph{(c)} Let us denote by $N(u)$ the number of min pointers created when inserting an element in a $u$-vEB tree. We have two cases: @@ -210,9 +212,9 @@ c)) - 1} \end{center} Then, the least significant bit set to one of a word $x$ of length $w$ can be -computed by first finding the rightmost non-empty cluster of length $w$ in $x$, -then extract this cluster by shifting and masking, and then finding the least -significant bit set to one in this cluster: +computed by first finding the rightmost non-empty cluster of length $\sqrt{w}$ +in $x$, then extracting this cluster by shifting and masking, and then finding +the least significant bit set to one in this cluster: \vspace{1em} @@ -221,7 +223,7 @@ significant bit set to one in this cluster: \hspace*{1cm}\texttt{if z == -1:}\newline \hspace*{2cm}\texttt{return -1}\newline \hspace*{1cm}\texttt{return z * $\sqrt{\texttt{w}}$ - + lsb-short((x >> z * $\sqrt{w}$) \& (1 << $\sqrt{w}$ - 1))} ++ lsb-short((x >> z * $\sqrt{\texttt{w}}$) \& (1 << $\sqrt{\texttt{w}}$ - 1))} Note that the above code only requires a constant number of multiplications and bitwise operations once the constants $m$, $a$, $b$ and $c$ have been |