Arduino остаток от деления

Из всех арифметических операций деление занимает особое место. По отношению к умножению деление является обратной операцией и не имеет конечной формулы для определения частного. Деление – единственная арифметическая операция ограниченной точности! Не смотря на это алгоритмы деления достаточно просты. Ниже будут показаны два таких алгоритма, которые используют только операции вычитания и сдвигов. Для того чтобы получить результат в виде целочисленных частного и остатка нужно предварительно убедиться в том, чтобы делимое было больше делителя и, конечно, исключить возникновение запрещённой операции деления на 0. При делении n-разрядного делимого на m-разрядный делитель под частное необходимо отвести n, а под остаток m разрядов.

Частным случаем является деление на целую степень 2:

Все коэффициенты xn двоичного числа X переместились на один разряд вправо (x стал при 1/2 1 , x1 стал при 2 0 и т.д.). Таким образом для деления двоичного числа на 2 n необходимо произвести сдвиг его содержимого на n разрядов в правую сторону. Так выглядит деление на 2 16-разрядного числа в регистрах R17:R16:

Обратите внимание на то, что после сдвига вправо во флаге переноса С окажется целочисленный остаток (младший коэффициент x0) от деления на 2.

Для другого частного случая деления на 3 существует один очень интересный алгоритм, основанный на разложении дроби X/3 в ряд вида:
X/3 = X/2 — X/4 + X/8 — X/16 + X/32 — …

Каждый член ряда получается делением X на целую степень 2, что как было показано выше, легко реализуется сдвиговыми операциями. Ниже приведена подпрограмма деления на 3 16-разрядного числа.

Этот пример очень эффективен. Его быстродействие ограничено только разрядностью делимого. Более того для делимого произвольной величины обрабатывается оптимальное число членов ряда (до 16), а результат автоматически округляется до ближайшего целого числа.

Естественно, что в тех случаях, когда необходимо разделить число на 6 можно совместно использовать приемы деления на 2 и 3:
X/6 = (X/2)/3 = (X >> 1)/3 = (X/3) >> 1

Для уменьшения погрешности деление чётных чисел следует начинать с деления на 2 (остаток 0) а, деление нечётных с деления на 3 (алгоритм этого вида деления учитывает остаток).

В общем случае самый естественный и простой способ разделить одно число на другое – это решить уравнение, вытекающее непосредственно из определения операции деления:
X = Z*Y + R,
R i и если X > Y*2 i , то в этом случае необходимо произвести вычитание Y*2 i из X, а соответствующий разряд zi установить в 1; если X i – вычитание пропускается и в этой итерации zi=0. Эта процедура продолжается до тех пор, пока не останется остаток Ri получаются простым сдвигом Y на i разрядов влево. Аналогично производится деление в любой позиционной системе (метод деления в столбик), но проще всего в двоичной из-за того, что в X может содержаться Y*2 i максимум один раз (на что и указывает единица в соответствующем разряде). Рассмотрим пример деления:

Необходимо обратить внимание на то, что число итераций сравнения должно совпадать с числом значащих разрядов частного (в данном случае n=4 для определения z…z3). Однако разрядность частного заранее никогда не известна и поэтому всегда необходимо знать максимально возможную разрядность результата деления. На практике чаще всего используют вычисления, в которых частное заведомо умещается в 8,16,24 бита (кратно одному байту) и т.д. При этом нужно использовать 8,16,24 итераций сравнения X с Y*2 i , соответственно. С целочисленным остатком R проблем не возникает – его размер ограничен разрядностью Y (R i (i ∈ <0,…,15>) вместо сдвига делителя Y на n разрядов вправо используется поочерёдный сдвиг делимого на n разрядов влево, а для экономии памяти частное записывается на тоже место, что и делимое. В начале программы осуществляется проверка условия Y ≠ 0, без которого деление не может быть корректно осуществлено.

Ниже приведена еще одна важная подпрограмма, реализующая деление 4-хбайтового числа на двухбайтовое с получением 16-разрядных частного и остатка. По своей структуре она аналогична предыдущей, кроме того, что при входе в подпрограмму производится проверка на переполнение результата и тем самым исключаются случаи, при которых частное может не умещаться в отведённых 2-х байтах (например, X = 0x51F356D, Y = 0x100, R = 0x6D, Z = 0x51F35 – имеет разрядность более 16 бит).

Преобразуем в строку. Часть 1. Целые числа.

Первое что приходит в голову это функция sprintf из стандартной библиотеки Си. Использовать её просто:

После чего в массиве buffer у нас лежит требуемая строка.
Но вот беда, sprintf это ведь функция форматированного вывода, которая много чего умеет и тянет за собой много другие функций стандартной библиотеки. Размер машинного кода при ее использовании увеличивается значительно. Например, даже минимальная версия sprintf из avr-libc (это то, что идет в составе WinAVR / AVR Toolchain) добавляет чуть менее 2 килобайт.

Читать еще:  Defort официальный сайт сервисный центр

2. utoa, ultoa

В состав библиотек, поставляемых с компиляторами, часто включают функции преобразования числа в строку itoa, ltoa, utoa, ultoa. Вообще эти функции не стандартные, ног часто имеются в наличии и, в отличии от sprintf, не делают ничего лишнего.

3. Извлечение цифр делением на 10.

Готовые стандартные и не очень способы посмотрели. Теперь пришло время свои велосипеды изобретать. Первый самый очевидный способ это конечно деление на 10 и вычисление остатка в цикле.

Остаток от деления выдаёт нам десятичные цифры в обратном порядке, начиная с младшего, поэтому записываем из в буфер начиная с конца, чтоб потом не разворачивать полученную строку.
Всё вроде просто красиво, ничего лишнего, но есть одно но. Собственно деление, да еще и вычисление остатка. Если в процессоре нет аппаратного деления, то это очень медленно.

4. Извлечение цифр делением на 10 с помощью функции div

Может попробовать использовать стандартную функцию div, которая возвращает сразу частное и остаток?

Но деление всё равно остается. К преимуществам этого и предыдущего метода можно отнести то, что они могут преобразовывать число в строку по любому основанию (если ёх чуть доработать), не обязательно 10.

5. Деление на 10 сдвигами и сложениями.

Если у целевого процессора нет аппаратной поддержки 32-х разрядного деления, то предыдущие два метода будут довольно медленными. Деление на 10 можно заменить на серию сдвигов и сложений. Вдохновившись книжкой «Алгоритмические трюки для программистов» (она-же «Hacker’s delight»), берём оттуда функцию деления на 10 с помощью сдвигов и сложений, заменив имеющееся там умножение на 10 (оно тоже «дорогое», на AVR по крайней мере) также сдвигами и сложениями. Модифицируем ее, чтоб она возвращала и частное и остаток:

Выглядит страшно и непонятно, но на самом деле всё просто. Сначала умножаем исходное число на 0.8 или 0.1100 1100 1100 1100 1100 1100 1100 1100 в двоичном представлении. Очень удобно, что дробь периодическая и удалось обойтись всего пятью сдвигами и четырьмя сложениями. Далее делим то, что получилось на 8, сдвигая на 3 разряда вправо. Получается исходное число делённое на 10 с точностью до единицы из-за ошибок округления. После находим остаток умножая полученное частное на 10 и вычитая его из исходного числа. Если остаток больше 9, то корректируем его и частное.
Сама функция использующее «быстрое» деление не отличается по виду от своих предшественниц.

6. Вычитание степеней 10.

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

40 байт размером. И сама функция:

Работает очень просто, пока число больше текущей степени 10 вычитаем эту степень 10 из числа и считаем сколько раз вычлось. Потом переходим на меньшую степень 10. И так пока не доберёмся до 1. Цифры получаются сразу в нужном порядке, нужно только удалить ведущие нули.

Методы на двоично-десятичных числах.

Следующие три метода основаны на операциях с упакованными двоично-десятичными числами — binary coded decimals (BCD). В этом представлении каждая тетрада (4 бита) хранит одну десятичную цифру. В 32-х разрядной переменной можно таким образом хранить 8 десятичных цифр. В двоичном представлении в 2-х разрядной переменной 10 десятичных цифр. Поэтому эти методы дают урезанные результаты для чисел больше 99999999. Двоично-десятичные числа очень легко преобразуются в строку:

Собственно из операций с BCD нам нужно сложение и умножение на 2, которое успешно заменяется сложением числа с самим собой. Поэтому нужно только сложение:

Выглядит страшно и непонятно — опять какое-то хитрое побитовое колдунство. На самом деле, чтоб сложить два BCD нужно просто сложить их как обычные двоичные числа — строчка a += b. А потом к каждой тетраде значение которой оказалось больше 9 нужно добавить корректирующее число 6 с переносом бита в старшую тетраду. И к каждой тетраде из которой был перенос бита в старшую тетраду, нужно также добавить корректирующее число 6. Все остальные строки функции — как раз эта коррекция. В первых двух строках мы определяем все биты суммы a + b + 0x66666666ul, которые изменили своё значение из-за переноса бита из младшего разряда. В третей строка складываем наши два числа. В четвёртой — выделяем младшие биты переноса для каждой тетрады. В остальных — прибавляем 6 к тем тетрадам из которых был перенос бита. Вот так вот — без единого условного перехода.

Читать еще:  1 Бухта это сколько метров

7. Сложение степеней двойки.

Первый способ, хорошо всем знакомый еще со школьных уроков информатики, — сложение десятичных представлений степеней двойки, соответствующих единичным битам в преобразуемом числе:

7. Сложение степеней двойки с таблицей.

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

Таблица содержит 30 элментов — 120 байт.

8. Horner’s method

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

Здесь уже две операции сложения BCD, но одна из них сложение с 1 и от неё одной можно избавиться.

При этом первый аргумент bcd_add может оказаться не корректным BCD, где младшая тетрада содержит цифру больше 9. Однако наша bcd_add это нормально прожевывает выдавая правильный результат. А вот если добавлять эту лишнюю единицу ко второму аргументы, то результат будет уже не правильным.
Количество итераций в цикле этого метода всегда будет равно разрядности числа, в отличии от предыдущих, где цикл закончится, как только в числе не останется единичных бит.

9. Извлечение цифр умножением на 10.

Идея заключается в том, что десятичные цифры можно извлекать со стороны старших бит числа и использовать умножение на 10 для перехода к следующему десятичному разряду. Для этого придётся представить наше двоично число как дробную часть, мысленно перенести запятую на сколько-то разрядов влево, в нашем случае это будет 27. При этом число будет состоять из 2^-27 долей. Чтоб извлекать десятичные цифры эта дробь должна состоять из каких-то десятичных долей пусть это будет 10^-9. Его нужно для этого умножить на 2^-27/10^-9 = 1.34217728. После этого биты начиная с 27 разряда будут содержать старшую десятичную цифру. Но это если исходное число было меньше 2^27. Если оно было больше, то две цифры со значением не более 31. Это надо учесть. Еще один момент — это переполнение. Начиная с чисела 3199999999 ((2^32-1) / 1.34217728) у нас будет переполнение на 1 разряд, которое тоже надо учесть. А как-же всё-таки умножить челое число на 1.34217728 и без изпользования плавающей точки? Всё так-же сдвиками и сложениями. И так вот, что получилось:

Как ни странно но это работает. Если кто-нибудь видел этот способ раньше — скажите мне, а то я могу претендовать на авторство.
Как видно при умножении пришлось использовать 40-ка битную арифметику — дополнительный байт для дробной части. Если дробную часть отбросить и использовать 32-х битную арифметику, то возникают ошибки округления, который достигают 7 для больших чисел. К сожалению в языке Си нет доступа к биту переноса и по этому перенос в/из дробной части пришлось организовывать вручную. Для эффективного использования бита переноса можно использовать ассемблерные вставки. Поскольку первая тестируемая платформа у нас будет avr-gcc, для него их и напишем, чисто ради спортивного интереса. С ними цикл умножения будет выглядеть так:

Теперь собственно та часть ради которой всё затевалось — сравнение скорости работы. Первой испытанной платформой будет будет AVR с использованием компилятора GCC.
Для методов разных типов время работы будет зависеть от разных факторов, например для методов основанных на делении на 10 время будет зависеть в большей степени от количества десятичных цифр, о есть от абсолютной величины числа и очень мало от самих этих цифр. Вычитание степеней 10 в цикле будет тем быстрее работать чем меньше сумма десятичных цифр составляющих число. То есть 1000000 обработается гораздо быстрее чем 999999. Методы основанные на двоично-десятичных числах будут быстрее работать если в исходном числе мало единичных бит — быстрее всего со степенями двойки. Время работы последнего метода будет зависеть только от абсолютной величины преобразуемого числа, но в меньшей степени чем методы с делением на 10. Итак в наборе для тестирования должны быть маленькие чила, большие числа, степени двойки, степени десяти, числа где много девяток.
Всякие тесты для AVR удобно проводить на симуляторе Simulavr — не нужно никакого железа, и многочисленных перепрошивок.
Для замера времени выполнения наших функций воспользуемся 16-ти разрядным таймером, тикающем на частоте ядра. Вывод на консоль через отладочный порт эмулятора. Оптимизация кода максимальная по скорости.
Вот что получилось в результате для 32-х разрядных чисел:

* после плюса размер зависимостей — таблицы или функции деления
** в скобках указаны результаты для варианта с ассемблерными вставками.

Читать еще:  Castorama котельники официальный сайт

Лидирует в этом бенчмарке с не большим отрывом метод на быстром делении на 10 сдвигами и сложениями. К нему близко подобралось вычитание степеней 10. Следом метод с умножением на 10. методы с честным делением (включая utoa), как и ожидалось, самые медленные, особенно тот, что использует функцию ldiv, но и самые компактные. Время выполнения метода Хорнера практически не зависит от конвертируемого числа. sprintf работает относительно быстро, по сравнению с utoa. И не удивительно — у неё внутри используется метод похожий на utoa_fast_div, но накладные на разбор форматной строки и медленный вывод в буффер через fputc дают о себе знать.

UPDATE.
Результат для 16-х разрядных чисел:

Здесь опять с заметным преимуществом лидирует быстрое деление сдвигами/сложениями. Худший результат теперь у sprintf, ведь внутри она всё равно использует 32- разрядные числа.

UPDATE #2. Результаты для MSP430.

Результаты для STM32.

Обсуждение результатов

Аутсайдером везде является функция использующая библиотечную функцию деления div. Несмотря на то, что она возвращает за один вызов и остаток и частное от деления, даже на STM32 аппаратным делением, она реализована программно и работает очень медленно. Очевидно этот способ использовать не стоит. Однако функция использующая встроенный оператор деления utoa_builtin_div, плетущаяся в конце на AVR и MSP430, на STM32 — в лидерах. Ничего удивительного, ведь в Cortex M3 есть аппаратное деление скажут многие, и будут не совсем правы — деление-то там есть, но оно не такое уж и быстрое (в скобках для utoa_builtin_div указано время, если заставить компилятор сгенерировать честное деление). Дело в том, что хитрый GCC при делении на константу использует хитрый трюк — заменяет деление на умножение на константу такую, что старшие 32 бита в 64 разрядном произведении, содержат исходное делимое, делённое на 10.

Этот код эквивалентен примерно следующему:
uint32_t tmp = value;

Такой способ тоже описан в книжке «Алгоритмические трюки для программистов». Однако на AVR и MSP430 этот номер не пройдёт — там умножение 32*32 => 64 работает неприлично долго, дольше честного деления.
Еще utoa_builtin_div всегда имеет минимальный размер.
Всегда хороший, а зачастую лучший результат даёт деление на 10 сдвигами и сложениями utoa_fast_div. Это практически безусловный лидер по скорости и часто имеет вполне скромный размер. Этот метод всегда удачный выбор.
Любимое многими вычитание степеней десяти utoa_cycle_sub по размеру вместе с таблицей примерно совпадает сutoa_fast_div, но всегда немного уступает по скорости. Вобщем, тоже не плохой выбор.
Методы основанные на двоично десятичных числах работают не очень быстро, имеют не самый маленький размер и к тому-же выдают только 8 цифр результата (в моей реализации, можно получить все 10 цифр, но будет еще медленнее). Их лучше использовать не для преобразования двоичных чисел в строки, а для преобразования двоичных чисел в упакованные двоично десятичные, для последующей работы сними.
Особняком стоит метод с умножением на 10 utoa_fract. Он не выглядит очень привлекательным по среднему времени, однако его худшее время часто оказывается меньше, чем худшее время лидеров. У этого метода разница между лучшим и худшим относительно небольшая — он работает стабильно.

UPDATE.
Нашел еще один интересный и очень быстрый метод. Вот Вот здесь.

Описание того, как это работает по ссылке выше на английском. К сожалению, корректные результаты этот метод выдаёт только для 15-ти битных значений, зато очень быстро:
для AVR лучшее время — 133 такта, худшее — 167, среднее — 146.

Coming next.

Часть 2. Фиксированная и плавающая точка.

PS. Может быть кто знает еще какие нибудь методы преобразования чисел в строку?

Ссылка на основную публикацию
Adblock
detector