Если аппаратное обеспечение не поддерживает операции модуля или деления, для моделирования модуля / деления с помощью программного обеспечения требуется гораздо больше циклов ЦП. Есть ли более быстрый способ вычисления деления и модуля, если операнд равен 10?
В моем проекте мне часто нужно вычислять целочисленный модуль 10. В частности, я работаю над PIC16F и мне нужно показать число на ЖК-дисплее. Поддерживается 4 цифры, поэтому имеется 4 вызова модуля и функции деления (программная реализация). То есть вроде следующего:
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
digit = number % 10; // call to an expensive function
number /= 10; // call to an expensive function
somehow_lit_segments();
Есть и другие области, в которых используется похожий код.
Ответы:
Вот алгоритм двоичного кода в BCD, который я использовал несколько лет назад на основе одного, найденного здесь . Я использовал внешний драйвер дисплея BCD для 7 сегментов, чтобы результат мог быть записан на соответствующие порты напрямую в виде упакованного BCD для вывода.
Это довольно быстро, если у вас есть аппаратный множитель в PIC, я использовал PIC18F97J60. Если у вас нет аппаратного множителя на вашей PIC, рассмотрите возможность использования shift + add для умножения.
Это принимает беззнаковое 16-битное int и возвращает упакованный BCD с 5 цифрами, его можно изменить и сделать быстрее для 4 цифр. Он использует shift + сложения для приблизительного деления на 10, но с учетом ограниченного входного диапазона он является точным для этого использования. Возможно, вы захотите упаковать результат по-другому, чтобы согласовать, как вы используете результат.
источник
Предполагая, что целые числа без знака, деление и умножение могут быть сформированы из битовых сдвигов. А из (целочисленного) деления и умножения можно вывести по модулю.
Чтобы умножить на 10:
Делить на 10 сложнее. Я знаю несколько алгоритмов деления. Если я правильно помню, есть способ быстро разделить на 10, используя сдвиги битов и вычитание, но я не могу вспомнить точный метод. Если это не так, то это алгоритм деления, который управляет <130 циклами . Я не уверен, какую микросхему вы используете, но вы можете использовать ее каким-то образом, даже если вам придется ее портировать.
РЕДАКТИРОВАТЬ: Кто-то говорит на переполнение стека , если вы можете допустить небольшую ошибку и иметь большой временный регистр, это будет работать:
Если у вас есть деление и умножение, по модулю все просто:
источник
Вы можете конвертировать из двоичного файла в упакованный BCD без деления, используя алгоритм двойного дублирования . Он использует только сдвиг и добавить 3 .
Например, преобразовать 243 10 = 11110011 2 в двоичный
Этот алгоритм очень эффективен, когда нет аппаратного делителя. Более того, используется только сдвиг влево на 1, поэтому он работает быстро, даже когда нет сдвига ствола
источник
В зависимости от количества цифр, которое вам нужно, вы можете использовать метод грубой силы (
d
- номер ввода,t
- строка вывода ASCII):Вы также можете изменить кратные if в цикл с степенями десяти, полученными умножением или таблицей поиска.
источник
В этом примечании по применению описаны алгоритмы арифметики BCD, включая преобразование из двоичного в BCD и наоборот. Приложение от Atmel, которое является AVR, но описанные алгоритмы не зависят от процессора.
источник
У меня нет хорошего ответа, но на нашем родственном сайте Stack Overflow ведется отличная дискуссия на ту же тему деления и оптимизации по модулю.
Достаточно ли у вас памяти для реализации таблицы поиска?
У Hackers Delight есть статья об оптимальных алгоритмах деления.
источник
Рассматривали ли вы постоянное хранение этого значения как BCD (используя простые специальные подпрограммы «BCD increment» и «BCD add») вместо того, чтобы хранить это значение в двоичном виде и конвертировать в BCD по мере необходимости (используя более сложное для понимания «преобразование» из двоичного в BCD "подпрограмма)?
Когда-то все компьютеры хранили все данные в виде десятичных цифр (шестизначные шестерни, вакуумные трубки с кодом два из пяти, BCD и т. Д.), И это наследие все еще сохраняется сегодня. (см. Почему чипы часов реального времени используют BCD ).
источник
PICList удивительный ресурс для людей программирования процессоров PIC.
BCD преобразование
Рассматривали ли вы использование готовой испытанной подпрограммы двоичного кода в BCD, специально оптимизированной для PIC16F?
В частности, люди из PICList потратили много времени на оптимизацию преобразования двоичных данных в BCD на PIC16F. Эти подпрограммы (каждая из которых оптимизирована для конкретного размера) приведены в разделе «Математические методы преобразования радиоканалов PIC» http://www.piclist.com/techref/microchip/math/radix/index.htm
целочисленное деление и мод
На процессоре, подобном PIC16F, подпрограмма, специализирующаяся на делении на константу, часто намного быстрее, чем обычная процедура «деления переменной А на переменную В». Вы можете указать свою константу (в данном случае «0,1») в разделе «Генерация кода для умножения / деления констант» http://www.piclist.com/techref/piclist/codegen/constdivmul.htm или проверить стандартные процедуры рядом с http://www.piclist.com/techref/microchip/math/basic.htm .
источник
Учитывая аппаратное умножение 8x8, можно вычислить divmod-10 числа произвольного размера, используя процедуру, которая вычисляет его для 12-разрядного числа в диапазоне 0-2559 с помощью процедуры:
Я бы предложил написать процедуру divmod, где MSB числа будет в W, а LSB указан FSR; процедура должна хранить частное в FSR с последующим декрементом и оставлять остаток в W. Чтобы разделить 32-битную длину на 10, можно использовать что-то вроде:
Шаг divmod-6 будет очень похожим, за исключением использования констант 85 и 6, а не 51 и 10. В любом случае, я ожидаю, что divmod10_step будет 20 циклов (плюс четыре для вызова / возврата), поэтому короткий divmod10 будет будет около 50 циклов, а длинный divmod10 будет около 100 (если один особый случай первый шаг, можно сохранить несколько циклов).
источник
это может быть не самый быстрый, но простой способ.
источник