<p>Conversion from binary to the Zeckendorf representation can be done in uniform <span class="math-container">$\def\tc{\mathrm{TC}^0}\tc$</span>, and a fortiori in logspace.</p>
<p>To fix notation, the Zeckendorf representation of a natural number <span class="math-container">$N$</span> is
<span class="math-container">$$N=\sum_{i\ge0}a_iF_{i+2},$$</span>
where <span class="math-container">$a_i\in\{0,1\}$</span>, <span class="math-container">$F_n$</span> is <span class="math-container">$n$</span>th Fibonacci number, and no two consecutive <span class="math-container">$a_i$</span> are <span class="math-container">$1$</span>. (This is really a finite sum with <span class="math-container">$O(\log N)$</span> terms by the exponential growth of Fibonacci numbers.)</p>
<p>Using standard methods (see in particular Hesse, Allender, Barrington, <em>Uniform constant-depth threshold circuits for division and iterated multiplication</em>), we can compute in <span class="math-container">$\tc$</span> approximations of <span class="math-container">$\sqrt5$</span> and <span class="math-container">$\let\fii\varphi\fii=(1+\sqrt5)/2$</span> to any given precision, approximations of <span class="math-container">$\fii^n$</span> for <span class="math-container">$n$</span> given in unary, <span class="math-container">$F_n=\lfloor\fii^n/\sqrt5\rceil$</span> (where <span class="math-container">$\lfloor x\rceil=\lfloor x+1/2\rfloor$</span>; we only need an approximation of <span class="math-container">$\phi^n/\sqrt5$</span> up to constant additive error here), and things like <span class="math-container">$\lfloor N\fii^{-1}\rfloor$</span>. (For the latter, we can compute an approximation of <span class="math-container">$N\fii^{-1}$</span> to any given precision by the above; since it is a quadratic algebraic number, it has irrationality measure <span class="math-container">$2$</span>, hence if we compute it to <span class="math-container">$\log_2N+O(1)$</span> bits of precision after the binary point, we will know that the integer part of the result is exact.)</p>
<p>Let
<span class="math-container">$$N\let\down\downarrow\down k=\sum_{i\ge0}a_{k+i}F_{i+2},$$</span>
i.e., the number whose Zeckendorf representation is obtained from the one of <span class="math-container">$N$</span> by removing the <span class="math-container">$k$</span> least significant “digits”. Since the <span class="math-container">$k$</span>th Zeckendorf digit of <span class="math-container">$N$</span> is the <span class="math-container">$0$</span>th digit of <span class="math-container">$N\down k$</span>, we are done if we can compute in <span class="math-container">$\tc$</span> <span class="math-container">$N\down k$</span> and the last digit.</p>
<p>Since <span class="math-container">$F_n\sim\fii^n/\sqrt5$</span>, we expect <span class="math-container">$N\down k$</span> to be roughly <span class="math-container">$N\fii^{-k}$</span>. Let us bound the difference. Using the expression <span class="math-container">$F_i=(\fii^i-(-\fii)^{-i})/\sqrt5$</span>, it is easy to show
<span class="math-container">$$F_{k+i}=F_i\fii^k+F_k(-\fii)^{-i},$$</span>
thus
<span class="math-container">$$\begin{align*}
N\fii^{-k}-N\down k&amp;=\fii^{-k}\sum_{i&lt;k}a_iF_{i+2}+\sum_{i\ge0}a_{k+i}(F_{k+i+2}\fii^{-k}-F_{i+2})\\
&amp;=\underbrace{\fii^{-k}\sum_{i&lt;k}a_iF_{i+2}}_A+\underbrace{F_k\fii^{-k}\sum_{i\ge0}a_{k+i}(-\fii)^{-i-2}}_B.
\end{align*}$$</span>
Since <span class="math-container">$\sum_{i&lt;k}a_iF_{i+2}$</span> is the Zeckendorf representation of an integer smaller than the first one whose digit <span class="math-container">$k$</span> is <span class="math-container">$1$</span>, which is <span class="math-container">$F_{k+2}$</span>, we have
<span class="math-container">$$0\le A\le(F_{k+2}-1)\fii^{-k}&lt;\fii^2/\sqrt5;$$</span>
more precisely,
<span class="math-container">$$\begin{align*}
a_{k-1}=0&amp;\implies&amp;0&amp;\le A\le(F_{k+1}-1)\fii^{-k}&lt;\fii/\sqrt5\approx0{.}7236,\\a_{k-1}=1&amp;\implies&amp;\fii/\sqrt5\sim F_{k+1}\fii^{-k}&amp;\le A\le(F_{k+2}-1)\fii^{-k}&lt;\fii^2/\sqrt5\approx1{.}1708.
\end{align*}$$</span>
Also,
<span class="math-container">$$\begin{align*}
B&amp;&gt;-F_k\fii^{-k}(\fii^{-3}+\fii^{-5}+\cdots)=-F_k\fii^{-k-2}\sim-\fii^{-2}/\sqrt5\\
B&amp;&lt;F_k\fii^{-k}(\fii^{-2}+\fii^{-4}+\cdots)=F_k\fii^{-k-1}\sim\fii^{-1}/\sqrt5,
\end{align*}$$</span>
where all the <span class="math-container">$\sim$</span> asymptotics hold in the limit <span class="math-container">$k\to\infty$</span>. More precisely,
<span class="math-container">$$\begin{align*}
a_k=0&amp;\implies B&gt;-F_k\fii^{-k}(\fii^{-3}+\fii^{-5}+\cdots)=-F_k\fii^{-k-2}\sim-\fii^{-2}/\sqrt5\approx-0{.}1708,\\
a_k=0&amp;\implies B&lt;F_k\fii^{-k}(\fii^{-4}+\fii^{-6}+\cdots)=F_k\fii^{-k-3}\sim\fii^{-3}/\sqrt5\approx0{.}1056,\\
a_k=1&amp;\implies B&gt;F_k\fii^{-k}(\fii^{-2}-\fii^{-5}-\fii^{-7}-\cdots)=F_k\fii^{-k-3}\sim\fii^{-3}/\sqrt5\approx0{.}1056,\\
a_k=1&amp;\implies B&lt;F_k\fii^{-k}(\fii^{-2}+\fii^{-4}+\cdots)=F_k\fii^{-k-1}\sim\fii^{-1}/\sqrt5\approx0{.}2764.
\end{align*}$$</span></p>
<p>We can draw the following consequences:</p>
<ul>
<li><p><strong>We can compute <span class="math-container">$N\down1$</span> and <span class="math-container">$a_0$</span> in <span class="math-container">$\tc$</span>.</strong> Indeed, for <span class="math-container">$k=1$</span>, we obtain (using <span class="math-container">$a_0=1\implies a_1=0$</span>)
<span class="math-container">$$\begin{align*}
a_0=0&amp;\implies&amp;-\fii^{-3}&amp;&lt;N\fii^{-1}-N\down1&lt;\fii^{-2},\\
a_0=1&amp;\implies&amp;\fii^{-1}-\fii^{-3}=\fii^{-2}&amp;&lt;N\fii^{-1}-N\down1&lt;\fii^{-1}+\fii^{-4}=1-\fii^{-3}.
\end{align*}$$</span>
Thus,
<span class="math-container">$$\begin{align*}
N\down1&amp;=\lfloor N\fii^{-1}+\fii^{-3}\rfloor,\\
a_0&amp;=1\iff\{N\fii^{-1}+\fii^{-3}\}&gt;\fii^{-1},\\
\text{i.o.w.: }a_0&amp;=\lfloor(N+\fii^{-2})\bmod\fii\rfloor.
\end{align*}$$</span></p>
</li>
<li><p><strong>We can compute in <span class="math-container">$\tc$</span> two candidates for <span class="math-container">$N\down k$</span> that differ by <span class="math-container">$1$</span>.</strong> Taking into account that <span class="math-container">$a_{k-1}=a_k=1$</span> cannot happen, the bounds on <span class="math-container">$A$</span> and <span class="math-container">$B$</span> above imply
<span class="math-container">$$\begin{align*}
N\fii^{-k}-N\down k&amp;&gt;-F_k\fii^{-k-2}\sim-\fii^{-2}/\sqrt5\approx-0{.}1708,\\
N\fii^{-k}-N\down k&amp;&lt;(F_{k+2}-1)\fii^{-k}+F_k\fii^{-k-3}\sim(\fii^2+\fii^{-3})/\sqrt5\approx1{.}2764.
\end{align*}$$</span>
We see that <span class="math-container">$N\down k$</span> is <span class="math-container">$\lfloor N\fii^{-k}\rceil$</span> or <span class="math-container">$\lfloor N\fii^{-k}\rceil-1$</span>. (There is leeway in the bounds here, thus it suffices to take an approximation of <span class="math-container">$N\fii^{-k}$</span> up to constant additive error.)</p>
</li>
</ul>
<p>We can compute in <span class="math-container">$\tc$</span> the pairs of candidates <span class="math-container">$N_k^+=\lfloor N\fii^{-k}\rceil$</span> and <span class="math-container">$N_k^-=N_k^+-1$</span> for all <span class="math-container">$k\le\lceil\log_\fii N\rceil$</span> in parallel. We can then select which candidates are correct using suitable consistency checks as follows.</p>
<p>Since the <span class="math-container">${}\down1$</span> operation is nondecreasing and nonexpanding, we have <span class="math-container">$N_k^+\down1=N_k^-\down1$</span> or <span class="math-container">$N_k^+\down1=(N_k^-\down1)+1$</span>. In view of the fact that <span class="math-container">$N\down k\in\{N_k^+,N_k^-\}$</span> and <span class="math-container">$N\down(k+1)\in\{N_{k+1}^+,N_{k+1}^-\}$</span> satisfy <span class="math-container">$(N\down k)\down1=N\down(k+1)$</span>, one of the following cases must happen for each <span class="math-container">$k$</span>:</p>
<ul>
<li><p><span class="math-container">$N_k^+\down1=N_{k+1}^-$</span>. Then also <span class="math-container">$N_k^-\down1\le N_{k+1}^-$</span>, hence the only possibility is <span class="math-container">$N\down(k+1)=N_{k+1}^-$</span>. We indicate this by an auxiliary variable <span class="math-container">$c_{k+1}=-1$</span>.</p>
</li>
<li><p><span class="math-container">$N_k^-\down1=N_{k+1}^+$</span>. Then <span class="math-container">$N\down(k+1)=N_{k+1}^+$</span>, and we put <span class="math-container">$c_{k+1}=+1$</span>.</p>
</li>
<li><p><span class="math-container">$N_k^+\down1=N_{k+1}^+$</span> and <span class="math-container">$N_k^-\down1=N_{k+1}^-$</span>. We put <span class="math-container">$c_{k+1}=0$</span>.</p>
</li>
</ul>
<p>We also have <span class="math-container">$N\down0=N=N_0^+$</span>, hence we put <span class="math-container">$c_0=+1$</span>. Again, we can compute all the <span class="math-container">$c_k$</span> in parallel in <span class="math-container">$\tc$</span>. Now we can compute <span class="math-container">$N\down k$</span> in <span class="math-container">$\tc$</span> by
<span class="math-container">$$N\down k=\begin{cases}N_k^+,&amp;\text{if }\exists i\le k\:c_i=+1,c_{i+1}=\dots=c_k=0,\\
N_k^-,&amp;\text{if }\exists i\le k\:c_i=-1,c_{i+1}=\dots=c_k=0.
\end{cases}$$</span>
(Exactly one of these two cases happens. If <span class="math-container">$i=k$</span>, we of course interpret “<span class="math-container">$c_{i+1}=\dots=c_k=0$</span>” as vacuously true.)</p>
<p>Finally, we extract <span class="math-container">$a_k=\lfloor((N\down k)+\fii^{-2})\bmod\fii\rfloor$</span> using the expression for <span class="math-container">$a_0$</span> above.</p>

CC BY-SA 4.0
2024-09-20T19:54:28.657Z
What does approximation exponent mean?
Turbo
CC BY-SA 4.0
2024-09-21T10:58:26.473Z
I changed it to the more common term “irrationality measure”.
Emil Jeřábek
CC BY-SA 4.0
2024-09-20T16:02:15.987Z
2024-09-21T10:57:40.373Z
2024-09-21T10:57:40.373Z
Emil Jeřábek
<p>By <a href="https://math.osu.edu/sites/math.osu.edu/files/henderson_zeckendorf.pdf" rel="nofollow noreferrer">Zeckendorf's theorem</a> any given integer can be represented as sum of Fibonacci numbers.</p>
<p>Given <span class="math-container">$n\in\mathbb N_{\geq 3}$</span> is there a logspace algorithm to represent <span class="math-container">$n$</span> as sum of <span class="math-container">$O(polylog(n))$</span> Fibonacci numbers?</p>
<p>There is a greedy algorithm but I am not sure if it is in Logspace and has <span class="math-container">$O(polylog(n))$</span> digits.</p>

CC BY-SA 4.0
2024-09-16T06:43:36.447Z
$n$ is given in binary, I assume? Then the greedy algorithm isn't logspace, and I don't believe this can be done, but I'm not sure. Do you know is base conversion can be done in logspace?
Command Master
CC BY-SA 4.0
2024-09-16T06:45:29.443Z
Fibonacci numbers grow exponentially. Thus the Zeckendorf representation, or more generally any representation as a sum of Fibonacci numbers with bounded multiplicity, obviously has only $O(\log n)$ “digits”.
Emil Jeřábek
CC BY-SA 4.0
2024-09-16T06:46:55.073Z
@CommandMaster Base conversion can be done in logspace, in fact in uniform $\mathrm{TC}^0$, and I’d expect this to be possible for Zeckendorf representation as well.
Emil Jeřábek
CC BY-SA 4.0
2024-09-16T06:54:46.927Z
@EmilJeřábek could you give a reference for that result?
Command Master
CC BY-SA 4.0
2024-09-16T07:02:50.463Z
@CommandMaster As with all nontrivial results about coputability in uniform $\mathrm{TC}^0$, the ultimate reference is Hesse, Allender, and Barrington, *Uniform constant-depth threshold circuits for division and iterated multiplication*. (Conversion from base $b$ to binary is $\vec a\mapsto\sum_ia_ib^i$, conversion from binary to base $b$ is $x\mapsto\langle\lfloor x/b^i\rfloor\bmod b:i<\log x\rangle$, thus what you really need is that you can compute bounded sums (this is easy), powering with unary exponents, and division with remainder (these two are difficult).) ...
Emil Jeřábek
CC BY-SA 4.0
2024-09-16T07:04:38.120Z
... For logspace computability, the results from the earlier paper of Chiu, Davida, and Litow suffice (but the HAB algorithm is more elegant anyway).
Emil Jeřábek
CC BY-SA 4.0
2024-09-16T07:05:39.020Z
And the result that uniform $\textbf{TC}^0$ is in $L$ is a consequence of Barrington's theorem, right?
Command Master
CC BY-SA 4.0
2024-09-16T07:06:58.690Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/155267/discussion-between-command-master-and-emil-jerabek).
Command Master
CC BY-SA 4.0
2024-09-16T07:20:15.887Z
Uniform $\mathrm{TC}^0$ is in L more or less trivially from the definition.
Emil Jeřábek
<nt.number-theory><logspace><comp-number-theory>
Logspace computation of Zeckendorf representation
Turbo
# Logspace computation of Zeckendorf representation

(Asked by: username_0 on 2024-09-16)

By [Zeckendorf's theorem](https://math.osu.edu/sites/math.osu.edu/files/henderson_zeckendorf.pdf) any given integer can be represented as sum of Fibonacci numbers.

Given $n\in\mathbb N\_{\geq 3}$ is there a logspace algorithm to represent $n$ as sum of $O(polylog(n))$ Fibonacci numbers?

There is a greedy algorithm but I am not sure if it is in Logspace and has $O(polylog(n))$ digits.

**Tags:** nt.number-theory, logspace, comp-number-theory

> **Comments:**
> **username_1**: $n$ is given in binary, I assume? Then the greedy algorithm isn't logspace, and I don't believe this can be done, but I'm not sure. Do you know is base conversion can be done in logspace?  
> **username_2**: Fibonacci numbers grow exponentially. Thus the Zeckendorf representation, or more generally any representation as a sum of Fibonacci numbers with bounded multiplicity, obviously has only $O(\log n)$ “digits”.  
> **username_2**: @CommandMaster Base conversion can be done in logspace, in fact in uniform $\mathrm{TC}^0$, and I’d expect this to be possible for Zeckendorf representation as well.  
> **username_1**: @EmilJeřábek could you give a reference for that result?  
> **username_2**: @CommandMaster As with all nontrivial results about coputability in uniform $\mathrm{TC}^0$, the ultimate reference is Hesse, Allender, and Barrington, *Uniform constant-depth threshold circuits for division and iterated multiplication*. (Conversion from base $b$ to binary is $\vec a\mapsto\sum_ia_ib^i$, conversion from binary to base $b$ is $x\mapsto\langle\lfloor x/b^i\rfloor\bmod b:i<\log x\rangle$, thus what you really need is that you can compute bounded sums (this is easy), powering with unary exponents, and division with remainder (these two are difficult).) ...  
> **username_2**: ... For logspace computability, the results from the earlier paper of Chiu, Davida, and Litow suffice (but the HAB algorithm is more elegant anyway).  
> **username_1**: And the result that uniform $\textbf{TC}^0$ is in $L$ is a consequence of Barrington's theorem, right?  
> **username_1**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/155267/discussion-between-command-master-and-emil-jerabek).  
> **username_2**: Uniform $\mathrm{TC}^0$ is in L more or less trivially from the definition.  

---

## 1 answers

### Answer by username_2 on 2024-09-20. Score: 4 | Accepted answer

Conversion from binary to the Zeckendorf representation can be done in uniform $\def\tc{\mathrm{TC}^0}\tc$, and a fortiori in logspace.

To fix notation, the Zeckendorf representation of a natural number $N$ is
$$N=\sum\_{i\ge0}a\_iF\_{i+2},$$
where $a\_i\in\{0,1\}$, $F\_n$ is $n$th Fibonacci number, and no two consecutive $a\_i$ are $1$. (This is really a finite sum with $O(\log N)$ terms by the exponential growth of Fibonacci numbers.)

Using standard methods (see in particular Hesse, Allender, Barrington, *Uniform constant-depth threshold circuits for division and iterated multiplication*), we can compute in $\tc$ approximations of $\sqrt5$ and $\let\fii\varphi\fii=(1+\sqrt5)/2$ to any given precision, approximations of $\fii^n$ for $n$ given in unary, $F\_n=\lfloor\fii^n/\sqrt5\rceil$ (where $\lfloor x\rceil=\lfloor x+1/2\rfloor$; we only need an approximation of $\phi^n/\sqrt5$ up to constant additive error here), and things like $\lfloor N\fii^{-1}\rfloor$. (For the latter, we can compute an approximation of $N\fii^{-1}$ to any given precision by the above; since it is a quadratic algebraic number, it has irrationality measure $2$, hence if we compute it to $\log\_2N+O(1)$ bits of precision after the binary point, we will know that the integer part of the result is exact.)

Let
$$N\let\down\downarrow\down k=\sum\_{i\ge0}a\_{k+i}F\_{i+2},$$
i.e., the number whose Zeckendorf representation is obtained from the one of $N$ by removing the $k$ least significant “digits”. Since the $k$th Zeckendorf digit of $N$ is the $0$th digit of $N\down k$, we are done if we can compute in $\tc$ $N\down k$ and the last digit.

Since $F\_n\sim\fii^n/\sqrt5$, we expect $N\down k$ to be roughly $N\fii^{-k}$. Let us bound the difference. Using the expression $F\_i=(\fii^i-(-\fii)^{-i})/\sqrt5$, it is easy to show
$$F\_{k+i}=F\_i\fii^k+F\_k(-\fii)^{-i},$$
thus
$$\begin{align\*}
N\fii^{-k}-N\down k&=\fii^{-k}\sum\_{i
Since $\sum\_{i is the Zeckendorf representation of an integer smaller than the first one whose digit $k$ is $1$, which is $F\_{k+2}$, we have
$$0\le A\le(F\_{k+2}-1)\fii^{-k}<\fii^2/\sqrt5;$$
more precisely,
$$\begin{align\*}
a\_{k-1}=0&\implies&0&\le A\le(F\_{k+1}-1)\fii^{-k}<\fii/\sqrt5\approx0{.}7236,\\a\_{k-1}=1&\implies&\fii/\sqrt5\sim F\_{k+1}\fii^{-k}&\le A\le(F\_{k+2}-1)\fii^{-k}<\fii^2/\sqrt5\approx1{.}1708.
\end{align\*}$$
Also,
$$\begin{align\*}
B&>-F\_k\fii^{-k}(\fii^{-3}+\fii^{-5}+\cdots)=-F\_k\fii^{-k-2}\sim-\fii^{-2}/\sqrt5\\
B&
where all the $\sim$ asymptotics hold in the limit $k\to\infty$. More precisely,
$$\begin{align\*}
a\_k=0&\implies B>-F\_k\fii^{-k}(\fii^{-3}+\fii^{-5}+\cdots)=-F\_k\fii^{-k-2}\sim-\fii^{-2}/\sqrt5\approx-0{.}1708,\\
a\_k=0&\implies BF\_k\fii^{-k}(\fii^{-2}-\fii^{-5}-\fii^{-7}-\cdots)=F\_k\fii^{-k-3}\sim\fii^{-3}/\sqrt5\approx0{.}1056,\\
a\_k=1&\implies B

We can draw the following consequences:

* **We can compute $N\down1$ and $a\_0$ in $\tc$.** Indeed, for $k=1$, we obtain (using $a\_0=1\implies a\_1=0$)
  $$\begin{align\*}
  a\_0=0&\implies&-\fii^{-3}&
  Thus,
  $$\begin{align\*}
  N\down1&=\lfloor N\fii^{-1}+\fii^{-3}\rfloor,\\
  a\_0&=1\iff\{N\fii^{-1}+\fii^{-3}\}>\fii^{-1},\\
  \text{i.o.w.: }a\_0&=\lfloor(N+\fii^{-2})\bmod\fii\rfloor.
  \end{align\*}$$
* **We can compute in $\tc$ two candidates for $N\down k$ that differ by $1$.** Taking into account that $a\_{k-1}=a\_k=1$ cannot happen, the bounds on $A$ and $B$ above imply
  $$\begin{align\*}
  N\fii^{-k}-N\down k&>-F\_k\fii^{-k-2}\sim-\fii^{-2}/\sqrt5\approx-0{.}1708,\\
  N\fii^{-k}-N\down k&<(F\_{k+2}-1)\fii^{-k}+F\_k\fii^{-k-3}\sim(\fii^2+\fii^{-3})/\sqrt5\approx1{.}2764.
  \end{align\*}$$
  We see that $N\down k$ is $\lfloor N\fii^{-k}\rceil$ or $\lfloor N\fii^{-k}\rceil-1$. (There is leeway in the bounds here, thus it suffices to take an approximation of $N\fii^{-k}$ up to constant additive error.)

We can compute in $\tc$ the pairs of candidates $N\_k^+=\lfloor N\fii^{-k}\rceil$ and $N\_k^-=N\_k^+-1$ for all $k\le\lceil\log\_\fii N\rceil$ in parallel. We can then select which candidates are correct using suitable consistency checks as follows.

Since the ${}\down1$ operation is nondecreasing and nonexpanding, we have $N\_k^+\down1=N\_k^-\down1$ or $N\_k^+\down1=(N\_k^-\down1)+1$. In view of the fact that $N\down k\in\{N\_k^+,N\_k^-\}$ and $N\down(k+1)\in\{N\_{k+1}^+,N\_{k+1}^-\}$ satisfy $(N\down k)\down1=N\down(k+1)$, one of the following cases must happen for each $k$:

* $N\_k^+\down1=N\_{k+1}^-$. Then also $N\_k^-\down1\le N\_{k+1}^-$, hence the only possibility is $N\down(k+1)=N\_{k+1}^-$. We indicate this by an auxiliary variable $c\_{k+1}=-1$.
* $N\_k^-\down1=N\_{k+1}^+$. Then $N\down(k+1)=N\_{k+1}^+$, and we put $c\_{k+1}=+1$.
* $N\_k^+\down1=N\_{k+1}^+$ and $N\_k^-\down1=N\_{k+1}^-$. We put $c\_{k+1}=0$.

We also have $N\down0=N=N\_0^+$, hence we put $c\_0=+1$. Again, we can compute all the $c\_k$ in parallel in $\tc$. Now we can compute $N\down k$ in $\tc$ by
$$N\down k=\begin{cases}N\_k^+,&\text{if }\exists i\le k\:c\_i=+1,c\_{i+1}=\dots=c\_k=0,\\
N\_k^-,&\text{if }\exists i\le k\:c\_i=-1,c\_{i+1}=\dots=c\_k=0.
\end{cases}$$
(Exactly one of these two cases happens. If $i=k$, we of course interpret “$c\_{i+1}=\dots=c\_k=0$” as vacuously true.)

Finally, we extract $a\_k=\lfloor((N\down k)+\fii^{-2})\bmod\fii\rfloor$ using the expression for $a\_0$ above.

> **Comments:**
> **username_0**: What does approximation exponent mean?  
> **username_2**: I changed it to the more common term “irrationality measure”.  

---

