Нецелая база счисления

Нецелое представление использует нецелые числа в качестве основы или основания позиционной системы счисления . Для нецелого счисления β > 1 значение

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

является

{\begin{aligned}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{aligned}}

Числа d _i являются неотрицательными целыми числами, меньшими β . Это также известно как β -расширение , понятие, введенное Реньи (1957) и впервые подробно изученное Парри (1960) . Каждое действительное число имеет хотя бы одно (возможно, бесконечное) β -разложение. Множество является всех β имеющих конечное представление, подмножеством кольца β Z [ -разложений , , β ⁻¹].

Существуют приложения β -разложений в теории кодирования. ^[1] и модели квазикристаллов . ^[2]

Строительство

β -разложения являются обобщением десятичных разложений . Хотя бесконечные десятичные разложения не уникальны (например, 1,000... = 0,999... ), все конечные десятичные разложения уникальны. Однако даже конечные β -разложения не обязательно единственны, например φ + 1 = φ ² для β = φ — золотое сечение . Канонический выбор β- разложения данного действительного числа может быть определен с помощью следующего жадного алгоритма , по существу предложенного Реньи (1957) и сформулированного здесь Фруньи (1992) .

Пусть $β > 1$ — основание, а x — неотрицательное действительное число. Обозначим через $⌊ x ⌋$ нижнюю функцию x { (то есть наибольшее целое число, меньшее или равное x ) и пусть $x} = x - ⌊ x ⌋$ будет дробной частью x . Существует целое число k такое, что $β к \leq х < β к +1$ . Набор

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

и

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

Для $k - 1 \geq j > -\infty$ положим

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

Другими словами, каноническое β -разложение x определяется выбором наибольшего d _k такого, что $β к d k \leq x$ , затем выбираем наибольший d _{k −1} такой, что $β к d k + β к -1 d k -1 \leq x$ и так далее. Таким образом, он выбирает самую большую лексикографически строку, представляющую x .

При целочисленной базе это определяет обычное разложение по системе счисления для числа x . Эта конструкция расширяет обычный алгоритм до возможных нецелых значений β .

Конверсия

Следуя описанным выше шагам, мы можем создать β -разложение для действительного числа. $n\geq 0$ (шаги идентичны для $n<0$ , хотя $n$ необходимо сначала умножить на -1, чтобы сделать его положительным, затем результат необходимо умножить на -1, чтобы он снова стал отрицательным).

Во-первых, мы должны определить наше $значение k$ (показатель степени ближайшей степени $β,$ большей, чем $n$ , а также количество цифр в $\lfloor n_{\beta }\rfloor$ , где $n_{\beta }$ записано $n$ в базе $β$ ). Значение $k$ для $n$ и $β$ можно записать как:

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

После того как $значение k$ найдено, $n_{\beta }$ можно записать как $d$ , где

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

для $k - 1 \geq j > -\infty$ . Первые $k$ значений $d$ появляются слева от десятичного знака.

Это также можно записать в следующем псевдокоде : ^[3]

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
}

Обратите внимание, что приведенный выше код действителен только для $1<\beta \leq 10$ и $n\geq 0$ , поскольку он не преобразует каждую цифру в ее правильные символы или правильные отрицательные числа. Например, если значение цифры равно 10 будет представлено как 10 вместо $A.$ , оно

Пример кода реализации

По основанию $π$

JavaScript : ^[3]

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("");
}

По основанию $π$

JavaScript: ^[3]

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

Примеры

База √ 2

Основание √ 2 ведет себя очень похоже на основание 2, поскольку все, что нужно сделать, чтобы преобразовать число из двоичного числа в основание √ 2, — это поместить нулевую цифру между каждой двоичной цифрой; например, 1911 ₁₀ = 11101110111 ₂ становится 101010001010100010101 _{√ 2} , а 5118 ₁₀ = 1001111111110 ₂ становится 1000001010101010101010100 _{√ 2} . Это означает, что любое целое число можно выразить по основанию √ 2 без десятичной точки. чтобы показать отношение стороны квадрата к Основание также можно использовать , его диагонали , поскольку квадрат с длиной стороны 1 _{√ 2} будет иметь диагональ 10 _{√ 2} , а квадрат с длиной стороны 10 _{√ 2} будет имеют диагональ 100 _{√ 2} . Другое использование базы — показать соотношение серебра , поскольку его представление в базе √ 2 равно просто 11 _{√ 2} . При этом площадь правильного восьмиугольника с длиной стороны 1 _{√ 2} равна 1100 _{√ 2} , площадь правильного восьмиугольника с длиной стороны 10 _{√ 2} равна 110 000 _{√ 2} , площадь правильного восьмиугольника с длиной стороны 100 _{√ 2} равна 11000000 _{√ 2} и т. д.

Золотая база

В золотой базе некоторые числа имеют более одного эквивалента десятичной системы счисления: они неоднозначны . Например: 11 _φ = 100 _φ .

База пс

есть числа В базе ψ , которые также неоднозначны. Например, 101 _ψ = 1000 _ψ .

Базовый e

С основанием e натуральный логарифм ведет себя как десятичный логарифм : ln(1e ₎ = 0, ln(10e ₎ = 1, ln(100e ₎ = 2 и ln(1000e ₎ = 3.

Основание e - наиболее экономичный выбор системы счисления β > 1, ^[4] где экономия системы счисления измеряется как произведение системы счисления и длины строки символов, необходимой для выражения заданного диапазона значений.

База р

Основание π чтобы легче показать связь между диаметром круга можно использовать , и его длиной , которая соответствует его периметру ; поскольку длина окружности = диаметр × π, то окружность диаметром 1 _π будет иметь длину окружности 10 _π , окружность диаметром 10 _π будет иметь длину окружности 100 _π и т. д. Кроме того, поскольку площадь = π × радиус ², круг радиусом 1 _π будет иметь площадь 10 _π , круг радиусом 10 _π будет иметь площадь 1000 _π и круг радиусом 100 _π будет иметь площадь 100000 _π . ^[5]

Характеристики

Ни в одной позиционной системе счисления каждое число не может быть выражено однозначно. Например, в десятичной системе число 1 имеет два представления: 1,000... и 0,999... . Набор чисел с двумя разными представлениями плотен в действительных числах, ^[6] но вопрос классификации действительных чисел с уникальными β -разложениями значительно более тонкий, чем вопрос о целочисленных основаниях. ^[7]

Другая проблема — классифицировать действительные числа, β -разложения которых являются периодическими. Пусть β > 1 и Q ( β ) — наименьшее расширение поля рациональных чисел , содержащее β . Тогда любое действительное число из [0,1), имеющее периодическое β -разложение, должно лежать в Q ( β ). С другой стороны, обратное не обязательно должно быть верным. Обратное справедливо, если β — число Писо , ^[8] хотя необходимые и достаточные условия неизвестны.

См. также

Ссылки

Сноски

^ Каутц 1965
^ Бурдик и др. 1998 год ; Терстон 1989 г.
^ Jump up to: Перейти обратно: ^а ^б ^с «Главная» , decimalsystem.js.org
^ Хейс 2001
^ «Странные числовые базы» , DataGenetics , получено 1 февраля 2018 г.
^ Петковшек 1990
^ Glendinning & Sidorov 2001
^ Шмидт 1980

Источники

Бюжо, Янн (2012), Распределение по модулю один и диофантово приближение , Cambridge Tracts in Mathematics, vol. 193, Кембридж: Издательство Кембриджского университета , ISBN 978-0-521-11169-0 , Збл 1260.11001
Бурдик, Ч.; Фруни, Ч.; Газо, Япония; Крейчар, Р. (1998), «Бета-целые числа как естественные системы счета для квазикристаллов», Journal of Physics A: Mathematical and General , 31 (30): 6449–6472, Бибкод : 1998JPhA...31.6449B , CiteSeerX 10.1. 30.1.5106 , doi : 10.1088/0305-4470/31/30/011 , ISSN 0305-4470 , MR 1644115 .
Фруни, Кристиана (1992), «Как записывать целые числа в нецелой системе счисления» , LATIN '92 , Конспекты лекций по информатике, том. 583/1992, Springer Berlin/Heidelberg, стр. 154–164, doi : 10.1007/BFb0023826 , ISBN 978-3-540-55284-0 , ISSN 0302-9743 .
Глендиннинг, Пол ; Сидоров, Никита (2001), «Уникальные представления действительных чисел в нецелых основаниях» , Mathematical Research Letters , 8 (4): 535–543, doi : 10.4310/mrl.2001.v8.n4.a12 , ISSN 1073- 2780 , МР 1851269 .
Хейс, Брайан (2001), «Третья база» , American Scientist , 89 (6): 490–494, doi : 10.1511/2001.40.3268 , заархивировано из оригинала 24 марта 2016 г.
Каутц, Уильям Х. (1965), «Коды Фибоначчи для управления синхронизацией», Институт инженеров по электротехнике и электронике. Транзакции по теории информации , IT-11 (2): 284–292, doi : 10.1109/TIT.1965.1053772 , ISSN 0018-9448 , MR 0191744 .
Парри, В. (1960), «О β-разложениях действительных чисел», Acta Mathematica Венгерской академии наук , 11 (3–4): 401–416, doi : 10.1007/bf02020954 , hdl : 10338.dmlcz /120535 , ISSN 0001-5954 , MR 0142719 , S2CID 116417864 .
Петковшек, Марко (1990), «Неоднозначные числа плотны», The American Mathematical Monthly , 97 (5): 408–411, doi : 10.2307/2324393 , ISSN 0002-9890 , JSTOR 2324393 , MR 1048915 .
Реньи, Альфред (1957), «Представления действительных чисел и их эргодические свойства», Acta Mathematica Венгерской академии наук , 8 (3–4): 477–493, doi : 10.1007/BF02020331 , hdl : 10338.dmlcz/ 102491 , ISSN 0001-5954 , MR 0097374 , S2CID 122635654 .
Шмидт, Клаус (1980), «О периодических разложениях чисел Писо и чисел Салема», Бюллетень Лондонского математического общества , 12 (4): 269–278, doi : 10.1112/blms/12.4.269 , hdl : 10338. dmlcz/141479 , ISSN 0024-6093 , MR 0576976 .
Терстон, В.П. (1989), «Группы, мозаики и конечные автоматы», лекции на коллоквиуме AMS

Дальнейшее чтение

Сидоров, Никита (2003), «Арифметическая динамика», в Безуглый, Сергей; Коляда, Сергей (ред.), Вопросы динамики и эргодической теории. Обзорные статьи и мини-курсы, представленные на международной конференции и американо-украинском семинаре по динамическим системам и эргодической теории, Кацивели, Украина, 21–30 августа 2000 г. , Лондон. Математика. Соц. Лект. Примечание Сер., вып. 310, Кембридж: Издательство Кембриджского университета , стр. 145–189, ISBN. 978-0-521-53365-2 , Збл 1051.37007

Внешние ссылки

Вайсштейн, Эрик В. «База» . Математический мир .

[1] Каутц 1965

[2] Бурдик и др. 1998 год ; Терстон 1989 г.

[DecimalSystem-3] Jump up to: Перейти обратно: ^а ^б ^с «Главная» , decimalsystem.js.org

[4] Хейс 2001

[5] «Странные числовые базы» , DataGenetics , получено 1 февраля 2018 г.

[6] Петковшек 1990

[7] Glendinning & Sidorov 2001

[8] Шмидт 1980

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Строительство

Конверсия

Пример кода реализации

По основанию π

По основанию π

Примеры

База √ 2

Золотая база

База пс

Базовый e

База р

Характеристики

См. также

Ссылки

Сноски

Источники

Дальнейшее чтение

Внешние ссылки

По основанию $π$

По основанию $π$