Как происходит разделение на наших компьютерах?

17

Как происходит деление внутри цифровых компьютеров? Какой алгоритм для этого?

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

Программа-о-стив
источник
1
@ program-o-steve Подразделение в АЛУ - сложная операция. Вы не получите «простую» блок-схему.
Majenko
5
@ Леон Хеллер Ох! Это не так. Это чисто аппаратный вопрос
program-o-steve
2
@ Леон Хеллер Я думаю, что это не ...., которые включают электронику, физические вычисления ...
program-o-steve
2
Деление в микроконтроллерах не прямое. Есть быстрые и медленные способы сделать это. Медленные способы легче понять, но быстрые способы используются в современных процессорах, о чем конкретно вы хотите знать? Вы просто хотите получить базовое понимание принципов или детальный анализ современных процессоров?
Консалик
4
@ LeonHeller Я обычно согласен с вопросами, которые вы хотите закрыть, но проектирование CPU - это в значительной степени вопрос электротехники. Этот вопрос может использовать некоторую помощь, чтобы сделать его намного более понятным о том, что нужно (например, о том, о чем спрашивает konsalik), но это не делает его не по теме.
Kellenjb

Ответы:

17

Алгоритмы деления в цифровых разработках можно разделить на две основные категории. Медленное деление и быстрое деление.

Я предлагаю вам прочитать о том, как работают двоичное сложение и вычитание, если вы еще не знакомы с этими понятиями.

Медленное деление

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

Пример:

7/3:

  1. 7-3знак равно4
  2. 4-3знак равно1
  3. 1<3

Таким образом, ответ 2 с остатком 1. Чтобы сделать этот ответ немного более актуальным, вот некоторые предыстории. Выполняется двоичное вычитание путем сложения отрицательных значений, например: 7 - 3 = 7 + (-3). Это достигается с помощью дополнения до двух. Каждое двоичное число добавляется с использованием серии полных сумматоров:

введите описание изображения здесь

Где каждый 1-битный полный сумматор реализован следующим образом:

введите описание изображения здесь

Быстрое деление

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

Рассмотрим метод Гольдшмидта:

Я воспользуюсь следующим:

Qзнак равноND

Этот метод работает следующим образом:

  1. Умножьте N и D на дробь F так, чтобы D приблизилось к 1.
  2. Когда D приближается к 1, N приближается к Q

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

Konsalik
источник
1
Некоторые блоки - схема для вариаций на «медленном» методы (реализованные в сборе на тысячных без аппаратного разрыва, но все же полезно) приведены в Atmel, AVR200 AppNote.
Кевин Вермеер
Не могли бы вы дать иллюстрацию о методе деления Гольдшмидта. Также приведенная здесь блок-схема является примером медленного деления?
программа o-steve
Что это за метод, в котором мы должны неоднократно сдвигать дивиденд влево?
программа о-Стив
@ program-o-steve Вот краткая иллюстрация: найдите 22/7 (прибл. пи). Во-первых, умножьте верх и низ на 0,1, чтобы получить: 2,2 / 0,7. Умножьте снова, используя 1,3, получив: 2,86 / 0,91. Используя 1,09, получите: 3,174 / 0,9919; 1,008 - 3,1423393 / 0,9998352. Продолжайте в том же духе. 1.000000 ...
Алан Кэмпбелл
Как вы «умножаете на дробь»? Дроби не представимы в плавающей точке. Дробь по определению - это числитель, деленный на знаменатель, так что вы остаетесь в круговом аргументе, все еще имея необходимость делить. И как оценивать эту долю в первую очередь?
CogitoErgoCogitoSum
4

Аппаратное обеспечение для деления с плавающей запятой является частью логического блока, который также выполняет умножение; имеется аппаратный модуль умножителя. Числа с плавающей точкой, скажем, A и B, делятся (образуя A / B) на

  1. разложение чисел с плавающей запятой на показатели знака (+1 или -1), мантиссы ("a" и "b" и (двоичный целочисленный тип)
  2. знак результата равен (+1), если оба знака совпадают, иначе (-1)
  3. экспоненты вычитаются (показатель B вычитается из показателя A), чтобы сформировать показатель результата
  4. мантиссы (двоичные цифры чисел) являются двоичными числами с фиксированной запятой между 1/2 и 1; это означает, что первая цифра после двоичной точки - «1», за которой следуют нули и единицы ... в качестве первого шага таблица поиска находит обратную величину с точностью до шести бит (есть только 32 возможности, это небольшая таблица)

  5. aбзнак равноa*ресяпросaL(б)б*ресяпросaL(б)

  6. d==1+ε
    d*(2-d)знак равно(1+ε)×(1-ε)знак равно1-ε2
    Это подразумевает, что наша пятибитовая точность «единица» в знаменателе станет десятибитной точностью после еще одной пары умножений, двадцать битной точностью после двух и сорокабитовой точностью после трех. Сделайте столько итераций умножения числителя и знаменателя на (2 - знаменатель), сколько требует точность вашего результата.
  7. Числитель теперь, когда знаменатель равен ровно 1, является мантиссой результата и может быть объединен с ранее вычисленным знаком и показателем степени.
  8. IEEE с плавающей запятой допускает некоторые исключения (денормализованные числа, NAN; они должны обрабатываться другими логическими операциями.

Интересно, что старая ошибка деления Pentium (очень достойная публикации в 1994 году) была вызвана ошибкой печати, которая приводила к ошибочным значениям обратной таблицы для шага (4). Ранняя статья «Метод деления с использованием параллельного множителя», Domenico Ferrari, IEEE Trans. Электрон. Вычи. В EC-16 / 224-228 (1967) описывается метод, а также в документе "IBM System / 360 Model 91: модуль выполнения с плавающей запятой" IBM J. Res. Девиация 11 : 34-53 (1967).

Whit3rd
источник
1

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

Вычисление обратного знаменателя не так уж плохо; это делается путем уточнения последовательных приближений. Пусть g будет вашим предположением для 1 / d. Для лучшего предположения используйте g '= g (2-й б). Это сходится квадратично, поэтому вы удваиваете цифры точности при каждом улучшении.

Пример: вычисление обратной величины 3.5.

Ваше первоначальное предположение 0,3. Вы вычисляете 0,3 * 3,5 = 1,15. Ваше скорректированное предположение составляет 0,3 * (2 - 1,15) = 0,285. Уже довольно близко! Повторите процесс, и вы получите 0,2857125, а третья попытка получит 0,2857142857.

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

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

richard1941
источник
-1

Компьютеры не делают итеративное сложение для умножения чисел - это будет очень медленно. Вместо этого есть несколько быстрых алгоритмов умножения. Проверьте: http://en.wikipedia.org/wiki/Karatsuba_algorithm

user59608
источник
Добро пожаловать в EE.SE. Ответы только на ссылки не приветствуются. Пожалуйста, обобщите информацию в ссылке.
Ноль
Они делают. Тонны процессоров до сих пор не имеют множителей одного цикла и используют программные мультипликаторы.
user3528438