Метод дополнений - Method of complements - Wikipedia

Дополнять числа на счетная машина c. 1910. Меньшие числа, используемые при вычитании, представляют собой дополнение к девяткам больших чисел, которые используются при сложении.

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

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

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

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

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

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

В дополнение системы счисления из п цифровой номер у в основание б по определению ${\displaystyle b^{n}-y}$.^{[нечеткий ]} Дополнительную систему счисления проще всего получить, добавив 1 к дополнение с уменьшенным основанием, который ${\displaystyle \left(b^{n}-1\right)-y}$. С ${\displaystyle \left(b^{n}-1\right)}$ это цифра ${\displaystyle b-1}$ повторяется п раз (потому что ${\displaystyle b^{n}-1=(b-1)\left(b^{n-1}+b^{n-2}+\ldots +b+1\right)=(b-1)b^{n-1}+\ldots +(b-1)}$; смотрите также Формула геометрического ряда ), уменьшенное дополнение основания числа находится путем дополнения каждой цифры относительно ${\displaystyle b-1}$ (то есть вычитая каждую цифру в у из ${\displaystyle b-1}$).

Вычитание у из Икс может выполняться следующим образом. Добавление дополнения к уменьшенному основанию системы счисления Икс к у приводит к значению ${\displaystyle b^{n}-1-x+y}$ или же ${\displaystyle b^{n}-1-(x-y)}$ который является уменьшенным дополнением системы счисления ${\displaystyle x-y}$. Уменьшенное дополнение системы счисления - это значение ${\displaystyle x-y}$. В качестве альтернативы добавление дополнения к основанию системы счисления у к Икс приводит к значению ${\displaystyle x+b^{n}-y}$ или же ${\displaystyle x-y+b^{n}}$. Предполагая у ≤ х , результат всегда будет больше или равен ${\displaystyle b^{n}}$ и удаление начальной "1" то же самое, что и вычитание ${\displaystyle b^{n}}$, делая результат ${\displaystyle x-y+b^{n}-b^{n}}$ или просто ${\displaystyle 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, уменьшаемое] - 218 [y, вычитаемое]

Первый способ

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

  126 [дополнение до девяти x = 999 - x] + 218 [y, вычитаемое]

=

  344 [999 - x + y]

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

  344 [результат] 655 [дополнение до девяти 344 = 999 - (999 - x + y) = x - y, правильный ответ]

Второй способ

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

Далее, сумма Икс и девятки дополнения у взят:

  873 [x] + 781 [дополнение до девяти y = 999 - y]

=

 1654 [999 + x - y]

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

 1654-1000  [-(999 + 1)]

=

  654 [x - y - 1]

Это еще не так. По сути, на первом этапе мы добавили к уравнению 999. Затем мы удалили 1000, когда опустили ведущую 1 в результате 1654 выше. Таким образом, полученный нами ответ (654) на единицу меньше правильного. ${\displaystyle (x-y)}$. Чтобы исправить это, мы должны добавить к нашему ответу 1:

  654+   1

=

  655 [x - y]

Добавление 1 дает 655, правильный ответ на нашу исходную задачу вычитания.

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

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

  123410 [x, уменьшенное] - 123401 [y, вычитаемое]

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

  876589 [дополнение x до девяти] + 123401 [y]

=

  999990

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

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

  48032 [x] - 391 [y]

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

  48032 [x] - 00391 [y с ведущими нулями]

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

  48032 [x] + 99608 [дополнение до девяти y] + 1

=

 147641

Если отбросить первую цифру "1", получится правильный ответ: 47641.

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

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

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

  0110 0100 [x, равно десятичному 100] - 0001 0110 [y, равно десятичному 22]

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

  0110 0100 [x] + 1110 1001 [дополнение до единиц y = 1111 1111 - y] + 1 [чтобы получить дополнение до двух = 1 0000 0000 - y]

=

 10100 1110 [x + 1 0000 0000 - y]

Если отбросить начальную единицу, получим ответ: 0100 1110 (равно 78 в десятичной системе).

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

Основная статья: Знаковые представления чисел

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

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

  185 [x] - 329 [y]

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

  185 [x] + 670 [девять дополнений к y] + 1

=

  856

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

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

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

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

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

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

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

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

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

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

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

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

В начальной школе

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

Смотрите также

• Два дополнения - специальный корпус для двоичных компьютеров

Рекомендации

1. Florida Tech
2. Простые инструкции по эксплуатации комптометра с управляемым ключом, Comptometer Division, Felt and Tarrant Mfg. Co., Чикаго, 1917, стр. 12
3. Карл Барнетт Аллендёрфер (1971). Основы арифметики и геометрии для учителей начальной школы. Макмиллан.