Отрицательное основание

редактировать

Нестандартная позиционная система счисления

A отрицательное основание (или отрицательное основание ) может быть используется для построения нестандартной позиционной системы счисления. Подобно другим системам с позиционными ценностями, каждая позиция имеет мощность, кратную соответствующей мощности основы системы; но это основание отрицательное, то есть основание b равно −r для некоторого натурального числа r (r ≥ 2).

В системах с отрицательным основанием могут использоваться все те же числа, что и в стандартных системах с разрядными значениями, но как положительные, так и отрицательные числа представлены без использования знака минус (или, в компьютерном представлении, знаковый бит ); этому преимуществу противостоит повышенная сложность арифметических операций. Необходимость хранить информацию, обычно содержащуюся в отрицательном знаке, часто приводит к тому, что отрицательное базовое число оказывается на одну цифру длиннее, чем его эквивалент с положительным основанием.

Общие имена для позиционных систем счисления с отрицательным основанием образуются с помощью префикса отрицательного- к имени соответствующей системы с положительным основанием; например, негадецимальный (основание -10) соответствует десятичному (основанию 10), негабаритному (основание -2) к двоичному ( основание 2), отрицательное (основание -3) до тройное (основание 3) и отрицательное (основание -4) до четвертичное (основание 4).

Содержание

1 Пример
2 История
3 Обозначение и использование
4 Расчет
- 4.1 Пример кода реализации
  - 4.1.1 В негабинарный
    - 4.1.1.1 C #
    - 4.1.1.2 C ++
  - 4.1.2 К отрицательному
    - 4.1.2.1 C #
    - 4.1.2.2 Visual Basic.NET
    - 4.1.2.3 Python
    - 4.1.2.4 Common Lisp
  - 4.1.3 На любую отрицательную базу
    - 4.1.3.1 Java
    - 4.1.3.2 AutoLisp
    - 4.1.3.3 PHP
    - 4.1.3.4 Visual Basic.NET
- 4.2 Вычисление ярлыка
  - 4.2.1 В негабинарный
  - 4.2.2 В негабинарный
5 Арифметические операции
- 5.1 Сложение
  - 5.1.1 Другой метод
  - 5.1.2 Негабинарный полный сумматор
  - 5.1.3 Увеличение отрицательных чисел
- 5.2 Вычитание
- 5.3 Умножение и деление
- 5.4 Сравнение отрицательных чисел
6 Дробные числа
- 6.1 Неуникальные представления
7 Мнимая база
8 См. Также
9 Ссылки
10 Дополнительная литература
11 Внешние ссылки

Пример

Рассмотрим, что подразумевается под представлением 12243 в негадецимальной системе с основанием b -10:

, кратное
(-10) = 10,000	(-10) = -1,000	(−10) = 100	(−10) = −10	(−10) = 1
1	2	2	4	3

Поскольку 10000 + (−2000) + 200 + (−40) + 3 = 8,163, представление 12,243 −10 в негадецимальной системе счисления эквивалентно 8,163 10 в десятичной системе счисления, тогда как -8,163 10 в десятичной системе счисления будет записано 9,977 -10 в негадецимальной системе счисления.

История

Отрицательные числовые основы были впервые рассмотрены Витторио Грюнвальдом в монографии 1885 года, опубликованной в Giornale di Matematiche di Battaglini. Грюнвальд дал алгоритмы для выполнения сложения, вычитания, умножения, деления, извлечения корня, проверки делимости и преобразования системы счисления. Отрицательные основания были позже упомянуты мимоходом А. Я. Кемпнер в 1936 г. и более подробно изученный Здиславом Павляком и А. Вакуличем в 1957 г.

Negabinary был реализован в раннем польском компьютере ( и UMC ), построенный в 1957–59 гг. на основе идей З. Павляка и А. Лазаркевича из Варшавы. С тех пор реализации были редкостью.

Обозначение и использование

Обозначая основание как -r, каждое целое число a может быть записано однозначно как

a = ∑ i = 0 ndi (- r) i {\ displaystyle a = \ sum _ {i = 0} ^ {n} d_ {i} (- r) ^ {i}}

a = \ sum _ {{i = 0}} ^ {{n}} d _ {{i}} (- r) ^ {{i}}

, где каждая цифра d k является целым числом от 0 до r - 1, а первая цифра d n равна>0 (если n = 0). Расширение base -r a затем задается строкой d ndn-1... d 1d0.

Таким образом, системы с отрицательным основанием можно сравнить с представлениями цифр со знаком, например, сбалансированный троичный, где основание системы счисления положительное, но цифры берутся из частично отрицательного диапазона. (В таблице ниже цифра значения -1 записана как одиночный символ T.)

Некоторые числа имеют такое же представление в базе -r, что и в базе r. Например, числа от 100 до 109 имеют одно и то же представление в десятичной и негадецимальной системе. Аналогичным образом

17 = 2 4 + 2 0 = (- 2) 4 + (- 2) 0 {\ displaystyle 17 = 2 ^ {4} + 2 ^ {0} = (- 2) ^ {4} + (-2) ^ {0}}

17 = 2 ^ {4} + 2 ^ {0} = (- 2) ^ { 4} + (- 2) ^ {0}

и представлен 10001 в двоичном и 10001 в негабинарном.

Некоторые числа с их расширениями в число положительных и соответствующих отрицательных оснований:

Десятичное	Негадецимальное	Двоичное	Отрицательное	Тернар	Негатернар	Сбалансированный тройной	Отрицательный сбалансированный тройной	Четвертичный	Негатернарный
−15	25	−1111	110001	−120	1220	T110	11T0	−33	1301
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮
−5	15	−101	1111	−12	21	T11	TT1	−11	23
−4	16	−100	1100	−11	22	TT	1T	−10	10
−3	17	−11	1101	- 10	10	T0	10	−3	11
−2	18	−10	10	−2	11	T1	11	−2	12
−1	19	−1	11	−1	12	T	T	−1	13
0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1
2	2	10	110	2	2	1T	TT	2	2
3	3	11	111	10	120	10	T0	3	3
4	4	100	100	11	121	11	T1	10	130
5	5	101	101	12	122	1TT	11T	11	131
6	6	110	11010	20	110	1T0	110	12	132
7	7	111	11011	21	111	1T1	111	13	133
8	8	1000	11000	22	112	10T	10T	20	120
9	9	1001	11001	100	100	100	100	21	121
10	190	1010	11110	101	101	101	101	22	122
11	191	1011	11111	102	102	11T	1TT	23	123
12	192	1100	11100	110	220	110	1T0	30	110
13	193	1101	11101	111	221	111	1T1	31	111
14	194	1110	10010	112	222	1TTT	TT1T	32	112
15	195	1111	10011	120	210	1TT0	TT10	33	113
16	196	10000	10000	121	211	1TT1	TT11	100	100
17	197	10001	10001	122	212	1T0T	TT0T	101	101
18	198	10010	10110	200	200	1T10	TTT0	102	102

Обратите внимание, что, за исключением отрицательно-симметричной тройной, базовая - r разложения отрицательных целых чисел имеют четное число цифр, в то время как разложения неотрицательных целых чисел по основанию −r имеют нечетное число цифр.

Вычисление

Расширение числа по основанию −r можно найти повторным делением на −r, записав неотрицательные остатки в ${0, 1,…, r - 1} {\ displaystyle \ {0,1, \ ldots, r-1 \}}$ ${\ displaystyle \ {0,1, \ ldots, r-1 \}}$ и объединение этих остатков, начиная с последнего. Обратите внимание: если a / b равно c с остатком d, то bc + d = a и, следовательно, d = a - bc. Чтобы получить правильное преобразование, значение c должно быть выбрано таким, чтобы d было неотрицательным и минимальным. Это проиллюстрировано в четвертой строке следующего примера, где –5 ÷ –3 должно быть выбрано, чтобы равняться 2 остатку 1 вместо 1 остатка 2.

Например, чтобы преобразовать 146 из десятичного числа в отрицательное:

146 ÷ (- 3) = - 48 остатков ⁡ 2-48 ÷ (- 3) = 16 остатков ⁡ 0 16 ÷ (- 3) = - 5 остатков ⁡ 1 - 5 ÷ (- 3) = 2 остатка ⁡ 1 2 ÷ (- 3) = 0 остаток ⁡ 2 {\ displaystyle {\ begin {array} {rr} 146 \ div (-3) = - 48 ~ \ operatorname {elseder} ~ 2 \\ - 48 \ div (-3) = 16 ~ \ operatorname {остаток} ~ 0 \\ 16 \ div (-3) = - 5 ~ \ operatorname {остаток} ~ 1 \\ - 5 \ div (-3) = 2 ~ \ operatorname {остаток} ~ 1 \\ 2 \ div (-3) = 0 ~ \ operatorname {elseder} ~ 2 \ end {array}}}

{\ displaystyle {\ begin {array} {rr} 146 \ div (-3) = - 48 ~ \ operatorname {restder} ~ 2 \\ - 48 \ div (-3) = 16 ~ \ operatorname {остаток} ~ 0 \\ 16 \ div (-3) = - 5 ~ \ operatorname {остаток} ~ 1 \\ - 5 \ div (-3) = 2 ~ \ operatorname {остаток} ~ 1 \\ 2 \ div (-3) = 0 ~ \ operatorname {остаток} ~ 2 \ end {array}}

Читая остатки назад, мы получаем отрицательное представление 146 10 : 21102 –3.

Доказательство: (((2 · (–3) + 1 ) · (–3) + 1 ) · (–3) + 0 ) · (–3) + 2 = 146 10.

Обратите внимание, что в большинстве языков программирования результат (в целочисленной арифметике) деления отрицательного номер по имени Отрицательное число округляется до 0, обычно оставляя отрицательный остаток. В таком случае имеем a = (−r) c + d = (−r) c + d - r + r = (−r) (c + 1) + (d + r). Потому что | d | < r, (d + r) is the positive remainder. Therefore, to get the correct result in such case, computer implementations of the above algorithm should add 1 and r to the quotient and remainder respectively.

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

В негабинарный

C #

статическая строка ToNegabinary (int value) {string result = string.Empty; while (значение! = 0) {int остаток = значение% -2; значение = значение / -2; if (остаток < 0) { remainder += 2; value += 1; } result = remainder.ToString() + result; } return result; }

C ++

auto to_negabinary (int value) {std :: bitset result; std :: size_t bit_position = 0; while (value! = 0) {const auto div_result = std :: div (value, -2); if (div_result.rem < 0) value = div_result.quot + 1; else value = div_result.quot; result.set(bit_position, div_result.rem != 0); ++bit_position; } return result; }

To negaternary

C #

static string negaternary (int value) {string result = string.Empty; while (value! = 0) { int остаток = значение% -3; значение = значение / -3; if (остаток < 0) { remainder += 3; value += 1; } result = remainder.ToString() + result; } return result; }

Visual Basic.NET

Частная общая функция ToNegaternary (значение как целое число) Как строка Тусклый результат Как String = String.Empty While value <>0 Размыть остаток как целое число = значение Mod -3 значение / = -3 Если остаток < 0 Then remainder += 3 value += 1 End If result = remainder.ToString() result End While Return result End Function

Python

def negaternary (i: int) ->str: "" "От десятичного до отрицательного." "" If i = = 0: digits = ["0"] else: digits = while i! = 0: i, остаток = divmod (i, -3), если остаток < 0: i, remainder = i + 1, remainder + 3 digits.append(str(remainder)) return "".join(digits[::-1])

>>>negaternary (1000) '2212001'

Обычный Lisp

(defun negaternary (i) (if (zerop i) "0" (let ((digits "") (rem 0)) (loop while (not (zerop i)) do (progn (multi-value- setq (i rem) (усечь i -3)) (когда (minusp re m) (incf i) (incf rem 3)) (setf digits (concatenate 'string (write-to-string rem) digits)))) digits)))

К любой отрицательной базе

Java

public String negativeBase (int integer, int base) {String result = ""; int число = целое число; в то время как (число! = 0) {int я = число% базы; число / = база; if (i < 0) { i += Math.abs(base); number++; } result = i + result; } return result; }

AutoLisp

из [-10-2] интервала:

(defun negabase (num baz / dig rst) ;; NUM - любое число. BAZ - любое число в интервале [ -10, -2]. ;; ;; NUM и BAZ будут усечены до целого числа, если они являются числами с плавающей запятой (например, 14,25 ;; будет усечено до 14, -123456789,87 до -123456789 и т. Д.). (If (и (numberp num) (numberp baz) (<= (fix baz) -2) (>(fix baz) -11)) (progn (setq baz (float (fix baz)) num (float (fix num)) dig (if (= num 0) "0 "" ")) (while (/ = num 0) (setq rst (- num (* baz (setq num (fix (/ num baz)))))) (if (minusp rst) (setq num (1+ num) rst (- rst baz))) (setq dig (strcat (itoa (fix rst)) dig))) dig) (progn (prompt (cond ((and (not (numberp num)) (not (numberp baz))) "\ nНеверный номер и негабаза.") ((not (numberp num)) "\ nНеверный номер.") ((not (not (numberp baz)) "\ nНеверный негабаза.") (t "\ nНегабаза должна быть внутри [- 10 -2] interval. "))) (Princ))))

PHP

Преобразование целого числа в некоторую отрицательную базу:

функция toNegativeBase ($ no, $ base) {$ digits = массив (); $ base = intval ($ base); в то время как ($ no! = 0) {$ temp_no = $ no; $ no = intval ($ temp_no / $ base); $ остаток = ($ temp_no% $ base); if ($ остаток < 0) { $remainder += abs($base); $no++; } array_unshift($digits, $remainder); } return $digits; }

Visual Basic.NET

Функция toNegativeBase (число как целое число, основание как целое число) Как System.Collections.Generic.List (Of Integer) Тусклые цифры как новые System.Collections.Generic.List (Of Целое число), а число <>0 Затемнить остаток как целое число = число Модифицировать базовое число = CInt (число / основание), если остаток < 0 then remainder += system.math.abs(base) Number+=1 end if digits.Insert(0, remainder) end while return digits end function

Вычисление быстрого доступа

Следующие алгоритмы предполагают, что

вход доступен в битовые строки и закодированы в (основание +2; цифры в ${0, 1} {\ displaystyle \ {0,1 \}}$ $\ {0,1 \}$ ) (как и в большинстве современных цифровых компьютеров),
существуют операции добавления (+) и xor (^), которые работают с такими строками битов (как в большинстве современных цифровых компьютеров),
набор $D {\ displaystyle D}$ $D$ выходных цифр является стандартным, т.е. $D = {0, | b | - 1} {\ displaystyle D = \ {0, | b | -1 \}}$ ${\ displaystyle D = \ {0, | b | -1 \}}$ с базой $b ∈ {- 2, - 4} {\ displaystyle b \ in \ {- 2, -4 \}}$ ${\ displaystyl eb \ in \ {- 2, -4 \}}$ ,
вывод кодируется в том же формате битовой строки, но значение места другое r один.

В негабинарный

Преобразование в негабинарный (основание -2; цифры в ${0, 1} {\ displaystyle \ {0,1 \}}$ $\ {0,1 \}$ ) позволяет использовать замечательный ярлык (реализация C):

unsigned int toNegaBinary (unsigned int value) // ввод в стандартном двоичном формате {unsigned int Schroeppel2 = 0xAAAAAAAA; // = 2/3 * ((2 * 2) ^ 16-1) =... 1010 return (value + Schroeppel2) ^ Schroeppel2; // исключающее ИЛИ // результирующее целое число без знака интерпретируется как строка элементов ε {0,1} (биты)}

Благодаря Д. Либрику (Судзик). Часть побитового XOR изначально связана с Schroeppel (1972).

портом JavaScript для того же вычисления ярлыка:

function toNegaBinary (number) {var Schroeppel2 = 0xAAAAAAAA; // Преобразование в отрицательную двоичную строку return ((число + Schroeppel2) ^ Schroeppel2).toString (2); }

В четвертичный

Преобразование в четвертичный (основание -4; цифры в ${0, 1, 2, 3} {\ displaystyle \ {0,1,2,3 \}}$ ${\ displaystyle \ {0, 1,2,3 \}}$ ) позволяет аналогичный ярлык (реализация C):

unsigned int toNegaQuaternary (unsigned int value) // ввод в стандартном двоичном формате {unsigned int Schroeppel4 = 0xCCCCCCCC; // = 4/5 * ((2 * 4) ^ 8-1) =... 11001100 =... 3030 return (value + Schroeppel4) ^ Schroeppel4; // исключающее ИЛИ // результирующее целое число без знака, которое будет интерпретировано как строка элементов ε {0,1,2,3} (пары битов)}

Порт JavaScript для того же вычисления ярлыка:

function toNegaQuaternary (number) {var Schroeppel4 = 0xCCCCCCCC; // Преобразование в NegaQuaternary String return ((number + Schroeppel4) ^ Schroeppel4).toString (4); }

Арифметические операции

Ниже описаны арифметические операции для негабинарных чисел; вычисления в более крупных базах аналогичны.

Сложение

Добавление отрицательных чисел происходит поразрядно, начиная с младших значащих битов ; биты из каждого слагаемого суммируются с переносом (сбалансированной троичной системы ) из предыдущего бита (0 в младшем разряде). Эта сумма затем разлагается на выходной бит и переносится для следующей итерации, как показано в таблице:

Sum		Output			Comment
Sum		Bit	Carry		Comment
−2	010 −2	0	1	01−2	−2 встречается только при вычитании.
−1	011 −2	1	1	01−2
0	000 −2	0	0	00−2
1	001 −2	1	0	00−2
2	110 −2	0	−1	11−2
3	111 −2	1	−1	11−2	3 встречается только во время сложения.

Вторая строка этой таблицы, например, выражает тот факт, что −1= 1+ 1× −2; в пятой строке указано 2= 0+ −1× −2; и т. д.

В качестве примера, чтобы добавить 1010101 −2 (1 + 4 + 16 + 64 = 85) и 1110100 −2 (4 + 16-32 + 64 = 52),

Перенести: 1 −1 0 −1 1 −1 0 0 0 Первое слагаемое: 1 0 1 0 1 0 1 Второе слагаемое: 1 1 1 0 1 0 0 + --- ----------------------- Число: 1 −1 2 0 3 −1 2 0 1 Бит (результат): 1 1 0 0 1 1 0 0 1 Перенести: 0 1 −1 0 −1 1 −1 0 0

, поэтому результат будет 110011001 −2 (1-8 + 16-128 + 256 = 137).

Другой метод

При добавлении двух отрицательных чисел каждый раз, когда создается перенос, дополнительный перенос должен передаваться на следующий бит. Рассмотрим тот же пример, что и выше

Дополнительный перенос: 1 1 0 1 0 0 0 Перенос: 1 0 1 1 0 1 0 0 0 Первое добавление: 1 0 1 0 1 0 1 Второе добавление: 1 1 1 0 1 0 0 + -------------------------- Ответ: 1 1 0 0 1 1 0 0 1

Негабинарный полный сумматор

A схема полного сумматора может быть сконструирована для сложения чисел в отрицательной системе. Следующая логика используется для вычисления суммы и переносов:

si = ai ⊕ bi ⊕ ci + ⊕ ci - {\ displaystyle s_ {i} = a_ {i} \ oplus b_ {i} \ oplus c_ {i} ^ {+} \ oplus c_ {i} ^ {-}}

{\ displaystyle s_ {i} = a_ {i} \ oplus b_ {i} \ oplus c_ {i} ^ {+} \ oplus c_ {i} ^ {-}}

ci + 1 + = ai ¯ bi ¯ ci + ¯ ci - {\ displaystyle c_ {i + 1} ^ {+} = {\ overline { a_ {i}}} {\ overline {b_ {i}}} {\ overline {c_ {i} ^ {+}}} c_ {i} ^ {-}}

{\ displaystyle c_ {i + 1} ^ { +} = {\ overline {a_ {i}}} {\ overline {b_ {i}}} {\ overline {c_ {i} ^ {+}}} c_ {i} ^ {-}}

ci + 1 - = aibici - ¯ + (ai ⊕ bi) ci + ci - ¯ {\ displaystyle c_ {i + 1} ^ {-} = a_ {i} b_ {i} {\ overline {c_ {i} ^ {-}}} + (a_ {i} \ oplus b_ {i}) c_ {i} ^ {+} {\ overline {c_ {i} ^ {-}}}}

{\ displaystyle c_ {i + 1} ^ {-} = a_ {i} b_ {i} {\ overline {c_ {i} ^ {-}}} + (a_ {i} \ oplus b_ {i }) c_ {i} ^ {+} {\ overline {c_ {i} ^ {-}}}}

Увеличение отрицательного числа

Увеличение отрицательного числа может выполняется по следующей формуле:

2 x ⊕ ((2 x ⊕ x) + 1) {\ displaystyle 2x \ oplus ((2x \ oplus x) +1)}

{\ displaystyle 2x \ oplus ((2x \ oplus x) +1)}

Вычитание

Чтобы вычесть, умножьте каждый бит второго числа на -1 и сложите числа, используя ту же таблицу, что и выше.

В качестве примера для вычисления 1101001 −2 (1-8-32 + 64 = 25) минус 1110100 −2 (4 + 16-32 + 64 = 52),

Перенести: 0 1 −1 1 0 0 0 Первое число: 1 1 0 1 0 0 1 Второе число: −1 −1 −1 0 −1 0 0 + ----- --------------- Число: 0 1 −2 2 −1 0 1 Бит (результат): 0 1 0 0 1 0 1 Перенести: 0 0 1 −1 1 0 0

, поэтому результат будет 100101 −2 (1 + 4 −32 = −27).

Унарное отрицание, −x, может быть вычислено как двоичное вычитание из нуля, 0 - x.

Умножение и деление

Сдвиг влево умножается на -2, сдвиг вправо делится на -2.

Для умножения умножайте как обычные десятичные или двоичные числа, но используя негабинарные правила для добавления переноса при сложении чисел.

Первое число: 1 1 1 0 1 1 0 Второе число: 1 0 1 1 0 1 1 × ----------------------- -------------- 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 + ------------------------------------- Перенести: 0 −1 0 −1 −1 −1 - 1 −1 0 −1 0 0 Число: 1 0 2 1 2 2 2 3 2 0 2 1 0 Бит (результат): 1 0 0 1 0 0 0 1 0 0 0 1 0 Перенести: 0 −1 0 −1 - 1 -1 -1 -1 0 -1 0 0

Для каждого столбца добавьте перенос к числу и разделите сумму на -2, чтобы получить новый перенос и полученный бит в качестве остатка.

Сравнение отрицательных чисел

Можно сравнивать отрицательные числа, немного отрегулировав обычный беззнаковый двоичный компаратор . При сравнении чисел $A {\ displaystyle A}$ $А$ и $B {\ displaystyle B}$ $B$ инвертируйте каждый нечетный бит обоих чисел. После этого сравните $A {\ displaystyle A}$ $А$ и $B {\ displaystyle B}$ $B$ с помощью стандартного компаратора без знака.

Дробные числа

Базовое представление -r, конечно, может быть перенесено за пределы точки счисления, что позволяет представлять нецелые числа.

Как и в системах с положительным основанием, завершающие представления соответствуют дробям, в которых знаменатель является степенью основания; повторяющиеся представления соответствуют другим рациональным числам и по той же причине.

Неуникальные представления

В отличие от систем с положительным основанием, в которых целые числа и завершающие дроби имеют неуникальные представления (например, в десятичном формате 0,999... = 1 ) в системах с отрицательной базой целые числа имеют только одно представление. Однако существуют рациональные числа с неуникальными представлениями. Для цифр {0, 1,..., t } с $t: = r - 1 = - b - 1 {\ displaystyle \ mathbf {t}: = r \! - \ ! \! 1 = -b \! - \! \! 1}$ ${\ displaystyle \ mathbf {t}: = г \! - \! \! 1 = -b \! - \! \! 1}$ самая большая цифра и

T: = 0. 01 ¯ b = ∑ i = 1 ∞ b - 2 i = 1 b 2-1 = 1 р 2-1 {\ displaystyle T: = 0. {\ Overline {01}} _ {b} = \ sum _ {i = 1} ^ {\ infty} b ^ {- 2i} = { \ frac {1} {b ^ {2} -1}} = {\ frac {1} {r ^ {2} -1}}}

{\ displaystyle T: = 0. {\ overline {01}} _ {b} = \ sum _ {i = 1} ^ {\ infty} b ^ { -2i} = {\ frac {1} {b ^ {2} -1}} = {\ frac {1} {r ^ {2} -1}}}

у нас

0. 0 T ¯ б знак равно T T знак равно р - 1 р 2-1 = 1 р + 1 {\ displaystyle 0. {\ Overline {0 \ mathbf {t}}} _ {b} = \ mathbf {t} T = { \ frac {r \! - \! \! 1} {r ^ {2} -1}} = {\ frac {1} {r + 1}}}

{\ displaystyle 0. {\ Overline {0 \ mathbf {t}}} _ {b} = \ mathbf {t} T = {\ frac { г \! - \! \! 1} {г ^ {2} -1}} = {\ гидроразрыва {1} {г + 1}}}

а также

1. t 0 ¯ b = 1 + t b T = (r 2 - 1) + (r - 1) b r 2 - 1 = 1 r + 1. {\ displaystyle 1. {\ overline {\ mathbf {t} 0}} _ {b} = 1 + \ mathbf {t} bT = {\ frac {(r ^ {2} -1) + (r \! - \! \! 1) b} {r ^ {2} -1}} = {\ frac {1} {r + 1}}.}

{\ displaystyle 1. {\ overline {\ mathbf {t} 0}} _ {b} = 1 + \ mathbf {t} bT = {\ frac {(r ^ {2} -1) + (r \! - \! \! 1) b} {r ^ {2} -1}} = {\ frac {1} {r + 1}}.}

Итак, каждое число $1 r + 1 + z {\ displaystyle {\ frac {1} {r + 1}} + z}$ ${\ displaystyle {\ frac {1} {r + 1}} + z}$ с конечной дробью $z ∈ Z r Z {\ displaystyle z \ in \ mathbb {Z } r ^ {\ mathbb {Z}}}$ ${\ displaystyle z \ in \ mathbb {Z} r ^ {\ mathbb {Z}}}$ added имеет два различных представления.

Например, в негативном, т.е. $b = - 3 {\ displaystyle b = -3}$ ${\ displaystyle b = -3}$ и $t = 2 {\ displaystyle \ mathbf {t} = 2}$ ${\ displaystyle \ mathbf {t} = 2 }$ , есть

1. 02 ¯ (- 3) = 5 4 = 2. 20 ¯ (- 3) {\ displaystyle 1. {\ Overline {02}} _ {(- 3)} = {\ frac {5} {4}} = 2. {\ overline {20}} _ {(- 3)}}

{\ displaystyle 1. {\ Overline {02}} _ {(- 3)} = {\ frac {5} {4}} = 2. {\ Overline {20}} _ {(- 3)}}

Такие неуникальные представления можно найти, рассматривая наибольшее и наименьшее возможные представления с целыми частями 0 и 1 соответственно, а затем отмечая, что они равны. (В самом деле, это работает с любой системой с целочисленным основанием.) Таким образом, не однозначно выражаемыми являются рациональные числа формы

z (r + 1) + 1 bi (r + 1) {\ displaystyle {\ frac {z ( r + 1) +1} {b ^ {i} (r + 1)}}}

{\ displaystyle {\ frac {z (r + 1) +1} {b ^ {i} (r + 1)}}}

с $z, i ∈ Z. {\ displaystyle z, i \ in \ mathbb {Z}.}$ ${\ displaystyle z, i \ in \ mathbb {Z}.}$

Мнимая основа

Так же, как использование отрицательной основы позволяет представлять отрицательные числа без явного отрицательного знака, используя мнимую base позволяет представление целых чисел Гаусса. Дональд Кнут предложил четвертичное мнимое основание (основание 2i) в 1955 году.

См. Также

Ссылки

Дополнительная литература

Уоррен-младший, Генри С. (2013) [2002]. Hacker's Delight (2 ed.). Эддисон Уэсли - Pearson Education, Inc. ISBN 978-0-321-84268-8. 0-321-84268-5.

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