Nicht ganzzahlige Numerierungsbasis - Non-integer base of numeration

Eine nicht-ganzzahlige Darstellung verwendet nicht - ganzzahlige Zahlen als radix oder Basis eines Positionszahlensystem . Für eine nicht ganzzahlige Radix β > 1 ist der Wert von

${\displaystyle x=d_{n}\dots d_{2}d_{1}d_{0}.d_{-1}d_{-2}\dots d_{-m}}$

ist

${\displaystyle {\begin{ausgerichtet}x&=\beta ^{n}d_{n}+\cdots +\beta ^{2}d_{2}+\beta d_{1}+d_{0}\\& \qquad +\beta^{-1}d_{-1}+\beta^{-2}d_{-2}+\cdots +\beta^{-m}d_{-m}.\end{ausgerichtet} }}$

Die Zahlen d _i sind nicht negative ganze Zahlen kleiner als β . Dies ist auch als β- Expansion bekannt , ein Begriff, der von Rényi (1957) eingeführt und zuerst von Parry (1960) ausführlich untersucht wurde . Jede reelle Zahl hat mindestens eine (möglicherweise unendliche) β- Erweiterung. Die Menge aller β- Erweiterungen, die eine endliche Darstellung haben, ist eine Teilmenge des Rings Z [ β ,  β ⁻¹ ].

Es gibt Anwendungen von β- Erweiterungen in der Codierungstheorie ( Kautz 1965 ) und Modellen von Quasikristallen ( Burdik et al. 1998 ; Thurston 1989 ).

Konstruktion

β- Erweiterungen sind eine Verallgemeinerung von Dezimalentwicklungen . Während unendliche Dezimalentwicklungen nicht eindeutig sind (z. B. 1.000... = 0,999... ), sind alle endlichen Dezimalerweiterungen eindeutig. Aber auch endliche β- Erweiterungen sind nicht unbedingt eindeutig, zB φ + 1 = φ ² für β = φ , der Goldene Schnitt . Eine kanonische Wahl für die β- Expansion einer gegebenen reellen Zahl kann durch den folgenden Greedy-Algorithmus bestimmt werden , der im Wesentlichen von Rényi (1957) stammt und wie hier von Frougny (1992) formuliert ist .

Sei β > 1 die Basis und x eine nicht-negative reelle Zahl. Es bezeichne ⌊ x ⌋ der Boden Funktion von x (die die größte ganze Zahl kleiner ist, als oder gleich x ) und lassen Sie { x } = x - ⌊ x ⌋ sein der Bruchteil von x . Es existiert eine ganze Zahl k , so dass β ^k ≤ x < β ^{k +1} . Satz

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

und

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

Für k − 1 ≥   j > −∞ , put

${\displaystyle d_{j}=\lfloor \beta r_{j+1}\rfloor ,\quad r_{j}=\{\beta r_{j+1}\}.}$

Mit anderen Worten, die kanonische β- Expansion von x wird definiert, indem man das größte d _k wählt, so dass β ^k d _k ≤ x , dann das größte d _{k −1} so gewählt wird, dass β ^k d _k + β ^{k −1} d _{k − 1} ≤ x und so weiter. Somit wählt es die lexikographisch größte Zeichenfolge, die x darstellt .

Bei einer ganzzahligen Basis definiert dies die übliche Radixentwicklung für die Zahl x . Diese Konstruktion erweitert den üblichen Algorithmus auf möglicherweise nicht ganzzahlige Werte von β .

Wandlung

Mit den obigen Schritten können wir eine β- Erweiterung für eine reelle Zahl erstellen (die Schritte sind für an identisch , obwohl n zuerst mit . multipliziert werden muss${\displaystyle n\geq 0}$${\displaystyle n<0}$−1 um es positiv zu machen, dann muss das Ergebnis mit multipliziert werden−1 , um es wieder negativ zu machen).

Zuerst müssen wir unseren definieren k - Wert (den Exponenten der nächsten Potenz von β größer ist als n sowie die Anzahl der Stellen , wo sie n in Basis geschrieben β ). Der k- Wert für n und β kann geschrieben werden als: ${\displaystyle \lfloor n_{\beta}\rfloor}$${\displaystyle n_{\beta}}$

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

Nachdem ein k- Wert gefunden wurde, kann als d geschrieben werden , wobei ${\displaystyle n_{\beta}}$

${\displaystyle d_{j}=\lfloor (n/\beta^{j}){\bmod {\beta}}\rfloor ,\quad n=n-d_{j}*\beta ^{j}}$

für k − 1 ≥   j > −∞ . Die ersten k Werte von d erscheinen links von der Dezimalstelle.

Dies kann auch in folgendem Pseudocode geschrieben werden :

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
}

Beachten Sie, dass der obige Code nur für und gültig ist , da er nicht jede Ziffer in die richtigen Symbole oder korrekten negativen Zahlen umwandelt. Wenn der Wert einer Ziffer beispielsweise ist${\displaystyle 1<\beta\leq 10}$${\displaystyle n\geq 0}$10 , wird es dargestellt als10 anstelle von A .

Beispielimplementierungscode

Zur Basis π

• 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)
              break;
      }
  
      if (digits.length > k)
          digits.splice(k, 0, ".");
  
      return digits.join("");
  }
  

Von der Basis π

• 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;
  }
  

Beispiele

Basis √ 2

Die Basis √ 2 verhält sich sehr ähnlich wie die Basis 2, da alles, was man tun muss, um eine Zahl von binär in die Basis √ 2 umzuwandeln , eine Nullstelle zwischen jede binäre Ziffer gesetzt wird; Beispiel: 1911 ₁₀ = 11101110111 ₂ wird zu 10010001010100010101 _{√ 2} und 5118 ₁₀ = 1001111111110 ₂ wird zu 1000001010101010101010100 _{√ 2} . Dies bedeutet, dass jede ganze Zahl in der Basis √ 2 ausgedrückt werden kann, ohne dass ein Dezimalpunkt erforderlich ist. Die Basis kann auch die Beziehung zwischen dem zeigen , verwendet wird Seite eines quadratischen seine Diagonalen als Quadrat mit einer Seitenlänge von 1 _{√ 2} eine Diagonale von 10 hat _{√ 2} mit einer Seitenlänge von 10 und einem quadratischen _{√ 2} Willen haben eine Diagonale von 100 _{√ 2} . Eine andere Verwendung der Basis besteht darin, das Silberverhältnis anzuzeigen, da seine Darstellung in Basis √ 2 einfach 11 _{√ 2 ist} . Außerdem ist die Fläche eines regelmäßigen Achtecks mit der Seitenlänge 1 _{√ 2} 1100 _{√ 2} , die Fläche eines regelmäßigen Achtecks mit der Seitenlänge 10 _{√ 2} beträgt 110000 _{√ 2} , die Fläche eines regelmäßigen Achtecks mit der Seitenlänge 100 _{√ 2} ist 11000000 _{√ 2} , usw…

Goldene Basis

In der goldenen Basis haben einige Zahlen mehr als ein Äquivalent zur Dezimalbasis: Sie sind mehrdeutig . Beispiel: 11 _φ = 100 _φ .

Basis ψ

Es gibt auch einige Zahlen in der Basis ψ, die ebenfalls mehrdeutig sind. Zum Beispiel 101 _ψ = 1000 _ψ .

Basis e

Mit der Basis e verhält sich der natürliche Logarithmus wie der gewöhnliche Logarithmus zu ln(1 _e ) = 0, ln(10 _e ) = 1, ln(100 _e ) = 2 und ln(1000 _e ) = 3.

Die Basis e ist die wirtschaftlichste Wahl des Radix β > 1 ( Hayes 2001 ), wobei die Radix-Ökonomie als das Produkt des Radix und der Länge der Zeichenkette gemessen wird, die benötigt wird, um einen gegebenen Wertebereich auszudrücken.

Basis π

Basis π kann verwendet werden, um die Beziehung zwischen dem Durchmesser eines Kreises und seinem Umfang , der seinem Umfang entspricht, einfacher darzustellen ; da Umfang = Durchmesser × π, ein Kreis mit einem Durchmesser von 1 _π wird mit einem Umfang von 10 haben _π , ein Kreis mit einem Durchmesser von 10 _π wird einen Umfang von 100 haben _π usw. Da ferner die Fläche = π × Radius ² , ein Kreis mit einem Radius von 1 _{& pgr} eine Fläche von 10 hat _π , ein Kreis mit einem Radius von 10 _π wird eine Fläche von 1000 hat _π und einen Kreis mit einem Radius von 100 _π wird eine Fläche von 100000 hat _π .

Eigenschaften

In keinem Positionszahlensystem kann jede Zahl eindeutig ausgedrückt werden. Zum Beispiel hat die Zahl 1 zur Basis zehn zwei Darstellungen: 1.000... und 0,999... . Die Menge der Zahlen mit zwei unterschiedlichen Darstellungen ist in den reellen Zahlen dicht ( Petkovšek 1990 ), aber die Frage der Klassifikation reeller Zahlen mit eindeutigen β- Erweiterungen ist wesentlich subtiler als die der ganzzahligen Basen ( Glendinning & Sidorov 2001 ).

Ein weiteres Problem besteht darin, die reellen Zahlen zu klassifizieren, deren β- Entwicklungen periodisch sind. Sei β > 1 und Q ( β ) die kleinste Körpererweiterung der rationalen Zahlen, die β enthalten . Dann muss jede reelle Zahl in [0,1) mit periodischer β -Entwicklung in Q ( β ) liegen. Andererseits muss das Umgekehrte nicht wahr sein. Das Umgekehrte gilt, wenn β eine Pisot-Zahl ist ( Schmidt 1980 ), obwohl notwendige und hinreichende Bedingungen nicht bekannt sind.

Siehe auch

• Beta-Encoder
• Nicht standardmäßige Positionsziffernsysteme
• Dezimalerweiterung
• Leistungsreihe
• Ostrowski-Nummerierung

Verweise

• Bugeaud, Yann (2012), Distribution Modulo One and Diophantine Approximation , Cambridge Tracts in Mathematics, 193 , Cambridge: Cambridge University Press , ISBN 978-0-521-11169-0, Zbl  1260.11001
• Burdik, .; Frogny, Ch.; Gazeau, JP; Krejcar, R. (1998), "Beta-Ganzzahlen als natürliche Zählsysteme für Quasikristalle", Journal of Physics A: Mathematical and General , 31 (30): 6449–6472, Bibcode : 1998JPhA...31.6449B , CiteSeerX  10.1. 1.30.5106 , doi : 10.1088/0305-4470/31/30/011 , ISSN  0305-4470 , MR  1644115.
• Frougny, Christiane (1992), "How to write integers in non-integer base" , LATIN '92 , Lecture Notes in Computer Science, 583/1992, Springer Berlin / Heidelberg, S. 154–164, doi : 10.1007/BFb0023826 , ISBN 978-3-540-55284-0, ISSN  0302-9743.
• Glendinning, Paul ; Sidorov, Nikita (2001), "Eindeutige Darstellungen von reellen Zahlen in nicht ganzzahligen Basen" , Mathematical Research Letters , 8 (4): 535–543, doi : 10.4310/mrl.2001.v8.n4.a12 , ISSN  1073- 2780 , HERR  1851269.
• Hayes, Brian (2001), "Third base" , American Scientist , 89 (6): 490–494, doi : 10.1511/2001.40.3268 , archiviert vom Original am 24.03.2016.
• Kautz, William H. (1965), "Fibonacci-Codes zur Synchronisationskontrolle", Institut für Elektro- und Elektronikingenieure. Transaktionen zur Informationstheorie , IT-11 (2): 284–292, doi : 10.1109/TIT.1965.1053772 , ISSN  0018-9448 , MR  0191744.
• Parry, W. (1960), "Über die β-Erweiterungen reeller Zahlen", Acta Mathematica Academiae Scientiarum Hungaricae , 11 (3–4): 401–416, doi : 10.1007/bf02020954 , hdl : 10338.dmlcz/120535 , ISSN  0001-5954 , MR  0142719 , S2CID  116417864.
• Petkovšek, Marko (1990), "Ambiguous numbers are Dense", The American Mathematical Monthly , 97 (5): 408-411, doi : 10.2307/2324393 , ISSN  0002-9890 , JSTOR  2324393 , MR  1048915.
• Rényi, Alfréd (1957), "Repräsentationen für reelle Zahlen und ihre ergodischen Eigenschaften", Acta Mathematica Academiae Scientiarum Hungaricae , 8 (3–4): 477–493, doi : 10.1007/BF02020331 , hdl : 10338.dmlcz/102491 , ISSN  0001-5954 , MR  0097374 , S2CID  122635654.
• Schmidt, Klaus (1980), "On periodic expansions of Pisot numbers and Salem numbers", The Bulletin of the London Mathematical Society , 12 (4): 269–278, doi : 10.1112/blms/12.4.269 , hdl : 10338. dmlcz/141479 , ISSN  0024-6093 , MR  0576976.
• Thurston, WP (1989), "Groups, tilings and finite state automata", AMS Colloquium Lectures

Weiterlesen

• Sidorov, Nikita (2003), "Arithmetische Dynamik", in Bezuglyi, Sergey; Kolyada, Sergiy (Hrsg.), Topics in Dynamics and Ergodic Theory. Auf der internationalen Konferenz und dem US-ukrainischen Workshop über dynamische Systeme und ergodische Theorie präsentierte Übersichtspapiere und Minikurse, Katsiveli, Ukraine, 21.–30. August 2000 , London. Mathematik. Soz. Lect. Note Ser., 310 , Cambridge: Cambridge University Press , S. 145–189, ISBN 978-0-521-53365-2, Zbl  1051.37007

Externe Links

• Weisstein, Eric W. "Basis" . MathWorld .