Today I want to write about the famous square-and-multiply (aka double-and-add) algorithm and how we can optimize it with the help of a special kind of signed binary representation: The non-adjacent form (NAF).
It turns out, that the non-adjacent form, besides from being useful for speed up arithmetic algorithms, is a very nice topic to study in itself. In many ways the results are parallel to the usual binary-number form, but slightly more involved.
Square and multiply
Square-and-multiply is an algorithm to efficiently calculate the exponentiation of an element $a \in G$ to the power of $n\in\mathbb{N}$. $G$ could be any semigroup (or monoid if we want to allow $n=0$), meaning that as long as we know how to ,,multiply” stuff in $G$ (and the associative law is valid) we can use our algorithm.
$G$ could even be an additive semigroup, in which case the exponentiation is really just a multiplication and our square-and-multiply transforms into double-and-add. This is important, for example, with elliptic-curves where the underlying operation is addition and we need a fast algorithm to calculate $n \cdot P$ where $P$ is a point and $n\in\mathbb{N}$.
But in the end this is just a matter of notation, the math really doesn’t care if people call an operation ,,multiplication” or ,,addition”. ;-)
The idea behind the algorithm is quite simple: Let’s assume we are given $a\in G$ and $n\in\mathbb{N}$, then it is \begin{equation} \label{powrec} a^n = \left\{ \begin{array}{ll} (a^2)^\frac{n}{2}, & 2 \mid n\cr a \cdot (a^2)^\frac{n-1}{2}, & 2 \nmid n\cr \end{array}\right.. \end{equation} So we reduced an exponentiation to the power of $n$ to an exponentiation to the power of $\lfloor\frac{n}{2}\rfloor$ which already suggests a logarithmic runtime (more on that later). On every reduction step we need one square-operation (to calculate the new base $a^2$) and, depending on the parity of $n$, one multiplication.
Note that we are only interested in counting the operations in $G$, because these are potentially expensive. Think $a$, for example, to be a big-integer that is represented by many machine-words. Also squaring is faster than general multiplication, so we count these seperately.
For example, let’s compute $a^{17}$: $$ a^{17} = a \cdot (a^2)^8 = a \cdot ((a^2)^2)^4 = \cdots = a \cdot (((a^2)^2)^2)^2 $$
Ok, it’s time to turn this idea into an algorithm:
algorithm: pow
input: $a \in M$ and $n \in \mathbb{N}_0$
output: $a^n$
$R \leftarrow 1$
$b \leftarrow a$
$m \leftarrow n$
while $m \neq 0$
if $2 \nmid m$
$R \leftarrow b \cdot R$
$b \leftarrow b^2$
$m \leftarrow \left\lfloor\frac{m}{2}\right\rfloor$
return $R$
To show that the algorithm is correct we note, by using \eqref{powrec}, that every time the while-expression is checked, the following invariant holds: $$ R \cdot b^m = a^n. $$ So if the loop finally terminates we necessarily have $m=0$ and therefore $$R = a^n$$ as stated.
To analyse the complexity we look at the binary representation of $n$: Let’s assume $n$’s binary representation has $k$ digits and $r$ of these digits are $1$. We can see, that the while-loop runs exactly $k$ times (and therefore terminates), which results in $k$ squaring operations. The if-branch will be taken $r$ times, so we get $r$ multiplications.
For a given $n\in\mathbb{N}$ we have $$ k = \lfloor\log_2(n)\rfloor + 1 $$ and, on average, we expect $r=k/2$.
Ok, this is already a pretty good algorithm, how can we possibly improve that?
The idea is, that we try to minimize the number of non-zero digits! There are some ways to do that, but we will focus on a special kind of signed binary numbers: With these we can achieve an average of $r=k/3$ non-zero digits without increasing $k$ by more than one.
But using signed binary numbers also means, that we will have an additional case in our algorithm $$ R \leftarrow b^{-1} R $$ which is only advantageous if we can efficiently calculate inverses in $G$ or if we have a list of precalculated $b^{-1}$ (for example if the base $a$ is always the same).
Definition of the NAF
The non-adjacent form (NAF) is a numeral system very similar to the ordinary binary system but with the unusual twist of allowing $-1$ as digit and disallowing two adjacent non-zero digits.
More formally we define the NAF as a sequence $$d_m \; d_{m-1} \;\cdots \; d_1 \; d_0$$ of digits $d_i\in\{-1,0,1\}$ such that for all $0 \leq i < m$ we have $$d_i \cdot d_{i+1} = 0.$$ Such a sequence then represents the number $$\left< d_m \; \cdots \; d_1 \; d_0\right> := d_m\cdot 2^m + \cdots + d_1\cdot 2 + d_0 \in \mathbb{Z},$$ very much like we are used to from the binary-number system. The empty sequence $\left<\right>$ is defined to be $0$.
So, for example, we get \begin{align*} \def\mone{\mathord-1} \def\mtwo{\mathord-2} \def\m{\mathord-} \left<1\;0\;\mone\right> &= 3,\cr \left<1\;0\;0\;1\right> &= 9,\cr \left<\m1\;0\;0\;1\right> &= -7,\cr \left<1\;0\;\mone\;0\;0\;\mone\right> &= 23.\cr \end{align*}
Note that $x$ is positive if, and only if, the leading non-zero digit is a $1$.
Of course from this definition it is not immediatly clear that every integer $x\in\mathbb{Z}$ possess such a representation and how to compute it. We will look at this below, but first turn our attention back to square-and-multiply and how to use NAF!
Note: The $\left< \cdots \right>$ notation from above is not standard and just made up for this article: NAF is far too uncommon to get it’s own default notation. Wikipedia, for example, uses $(d_m \; \cdots \; d_0)_2$ instead.
Square-and-multiply with NAF
So, now that we know what NAF is, we can use it to our advantage and modify our square-and-multiply from above:
algorithm: pownaf
input: $a \in M$ and $n = \left< d_{k-1} \; \cdots \; d_0 \right>\in\mathbb{N}$
output: $a^n$
$R \leftarrow 1$
$b \leftarrow a$
for $i = 0$ to $k-1$
if $d_i = 1$
$R \leftarrow b \cdot R$
if $d_i = -1$
$R \leftarrow b^{-1} \cdot R$
$b \leftarrow b^2$
return $R$
Although looking a bit different, this is actually the same algorithm as pow above. We just have the new case of $d_i = -1$ which is only efficient if we can compute $b^{-1}$ fast.
But why is this better? As we will show in the following the number of NAF digits $k$ is at most one bigger than the number of binary digits. The advantage comes from the fact that the number of non-zero digits is $k/3$ on average.
How to calculate the NAF
The NAF of a number $x\in\mathbb{Z}$ can be calculated efficiently, by the following recursive algorithm:
algorithm: NAF
input: $x\in\mathbb{Z}$
output: sequence $(d_{k-1}, \cdots, d_0)$ with $x=\left< d_{k-1} \; \cdots \; d_0 \right>$ or $()$ if $x=0$
if $x = 0$
return $\left(\right)$
$z \leftarrow \left\{\begin{array}{ll}
0, &2\mid x\cr
2-(x\mod 4), &\text{otherwise}\cr
\end{array}\right.$
return NAF$(\frac{x-z}{2}) \mid\!\mid \left( z \right)$
This code translates directly to python if you prefer a concrete implementation over pseudo-code (NAF numbers are represented by integer-lists here):
def NAF(x):
if x == 0:
return []
z = 0 if x % 2 == 0 else 2 - (x % 4)
return NAF( (x-z) // 2 ) + [z]
First let’s discuss why the algorithm terminates: If $|x| \leq 1$ the algorithm clearly terminates, otherwise we have $$ \left|\frac{x-z}{2}\right| \leq \frac{|x|+|z|}{2} \leq \frac{|x|+1}{2} < |x|. \def\NAF{\mathrm{NAF}} $$
Ok, we do terminate! If the digit $z$ we produce in a step is not zero, it is chosen in a way that $4 \mid x-z$, so we are guaranteed that $\frac{x-z}{2}$ is even and the next step will produce a zero-digit. That proves that the algorithm does indeed produce NAF numbers as we defined them above. Finally, since $\left<\NAF(0)\right> = 0$ and $$ <\NAF\left(\frac{x-z}{2}\right)> \cdot\; 2 + z = x \quad\text{ for }x > 0 $$ the returned NAF represents $x$ by mathematical induction.
Now let’s look at the number $k$ of NAF digits we got for a number $x\in\mathbb{N}$. If we define $N(x)$ to be the number of digits in the usual binary system, i.e. $$N(x) = \left\lfloor \log_2(x) \right\rfloor + 1,$$ than we have $$ N(x) \leq k \leq N(x) + 1. $$
So the NAF is at most one digit longer than the normal binary system.
To see that we start with a NAF sequence $\left< a_{k-1} \; \cdots \; a_0 \right>$ of a positive number (i.e. $a_{k-1} = 1$) and transform it bit by bit into a normal binary representation, by removing the $-1$’s and breaking our non-adjacent rule: We start with the smallest $i\in\mathbb{N}_0$ such that $a_i < 0$ and set $a_i := a_i + 2$ and $a_{i+1} := a_{i+1}-1$. This does not change the value of our sequence, but removes the lowest negative digit in it. By repeating, the value of $i$ will grow and finally we end up with a normal binary number that has either the same number of digits as the NAF we started with or one digit less (in case we changed the leading $1$ to $0$).
For example: \begin{align*} 23 &= \left<1 \; 0 \; \m1 \; 0 \; 0 \; \m1 \right>\cr &= \left< 1 \; 0 \; \m1 \; 0 \; \m1 \; 1 \right>\cr &= \left< 1 \; 0 \; \m1 \; \m1 \; 1 \; 1 \right>\cr &= \left< 1 \; 0 \; \m2 \; 1 \; 1 \; 1 \right>\cr &= \left< 1 \; \m1 \; 0 \; 1 \; 1 \; 1 \right>\cr &= \left< 0 \; 1 \; 0 \; 1 \; 1 \; 1 \right>.\cr \end{align*} Please note, that we abuse our own notation, by breaking the non-adjacent rule and even having a $-2$ digit somewhere, but the value is always 23 and the first form is a legal NAF while the last is a legal binary number.
Proof of uniqueness
It is not trivial to see, that the NAF is an unique representation of integers.
Let’s assume we have two NAFs $\left< a_k \; \cdots \; a_0 \right>$ and $\left< b_k \; \cdots \; b_0 \right>$ representing the same number $x \in \mathbb{Z}$, so \begin{align*} x &= \left< a_k \; \cdots \; a_0 \right> = \left< b_k \; \cdots \; b_0 \right>\cr \iff 0 &= (a_k-b_k)\cdot 2^k + \cdots + (a_1-b_1)\cdot 2 + (a_0 - b_0)\cr \end{align*}
with $-2 \leq (a_i - b_i) \leq 2$.
Note that for every $i$ with $a_i-b_i = \pm 2$ we also have $a_{i+1}-b_{i+1}=0$, because of the non-adjacent rule. That means we can get rid of all $\pm 2$ by changing the corresponding digit to zero and compensate for it by incrementing or decrementing the following digit (which was zero before).
Or, more formally, we define $$ \def\sgn{\mathop{\mathrm{sgn}}} c_i := \left\{ \begin{array}{ll} 0, & |a_i - b_i| = 2\cr \sgn(a_{i-1}-b_{i-1}), &i > 0 \text{ and } |a_{i-1}-b_{i-1}| = 2\cr a_i - b_i, &\text{otherwise}\cr \end{array}\right. $$ for $0 \leq i \leq k$. Now we have $c_i \in \{-1, 0, 1\}$ and $$ c_k\cdot 2^k + \cdots + c_1 \cdot 2 + c_0 = (a_k-b_k) \cdot 2^k + \cdots + (a_0-b_0) = 0 $$ which implies $c_i = 0$ for $0 \leq i \leq k$. But, by definition of $c_i$, this is only possible if we had $a_i-b_i=0$ for $0\leq i \leq k$ as well.
This proves the uniqueness of the NAF.
Hamming-weight of NAF
Here we want to show that, on average, only one third of the NAF digits are non-zero.
We will do this in three steps:
- count the number $R_k$ of $k$-digit NAFs
- count the number $N_{k,m}$ of $k$-digit NAFs with exactly $m$ non-zero-digits
- calculate the expected value $$E_k = \frac{1}{R_k} \sum_{m=1}^k m N_{k,m}$$ of non-zero-digits in a random $k$-digit NAF
Step 1: How many k-digit NAFs are there?
In this section we try to find a formula for the range $R_k$ of a $k$-digit NAF $$ R_k := | \{ x \in \mathbb{Z} \mid x = \left< a_{k-1} \; \cdots \; a_0 \right> \} |. $$ Or in words: $R_k$ is the number of integers we can express with a $k$-digit NAF, leading zeros allowed.
For example we get \begin{align*} R_0 &= 1 \quad\text{because of } \left<\right>,\cr R_1 &= 3 \quad\text{because of } \left<-1\right>, \left<0\right>, \left<1\right>,\cr R_2 &= 5 \quad\text{because of } \left<-1\;0\right>, \left<0\;-1\right>, \left<0\;0\right>, \left<0\;1\right>, \left<1\;0\right>.\cr \end{align*}
We attack this problem by trying to find a formula for the maximum numeric value $M_k$ a $k$-digit NAF can obtain. If we have found such a formula, we are done, because it is $$ R_k = 2 M_k + 1. $$
It is quite easy to see what bit pattern a $k$-digit NAF has the highest numeric value: The leading bit must be set, since it’s value exceeds that of all other digits combined. The second highest digit must be $0$ to fullfil our non-adjacency rule. So the highest value $M_k$ for $k$-digit NAF is $$ M_k := \left\{ \begin{array}{ll} <1 \; 0 \; 1 \; \cdots \; 1 \; 0>, & 2\mid k\cr <\underbrace{1 \; 0 \; 1 \; \cdots \; 0 \; 1}_{k\text{ digits}}>, & 2\nmid k\cr \end{array} \right.. $$
For example we get \begin{align*} M_1 &= \left< 1 \right> = 1\cr M_2 &= \left< 1 \; 0 \right> = 2\cr M_3 &= \left< 1 \; 0 \; 1\right> = 5\cr M_4 &= \left< 1 \; 0 \; 1 \; 0 \right> = 10\cr M_5 &= \left< 1 \; 0 \; 1 \; 0 \; 1\right> = 21\cr \cdots \end{align*}
From the bit-patterns one can see $M_{k-1} + M_{k} = 1 + 2 + \cdots + 2^{k-1} = 2^k-1$ and induction shows \begin{equation} \label{formMk} M_k = \frac{1}{3} \left(2^{k+1} - \frac{3 + (-1)^k}{2}\right). \end{equation}
Or, if you are not in the mood for induction, we can use a trick to derive \eqref{formMk} directly: Define the polynomial $$f_k(x) := 1 + x + \cdots + x^{k-1}$$ and note \begin{align*} \frac{f_k(x) + f_k(-x)}{2} &= 1 + x^2 + x^4 + \cdots = \sum_{\substack{i=0\cr 2\mid i}}^{k-1} x^k = \left<1 \; 0 \; \cdots \; 0 \; 1\right>\cr \frac{f_k(x) - f_k(-x)}{2} &= x + x^3 + x^5 + \cdots = \sum_{\substack{i=0\cr 2\nmid i}}^{k-1} x^k = \left<1 \; 0 \; \cdots \; 1 \; 0\right>\cr \end{align*}
From this we immediately get \begin{equation} \label{formMkf} M_k = \left\{ \begin{array}{ll} \frac{f_k(2) - f_k(-2)}{2}, & 2 \mid k\cr \frac{f_k(2) + f_k(-2)}{2}, & 2 \nmid k\cr \end{array}\right. \end{equation} and, using the formula for geometric progression, we can rewrite $f_k$ to $$ f_k(x) = \frac{x^k-1}{x-1} $$ and use this in \eqref{formMkf} to confirm \eqref{formMk}.
Finally we can complete our task from this subsection of finding a formula for $R_k$, it is $$ R_k = 2 \cdot M_k + 1 = \frac{1}{3} \left(2^{k+2} - (-1)^k \right). $$
Step 2: count k-digit NAF with m non-zero digits
Let us now look at the number $N_{k,m}$ of $k$-digits NAF with a given number $m$ of non-zero digits \begin{equation} \label{defNkm} N_{k,m} := \left|\{ x \in \mathbb{Z} \mid x = \left< a_{k-1}\;\cdots\;a_0\right> \text{ with } a_0^2 + \cdots + a_{k-1}^2 = m \}\right|. \end{equation}
To analyse $N_{k,m}$ we now define a very similar set as used in \eqref{defNkm}, but instead of looking at numbers $x\in\mathbb{Z}$ that have special properties in their NAF representation, we now focus on the NAF sequences itself by modelling them as $k$-tuples: We define $\def\NAF{\mathrm{NAF}}\NAF_{k,m}$ as the subset of $\{-1,0,1\}^k$ with exactly $m$ non-zero entries and confirming to the NAF’s non-adjacent rule $$ \NAF_{k,m} := \left\{ a \in \{-1, 0, 1\}^k \mid a_1^2 + \cdots + a_k^2 = m \text{ and } a_ia_{i+1} = 0 \text{ for } 1\leq i < k \right\}, $$ so we have $$ N_{k,m} = \left| \NAF_{k,m} \right|. $$
And we define $\def\SB{\mathrm{SB}}\SB_{k,m}$ as the set of $k$-tuple over $\{-1, 0, 1\}$ with exactly $m$ non-zero entries: $$ \def\SB{\mathrm{SB}} \SB_{k,m} := \left\{ v \in \{ -1, 0, 1 \}^k \mid v_1^2 + \cdots + v_k^2 = m \right\}. $$ So $\SB_{k,m}$ is the signed binary analogon to $\NAF_{k,m}$ lacking the non-adjacency rule.
We define the function $\Phi$ between $\NAF_{k,m}$ and $\SB_{k-m+1,m}$ which turns a $k$-digit NAF into a $(k-m+1)$-digit signed integer by removing $m-1$ zeros \begin{align*} \Phi : \; &\NAF_{k,m} \rightarrow \SB_{k-m+1,m}, \cr &\left( 0^{e_0} \; 1 \; 0^{e_1} \; \cdots \; 1 \; 0^{e_{m-1}} \; 1 \; 0^{e_m}\right) \mapsto \left( 0^{e_0} \; 1 \; 0^{e_1 - 1} \; \cdots \; 1 \; 0^{e_{m-1}-1} \; 1 \; 0^{e_m} \right). \end{align*}
The notation $0^n$ means $n$ subsequent appearances of the $0$ element in our tuple. So $(1 \; 0^2 \; 1)$ stands for $(1, 0, 0, 1)$ and $(1 \; 0^0 \; 1)$ for $(1, 1)$. The function $\Phi$ is well defined, because $e_i \geq 1$ for $1 \leq i \leq m-1$ and we remove exactly $m-1$ zero-digits. For example we have $$ (1, 0, -1, 0, 0, -1) \mapsto (1, -1, 0, -1) $$ Please note, that while $\Phi$ preserves the number of non-zero elements, it does not preserve the corresponding value of the signed-integer representation!
Since $\Phi$ is obviously invertible it is a bijection and we get $$ \left| \NAF_{k,m} \right| = \left| \SB_{k-m+1, m} \right|. $$
But without the non-adjacency rule $\SB_{k,m}$ can easily be counted $$ \left| \SB_{k,m} \right| = 2^m \binom{k}{m} $$ where $\binom{k}{m}$ denotes the binomial coefficient and we get our result $$ N_{k,m} = \left| \NAF_{k,m} \right| = \left| \SB_{k-m+1,m} \right| = 2^m \binom{k-m+1}{m}. $$
Step 3: The expected value of non-zero digits
The expected value $E_k$ of non-zero digits in a $k$-digit NAF is given by $$ E_k = \frac{1}{R_k}\left(\sum_{m=1}^k m\cdot N_{k,m} \right). $$
To proof that only one third of the digits of a NAF are non-zero on average, we need to show, that $$ \lim_{k\rightarrow\infty} \frac{E_k}{k} = \frac{1}{3}. $$
But to make make any sense out of $E_k$ we have to study it’s numerator $$ \sum_{m=1}^k m\cdot N_{k,m} $$ and for this we need some serious math-voodoo. Let’s define a sequence of polynoms: $$ f_n(x) := \sum_{m=0}^\infty \binom{n-m}{m} x^m, $$ please note that this is a finite sum because the binomial coefficient vanishes whenever $m > n/2$.
The importance of these become clear if you look at $$ f_{k+1}(2) = \sum_{m=0}^\infty \binom{k+1-m}{m} 2^m = \sum_{m=0}^k N_{k,m} = R_k $$ and their derivatives \begin{equation} \label{fder} 2 f’_{k+1}(2) = \sum_{m=1}^\infty m \binom{k+1-m}{m} 2^m = \sum_{m=1}^k m \cdot N_{k,m}. \end{equation}
This should be enough motivation to study $f_n$ more thoroughly. We have \begin{align*} f_0 &= 1\cr f_1 &= 1\cr f_2 &= 1 + x\cr f_3 &= 1 + 2x\cr f_4 &= 1 + 3x + x^2\cr \end{align*} and it is easy to see, that $f_n$ conforms to the recursion \begin{align*} f_{n-1} + x\cdot f_{n-2} &= \sum_{m=0}^\infty \binom{n-1-m}{m}x^m + x\sum_{m=0}^\infty \binom{n-2-m}{m}x^{m}\cr &= \sum_{m=0}^\infty \binom{n-m-1}{m}x^m + \sum_{m=1}^\infty \binom{n-m-1}{m-1}x^m\cr &= 1 + \sum_{m=1}^\infty \binom{n-m}{m}x^m = f_n. \end{align*}
We now define a power series over the ring $\mathbb{Z}[x]$ $$ F := \sum_{k=0}^\infty f_k z^k \in (\mathbb{Z}[x])[\![z]\!] $$ and get \begin{align*} F &= 1 + z + \sum_{k=2}^\infty f_k z^k\cr &= 1 + z + \sum_{k=2}^\infty (f_{k-1} + xf_{k-2}) z^k\cr &= 1 + z + z \sum_{k=1}^\infty f_k z^k + x z^2 \sum_{k=0}^\infty f_k z^k\cr &= 1 + z + z (F-1) + x z^2 F. \end{align*} This yields the closed form $$ F = \frac{1}{1-z-xz^2}. $$
Analysing the $z$-coefficients of $F$ for $x=2$ would result in another proof for $R_k$, but since we are now more interested in \eqref{fder} we look at the $x$-derivate of $F$ $$ G := \sum_{k=0}^\infty 2 f’_{k+1}(2) z^k = 2 z^{-1} \cdot\left.\frac{\partial F}{\partial x} \;\right|_{x=2} = \frac{2z}{(1-z-2z^2)^2}. $$
The denominator of $G$ has the double-roots $z=\frac{1}{2}$ and $z=-1$, so we can factorize it as $$ (1-z-2z^2) = (1+z)^2 (1-2z)^2 $$ and rewrite $G$ using partial fraction decomposition $$ G = \frac{A}{1+z} + \frac{B}{(1+z)^2} + \frac{C}{1-2z} + \frac{D}{(1-2z)^2}, $$ with $A,B,C,D \in \mathbb{Q}$. Now we could easily derive the series expansion of every single summand of $G$ from the geometric series and get a formula for the coefficients $g_k = 2f’_{k+1}(2)$ of $G$: \begin{equation} \label{gkABCD} g_k = A\cdot (-1)^k + B\cdot (k+1)(-1)^k + C\cdot 2^k + D\cdot (k+1) 2^k. \end{equation}
Determining $A,B,C$ and $D$ can be achieved by solving a linear system using four special cases: \begin{align*} 0 &= g_0 = A + B + C + D\cr 2 &= g_1 = -A -2B + 2C + 4D\cr 4 &= g_2 = A + 3B + 4C + 12D\cr 14 &= g_3 = -A -4B + 8C + 32D\cr \end{align*} This gives $A=-\frac{2}{27}, \; B=-\frac{2}{9}, \; C=-\frac{4}{27}$ and $D=\frac{4}{9}$ and plugging these in our formula \eqref{gkABCD} above yields \begin{equation} \label{gkclos} \sum_{m=1}^k m \cdot N_{k,m} = \frac{2}{9} \left( (k+\frac{2}{3})\cdot 2^{k+1} + (k+\frac{4}{3})\cdot (-1)^{k+1} \right). \end{equation}
Now we can finally go back to $E_k$ and proof the main theorem of this section \begin{align*} \lim_{k\rightarrow\infty} \frac{E_k}{k} &= \frac{2}{3} \; \lim_{k\rightarrow\infty} \frac{1}{k} \cdot \frac{(k+\frac{4}{3})\cdot(-1)^{k+1} + (k+\frac{2}{3})\cdot 2^{k+1}}{2^{k+2}-(-1)^k}\cr &= \frac{2}{3} \; \lim_{k\rightarrow\infty} \frac{k+\frac{2}{3}}{k} \;\cdot\; \lim_{k\rightarrow\infty}\frac{2^{k+1}}{2^{k+2}-(-1)^k}\cr &= \frac{1}{3}. \end{align*}
So we expect $\frac{1}{3}$ of the digits to be non-zero on average, just as advertised. :-)
This finally completes our journey. Thx for staying with me!