Я - специалист в области компьютерных наук, интересующийся тем, как языки ассемблера обрабатывают целочисленную функцию деления.Кажется, что просто сложить числитель, давая и деление, и мод, слишком непрактично, поэтому я придумал другой способ деления, используя сдвиги битов, вычитание и таблицы поиска 2.
По сути, функция берет знаменатель и создает «блоки» на основе наибольшей степени 2. Таким образом, деление на 15 делает двоичные блоки по 4, деление на 5 делает двоичные блоки по 3 и т. Д. Затем генерируется первый блок 2 ^размер, кратный знаменателю.Для каждого множителя запишите значения ПОСЛЕ первого блока в справочную таблицу с указанием значения первого блока.
Пример: кратные 5 в двоичном - размер блока 3 (восьмеричный)
000 000 **101** - 5 maps to 0
000 001 **010** - 2 maps to 1
000 001 **111** - 7 maps to 1
000 010 **100** - 4 maps to 2
000 011 **001** - 1 maps to 3
000 011 **110** - 6 maps to 3
000 100 **011** - 3 maps to 4
000 101 **000** - 0 maps to 5
Таким образом, фактическая процедура включает в себя получение первого блока, сдвиг влево по первому блоку и вычитание значения, на которое отображаются блоки.Если полученное число получается равным 0, то оно идеально делится, а если значение становится отрицательным, это не так.
Если вы добавите другую таблицу поиска для перечисления , в которой вы отобразите значенияна счетчик, как они входят, вы можете рассчитать результат деления!
Пример: снова умножить на 5
5 maps to 1
2 maps to 2
7 maps to 3
4 maps to 4
1 maps to 5
6 maps to 6
3 maps to 7
0 maps to 8
Затем все, что осталось, - сопоставить каждый блок с таблицей, и у вас есть ответ.
Есть несколько проблем сЭтот метод.
- Если ответ не делится идеально, то функция возвращает обратно мусор.
- Для больших значений Integer это не сработает, потому что размер 5 блоков будет усечен в конце 32-разрядного или 64-разрядного целого числа.
- Это примерно в 100 раз медленнее, чем стандартное деление в C.
- Если знаменатель является фактором делителя, то ваши блоки должны отображаться в несколько значений, и вам нужно даже больше таблиц.Эту проблему можно решить с помощью простой факторизации, но все методы, которые я читал о простой / быстрой простой факторизации, включают в себя деление, побеждающее цель этого.
Итак, у меня есть 2 вопроса: во-первых, есть ли уже подобный алгоритм?Я огляделся и не могу найти ничего подобного.Во-вторых, как реальные языки ассемблера обрабатывают целочисленное деление?
Извините, если есть какая-либо ошибка форматирования, я впервые публикую сообщение о переполнении стека.