From 6bf6d1ce213dbc70dd881b16954a1b7575fbd06a Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 2 Feb 2008 18:56:20 +0100
Subject: [PATCH] Fixed typography.

---
 ram.tex | 34 +++++++++++++++++++++-------------
 1 file changed, 21 insertions(+), 13 deletions(-)

diff --git a/ram.tex b/ram.tex
index aca5518..9f95610 100644
--- a/ram.tex
+++ b/ram.tex
@@ -424,11 +424,13 @@ using masking and shifts.
 
 \algn{Operations on vectors with $d$~elements of $b$~bits each}
 
-\>$\<Replicate>(\alpha)$ --- creates a~vector $(\alpha,\ldots,\alpha)$:
+\itemize\ibull
+
+\:$\<Replicate>(\alpha)$ --- creates a~vector $(\alpha,\ldots,\alpha)$:
 
 \alik{\<Replicate>(\alpha)=\alpha\cdot(\0^b\1)^d. \cr}
 
-\>$\<Sum>(x)$ --- calculates the sum of the elements of~${\bf x}$, assuming that
+\:$\<Sum>(x)$ --- calculates the sum of the elements of~${\bf x}$, assuming that
 it fits in~$b$ bits:
 
 \alik{\<Sum>(x) = x \bmod \1^{b+1}. \cr}
@@ -462,7 +464,7 @@ If we want to avoid division, we can use double-precision multiplication instead
 This way, we even get the vector of all partial sums:
 $s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{d-1}x_i$.
 
-\>$\<Cmp>(x,y)$ --- element-wise comparison of~vectors ${\bf x}$ and~${\bf y}$,
+\:$\<Cmp>(x,y)$ --- element-wise comparison of~vectors ${\bf x}$ and~${\bf y}$,
 i.e., a~vector ${\bf z}$ such that $z_i=1$ iff $x_i<y_i$.
 
 We replace the separator zeroes in~$x$ by ones and subtract~$y$. These ones
@@ -481,19 +483,19 @@ carries from propagating, so the fields do not interact with each other:
 It only remains to shift the separator bits to the right positions, negate them
 and zero out all other bits.
 
-\>$\<Rank>(x,\alpha)$ --- return the number of elements of~${\bf x}$ which are less than~$\alpha$,
+\:$\<Rank>(x,\alpha)$ --- return the number of elements of~${\bf x}$ which are less than~$\alpha$,
 assuming that the result fits in~$b$ bits:
 
 \alik{
 \<Rank>(x,\alpha) = \<Sum>(\<Cmp>(x,\<Replicate>(\alpha))). \cr
 }
 
-\>$\<Insert>(x,\alpha)$ --- insert~$\alpha$ into a~sorted vector $\bf x$:
+\:$\<Insert>(x,\alpha)$ --- insert~$\alpha$ into a~sorted vector $\bf x$:
 
 Calculate $k = \<Rank>(x,\alpha)$ first, then insert~$\alpha$ as the $k$-th
 field of~$\bf x$ using masking operations.
 
-\>$\<Unpack>(\alpha)$ --- create a~vector whose elements are the bits of~$\(\alpha)_d$.
+\:$\<Unpack>(\alpha)$ --- create a~vector whose elements are the bits of~$\(\alpha)_d$.
 In other words, we insert blocks~$\0^b$ between the bits of~$\alpha$. Assuming that $b\ge d$,
 we can do it as follows:
 
@@ -508,13 +510,13 @@ Let us observe that $z_i$ is either zero or equal to~$y_i$ depending on the valu
 of the $i$-th bit of the number~$\alpha$. Comparing it with~$y_i$ normalizes it
 to either zero or one.
 
-\>$\<Unpack>_\varphi(\alpha)$ --- like \<Unpack>, but changes the order of the
+\:$\<Unpack>_\varphi(\alpha)$ --- like \<Unpack>, but changes the order of the
 bits according to a~fixed permutation~$\varphi$: The $i$-th element of the
 resulting vector is equal to~$\alpha[\pi(i)]$.
 
 Implemented as above, but with mask~$y=(2^{\pi(b-1)},\ldots,2^{\pi(0)})$.
 
-\>$\<Pack>(x)$ --- the inverse of \<Unpack>: given a~vector of zeroes and ones,
+\:$\<Pack>(x)$ --- the inverse of \<Unpack>: given a~vector of zeroes and ones,
 it produces a~number whose bits are the elements of the vector (in other words,
 it crosses out the $\0^b$ blocks).
 
@@ -538,6 +540,8 @@ We use the technique based on multiplication instead, which does not need
 the separators. (Alternatively, we can observe that $\1^b$ is the only case
 affected, so we can handle it separately.)
 
+\endlist
+
 \para
 We can use the above tricks to perform interesting operations on individual
 numbers in constant time, too. Let us assume for a~while that we are
@@ -547,17 +551,19 @@ of $b$~bits each.
 
 \algn{Integer operations in quadratic workspace}\id{lsbmsb}
 
-\>$\<Weight>(\alpha)$ --- compute the Hamming weight of~$\alpha$, i.e., the number of ones in~$\(\alpha)$.
+\itemize\ibull
+
+\:$\<Weight>(\alpha)$ --- compute the Hamming weight of~$\alpha$, i.e., the number of ones in~$\(\alpha)$.
 
 Perform \<Unpack> and then \<Sum>.
 
-\>$\<Permute>_\pi(\alpha)$ --- shuffle the bits of~$\alpha$ according
+\:$\<Permute>_\pi(\alpha)$ --- shuffle the bits of~$\alpha$ according
 to a~fixed permutation~$\pi$.
 
 Perform $\<Unpack>_\pi$ and \<Pack> back.
 
-\>$\<LSB>(\alpha)$ --- find the least significant bit of~$\alpha$,
-i.e., the minimum~$i$ such that $\alpha[i]=1$.
+\:$\<LSB>(\alpha)$ --- find the least significant bit of~$\alpha$,
+i.e., the smallest~$i$ such that $\alpha[i]=1$.
 
 By a~combination of subtraction with $\bxor$, we create a~number
 which contain ones exactly at positions below $\<LSB>(\alpha)$:
@@ -570,12 +576,14 @@ which contain ones exactly at positions below $\<LSB>(\alpha)$:
 
 Then calculate the \<Weight> of the result.
 
-\>$\<MSB>(\alpha)$ --- find the most significant bit (the position
+\:$\<MSB>(\alpha)$ --- find the most significant bit (the position
 of the highest bit set in~$\alpha$).
 
 Reverse the bits of the number first by~\<Permute>, then apply \<LSB>
 and subtract the result from~$b-1$.
 
+\endlist
+
 \rem
 As noted by Brodnik~\cite{brodnik:lsb} and others, the space requirements of
 the \<LSB> operation can be reduced to linear. We split the input to $\sqrt{b}$
-- 
2.39.5