Отрицательная база

Отрицательное основание (или отрицательное основание системы счисления ) может использоваться для построения нестандартной позиционной системы счисления . Как и в других системах разрядной стоимости, каждая позиция имеет кратную соответствующую мощность базы системы; но эта база отрицательна, то есть база $b$ равна $-r$ для некоторого натурального числа $r$ ( $r \geq 2$ ).

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

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

Пример

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

кратные
$(-10) 4 = 10,000$	$(-10) 3 = -1,000$	$(-10) 2 = 100$	$(-10) 1 = -10$	$(-10) 0 = 1$
1	2	2	4	3

Представление 12 243 ₋₁₀ (которое предназначено для недесятеричного представления) эквивалентно 8 163 ₁₀ в десятичном представлении, поскольку 10 000 + (−2 000) + 200 + (−40) + 3 = 8 163 .

Примечание

С другой стороны, -8,163 ₁₀ в десятичном формате будет записано как 9,977 _-10 в недесятичном формате.

История

Отрицательные числовые основы были впервые рассмотрены Витторио Грюнвальдом в монографии 1885 года, опубликованной в «Giornale di Matematiche» Баттальини . ^[3] Грюнвальд предложил алгоритмы сложения, вычитания, умножения, деления, извлечения корня, проверки делимости и преобразования системы счисления. Отрицательные основания были позже упомянуты А. Дж. Кемпнером в 1936 году. ^[4] и более подробно изучен Здиславом Павляком и А. Вакуличем в 1957 году. ^[5]

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

zfp, алгоритм сжатия чисел с плавающей запятой от Ливерморской национальной лаборатории Лоуренса , использует негабинарный код для хранения чисел. Согласно документации zfp: ^[7]

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

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

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

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

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

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

Некоторые числа имеют то же представление по основанию $-r,$ что и по основанию $r$ . Например, числа от 100 до 109 имеют одинаковое представление в десятичной и недесятеричной форме. Сходным образом,

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

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

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

Десятичный	недесятеричный	Двоичный	Негабинарный	тройной	отрицательный	Сбалансированная тройная система	Сбалансированный отрицательный	Четвертичный период	Негачетвертичный
−15	25	−1111	110001	−120	1220	Т110	11Т0	−33	1301
⋮
−5	15	−101	1111	−12	21	Т11	ТТ1	−11	23
−4	16	−100	1100	−11	22	ТТ	1Т	−10	10
−3	17	−11	1101	−10	10	Т0	10	−3	11
−2	18	−10	10	−2	11	Т1	11	−2	12
−1	19	−1	11	−1	12	Т	Т	−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	1Т	ТТ	2	2
3	3	11	111	10	120	10	Т0	3	3
4	4	100	100	11	121	11	Т1	10	130
5	5	101	101	12	122	1ТТ	11Т	11	131
6	6	110	11010	20	110	1Т0	110	12	132
7	7	111	11011	21	111	1Т1	111	13	133
8	8	1000	11000	22	112	10Т	10Т	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	11Т	1ТТ	23	123
12	192	1100	11100	110	220	110	1Т0	30	110
13	193	1101	11101	111	221	111	1Т1	31	111
14	194	1110	10010	112	222	1ТТТ	ТТ1Т	32	112
15	195	1111	10011	120	210	1TT0	ТТ10	33	113
16	196	10000	10000	121	211	1ТТ1	ТТ11	100	100
17	197	10001	10001	122	212	1Т0Т	ТТ0Т	101	101
18	198	10010	10110	200	200	1T00	ТТ00	102	102

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

Расчет

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

-5\div (-3)=2~\mathrm {remainder} ~1

должен быть выбран, а не $=3~\mathrm {remainder} ~4$ ни $=1~\mathrm {remainder} ~-\!2.$

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

{\begin{array}{rr}146\div (-3)=&-48~\mathrm {remainder} ~2\\-48\div (-3)=&16~\mathrm {remainder} ~0\\16\div (-3)=&-5~\mathrm {remainder} ~1\\-5\div (-3)=&2~\mathrm {remainder} ~1\\2\div (-3)=&0~\mathrm {remainder} ~2\end{array}}

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

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

= 146 ₁₀.

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

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

Обратите внимание, что в большинстве языков программирования результат (в целочисленной арифметике) деления отрицательного числа на отрицательное число округляется в сторону 0, обычно оставляя отрицательный остаток. В таком случае мы имеем $a = (- r) c + d = (- r) c + d - r + r = (- r)(c + 1) + (d + r)$ . Потому что $| д | < r$ , $(d + r)$ — положительный остаток. Следовательно, чтобы получить правильный результат в таком случае, компьютерные реализации приведенного выше алгоритма должны добавить 1 и $r$ к частному и остатку соответственно.

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

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

С#

static string ToNegabinary(int val)
{
	string result = string.Empty;

	while (val != 0)
	{
		int remainder = val % -2;
		val = val / -2;

		if (remainder < 0)
		{
			remainder += 2;
			val += 1;
		}

		result = remainder.ToString() + result;
	}

	return result;
}

С++

auto to_negabinary(int value)
{
    std::bitset<sizeof(int) * CHAR_BIT > 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;
}

Отрицательный

С#

static string Negaternary(int val)
{
	string result = string.Empty;

	while (val != 0)
	{
		int remainder = val % -3;
		val = val / -3;

		if (remainder < 0)
		{
			remainder += 3;
			val += 1;
		}

		result = remainder.ToString() + result;
	}

	return result;
}

Питон

def negaternary(i: int) -> str:
    """Decimal to negaternary."""
    if i == 0:
        digits = ["0"]
    else:
        digits = []
        while i != 0:
            i, remainder = divmod(i, -3)
            if remainder < 0:
                i, remainder = i + 1, remainder + 3
            digits.append(str(remainder))
    return "".join(digits[::-1])

>>> negaternary(1000)
'2212001'

Общий Лисп

(defun negaternary (i)
  (if (zerop i)
      "0"
      (let ((digits "")
            (rem 0))
        (loop while (not (zerop i)) do
          (progn
            (multiple-value-setq (i rem) (truncate i -3))
            (when (minusp rem)
              (incf i)
              (incf rem 3))
            (setf digits (concatenate 'string (write-to-string rem) digits))))
        digits)))

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

Ява

import java.util.ArrayList;
import java.util.Collections;
public ArrayList<Integer> negativeBase(int input, int base) {
    ArrayList<Integer> result_rev = new ArrayList<>();
    int number = input;
    while (number != 0) {
        int i = number % base;
        number /= base;
        if (i < 0) {
            i += Math.abs(base);
            number++;
        }
        result_rev.add(i);
    }
    return Collections.reverse(results_rev.clone());
}

Вышеприведенное дает результат в виде ArrayList целых чисел, поэтому коду не нужно обрабатывать представление базы меньше -10. Чтобы отобразить результат в виде строки, можно выбрать сопоставление базы с символами. Например:

import java.util.stream.Collectors;
final String alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@_";
public String toBaseString(ArrayList<Integer> lst) {
    // Would throw exception if base is beyond the 64 possible characters
    return lst.stream().map(n -> alphabet[n]).collect(Collectors.joining(""));
}

АвтоЛисп

(defun negabase (num baz / dig rst)
  ;; NUM is any number.
  ;; BAZ is any number in the interval [-10, -2]. (This is forced by how we do string notation.)
  ;;
  ;; NUM and BAZ will be truncated to an integer if they're floats (e.g. 14.25
  ;; will be truncated to 14, -123456789.87 to -123456789, etc.).
  (if (and (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)))
            "\nWrong number and negabase.")
           ((not (numberp num))
            "\nWrong number.")
           ((not (numberp baz))
            "\nWrong negabase.")
           (t
            "\nNegabase must be inside [-10 -2] interval.")))
        (princ))))

Ускоренный расчет

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

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

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

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

uint32_t toNegaBinary(uint32_t value) // input in standard binary
{
	uint32_t Schroeppel2 = 0xAAAAAAAA; // = 2/3*((2*2)^16-1) = ...1010
	return (value + Schroeppel2) ^ Schroeppel2; // eXclusive OR
	// resulting unsigned int to be interpreted as string of elements ε {0,1} (bits)
}

Порт JavaScript для того же быстрого расчета:

function toNegaBinary(value) {
    const Schroeppel2 = 0xAAAAAAAA;
    // Convert as in C, then convert to a NegaBinary String
    return ( ( value + Schroeppel2 ) ^ Schroeppel2 ).toString(2);
}

Алгоритм впервые описан Шреппелем в HAKMEM (1972) под номером 128. В Wolfram MathWorld документирована версия на языке Wolfram Language, написанная Д. Либриком (Ссудзиком). ^[8]

Негачетвертичный

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

uint32_t toNegaQuaternary(uint32_t value) // input in standard binary
{
	uint32_t Schroeppel4 = 0xCCCCCCCC; // = 4/5*((2*4)^8-1) = ...11001100 = ...3030
	return (value + Schroeppel4) ^ Schroeppel4; // eXclusive OR
	// resulting unsigned int to be interpreted as string of elements ε {0,1,2,3} (pairs of bits)
}

Порт JavaScript для того же быстрого расчета:

function toNegaQuaternary(value) {
    const Schroeppel4 = 0xCCCCCCCC;
    // Convert as in C, then convert to NegaQuaternary String
    return ( ( value + Schroeppel4 ) ^ Schroeppel4 ).toString(4);
}

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

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

Добавление

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

Сумма		Выход			Комментарий
Сумма		Кусочек	Нести		Комментарий
−2	010 ₋₂	0	1	01 ₋₂	−2 возникает только при вычитании.
−1	011 ₋₂	1	1	01 ₋₂
0	000 ₋₂	0	0	00 ₋₂
1	001 ₋₂	1	0	00 ₋₂
2	110 ₋₂	0	−1	11 ₋₂
3	111 ₋₂	1	−1	11 ₋₂	3 происходит только во время сложения.

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

Например, чтобы сложить 1010101 ₋₂ (1 + 4 + 16 + 64 = 85) и 1110100 ₋₂ (4 + 16 − 32 + 64 = 52),

Carry:          1 −1  0 −1  1 −1  0  0  0
First addend:         1  0  1  0  1  0  1
Second addend:        1  1  1  0  1  0  0 +
               --------------------------
Number:         1 −1  2  0  3 −1  2  0  1
Bit (result):   1  1  0  0  1  1  0  0  1
Carry:          0  1 −1  0 −1  1 −1  0  0

таким образом, результат равен 110011001 _-2 (1 - 8 + 16 - 128 + 256 = 137).

Другой метод

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

Extra carry:    1  1  1  0  1  0  0  0     
Carry:             0  1  1  0  1  0  0  0
First addend:         1  0  1  0  1  0  1
Second addend:        1  1  1  0  1  0  0 +
               --------------------------
Answer:         1  1  0  0  1  1  0  0  1

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

Схема полного сумматора может быть спроектирована для сложения чисел в негабинарном формате. Для вычисления суммы и переносов используется следующая логика: ^[9]

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

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

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

Увеличение небинарных чисел

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

2x\oplus ((2x\oplus x)+1)

(Операции в этой формуле следует интерпретировать как операции над обычными двоичными числами. Например, $2x$ представляет собой двоичный сдвиг влево на один бит.)

Вычитание

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

Например, чтобы вычислить 1101001 ₋₂ (1 − 8 − 32 + 64 = 25) минус 1110100 ₋₂ (4 + 16 − 32 + 64 = 52),

Carry:          0  1 −1  1  0  0  0
First number:   1  1  0  1  0  0  1
Second number: −1 −1 −1  0 −1  0  0 +
               --------------------
Number:         0  1 −2  2 −1  0  1
Bit (result):   0  1  0  0  1  0  1
Carry:          0  0  1 −1  1  0  0

таким образом, результат равен 100101 ₋₂ (1 + 4 −32 = −27).

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

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

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

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

First number:                   1  1  1  0  1  1  0
Second number:                  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                   +
              -------------------------------------
Carry:        0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0
Number:       1  0  2  1  2  2  2  3  2  0  2  1  0
Bit (result): 1  0  0  1  0  0  0  1  0  0  0  1  0
Carry:           0 −1  0 −1 −1 −1 −1 −1  0 −1  0  0

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

Сравнение небинарных чисел

Негабинарные числа можно сравнивать, слегка изменив обычный беззнаковый двоичный компаратор . При сравнении чисел $A$ и $B$ , инвертируйте каждый нечетный бит обоих чисел. После этого сравните $A$ и $B$ используя стандартный беззнаковый компаратор. ^[11]

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

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

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

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

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

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

у нас есть

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

а также

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

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

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

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

.

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

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

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

Воображаемая база

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

См. также

Ссылки

^ Кнут, Дональд (1998), Искусство компьютерного программирования , Том 2 (3-е изд.), стр. 204–205 . Кнут упоминает как недвоичную, так и недесятеричную систему счисления.
^ Негативная система кратко обсуждается в Петковшек, Марко (1990), «Неоднозначные числа плотны», The American Mathematical Monthly , 97 (5): 408–411, doi : 10.2307/2324393 , ISSN 0002-9890 , JSTOR 2324393 , MR 1048915 .
^ Витторио Грюнвальд. Вокруг арифметики систем счисления с отрицательным основанием, с особым вниманием к системе счисления с отрицательным десятичным числом для изучения ее аналогий с обычной (десятичной) арифметикой, Giornale di Matematiche di Battaglini (1885), 203-221, 367.
^ Кемпнер, А.Дж. (1936), «Анормальные системы счисления», American Mathematical Monthly , 43 (10): 610–617, doi : 10.2307/2300532 , JSTOR 2300532 , MR 1523792 . Единственная ссылка на отрицательные основания - это сноска на странице 610, которая гласит: «Положительные числа меньше 1 и отрицательные числа могут использоваться в качестве оснований с небольшими изменениями процесса и соответствующими ограничениями на набор используемых цифр».
^ Павляк, З.; Вакулич, А. (1957), «Использование разложений с отрицательным основанием в арифмометре цифрового компьютера», Bulletin de l'Académie Polonaise des Sciences , Classe III, 5 : 233–236 .
^ Марчинский, RW, «Первые семь лет польских вычислений». Архивировано 19 июля 2011 г. в Wayback Machine , IEEE Annals of the History of Computing, Vol. 2, № 1, январь 1980 г.
^ «Алгоритм — документация zfp 1.0.1» . zfp.readthedocs.io .
^
См. ссылку MathWorld Negabinary. В частности, ссылки:
- Судзик, М. «Программирование: соревнование по программированию Mathematica». Технологическая конференция Wolfram, 1999 г.
- Шреппель Р. Пункт 128 в деле Билер М.; Госпер, RW; и Шреппель, Р. ХАКМЕМ . Кембридж, Массачусетс: Лаборатория искусственного интеллекта Массачусетского технологического института, Memo AIM-239, стр. 24 февраля 1972 г. http://www.hakmem.org/#item128.
^ Фрэнсис, Ю; Суганда, Хутамулия; Шизухуо, Инь (4 сентября 2001 г.). Введение в информационную оптику . Академическая пресса. п. 498. ИСБН 9780127748115 .
^ «Почему следующая формула увеличивает отрицательное число (число по основанию -2)?» . Проверено 29 августа 2016 г.
^ Муругесан, Сан (1977). «Негабинарные арифметические схемы, использующие двоичную арифметику». Журнал IEE по электронным схемам и системам . 1 (2): 77. doi : 10.1049/ij-ecs.1977.0005 .
^ Д. Кнут. Искусство компьютерного программирования. Том 2, 3-е издание. Аддисон-Уэсли. стр. 205, «Позиционные системы счисления».

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

Уоррен-младший, Генри С. (2013) [2002]. Хакерское наслаждение (2-е изд.). Аддисон Уэсли - Pearson Education, Inc. ISBN 978-0-321-84268-8 . 0-321-84268-5.

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

[1] Кнут, Дональд (1998), Искусство компьютерного программирования , Том 2 (3-е изд.), стр. 204–205 . Кнут упоминает как недвоичную, так и недесятеричную систему счисления.

[2] Негативная система кратко обсуждается в Петковшек, Марко (1990), «Неоднозначные числа плотны», The American Mathematical Monthly , 97 (5): 408–411, doi : 10.2307/2324393 , ISSN 0002-9890 , JSTOR 2324393 , MR 1048915 .

[3] Витторио Грюнвальд. Вокруг арифметики систем счисления с отрицательным основанием, с особым вниманием к системе счисления с отрицательным десятичным числом для изучения ее аналогий с обычной (десятичной) арифметикой, Giornale di Matematiche di Battaglini (1885), 203-221, 367.

[4] Кемпнер, А.Дж. (1936), «Анормальные системы счисления», American Mathematical Monthly , 43 (10): 610–617, doi : 10.2307/2300532 , JSTOR 2300532 , MR 1523792 . Единственная ссылка на отрицательные основания - это сноска на странице 610, которая гласит: «Положительные числа меньше 1 и отрицательные числа могут использоваться в качестве оснований с небольшими изменениями процесса и соответствующими ограничениями на набор используемых цифр».

[5] Павляк, З.; Вакулич, А. (1957), «Использование разложений с отрицательным основанием в арифмометре цифрового компьютера», Bulletin de l'Académie Polonaise des Sciences , Classe III, 5 : 233–236 .

[6] Марчинский, RW, «Первые семь лет польских вычислений». Архивировано 19 июля 2011 г. в Wayback Machine , IEEE Annals of the History of Computing, Vol. 2, № 1, январь 1980 г.

[zfp-7] «Алгоритм — документация zfp 1.0.1» . zfp.readthedocs.io .

[8] См. ссылку MathWorld Negabinary. В частности, ссылки:
Судзик, М. «Программирование: соревнование по программированию Mathematica». Технологическая конференция Wolfram, 1999 г.

Шреппель Р. Пункт 128 в деле Билер М.; Госпер, RW; и Шреппель, Р. ХАКМЕМ . Кембридж, Массачусетс: Лаборатория искусственного интеллекта Массачусетского технологического института, Memo AIM-239, стр. 24 февраля 1972 г. http://www.hakmem.org/#item128.

[9] Судзик, М. «Программирование: соревнование по программированию Mathematica». Технологическая конференция Wolfram, 1999 г.

[10] Шреппель Р. Пункт 128 в деле Билер М.; Госпер, RW; и Шреппель, Р. ХАКМЕМ . Кембридж, Массачусетс: Лаборатория искусственного интеллекта Массачусетского технологического института, Memo AIM-239, стр. 24 февраля 1972 г. http://www.hakmem.org/#item128.

[9] Фрэнсис, Ю; Суганда, Хутамулия; Шизухуо, Инь (4 сентября 2001 г.). Введение в информационную оптику . Академическая пресса. п. 498. ИСБН 9780127748115 .

[10] «Почему следующая формула увеличивает отрицательное число (число по основанию -2)?» . Проверено 29 августа 2016 г.

[11] Муругесан, Сан (1977). «Негабинарные арифметические схемы, использующие двоичную арифметику». Журнал IEE по электронным схемам и системам . 1 (2): 77. doi : 10.1049/ij-ecs.1977.0005 .

[12] Д. Кнут. Искусство компьютерного программирования. Том 2, 3-е издание. Аддисон-Уэсли. стр. 205, «Позиционные системы счисления».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]