Деление целых чисел(dw) через вычитание

[Alex1991]

Напишите пожалуйста сам алгоритм, как с помощью команды вычитания можно поделить число ?

[Mikl___]

Alex1991
Частное от деления можно представить как количество вычитаний делителя из делимого до тех пор, пока делимое сохраняет знак. Это дало возможность организовать деление путем повторения последовательности вычитаний с проверкой знака делимого. Если произошла перемена знака, то нужно уменьшить счетчик числа вычитаний на единицу, а делимое и делитель сложить. Теперь делимое будет равно остатку, а счетчик числа вычитаний равен частному. Так делили на ранних микропроцессорах Intel (i4004, i8080), которые еще не поддерживали команду деления.
Пример: делим 125 на 11
125 - 11 = 114 результат >0 частное = 1
114 - 11 = 103 результат >0 частное = 2
103 - 11 = 92 результат >0 частное = 3
92 - 11 = 81 результат >0 частное = 4
81 - 11 = 70 результат >0 частное = 5
70 - 11 = 59 результат >0 частное = 6
59 - 11 = 48 результат >0 частное = 7
48 - 11 = 37 результат >0 частное = 8
37 - 11 = 26 результат >0 частное = 9
26 - 11 = 15 результат >0 частное = 10
15 - 11 = 4 результат >0 частное = 11
4 - 11 = -7 результат <0 частное = 12 -1 = 11 остаток = -7+11 = 4 результат получили за 12 вычитаний
проверяем: 125 / 11 = 11,363636363636363636363636363636
остаток: 0,363636363636363636363636363636 * 11 = 3,999999999999999999999999999996 = 4
но это не самый быстрый способ деления, количество вычитаний будет расти с ростом делимого и уменьшением вычитаемого. Вот так можно увеличить скорость деления -- из делимого вычитаем делитель, умноженный на степень двойки. Произведение числа на 2ⁿ эквивалентно сдвигу этого числа на n разрядов влево. Если знак результата положительный, то нужно прибавить 2ⁿ к частному, если знак результата отрицательный – частное не увеличивается. Когда знак результата меняется на отрицательный, вычитание заменяется сложением. Так повторяется при уменьшающихся степенях двойки до тех пор, пока не будет достигнута степень, равная нулю. Остатком считается последний положительный результат.
Опять разделим 125 на 11. Делитель укладывается в байт (11<255), поэтому начинаем с 2^7. В начале вычисления частное всегда равно 0:
125 – 11 * 2^7 = –1283
–1283 +11 * 2^6 = –579
–579 +11 * 2^5 = –227
–227 +11 * 2^4 = –51
–51 + 11 * 2³ = 37 результат положительный, поэтому складываем 2³ с частным, частное равно 8+0=8
37 – 11 * 2² = – 7
–7 + 11 * 2¹ = 15 результат положительный, поэтому складываем 2¹ с частным, частное равно 2+8=10
15 –11 * 2º = 4 результат положительный, поэтому складываем 2º с частным, частное равно 1+10=11, остаток равен 4
результат получили за 8 вычитаний
А теперь самостоятельно попробуйте разделить 1023 на 5 первым и вторым способом

[_ILYA_]

http://programmersforum.ru/showthread.php?t=120550
это пиар

[Alex1991]

Mikl___, Благодарю принцип понятен !

[Mikl___]

Alex1991
А дополнительное задание сделал?(разделить 1023 на 5) Сколько вычитаний получилось при использовании первого способа и сколько -- вторым способом?
Да, в #2 опечатка -- вместо "Делитель укладывается в байт (11 < 255)" следует читать "Делимое укладывается в байт (125 < 256)" поэтому при делении 1023 на 5 (255 < 1023 < 65536) следует начать с 2^15. Количество вычитаний можно еще больше уменьшить если найти ближайшую степень 2 умноженную на 5, которая будет больше или равна 1023, то есть 5*2^8 = 1280 > 1023 и вычисления начинать с 2^8
Итого: в первом варианте 205 вычитаний, а во втором варианте всего 9 вычитаний

[Alex1991]

Сообщение от Mikl___

Alex1991
А дополнительное задание сделал?(разделить 1023 на 5) Сколько вычитаний получилось при использовании первого способа и сколько -- вторым способом?
Да, в #2 опечатка -- вместо "Делитель укладывается в байт (11 < 255)" следует читать "Делимое укладывается в байт (125 < 256)" поэтому при делении 1023 на 5 (255 < 1023 < 65536) следует начать с 2^15. Количество вычитаний можно еще больше уменьшить если найти ближайшую степень 2 умноженную на 5, которая будет больше или равна 1023, то есть 5*2^8 = 1280 > 1023 и вычисления начинать с 2^8
Итого: в первом варианте 205 вычитаний, а во втором варианте всего 9 вычитаний

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

[Mikl___]

Сообщение от Alex1991

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

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

[Alex1991]

Сообщение от Mikl___

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

Хм... интересно, спасибо