From a92f6a1f6adea8f41ffac2727bb645c245075ca2 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 2 Feb 2008 00:44:35 +0100
Subject: [PATCH] Bit string notation.

---
 macros.tex   |  6 ++++++
 notation.tex |  3 +++
 ram.tex      | 25 ++++++++++++++++++++-----
 3 files changed, 29 insertions(+), 5 deletions(-)

diff --git a/macros.tex b/macros.tex
index 1b0d8c1..adef15e 100644
--- a/macros.tex
+++ b/macros.tex
@@ -43,6 +43,11 @@
 \def\timesbeta{\mskip2mu\beta}
 \def\tower{\mathop\uparrow}
 
+% Bit strings
+\def\0{{\bf 0}}
+\def\1{{\bf 1}}
+\def\(#1){\left<#1\right>}
+
 % A reversed version of \ddots with extra space at the top to get good alignment of exponents.
 \def\rddots{\mathinner{\mkern1mu\raise\p@\vbox{\kern7\p@\hbox{.}}\mkern2mu
     \raise4\p@\hbox{.}\mkern2mu\raise7\p@\hbox{.}\raise11\p@\hbox{}\mkern1mu}}
@@ -326,6 +331,7 @@
 \def\lemman{\lemma\label}
 \def\defnn{\defn\label}
 \def\algn{\alg\label}
+\def\notan{\nota\label}
 
 \def\proof{\noindent {\sl Proof.}\enspace}
 \def\proofsketch{\noindent {\sl Proof sketch.}\enspace}
diff --git a/notation.tex b/notation.tex
index 1f75d13..d89ece3 100644
--- a/notation.tex
+++ b/notation.tex
@@ -42,6 +42,9 @@
 \n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n < 1\}$; the inverse of~$2\tower n$}
 \n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n < m/n \}$ \[itjarthm]}
 \n{$W$}{word size of the RAM \[wordsize]}
+\n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bintota]}
+\n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]}
+\n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]}
 }
 
 %--------------------------------------------------------------------------------
diff --git a/ram.tex b/ram.tex
index fb3bd54..14a4676 100644
--- a/ram.tex
+++ b/ram.tex
@@ -370,15 +370,30 @@ starting approximation can be obtained by dividing the two most-significant
 Another approach to division is using the improved elementary school algorithm as described
 by Knuth in~\cite{knuth:seminalg}. It uses $\O(k^2)$ steps, but the steps involve
 calculation of the most significant bit set in a~word. We will show below that it
-can be done in constant time without using division.
+can be done in constant time, but we have to be careful to avoid division instructions.
 \qed
 
-\nota
+\notan{Vectors}
 We will use boldface letters for vectors. The components of a~vector~${\bf x}$
-will be denoted as $x_1,\ldots,x_n$.
+will be denoted as $x_0,\ldots,x_{d-1}$.
+
+\notan{Bit strings}\id{bitnota}%
+We will work with binary representations of natural numbers as strings over the
+alphabet $\{\0,\1\}$: we will use $\(x)$ for the number~$x$ written in binary,
+$\(x)_b$ for the same padded to exactly $b$ bits by adding zeroes at the beginning.
+Strings will be denoted by Greek letters and the usual conventions will be utilized
+for string operations: $\alpha\beta$ for concatenation and $\alpha^k$ for the
+string~$\alpha$ repeated $k$~times. When the meaning is clear from the context,
+we will use $x$ and $\(x)$ interchangeably to avoid outbreak of symbols.
 
 \defn
-The \df{canonical representation} of a~vector $(x_1,\ldots,x_n)$ of~$b$-bit numbers
-is an~integer XXXXXXXXXXXXXXX
+The \df{bitwise encoding} of a~vector ${\bf x}=(x_0,\ldots,x_{d-1})$ of~$b$-bit numbers
+is an~integer $\0\(x_{d-1})_b\0\(x_{d-2})_b\0\ldots\0\(x_0)_b$.
+
+\para
+If we wish for the whole vector to fit in a~single word, we need $(b+1)d\le W$.
+By using multiple-precision arithmetics, we can encode all vectors satisfying $bd=\O(W)$.
+We will now describe how to translate simple vector manipulations to RAM operations on their
+codes.
 
 \endpart
-- 
2.39.5