Метод дополнений

В математике и вычислительной технике метод дополнений — это метод кодирования симметричного диапазона положительных и отрицательных целых чисел таким образом, чтобы они могли использовать один и тот же алгоритм (или механизм ) для сложения во всем диапазоне. Для данного количества мест половина возможных представлений чисел кодирует положительные числа, другая половина представляет их соответствующие аддитивные обратные числа . Пары взаимно аддитивных обратных чисел называются дополнениями . Таким образом, вычитание любого числа осуществляется путем прибавления его дополнения. Изменение знака любого числа кодируется путем генерации его дополнения, что можно выполнить с помощью очень простого и эффективного алгоритма. Этот метод широко использовался в механических калькуляторах и до сих пор используется в современных компьютерах . Обобщенная концепция дополнения по системе счисления (как описано ниже) также ценна в теории чисел , например, в теореме Миди .

Дополнение девяток числа, заданного в десятичном представлении, формируется путем замены каждой цифры на девять минус эта цифра. Чтобы вычесть десятичное число y ( вычитаемое ) из другого числа x ( вычитаемое ), можно использовать два метода:

дополнение девяток x добавляется В первом методе к y . Затем формируется дополнение девяток полученного результата для получения желаемого результата.

Во втором методе дополнение девяток числа y добавляется к x , а к сумме добавляется единица. Крайняя левая цифра «1» результата затем отбрасывается. Отбрасывать крайнюю левую единицу особенно удобно на калькуляторах или компьютерах, использующих фиксированное количество цифр: ей некуда деваться, поэтому она просто теряется во время вычислений. Комплект девяток плюс один известен как комплект десятков.

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

Числовые дополнения

Радикс дополнение - $n$ -значное число $y$ в системе счисления $b$ определяется как $b^{n}-y$ . На практике дополнение по системе счисления легче получить, прибавив 1 к уменьшенному дополнению по системе счисления , что равно $\left(b^{n}-1\right)-y$ . Хотя это кажется столь же трудным для вычисления, как и дополнение по системе счисления, на самом деле это проще, поскольку $\left(b^{n}-1\right)$ это просто цифра $b-1$ повторенный $n$ раз. Это потому, что $b^{n}-1=(b-1)\left(b^{n-1}+b^{n-2}+\cdots +b+1\right)=(b-1)b^{n-1}+\cdots +(b-1)$ (см. также Формулу геометрического ряда ). Зная это, уменьшенное дополнение числа по системе счисления можно найти, дополняя каждую цифру относительно $b-1$ , то есть вычитание каждой цифры в $y$ от $b-1$ .

Вычитание $y$ от $x$ использование уменьшенного дополнения по системе счисления может быть выполнено следующим образом. Добавьте уменьшенное дополнение по системе счисления $x$ к $y$ чтобы получить $b^{n}-1-x+y$ или эквивалентно $b^{n}-1-(x-y)$ , который представляет собой уменьшенное дополнение по основанию $x-y$ . Далее, взяв уменьшенное дополнение по системе счисления $b^{n}-1-(x-y)$ приводит к желаемому ответу $x-y$ .

Альтернативно используя дополнение по системе счисления, $x-y$ можно получить добавлением дополняющего системы счисления $y$ к $x$ чтобы получить $x+b^{n}-y$ или $x-y+b^{n}$ . Предполагая $y\leq x$ , результат будет больше или равен $b^{n}$ и отбросить ведущее $1$ из результата это то же самое, что вычитание $b^{n}$ , делая результат $x-y+b^{n}-b^{n}$ или просто $x-y$ , желаемый результат.

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

Десятичный пример

цифра	Девятки дополнять
0	9
1	8
2	7
3	6
4	5
5	4
6	3
7	2
8	1
9	0

Дополнение девяток десятичной цифры — это число, которое к ней нужно прибавить, чтобы получить 9; комплект девяток из 3 равен 6, комплект девяток из 7 равен 2 и т. д., см. таблицу. Чтобы сформировать дополнение девяток большего числа, каждая цифра заменяется дополнением девяток.

Рассмотрим следующую задачу на вычитание:

  873  [x, the minuend]
- 218  [y, the subtrahend]

Первый метод

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

  126  [nines' complement of x = 999 - x]
+ 218  [y, the subtrahend]
—————
  344  [999 - x + y]

Теперь вычислите дополнение девяток результата

  344  [result]
  655  [nines' complement of 344 = 999 - (999 - x + y) = x - y, the correct answer]

Второй метод

Вычислите дополнение девяток числа 218, то есть 781. Поскольку число 218 состоит из трех цифр, это то же самое, что вычитание 218 из 999.

Далее сумма $x$ и комплект девяток $y$ берется:

  873  [x]
+ 781  [nines' complement of y = 999 - y]
—————
 1654  [999 + x - y]

Затем первая цифра «1» опускается, что дает 654.

 1654
-1000  [-(999 + 1)]
—————
  654  [-(999 + 1) + 999 + x - y]

Это еще не правильно. На первом этапе к уравнению было добавлено 999. Затем 1000 было вычтено, когда была отброшена ведущая 1. Значит, полученный ответ (654) на единицу меньше правильного ответа. $x-y$ . Чтобы это исправить, к ответу добавляется 1:

  654
+   1
—————
  655  [x - y]

Прибавление 1 дает 655 — правильный ответ на нашу первоначальную задачу на вычитание. Последний шаг добавления 1 можно было бы пропустить, если бы вместо этого на первом шаге использовалось дополнение до десяти к y.

Величина чисел

В следующем примере результат вычитания содержит меньше цифр, чем $x$ :

  123410  [x, the minuend]
- 123401  [y, the subtrahend]

Используя первый метод, сумма набора девяток чисел $x$ и $y$ является

  876589  [nines' complement of x]
+ 123401  [y]
————————
  999990

Дополнение девяток числа 999990 равно 000009. Удаление ведущих нулей дает 9, желаемый результат.

Если вычитаемое, $y$ , имеет меньше цифр, чем уменьшаемое, $x$ , во втором методе необходимо добавить ведущие нули. Эти нули становятся ведущими девятками, когда берется дополнение. Например:

  48032  [x]
-   391  [y]

можно переписать

  48032  [x]
- 00391  [y with leading zeros]

Замена 00391 его дополнением девяток и добавление 1 дает сумму:

  48032  [x]
+ 99608  [nines' complement of y]
+     1
———————
 147641

Отбросив ведущую единицу, получим правильный ответ: 47641.

Бинарный метод

Двоичный цифра	Единицы дополнять
0	1
1	0

Метод дополнений особенно полезен в двоичных числах (основание 2), поскольку дополнение единиц очень легко получить путем инвертирования каждого бита (замены «0» на «1» и наоборот). Добавление 1 для получения дополнения до двух можно выполнить путем имитации переноса в младший бит. Например:

  0110 0100  [x, equals decimal 100]
- 0001 0110  [y, equals decimal 22]

становится суммой:

  0110 0100  [x]
+ 1110 1001  [ones' complement of y = 1111 1111 - y]
+         1  [to get the two's complement = 1 0000 0000 - y]
———————————
 10100 1110  [x + 1 0000 0000 - y]

Удаление начальной «1» дает ответ: 0100 1110 (равно десятичному 78).

Представления отрицательных чисел

Метод дополнений обычно предполагает, что операнды положительны и что y ≤ x , логические ограничения, учитывая, что сложение и вычитание произвольных целых чисел обычно выполняется путем сравнения знаков, сложения двух или вычитания меньшего из большего и получения правильного результата. знак.

Давайте посмотрим, что произойдет, если x < y . В этом случае после сложения не будет цифры «1», которую можно было бы зачеркнуть, поскольку $x-y+b^{n}$ будет меньше, чем $b^{n}$ . Например, (в десятичном формате):

  185  [x]
- 329  [y]

Дополнение y и добавление дает:

  185  [x]
+ 670  [nines' complement of y]
+   1
—————
  856

На данный момент нет простого способа завершить расчет вычитанием $b^{n}$ (в данном случае 1000); нельзя просто игнорировать ведущую 1. Ожидаемый ответ — −144, что не так уж далеко, как кажется; Число 856 является дополнением десяти к числу 144. Эту проблему можно решить несколькими способами:

Игнорируйте проблему. Это разумно, если человек использует вычислительное устройство, которое не поддерживает отрицательные числа, поскольку сравнение двух операндов перед вычислением, чтобы их можно было ввести в правильном порядке, и проверка того, что результат является разумным, людям легко сделать. .
Используйте тот же метод, чтобы вычесть 856 из 1000, а затем добавить к результату отрицательный знак.
Представляйте отрицательные числа как дополнения к их положительным аналогам. Числа меньше $b^{n}/2$ считаются положительными; остальные считаются отрицательными (и их величину можно получить, взяв дополнение по системе счисления). Лучше всего это работает для четных корней, поскольку знак можно определить, посмотрев на первую цифру. Например, числа в десятичной записи являются положительными, если первая цифра равна 0, 1, 2, 3 или 4, и отрицательными, если 5, 6, 7, 8 или 9. И это очень хорошо работает в двоичном формате, поскольку первая цифра Бит можно считать знаковым битом: число является положительным, если знаковый бит равен 0, и отрицательным, если он равен 1. Действительно, дополнение до двух . в большинстве современных компьютеров для представления чисел со знаком используется
Дополните результат, если нет переноса самой старшей цифры (признак того, что x было меньше y ). Это легче реализовать с помощью цифровых схем , чем сравнивать и менять местами операнды. Но поскольку для получения дополнения по системе счисления требуется прибавить 1, это сложно сделать напрямую. К счастью, можно использовать хитрость, чтобы обойти это сложение: вместо того, чтобы всегда устанавливать перенос в наименее значащую цифру при вычитании, перенос самой старшей цифры используется в качестве входных данных переноса в наименее значащую цифру (операция, называемая перенос по кругу ). Таким образом, если y ≤ x , добавляется перенос от самой старшей цифры, которая обычно игнорируется, что дает правильный результат. А если нет, то 1 не добавляется, и результат оказывается на единицу меньше, чем дополнение по системе счисления ответа или уменьшенное дополнение по системе счисления, для получения которого не требуется сложение. Этот метод используется компьютерами, которые используют знак и величину для представления чисел со знаком.

Практическое использование

Комптометр 1920-х годов, на каждой клавише отмечено число девяток.

Метод дополнений использовался во многих механических калькуляторах как альтернатива вращению шестерен назад. Например:

Калькулятор Паскаля имел два набора цифр результата: черный набор, отображающий нормальный результат, и красный набор, отображающий его дополнение до девяток. Горизонтальная планка использовалась, чтобы закрыть один из этих наборов, обнажая другой. Для вычитания красные цифры были выставлены и установлены на 0. Затем было введено дополнение девяток вычитаемого числа. На некоторых машинах это можно было сделать путем набора уменьшаемого числа с помощью внутренних колес дополнений (т. е. без необходимости мысленно определять дополнение девяток уменьшаемого числа). Отображая эти данные в окне дополнения (красный набор), оператор мог видеть дополнение девяток к дополнению девяток вычитаемого числа, то есть вычитаемого числа. Затем планку переместили, чтобы обнажить черные цифры (которые теперь отображали дополнение девяток к вычитаемому), и вычитаемое добавлялось путем его набора. Наконец, оператору пришлось снова переместить планку, чтобы прочитать правильный ответ.
цифры На комптометре , дополняющие девятки, были напечатаны мелким шрифтом вместе с обычными цифрами на каждой клавише. Для вычитания оператор должен был мысленно вычесть 1 из вычитаемого и ввести результат, используя меньшие цифры. Поскольку вычитание 1 перед дополнением эквивалентно добавлению 1 после него, оператор, таким образом, фактически добавит дополнение до десяти к вычитаемому. Оператору также необходимо было зажать «вкладку отсечки вычитания», соответствующую крайней левой цифре ответа. Эта вкладка предотвращала распространение переноса за ее пределы - метод Comptometer, позволяющий исключить начальную 1 из результата. ^[2]
Калькулятор Curta использовал метод дополнений для вычитания и сумел скрыть это от пользователя. Числа вводились с помощью слайдеров для ввода цифр, расположенных на боковой стороне устройства. Число на каждом слайде добавлялось к счетчику результатов с помощью зубчатого механизма, который зацеплял кулачки на вращающемся «ступенчатом барабане» (также известном как «ступенчатый барабан»). Барабан вращался с помощью рукоятки на верхней части инструмента. Количество кулачков, с которыми сталкивается каждая цифра при повороте рукоятки, определялось значением этой цифры. Например, если ползун установлен в положение «6», вокруг барабана будет обнаружен ряд из 6 кулачков, соответствующий этому положению. Для вычитания барабан перед поворотом слегка смещался, в результате чего на место перемещался другой ряд кулачков. Этот альтернативный ряд содержал набор девяток цифр. Таким образом, ряд из 6 кулачков, который был готов к добавлению, теперь имел ряд из 3 кулачков. Перемещенный барабан также задействовал один дополнительный кулачок, что прибавило к результату 1 (как того требует метод дополнений). Всегда присутствующее дополнение до десяти «переполнение 1», выходящее за пределы старшей цифры регистра результатов, фактически было отброшено.

В компьютерах

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

Если используется представление дополнения до двух, для вычитания требуется только инвертировать биты вычитаемого и устанавливать перенос в самый правый бит.
Использование представления дополнения до единиц требует инвертирования битов вычитаемого и соединения переноса наиболее значимого бита с переносом младшего бита (концевой перенос).
Использование знаково-амплитудного представления требует только дополнения знакового бита вычитаемого и сложения, но логика сложения/вычитания должна сравнивать знаковые биты, дополнять один из входных данных, если они разные, реализовывать циклический перенос и дополнять результат, если не было переноса от старшего бита.

Ручное использование

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

Пополнение суммы удобно для кассиров, осуществляющих сдачу за покупку из валюты одного номинала 1, возведенной в целую степень базовой валюты. Для десятичных валют это будут 10, 100, 1000 и т. д., например, купюра в 10 долларов.

В начальной школе образование

В начальных школах учащихся иногда учат методу дополнений как сокращенному методу, полезному в ментальной арифметике . ^[3] Вычитание выполняется путем добавления дополнения десяти к вычитаемому , которое представляет собой дополнение девяток плюс 1. Результат этого сложения используется, когда ясно, что разница будет положительной, в противном случае дополнение десяти к результату сложения используется с он отмечен как отрицательный. Тот же метод работает и для вычитания на счетной машине.

См. также

Нравиться

Ссылки

^ Технологический институт Флориды
^ Простые инструкции по эксплуатации комптометра с управляемым ключом , Отдел комптометров, Felt and Tarrant Mfg. Co., Чикаго, 1917, стр. 12
^ Карл Барнетт Аллендорфер (1971). Основы арифметики и геометрии для учителей начальной школы . Макмиллан.

[1] Технологический институт Флориды

[2] Простые инструкции по эксплуатации комптометра с управляемым ключом , Отдел комптометров, Felt and Tarrant Mfg. Co., Чикаго, 1917, стр. 12

[3] Карл Барнетт Аллендорфер (1971). Основы арифметики и геометрии для учителей начальной школы . Макмиллан.

[1]

[2]

[3]