Non-integer base of numeration

${\displaystyle x=d_n\dots d_2{d}_1{d}_0.d_{-1}{d}_{-2}\dots d_{-m}}$

is

${\displaystyle \begin{array}{cc}x& ={\beta }^n{d}_n+\cdots +{\beta }^2{d}_2+\beta d_1+d_0\\ & +{\beta }^{-1}{d}_{-1}+{\beta }^{-2}{d}_{-2}+\cdots +{\beta }^{-m}{d}_{-m}.\end{array}}$

The numbers d_i are non-negative integers less than β. This is also known as a β-expansion, a notion introduced by Rényi (1957) and first studied in detail by Parry (1960). Every real number has at least one (possibly infinite) β-expansion. The set of all β-expansions that have a finite representation is a subset of the ring Z[β, β⁻¹].

There are applications of β-expansions in coding theory and models of quasicrystals.

Construction

β-expansions are a generalization of decimal expansions. While infinite decimal expansions are not unique (for example, 1.000... = 0.999...), all finite decimal expansions are unique. However, even finite β-expansions are not necessarily unique, for example φ + 1 = φ² for β = φ, the golden ratio. A canonical choice for the β-expansion of a given real number can be determined by the following greedy algorithm, essentially due to Rényi (1957) and formulated as given here by Frougny (1992).

Let β > 1 be the base and x a non-negative real number. Denote by ⌊x⌋ the floor function of x (that is, the greatest integer less than or equal to x) and let {x} = x − ⌊x⌋ be the fractional part of x. There exists an integer k such that β^k ≤ x < β^k+1. Set

${\displaystyle d_k=\lfloor x/{\beta }^k\rfloor }$

and

${\displaystyle r_k=\{x/{\beta }^k\}.}$

For k − 1 ≥ j > −∞, put

${\displaystyle d_j=\lfloor \beta r_{j+1}\rfloor ,r_j=\{\beta r_{j+1}\}.}$

In other words, the canonical β-expansion of x is defined by choosing the largest d_k such that β^kd_k ≤ x, then choosing the largest d_k−1 such that β^kd_k + β^k−1d_k−1 ≤ x, and so on. Thus it chooses the lexicographically largest string representing x.

With an integer base, this defines the usual radix expansion for the number x. This construction extends the usual algorithm to possibly non-integer values of β.

Conversion

Following the steps above, we can create a β-expansion for a real number ${\displaystyle n\ge 0}$ (the steps are identical for an ${\displaystyle n<0}$, although n must first be multiplied by −1 to make it positive, then the result must be multiplied by −1 to make it negative again).

First, we must define our k value (the exponent of the nearest power of β greater than n, as well as the amount of digits in ${\displaystyle \lfloor n_{\beta }\rfloor }$, where ${\displaystyle n_{\beta }}$ is n written in base β). The k value for n and β can be written as:

${\displaystyle k=\lfloor {\log }_{\beta }(n)\rfloor +1}$

After a k value is found, ${\displaystyle n_{\beta }}$ can be written as d, where

${\displaystyle d_j=\lfloor (n/{\beta }^j)mod\beta \rfloor ,n=n-d_j\ast {\beta }^j}$

for k − 1 ≥ j > −∞. The first k values of d appear to the left of the decimal place.

This can also be written in the following pseudocode:

<span id="mwlQ"></span><span class="kd" id="mwlg">function</span><span class="w" id="mwlw"> </span><span class="nx" id="mwmA">toBase</span><span class="p" id="mwmQ">(</span><span class="nx" id="mwmg">n</span><span class="p" id="mwmw">,</span><span class="w" id="mwnA"> </span><span class="nx" id="mwnQ">b</span><span class="p" id="mwng">)</span><span class="w" id="mwnw"> </span><span class="p" id="mwoA">{</span> <span class="w" id="mwoQ"> </span><span class="nx" id="mwog">k</span><span class="w" id="mwow"> </span><span class="o" id="mwpA">=</span><span class="w" id="mwpQ"> </span><span class="nx" id="mwpg">floor</span><span class="p" id="mwpw">(</span><span class="nx" id="mwqA">log</span><span class="p" id="mwqQ">(</span><span class="nx" id="mwqg">b</span><span class="p" id="mwqw">,</span><span class="w" id="mwrA"> </span><span class="nx" id="mwrQ">n</span><span class="p" id="mwrg">))</span><span class="w" id="mwrw"> </span><span class="o" id="mwsA">+</span><span class="w" id="mwsQ"> </span><span class="mf" id="mwsg">1</span> <span class="w" id="mwsw"> </span><span class="nx" id="mwtA">precision</span><span class="w" id="mwtQ"> </span><span class="o" id="mwtg">=</span><span class="w" id="mwtw"> </span><span class="mf" id="mwuA">8</span> <span class="w" id="mwuQ"> </span><span class="nx" id="mwug">result</span><span class="w" id="mwuw"> </span><span class="o" id="mwvA">=</span><span class="w" id="mwvQ"> </span><span class="s2" id="mwvg">""</span> <span class="w" id="mwvw"> </span><span class="k" id="mwwA">for</span><span class="w" id="mwwQ"> </span><span class="p" id="mwwg">(</span><span class="nx" id="mwww">i</span><span class="w" id="mwxA"> </span><span class="o" id="mwxQ">=</span><span class="w" id="mwxg"> </span><span class="nx" id="mwxw">k</span><span class="w" id="mwyA"> </span><span class="o" id="mwyQ">-</span><span class="w" id="mwyg"> </span><span class="mf" id="mwyw">1</span><span class="p" id="mwzA">,</span><span class="w" id="mwzQ"> </span><span class="nx" id="mwzg">i</span><span class="w" id="mwzw"> </span><span class="o" id="mw0A">></span><span class="w" id="mw0Q"> </span><span class="o" id="mw0g">-</span><span class="nx" id="mw0w">precision</span><span class="o" id="mw1A">-</span><span class="mf" id="mw1Q">1</span><span class="p" id="mw1g">,</span><span class="w" id="mw1w"> </span><span class="nx" id="mw2A">i</span><span class="o" id="mw2Q">--</span><span class="p" id="mw2g">)</span><span class="w" id="mw2w"> </span><span class="p" id="mw3A">{</span> <span class="w" id="mw3Q"> </span><span class="k" id="mw3g">if</span><span class="w" id="mw3w"> </span><span class="p" id="mw4A">(</span><span class="nx" id="mw4Q">result</span><span class="p" id="mw4g">.</span><span class="nx" id="mw4w">length</span><span class="w" id="mw5A"> </span><span class="o" id="mw5Q">==</span><span class="w" id="mw5g"> </span><span class="nx" id="mw5w">k</span><span class="p" id="mw6A">)</span><span class="w" id="mw6Q"> </span><span class="nx" id="mw6g">result</span><span class="w" id="mw6w"> </span><span class="o" id="mw7A">+=</span><span class="w" id="mw7Q"> </span><span class="s2" id="mw7g">"."</span> <span class="w" id="mw7w"> </span> <span class="w" id="mw8A"> </span><span class="nx" id="mw8Q">digit</span><span class="w" id="mw8g"> </span><span class="o" id="mw8w">=</span><span class="w" id="mw9A"> </span><span class="nx" id="mw9Q">floor</span><span class="p" id="mw9g">((</span><span class="nx" id="mw9w">n</span><span class="w" id="mw-A"> </span><span class="o" id="mw-Q">/</span><span class="w" id="mw-g"> </span><span class="nx" id="mw-w">b</span><span class="o" id="mw_A">^</span><span class="nx" id="mw_Q">i</span><span class="p" id="mw_g">)</span><span class="w" id="mw_w"> </span><span class="nx" id="mwAQA">mod</span><span class="w" id="mwAQE"> </span><span class="nx" id="mwAQI">b</span><span class="p" id="mwAQM">)</span> <span class="w" id="mwAQQ"> </span><span class="nx" id="mwAQU">n</span><span class="w" id="mwAQY"> </span><span class="o" id="mwAQc">-=</span><span class="w" id="mwAQg"> </span><span class="nx" id="mwAQk">digit</span><span class="w" id="mwAQo"> </span><span class="o" id="mwAQs">*</span><span class="w" id="mwAQw"> </span><span class="nx" id="mwAQ0">b</span><span class="o" id="mwAQ4">^</span><span class="nx" id="mwAQ8">i</span> <span class="w" id="mwARA"> </span><span class="nx" id="mwARE">result</span><span class="w" id="mwARI"> </span><span class="o" id="mwARM">+=</span><span class="w" id="mwARQ"> </span><span class="nx" id="mwARU">digit</span> <span class="w" id="mwARY"> </span><span class="p" id="mwARc">}</span> <span class="w" id="mwARg"> </span><span class="k" id="mwARk">return</span><span class="w" id="mwARo"> </span><span class="nx" id="mwARs">result</span> <span class="p" id="mwARw">}</span>

Note that the above code is only valid for ${\displaystyle 1<\beta \le 10}$ and ${\displaystyle n\ge 0}$, as it does not convert each digits to their correct symbols or correct negative numbers. For example, if a digit's value is 10, it will be represented as 10 instead of A.

Example implementation code

To base π

• JavaScript:

  <span id="mwAS8"></span><span class="kd" id="mwATA">function</span><span class="w" id="mwATE"> </span><span class="nx" id="mwATI">toBasePI</span><span class="p" id="mwATM">(</span><span class="nx" id="mwATQ">num</span><span class="p" id="mwATU">,</span><span class="w" id="mwATY"> </span><span class="nx" id="mwATc">precision</span><span class="w" id="mwATg"> </span><span class="o" id="mwATk">=</span><span class="w" id="mwATo"> </span><span class="mf" id="mwATs">8</span><span class="p" id="mwATw">)</span><span class="w" id="mwAT0"> </span><span class="p" id="mwAT4">{</span><span class="w" id="mwAT8"> </span> <span class="w" id="mwAUA"> </span><span class="kd" id="mwAUE">let</span><span class="w" id="mwAUI"> </span><span class="nx" id="mwAUM">k</span><span class="w" id="mwAUQ"> </span><span class="o" id="mwAUU">=</span><span class="w" id="mwAUY"> </span><span class="nb" id="mwAUc">Math</span><span class="p" id="mwAUg">.</span><span class="nx" id="mwAUk">floor</span><span class="p" id="mwAUo">(</span><span class="nb" id="mwAUs">Math</span><span class="p" id="mwAUw">.</span><span class="nx" id="mwAU0">log</span><span class="p" id="mwAU4">(</span><span class="nx" id="mwAU8">num</span><span class="p" id="mwAVA">)</span><span class="o" id="mwAVE">/</span><span class="nb" id="mwAVI">Math</span><span class="p" id="mwAVM">.</span><span class="nx" id="mwAVQ">log</span><span class="p" id="mwAVU">(</span><span class="nb" id="mwAVY">Math</span><span class="p" id="mwAVc">.</span><span class="nx" id="mwAVg">PI</span><span class="p" id="mwAVk">))</span><span class="w" id="mwAVo"> </span><span class="o" id="mwAVs">+</span><span class="w" id="mwAVw"> </span><span class="mf" id="mwAV0">1</span><span class="p" id="mwAV4">;</span> <span class="w" id="mwAV8"> </span><span class="k" id="mwAWA">if</span><span class="w" id="mwAWE"> </span><span class="p" id="mwAWI">(</span><span class="nx" id="mwAWM">k</span><span class="w" id="mwAWQ"> </span><span class="o" id="mwAWU"><</span><span class="w" id="mwAWY"> </span><span class="mf" id="mwAWc">0</span><span class="p" id="mwAWg">)</span><span class="w" id="mwAWk"> </span><span class="nx" id="mwAWo">k</span><span class="w" id="mwAWs"> </span><span class="o" id="mwAWw">=</span><span class="w" id="mwAW0"> </span><span class="mf" id="mwAW4">0</span><span class="p" id="mwAW8">;</span> <span class="w" id="mwAXA"> </span><span class="kd" id="mwAXE">let</span><span class="w" id="mwAXI"> </span><span class="nx" id="mwAXM">digits</span><span class="w" id="mwAXQ"> </span><span class="o" id="mwAXU">=</span><span class="w" id="mwAXY"> </span><span class="p" id="mwAXc">[];</span> <span class="w" id="mwAXg"> </span><span class="k" id="mwAXk">for</span><span class="w" id="mwAXo"> </span><span class="p" id="mwAXs">(</span><span class="kd" id="mwAXw">let</span><span class="w" id="mwAX0"> </span><span class="nx" id="mwAX4">i</span><span class="w" id="mwAX8"> </span><span class="o" id="mwAYA">=</span><span class="w" id="mwAYE"> </span><span class="nx" id="mwAYI">k</span><span class="o" id="mwAYM">-</span><span class="mf" id="mwAYQ">1</span><span class="p" id="mwAYU">;</span><span class="w" id="mwAYY"> </span><span class="nx" id="mwAYc">i</span><span class="w" id="mwAYg"> </span><span class="o" id="mwAYk">></span><span class="w" id="mwAYo"> </span><span class="p" id="mwAYs">(</span><span class="o" id="mwAYw">-</span><span class="mf" id="mwAY0">1</span><span class="o" id="mwAY4">*</span><span class="nx" id="mwAY8">precision</span><span class="p" id="mwAZA">)</span><span class="o" id="mwAZE">-</span><span class="mf" id="mwAZI">1</span><span class="p" id="mwAZM">;</span><span class="w" id="mwAZQ"> </span><span class="nx" id="mwAZU">i</span><span class="o" id="mwAZY">--</span><span class="p" id="mwAZc">)</span><span class="w" id="mwAZg"> </span><span class="p" id="mwAZk">{</span> <span class="w" id="mwAZo"> </span><span class="kd" id="mwAZs">let</span><span class="w" id="mwAZw"> </span><span class="nx" id="mwAZ0">digit</span><span class="w" id="mwAZ4"> </span><span class="o" id="mwAZ8">=</span><span class="w" id="mwAaA"> </span><span class="nb" id="mwAaE">Math</span><span class="p" id="mwAaI">.</span><span class="nx" id="mwAaM">floor</span><span class="p" id="mwAaQ">((</span><span class="nx" id="mwAaU">num</span><span class="w" id="mwAaY"> </span><span class="o" id="mwAac">/</span><span class="w" id="mwAag"> </span><span class="nb" id="mwAak">Math</span><span class="p" id="mwAao">.</span><span class="nx" id="mwAas">pow</span><span class="p" id="mwAaw">(</span><span class="nb" id="mwAa0">Math</span><span class="p" id="mwAa4">.</span><span class="nx" id="mwAa8">PI</span><span class="p" id="mwAbA">,</span><span class="w" id="mwAbE"> </span><span class="nx" id="mwAbI">i</span><span class="p" id="mwAbM">))</span><span class="w" id="mwAbQ"> </span><span class="o" id="mwAbU">%</span><span class="w" id="mwAbY"> </span><span class="nb" id="mwAbc">Math</span><span class="p" id="mwAbg">.</span><span class="nx" id="mwAbk">PI</span><span class="p" id="mwAbo">);</span> <span class="w" id="mwAbs"> </span><span class="nx" id="mwAbw">num</span><span class="w" id="mwAb0"> </span><span class="o" id="mwAb4">-=</span><span class="w" id="mwAb8"> </span><span class="nx" id="mwAcA">digit</span><span class="w" id="mwAcE"> </span><span class="o" id="mwAcI">*</span><span class="w" id="mwAcM"> </span><span class="nb" id="mwAcQ">Math</span><span class="p" id="mwAcU">.</span><span class="nx" id="mwAcY">pow</span><span class="p" id="mwAcc">(</span><span class="nb" id="mwAcg">Math</span><span class="p" id="mwAck">.</span><span class="nx" id="mwAco">PI</span><span class="p" id="mwAcs">,</span><span class="w" id="mwAcw"> </span><span class="nx" id="mwAc0">i</span><span class="p" id="mwAc4">);</span> <span class="w" id="mwAc8"> </span><span class="nx" id="mwAdA">digits</span><span class="p" id="mwAdE">.</span><span class="nx" id="mwAdI">push</span><span class="p" id="mwAdM">(</span><span class="nx" id="mwAdQ">digit</span><span class="p" id="mwAdU">);</span> <span class="w" id="mwAdY"> </span><span class="k" id="mwAdc">if</span><span class="w" id="mwAdg"> </span><span class="p" id="mwAdk">(</span><span class="nx" id="mwAdo">num</span><span class="w" id="mwAds"> </span><span class="o" id="mwAdw"><</span><span class="w" id="mwAd0"> </span><span class="mf" id="mwAd4">0.1</span><span class="o" id="mwAd8">**</span><span class="p" id="mwAeA">(</span><span class="nx" id="mwAeE">precision</span><span class="o" id="mwAeI">+</span><span class="mf" id="mwAeM">1</span><span class="p" id="mwAeQ">)</span><span class="w" id="mwAeU"> </span><span class="o" id="mwAeY">&&</span><span class="w" id="mwAec"> </span><span class="nx" id="mwAeg">i</span><span class="w" id="mwAek"> </span><span class="o" id="mwAeo"><=</span><span class="w" id="mwAes"> </span><span class="mf" id="mwAew">0</span><span class="p" id="mwAe0">)</span> <span class="w" id="mwAe4"> </span><span class="k" id="mwAe8">break</span><span class="p" id="mwAfA">;</span> <span class="w" id="mwAfE"> </span><span class="p" id="mwAfI">}</span> <span class="w" id="mwAfM"> </span><span class="k" id="mwAfQ">if</span><span class="w" id="mwAfU"> </span><span class="p" id="mwAfY">(</span><span class="nx" id="mwAfc">digits</span><span class="p" id="mwAfg">.</span><span class="nx" id="mwAfk">length</span><span class="w" id="mwAfo"> </span><span class="o" id="mwAfs">></span><span class="w" id="mwAfw"> </span><span class="nx" id="mwAf0">k</span><span class="p" id="mwAf4">)</span> <span class="w" id="mwAf8"> </span><span class="nx" id="mwAgA">digits</span><span class="p" id="mwAgE">.</span><span class="nx" id="mwAgI">splice</span><span class="p" id="mwAgM">(</span><span class="nx" id="mwAgQ">k</span><span class="p" id="mwAgU">,</span><span class="w" id="mwAgY"> </span><span class="mf" id="mwAgc">0</span><span class="p" id="mwAgg">,</span><span class="w" id="mwAgk"> </span><span class="s2" id="mwAgo">"."</span><span class="p" id="mwAgs">);</span> <span class="w" id="mwAgw"> </span><span class="k" id="mwAg0">return</span><span class="w" id="mwAg4"> </span><span class="nx" id="mwAg8">digits</span><span class="p" id="mwAhA">.</span><span class="nx" id="mwAhE">join</span><span class="p" id="mwAhI">(</span><span class="s2" id="mwAhM">""</span><span class="p" id="mwAhQ">);</span> <span class="p" id="mwAhU">}</span>

From base π

• JavaScript:

  <span id="mwAiA"></span><span class="kd" id="mwAiE">function</span><span class="w" id="mwAiI"> </span><span class="nx" id="mwAiM">fromBasePI</span><span class="p" id="mwAiQ">(</span><span class="nx" id="mwAiU">num</span><span class="p" id="mwAiY">)</span><span class="w" id="mwAic"> </span><span class="p" id="mwAig">{</span> <span class="w" id="mwAik"> </span><span class="kd" id="mwAio">let</span><span class="w" id="mwAis"> </span><span class="nx" id="mwAiw">numberSplit</span><span class="w" id="mwAi0"> </span><span class="o" id="mwAi4">=</span><span class="w" id="mwAi8"> </span><span class="nx" id="mwAjA">num</span><span class="p" id="mwAjE">.</span><span class="nx" id="mwAjI">split</span><span class="p" id="mwAjM">(</span><span class="sr" id="mwAjQ">/\./g</span><span class="p" id="mwAjU">);</span> <span class="w" id="mwAjY"> </span><span class="kd" id="mwAjc">let</span><span class="w" id="mwAjg"> </span><span class="nx" id="mwAjk">numberLength</span><span class="w" id="mwAjo"> </span><span class="o" id="mwAjs">=</span><span class="w" id="mwAjw"> </span><span class="nx" id="mwAj0">numberSplit</span><span class="p" id="mwAj4">[</span><span class="mf" id="mwAj8">0</span><span class="p" id="mwAkA">].</span><span class="nx" id="mwAkE">length</span><span class="p" id="mwAkI">;</span> <span class="w" id="mwAkM"> </span><span class="kd" id="mwAkQ">let</span><span class="w" id="mwAkU"> </span><span class="nx" id="mwAkY">output</span><span class="w" id="mwAkc"> </span><span class="o" id="mwAkg">=</span><span class="w" id="mwAkk"> </span><span class="mf" id="mwAko">0</span><span class="p" id="mwAks">;</span> <span class="w" id="mwAkw"> </span><span class="kd" id="mwAk0">let</span><span class="w" id="mwAk4"> </span><span class="nx" id="mwAk8">digits</span><span class="w" id="mwAlA"> </span><span class="o" id="mwAlE">=</span><span class="w" id="mwAlI"> </span><span class="nx" id="mwAlM">numberSplit</span><span class="p" id="mwAlQ">.</span><span class="nx" id="mwAlU">join</span><span class="p" id="mwAlY">(</span><span class="s2" id="mwAlc">""</span><span class="p" id="mwAlg">);</span> <span class="w" id="mwAlk"> </span><span class="k" id="mwAlo">for</span><span class="w" id="mwAls"> </span><span class="p" id="mwAlw">(</span><span class="kd" id="mwAl0">let</span><span class="w" id="mwAl4"> </span><span class="nx" id="mwAl8">i</span><span class="w" id="mwAmA"> </span><span class="o" id="mwAmE">=</span><span class="w" id="mwAmI"> </span><span class="mf" id="mwAmM">0</span><span class="p" id="mwAmQ">;</span><span class="w" id="mwAmU"> </span><span class="nx" id="mwAmY">i</span><span class="w" id="mwAmc"> </span><span class="o" id="mwAmg"><</span><span class="w" id="mwAmk"> </span><span class="nx" id="mwAmo">digits</span><span class="p" id="mwAms">.</span><span class="nx" id="mwAmw">length</span><span class="p" id="mwAm0">;</span><span class="w" id="mwAm4"> </span><span class="nx" id="mwAm8">i</span><span class="o" id="mwAnA">++</span><span class="p" id="mwAnE">)</span><span class="w" id="mwAnI"> </span><span class="p" id="mwAnM">{</span> <span class="w" id="mwAnQ"> </span><span class="nx" id="mwAnU">output</span><span class="w" id="mwAnY"> </span><span class="o" id="mwAnc">+=</span><span class="w" id="mwAng"> </span><span class="nx" id="mwAnk">digits</span><span class="p" id="mwAno">[</span><span class="nx" id="mwAns">i</span><span class="p" id="mwAnw">]</span><span class="w" id="mwAn0"> </span><span class="o" id="mwAn4">*</span><span class="w" id="mwAn8"> </span><span class="nb" id="mwAoA">Math</span><span class="p" id="mwAoE">.</span><span class="nx" id="mwAoI">pow</span><span class="p" id="mwAoM">(</span><span class="nb" id="mwAoQ">Math</span><span class="p" id="mwAoU">.</span><span class="nx" id="mwAoY">PI</span><span class="p" id="mwAoc">,</span><span class="w" id="mwAog"> </span><span class="nx" id="mwAok">numberLength</span><span class="o" id="mwAoo">-</span><span class="nx" id="mwAos">i</span><span class="o" id="mwAow">-</span><span class="mf" id="mwAo0">1</span><span class="p" id="mwAo4">);</span> <span class="w" id="mwAo8"> </span><span class="p" id="mwApA">}</span> <span class="w" id="mwApE"> </span><span class="k" id="mwApI">return</span><span class="w" id="mwApM"> </span><span class="nx" id="mwApQ">output</span><span class="p" id="mwApU">;</span> <span class="p" id="mwApY">}</span>