View source for Non-integer base of numeration

{{short description|Number systems with a non-integer radix (base), such as base 2.5}}
{{Numeral systems}}
A '''non-integer representation''' uses non-[[Integer|integer]] numbers as the [[Radix|radix]], or base, of a [[Positional notation|positional numeral system]]. For a non-integer radix ''β'' > 1, the value of
:<math>x = d_n \dots d_2d_1d_0.d_{-1}d_{-2}\dots d_{-m}</math>
is
:<math>\begin{align}
x &= \beta^nd_n + \cdots + \beta^2d_2 + \beta d_1 + d_0 \\
  &\qquad + \beta^{-1}d_{-1} + \beta^{-2}d_{-2} + \cdots + \beta^{-m}d_{-m}.
\end{align}</math>
The numbers ''d''<sub>''i''</sub> are non-negative integers less than ''β''.  This is also known as a '''''β''-expansion''', a notion introduced by {{harvtxt|Rényi|1957}} and first studied in detail by {{harvtxt|Parry|1960}}.  Every [[Real number|real number]] has at least one (possibly infinite) ''β''-expansion. The [[Set (mathematics)|set]] of all ''β''-expansions that have a finite representation is a [[Subset|subset]] of the [[Ring (mathematics)|ring]] '''Z'''[''β'',&thinsp;''β''<sup>−1</sup>].

There are applications of ''β''-expansions in [[Coding theory|coding theory]] {{harv|Kautz|1965}} and models of [[Physics:Quasicrystal|quasicrystal]]s ({{harvnb|Burdik|Frougny|Gazeau|Krejcar|1998}}; {{harvnb|Thurston|1989}}).

==Construction==
''β''-expansions are a generalization of decimal expansions. While infinite decimal expansions are not unique (for example, 1.000... = [[0.999...|0.999...]]), all finite decimal expansions are unique. However, even finite ''β''-expansions are not necessarily unique, for example ''φ'' + 1 = ''φ''<sup>2</sup> for ''β'' = ''φ'', the [[Golden ratio|golden ratio]]. A canonical choice for the ''β''-expansion of a given real number can be determined by the following [[Greedy algorithm|greedy algorithm]], essentially due to {{harvtxt|Rényi|1957}} and formulated as given here by {{harvtxt|Frougny|1992}}.

Let {{math|''β'' > 1}} be the base and ''x'' a non-negative real number.  Denote by {{math|⌊''x''⌋}} the floor function of ''x'' (that is, the greatest integer less than or equal to ''x'') and let {{math|1={{mset|''x''}} = ''x'' − ⌊''x''⌋}} be the fractional part of ''x''. There exists an integer ''k'' such that {{math|''β''<sup>''k''</sup> ≤ ''x'' < ''β''<sup>''k''+1</sup>}}. Set
:<math>d_k = \lfloor x/\beta^k\rfloor</math>
and
:<math>r_k = \{x/\beta^k\}.\,</math>
For {{math|''k'' − 1 ≥ &thinsp;''j'' > −∞}}, put
:<math>d_j = \lfloor\beta r_{j+1}\rfloor, \quad r_j = \{\beta r_{j+1}\}.</math>

In other words, the canonical ''β''-expansion of ''x'' is defined by choosing the largest ''d''<sub>''k''</sub> such that {{math|''β''<sup>''k''</sup>''d''<sub>''k''</sub> ≤ ''x''}}, then choosing the largest ''d''<sub>''k''−1</sub> such that {{math|''β''<sup>''k''</sup>''d''<sub>''k''</sub> + β<sup>''k''−1</sup>''d''<sub>''k''−1</sub> ≤ ''x''}}, and so on. Thus it chooses the [[Lexicographical order|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 <math>n \geq 0</math> (the steps are identical for an <math>n < 0</math>, although {{mvar|n}} must first be multiplied by {{val|-1}} to make it positive, then the result must be multiplied by {{val|-1}} to make it negative again).

First, we must define our {{mvar|k}} value (the exponent of the nearest power of {{mvar|&beta;}} greater than {{mvar|n}}, as well as the amount of digits in <math>\lfloor n_\beta \rfloor</math>, where <math>n_\beta</math> is {{mvar|n}} written in base {{mvar|&beta;}}). The {{mvar|k}} value for {{mvar|n}} and {{mvar|&beta;}} can be written as:

:<math>k = \lfloor \log_\beta(n) \rfloor + 1</math>

After a {{mvar|k}} value is found, <math>n_\beta</math> can be written as {{mvar|d}}, where

:<math>d_j = \lfloor (n/\beta^j) \bmod \beta \rfloor, \quad n = n-d_j*\beta^j </math>

for {{math|''k'' − 1 ≥ &thinsp;''j'' > −∞}}. The first {{mvar|k}} values of {{mvar|d}} appear to the left of the decimal place.

This can also be written in the following [[Pseudocode|pseudocode]]: 
<source lang="javascript">
function toBase(n, b) {
	k = floor(log(b, n)) + 1
	precision = 8
	result = ""

	for (i = k - 1, i > -precision-1, i--) {
		if (result.length == k) result += "."
		
		digit = floor((n / b^i) mod b)
		n -= digit * b^i
		result += digit
	}

	return result
}
</source>
<ref name="DecimalSystem">{{cite web |url=https://decimalsystem.js.org/ |title=Home |website=decimalsystem.js.org}}</ref>

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

=== Example implementation code ===
==== To base {{pi}} ====
* [[JavaScript]]:<ref name="DecimalSystem" /><source lang="javascript">
function toBasePI(num, precision = 8) {    
    let k = Math.floor(Math.log(num)/Math.log(Math.PI)) + 1;
    if (k < 0) k = 0;

    let digits = [];

    for (let i = k-1; i > (-1*precision)-1; i--) {
        let digit = Math.floor((num / Math.pow(Math.PI, i)) % Math.PI);
        num -= digit * Math.pow(Math.PI, i);
        digits.push(digit);

        if (num < 0.1**(precision+1) && i <= 0)
            break;
    }

    if (digits.length > k)
        digits.splice(k, 0, ".");

    return digits.join("");
}
</source>

==== From base {{pi}} ====
* JavaScript:<ref name="DecimalSystem" /><source lang="javascript">
function fromBasePI(num) {
    let numberSplit = num.split(/\./g);
    let numberLength = numberSplit[0].length;

    let output = 0;
    let digits = numberSplit.join("");

    for (let i = 0; i < digits.length; i++) {
        output += digits[i] * Math.pow(Math.PI, numberLength-i-1);
    }

    return output;
}
</source>

==Examples==
===Base {{radic|2}}===
Base [[Square root of 2|{{radic|2}}]] behaves in a very similar way to base 2 as all one has to do to convert a number from binary into base {{radic|2}} is put a zero digit in between every binary digit; for example, 1911<sub>10</sub> = 11101110111<sub>2</sub> becomes 101010001010100010101<sub>{{radic|2}}</sub> and 5118<sub>10</sub> = 1001111111110<sub>2</sub> becomes 1000001010101010101010100<sub>{{radic|2}}</sub>. This means that every integer can be expressed in base {{radic|2}} without the need of a decimal point. The base can also be used to show the relationship between the [[Edge (geometry)|side]] of a square to its [[Diagonal|diagonal]] as a square with a side length of 1<sub>{{radic|2}}</sub> will have a diagonal of 10<sub>{{radic|2}}</sub> and a square with a side length of 10<sub>{{radic|2}}</sub> will have a diagonal of 100<sub>{{radic|2}}</sub>. Another use of the base is to show the [[Silver ratio|silver ratio]] as its representation in base {{radic|2}} is simply 11<sub>{{radic|2}}</sub>. In addition, the area of a regular octagon with side length 1<sub>{{radic|2}}</sub> is 1100<sub>{{radic|2}}</sub>, the area of a regular octagon with side length 10<sub>{{radic|2}}</sub> is 110000<sub>{{radic|2}}</sub>, the area of a regular octagon with side length 100<sub>{{radic|2}}</sub> is 11000000<sub>{{radic|2}}</sub>, etc…

===Golden base ===
{{main|Golden ratio base}}
In the golden base, some numbers have more than one decimal base equivalent: they are '''ambiguous'''. For example:
11<sub>φ</sub> = 100<sub>φ</sub>.

===Base ψ===
There are also some numbers in base [[Supergolden ratio|ψ]] are also ambiguous. For example, 101<sub>ψ</sub> = 1000<sub>ψ</sub>.

===Base ''e''===
With base [[E (mathematical constant)|''e'']] the [[Natural logarithm|natural logarithm]] behaves like the [[Common logarithm|common logarithm]] as ln(1<sub>''e''</sub>) = 0, ln(10<sub>''e''</sub>) = 1, ln(100<sub>''e''</sub>) = 2 and ln(1000<sub>''e''</sub>) = 3.

The base ''e'' is the most economical choice of radix ''β'' > 1 {{harv|Hayes|2001}}, where the [[Radix economy|radix economy]] is measured as the product of the radix and the length of the string of symbols needed to express a given range of values.

===Base π===
Base [[Pi|π]] can be used to more easily show the relationship between the [[Diameter|diameter]] of a [[Circle|circle]] to its [[Circumference|circumference]], which  corresponds to its [[Perimeter|perimeter]]; since circumference = diameter × π, a circle with a diameter 1<sub>π</sub> will have a circumference of 10<sub>π</sub>, a circle with a diameter 10<sub>π</sub> will have a circumference of 100<sub>π</sub>, etc. Furthermore, since the [[Area|area]] = π × [[Radius|radius]]<sup>2</sup>, a circle with a radius of 1<sub>π</sub> will have an area of 10<sub>π</sub>, a circle with a radius of 10<sub>π</sub> will have an area of 1000<sub>π</sub> and a circle with a radius of 100<sub>π</sub> will have an area of 100000<sub>π</sub>.<ref>{{Cite web|url=http://datagenetics.com/blog/december22015/index.html|title=Weird Number Bases|website=DataGenetics|access-date=2018-02-01}}</ref>

== Properties ==
In no positional number system can every number be expressed uniquely.  For example, in base ten, the number 1 has two representations: 1.000... and [[0.999...|0.999...]].  The set of numbers with two different representations is [[Dense set|dense]] in the reals {{harv|Petkovšek|1990}}, but the question of classifying real numbers with unique ''β''-expansions is considerably more subtle than that of integer bases {{harv|Glendinning|Sidorov|2001}}.

Another problem is to classify the real numbers whose ''β''-expansions are periodic.  Let ''β'' > 1, and '''Q'''(''β'') be the smallest field extension of the [[Rational number|rationals]] containing ''β''.  Then any real number in [0,1) having a periodic ''β''-expansion must lie in '''Q'''(''β'').  On the other hand, the [[Philosophy:Converse (logic)|converse]] need not be true.  The converse does hold if ''β'' is a Pisot number {{harv|Schmidt|1980}}, although necessary and sufficient conditions are not known.

== See also ==
* [[Beta encoder]]
* [[Non-standard positional numeral systems]]
* Decimal expansion
* [[Power series]]
* [[Ostrowski numeration]]

== References ==
{{Reflist}}
*{{citation | last=Bugeaud | first=Yann | title=Distribution modulo one and Diophantine approximation | series=Cambridge Tracts in Mathematics | volume=193 | location=Cambridge | publisher={{wipe|Cambridge University Press}} | year=2012 | isbn=978-0-521-11169-0 | zbl= 1260.11001}}
*{{Citation | last1=Burdik | first1=Č. | last2=Frougny | first2=Ch. | last3=Gazeau | first3=J. P. | last4=Krejcar | first4=R. | title=Beta-integers as natural counting systems for quasicrystals | doi=10.1088/0305-4470/31/30/011 | bibcode=1998JPhA...31.6449B | mr=1644115 | year=1998 | journal=Journal of Physics A: Mathematical and General | issn=0305-4470 | volume=31 | issue=30 | pages=6449–6472| citeseerx=10.1.1.30.5106 }}.
*{{citation|series=Lecture Notes in Computer Science
|publisher=Springer Berlin / Heidelberg
|issn=0302-9743
|volume=583/1992
|title=LATIN '92
|doi=10.1007/BFb0023826
|year=1992
|isbn=978-3-540-55284-0
|pages=154–164
|chapter=How to write integers in non-integer base
|first=Christiane
|last=Frougny
|chapter-url=https://books.google.com/books?id=I3fC6batwokC&pg=PA154
}}.
*{{Citation | last1=Glendinning | first1=Paul |  last2=Sidorov | first2=Nikita | title=Unique representations of real numbers in non-integer bases | url=http://intlpress.com/site/pub/pages/journals/items/mrl/content/vols/0008/0004/00019835/index.html | mr=1851269 | year=2001 | journal=Mathematical Research Letters | issn=1073-2780 | volume=8 | issue=4 | pages=535–543 | doi=10.4310/mrl.2001.v8.n4.a12| doi-access=free }}.
*{{citation | first=Brian|last=Hayes|title=Third base|journal=American Scientist|url=http://www.americanscientist.org/issues/pub/third-base/2|year=2001|volume=89|issue=6|pages=490–494|doi=10.1511/2001.40.3268 | archive-url = https://web.archive.org/web/20160324100419/http://www.americanscientist.org/issues/pub/2001/11/third-base/2 | archive-date = 2016-03-24 | url-status = dead }}.
*{{Citation | last1=Kautz | first1=William H. | title=Fibonacci codes for synchronization control | mr=0191744 | year=1965 | journal=Institute of Electrical and Electronics Engineers. Transactions on Information Theory | issn=0018-9448 | volume=IT-11 | issue=2 | pages=284–292| doi=10.1109/TIT.1965.1053772 }}.
*{{Citation | last1=Parry | first1=W. |  title=On the β-expansions of real numbers | mr=0142719 | year=1960 | journal=Acta Mathematica Academiae Scientiarum Hungaricae | issn=0001-5954 | volume=11 | issue=3–4 | pages=401–416 | doi=10.1007/bf02020954| hdl=10338.dmlcz/120535 | s2cid=116417864 | hdl-access=free }}.
*{{Citation | last1=Petkovšek | first1=Marko |  title=Ambiguous numbers are dense | doi=10.2307/2324393 | mr=1048915 | year=1990 | journal=[[American Mathematical Monthly|The American Mathematical Monthly]] | issn=0002-9890 | volume=97 | issue=5 | pages=408–411| jstor=2324393 }}.
*{{Citation | last1=Rényi | first1=Alfréd |  title=Representations for real numbers and their ergodic properties | mr=0097374 | doi=10.1007/BF02020331 | hdl=10338.dmlcz/102491 | year=1957 | journal=Acta Mathematica Academiae Scientiarum Hungaricae | issn=0001-5954 | volume=8 | issue=3–4 | pages=477–493| s2cid=122635654 | hdl-access=free }}.
*{{Citation | last1=Schmidt | first1=Klaus | title=On periodic expansions of Pisot numbers and Salem numbers | doi=10.1112/blms/12.4.269 | hdl=10338.dmlcz/141479 | mr=576976 | year=1980 | journal=The Bulletin of the London Mathematical Society | issn=0024-6093 | volume=12 | issue=4 | pages=269–278| hdl-access=free }}.
*{{Citation | last1=Thurston | first1=W.P. | title=Groups, tilings and finite state automata |journal=AMS Colloquium Lectures | year=1989}}

==Further reading==
* {{citation | last=Sidorov | first=Nikita | chapter=Arithmetic dynamics | zbl=1051.37007 | editor1-last=Bezuglyi | editor1-first=Sergey | editor2-last=Kolyada | editor2-first=Sergiy | title=Topics in dynamics and ergodic theory. Survey papers and mini-courses presented at the international conference and US-Ukrainian workshop on dynamical systems and ergodic theory, Katsiveli, Ukraine, August 21–30, 2000 | location=Cambridge | publisher={{wipe|Cambridge University Press}} | isbn=978-0-521-53365-2 | series=Lond. Math. Soc. Lect. Note Ser. | volume=310 | pages=145–189 | year=2003 }}

==External links==
* {{mathworld|title=Base|urlname=Base}}

{{DEFAULTSORT:Non-Integer Representation}}
[[Category:Number theory]]
[[Category:Ring theory]]
[[Category:Coding theory]]
[[Category:Non-standard positional numeral systems]]

{{Sourceattribution|Non-integer base of numeration}}