Как компьютер делит числа
Обновлено: 06.07.2024
Встроенный калькулятор Windows прошел долгий путь с момента его появления в Windows 1.0 в 1985 году.
Он включает в себя различные режимы, вычисления даты и многие удобные функции для ежедневных преобразований.
Получите максимальную отдачу от часто забываемого приложения - калькулятора.
Как открыть калькулятор
Переключение между режимами калькулятора
Как вы увидите ниже, Калькулятор делает намного больше, чем прибавляет, вычитает, умножает и делит.
Вы можете выбрать один из 18 режимов, в зависимости от ваших потребностей.
Чтобы переключиться между режимами, нажмите кнопку меню в верхнем левом углу, а затем выберите режим.
Ностальгический звук вашего детства еще более успокаивает, когда он замедляется до глубокого, дзэн-подобного темпа.
Обычный режим
Стандартный режим полезен для основных математических операций, таких как добавление, вычитание, умножение и деление, а также поиск квадратных корней, вычисление процентов. Вероятно, этот режим, для большинства людей.
Инженерный режим
В дополнение к операторам стандартного режима он содержит функции типа log, modulo, exponent, тригонометрические градусы и SIN, COS и TAN.
Режим программист
Предоставляет возможность обработки данных в двоичной, восьмеричной и шестнадцатеричной системах счисления.
При работе с любой системой счисления в данном режиме под «дисплеем» показывается двоичное представление текущего результата, разделённое на тетрады.
Он также добавляет новые методы для работы с логическими операциями: Or, And, Xor, Not и бит - Lsh, Rsh, RoR и RoL
путем не сложных манипуляций в реестре, отключить рекламные приложения установленные на этой операционной системе.
Вычисление даты
Данный режим калькулятора в Windows 10 позволит вычислить количество дней между двумя конкретными датами или прибавить нужное количество лет, месяцев, дней, что бы узнать какое будет календарное число через этот период времени.
Режим преобразователь
Вот нашел нужный кулинарный рецепт, а он рассказывает про жидкие унции, вы легко с помощью встроенного калькулятора переведете в миллилитры.
Вкладка Валюта
Моментальная конвертация любых известных валют по состоянию курса текущего дня.
Деление — одна из самых дорогих операций в современных процессорах. За доказательством далеко ходить не нужно: Agner Fog[1] вещает, что на процессорах Intel / AMD мы легко можем получить Latency в 25-119 clock cycles, а reciprocal throughput — 25-120. В переводе на Русский — МЕДЛЕННО! Тем не менее, возможность избежать инструкции деления в вашем коде — есть. И в этой статье, я расскажу как это работает, в частности в современных компиляторах(они то, умеют так уже лет 20 как), а также, расскажу как полученное знание можно использовать для того чтобы сделать код лучше, быстрее, мощнее.
Собственно, я о чем: если делитель известен на этапе компиляции, есть возможность заменить целочисленное деление умножением и логическим сдвигом вправо (а иногда, можно обойтись и без него вовсе — я конечно про реализацию в Языке Программирования). Звучит весьма обнадеживающе: операция целочисленного умножения и сдвиг вправо на, например, Intel Haswell займут не более 5 clock cycles. Осталось лишь понять, как, например, выполняя целочисленное деление на 10, получить тот же результат целочисленным умножением и логическим сдвигом вправо? Ответ на этот вопрос лежит через понимание… Fixed Point Arithmetic (далее FPA). Чуть-чуть основ.
При использовании FP, экспоненту (показатель степени 2 => положение точки в двоичном представлении числа) в числе не сохраняют (в отличие от арифметики с плавающей запятой, см. IEE754), а полагают ее некой оговоренной, известной программистам величиной. Сохраняют же, только мантиссу (то, что идёт после запятой). Пример:
0.1 — в двоичной записи имеет 'бесконечное представление', что в примере выше отмечено круглыми скобками — именно эта часть будет повторяться от раза к разу, следуя друг за другом в двоичной FP записи числа 0.1.
В примере выше, если мы используем для хранения FP чисел 16-битные регистры, мы не сможем уместить FP представление числа 0.1 в такой регистр не потеряв в точности, а это в свою очередь скажется на результате всех дальнейших вычислений в которых значение этого регистра участвует.
Пусть дано 16-битное целое число A и 16-битная Fraction часть числа B. Произведение A на B результатом дает число с 16 битами в целой части и 16-тью битами в дробной части. Чтобы получить только целую часть, очевидно, нужно сдвинуть результат на 16 бит вправо.
Поздравляю, вводная часть в FPA окончена.
Формируем следующую гипотезу: для выполнения целочисленного деления на 10, нам нужно выполнить умножение Числа Делимого на FP представление числа 0.1, взять целую часть и дело в шля… минуточку… А будет ли полученный результат точным, точнее его целая часть? — Ведь, как мы помним, в памяти у нас хранится лишь приближенная версия числа 0.1. Ниже я выписал три различных представления числа 0.1: бесконечно точное представление числа 0.1, обрезанное после 16-ого бита без округления представление числа 0.1 и обрезанное после 16 ого бита с округлением вверх представление числа 0.1.
Оценим погрешности truncating представлений числа 0.1:
Чтобы результат умножения целого числа A, на Аппроксимацию числа 0.1 давал точную целую часть, нам нужно чтобы:
Удобнее использовать первое выражение: при мы всегда получим тождество (но, заметь, не все решения, что в рамках данной задачи — более чем достаточно). Решая, получаем . То есть, умножая любое 14-битное число A на truncating with rounding up представление числа 0.1, мы всегда получим точную целую часть, которую бы получили умножая бесконечно точно 0.1 на A. Но, по условию у нас умножается 16-битные число, а значит, в нашем случае ответ будет неточным и довериться простому умножению на truncating with rounding up 0.1 мы не можем. Вот если бы мы могли сохранить в FP представлении числа 0.1 не 16 бит, а, скажем 19, 20 — то все было бы ОК. И ведь можем же!
Внимательно смотрим на двоичное представление — truncating with rounding up 0.1: старшие три бита — нулевые, а значит, и никакого вклада в результат умножения не вносят (новых бит).
Следовательно, мы можем сдвинуть наше число влево на три бита, выполнить округление вверх и, выполнив умножение и логический сдвиг вправо сначала на 16, а затем на 3 (то есть, за один раз на 19 вообще говоря) — получим нужную, точную целую часть. Доказательство корректности такого '19' битного умножения аналогично предыдущему, с той лишь разницей, что для 16-битных чисел оно работает правильно. Аналогичные рассуждения верны и для чисел большей разрядности, да и не только для деления на 10.
Ранее я писал, что вообще говоря, можно обойтись и без какого-либо сдвига вовсе, ограничившись лишь умножением. Как? Ассемблер x86 / x64 на барабане:
В современных процессорах, есть команда MUL (есть еще аналоги IMUL, MULX — BMI2), которая принимая один, скажем 32 / 64 -битный параметр, способна выполнять 64 / 128 битное умножение, сохраняя результат частями в два регистра (старшие 32 / 64 бита и младшие, соответственно):
В регистре RCX пусть хранится некое целое 62-битное A, а в регистре RAX пускай хранится 64 битное FA представление truncating with rounding up числа 0.1 (заметь, никаких сдвигов влево нету). Выполнив 64-битное умножение получим, что в регистре RDX сохранятся старшие 64 бита результата, или, точнее говоря — целая часть, которая для 62 битных чисел, будет точной. То есть, сдвиг вправо (SHR, SHRX) не нужен. Наличие же такого сдвига нагружает Pipeline процессора, вне зависимости поддерживает ли он OOOE или нет: как минимум появляется лишняя зависимость в, скорее всего и без того длинной цепочке таких зависимостей (aka Dependency Chain). И вот тут, очень важно упомянуть о том, что современные компиляторы, видя выражение вида some_integer / 10 — автоматически генерируют ассемблерный код для всего диапазона чисел Делимого. То есть, если вам известно что числа у вас всегда 53-ех битные (в моей задаче именно так и было), то лишнюю инструкцию сдвига вы получите все равно. Но, теперь, когда вы понимаете как это работает, можете сами с легкостью заменить деление — умножением, не полагаясь на милость компилятору. К слову сказать, получение старших битов 64 битного произведения в C++ коде реализуется интринсиком (something like mulh), что по Asm коду, должно быть равносильно строчкам инструкции MUL выше.
Возможно, с появлением контрактов (в С++ 20 не ждем) ситуация улучшится, и в каких-то кейсах, мы сможем довериться машине! Хотя, это же С++, тут за все отвечает программист — не иначе.
Рассуждения описанные выше — применимы к любым делителям константам, ну а ниже список полезных ссылок:
Эта статья размещена в разделе практики программирования, а не в разделе для начинающих, что было бы логичнее, на первый взгляд. Но вопросы по делению, и умножению, как не странно, не редко встречаются и на серьезных форумах, причем далеко не только от новичков.
Сначала напомню, что деление на степени двойки можно заменить сдвигом делимого вправо. Например, деление на 8 равнозначно сдвигу на три разряда вправо. При этом мы можем сохранять выдвигаемые разряды в отдельной переменной, которая будет являться остатком от деления. Если у нас делитель известен на этапе написания программы мы можем сразу заменить деление на комбинацию сдвигов, вычитаний и сложений. Зачастую это будет выполняться быстрее собственно деления. Сложности начинаются тогда, когда у нас делитель становится известен только на этапе выполнения. Тут уже нужно какое то универсальное решение.
Существующие алгоритмы деления, в большинстве своем, так или иначе сводятся к привычному всем делению столбиком. Для тех, кто давно ничего не считал вручную, напомню, как это выглядит
Частное от деления равно 2301, а остаток 30. Обратите внимание, что результатом являются два числа, а не одно, как в стандартных операциях языков высокого уровня, например, С. Это бывает важно, например, при преобразованиях систем счисления (для вывода на индикатор числа в десятичном виде, например). В программе на языке С нам бы пришлось для получения частного использовать операцию "/", а для получения остатка операцию "%" (или умножение с вычитанием, что не проще). При том, что достаточно только деления. Да, проблема решается библиотечными процедурами, но они не всегда доступны, например, могут отсутствовать в бесплатной версии компилятора. Наша реализация деления позволит получать оба числа за одну операцию (за один вызов процедуры). Так что это полезно не только тем, кто пишет программы на ассемблере.
Уже сейчас можно заметить основные принципы деления столбиком. Во первых, мы начинаем со старших, самых левых, цифр делимого и двигаемся вправо, к младшим цифрам. Если очередной остаток от вычитания с очередной "снесенной" цифрой делимого меньше делителя, то в результат заносится 0 и "сносится" очередная цифра делимого. Причем частное у нас начинает получаться начиная с самой старшей, самой левой цифры. С двоичными числами все будет проще.
Деление 8 разрядных беззнаковых чисел
Частное 10 и остаток 15. Пример получился довольно коротким. Но сам принцип и основные шаги видно. И они такие же, как для десятичного деления. А вот дальше я вас немного запутаю (но потом, обязательно, распутаю). Для начала вспомним, что в этом мире все относительно и еще раз посмотрим на примеры деления. Да, делитель сдвигается вправо относительно делимого в процессе деления. Но ведь можно сказать, что делимое сдвигается влево относительно делителя. Казалось бы, какая разница? На результат это не должно влиять. Забегая вперед могу сказать, что действительно не влияет. Результат деления будет одинаков. Ну почти одинаков. Но дьявол, как известно, кроется в деталях. И это детали реализации, причем довольно важные.Давайте разбираться.
Алгоритм деления, вариант первый, сдвигаем делитель
Сначала попробуем написать алгоритм "в лоб", как обычно делят в столбик. То есть, делимое оставим на месте, а будем двигать вправо делитель.
Проверка делителя на ноль. Для этого варианта алгоритма важный шаг. Иначе программа зациклится на следующем шаге. Да и школьные правила деления говорят, что на ноль делить нельзя.
Нормализация. Именно так этот шаг алгоритма обычно называют. Дело в том, что начинать мы должны с самого старшего разряда. А это означает, что самый старший разряд делителя должен быть равным 1. Что бы достичь этого мы сдвигаем делитель влево столько раз, сколько потребуется. Но не забываем считать, сколько сдвигов сделали. Число разрядов частного будет равно числу сдвигов плюс 1. Плюс 1, так как как минимум одно вычитание (один разряд частного) будет даже при отсутствии необходимости сдвигать делитель.
Вычитание и определение значения очередного разряда частного. Вычитаем сдвинутый делитель из делимого. Если разность положительна, то есть, делимое больше делителя, то в частное вдвигаем справа единицу. При этом разность становится новым значением делимого. Если разность отрицательна, то вдвигаем в частное ноль, а делимое оставляем без изменений.
Сдвиг делителя. Сдвигаем делитель на один разряд вправо.
Проверка завершения деления. Уменьшаем на 1 счетчик вычитаний (его мы получили на первом шаге). Если он стал 0, то деление закончено. При этом делимое будет равно остатку. Если же счетчик не равен 0, то возвращаемся к шагу 3.
Вот так все просто. Нам не надо пытаться угадать, или подобрать, очередную цифру частного, что значительно усложняет алгоритмы десятичного деления. При этом цикл деления у нас будет переменной длины. Своего рода оптимизация.
Прежде, чем переходить к тексту программы нужно сказать буквально пару слов об архитектуре и системе команд MidRange PIC, что бы те, кто незнаком с этими микроконтроллерами появилась возможность уловить суть. Более подробно о системе команд MidRange PIC вы можете прочитать здесь. А особенности конкретной модели, которую собираетесь использовать, нужно искать в документации производителя.
В микроконтроллерах MidRange PIC память данных представлена виде "регистровых файлов" (терминология Microchip) разделенных на банки. При этом каждый такой регистр, или ячейка памяти данных, может быть напрямую адресована в коде команды. Углубляться в тонкости организации и управления банками памяти данных не буду, нам это почти не потребуется. В PIC нет двухадресных команд. Там, где команде требуется два операнда, неявно используется специальный рабочий регистр W (WREG), что, впрочем, часто отражается в мнемонике команды. Результат выполнения команды может, за некоторым исключением, помещаться обратно в адресуемую командой ячейку памяти или в WREG. Флаг переноса С размещен в регистре STATUS и для команды вычитания имеет инверсное значение. То есть, 1 состояние флага свидетельствует об отсутствии переноса (положительная разность), а 0 наличию переноса (отрицательная разность). При этом на флаг переноса влияет ограниченное количество команд. Команды проверки нулевого значения или знака регистра или ячейки памяти нет, но флаг Z существует. Есть и экзотические команды проверки бита и пропуска следующей команды по условию, они заменяют команды условных переходов. И удобные, но трудно воспринимаемые новичками, команды инкремента декремента с одновременной проверкой на нулевой результат, которые часто применяют для организации циклов.
А теперь, наконец, текст программы деления. Специально несколько излишне прокомментировал каждый шаг, для тех, кто не знаком с микроконтроллером.
В начале программы размещены используемые параметры и рабочие переменные. Что бы не возиться с банками памяти они размещены в разделяемой между всеми банками области. Такое есть в некоторых моделях. Сама процедура размещается в секции Division и называется Udiv8x8. Процедура полностью рабочая и занимает в памяти программ 29 слов (по 14 разрядов, такова организация памяти программ). Кроме того, использовано 5 байт в памяти данных.
Давайте попробуем оценить быстродействие, то есть, количество машинных циклов для выполнения деления. Почти все команды, за исключением команд передачи управления, которым нужно два цикла, выполняются за один машинный цикл. Команды btfsc и btfss выполняются за один или два цикла, в зависимости от значения проверяемого бита. Команда decfsz выполняется за один или два цикла, в зависимости от равенства нулю своего операнда после выполнения декремента. При этом будем считать, что делитель не равен нулю, так иначе нам не интересен результат.
Поскольку у нас количество итераций цикла переменное, то точное быстродействие подсчитать не просто. Проверка делителя займет 3 машинных цикла. Нормализация может выполняться от 3, когда старший бит делителя равен единице, до 52 циклов, когда делитель равен 1. Первый шаг и начальная инициализация переменных выполнятся за 5 циклов в любом случае. Остальные шаги выполнятся за 9 или 11 циклов на каждую итерацию цикла. Например, для нашего примера деления 185 на 17 потребуется 4 итерации. И завершающая часть программы, вместе с инструкцией возврата, потребует 5 циклов. Получается, что в лучшем случае потребуется примерно 25 машинных циклов, а в худшем примерно 137. Не очень быстро. И занимает довольно много места в памяти программ. Чем больше в делителе значащих разрядов, тем быстрее выполняется деление.
Алгоритм деления, вариант второй, сдвигаем делимое
А теперь попробуем пойти по менее очевидному пути, сдвигать не делитель, а делимое. Причем всегда будем выполнять 8 итераций цикла, по одной на каждый бит. При этом у нас автоматически получится обработка начиная со старших разрядов, а остаток будет сразу формироваться на нужном месте, как и частное. Да еще и проверка делителя на нулевое значение не потребуется, так как это не приведет к неработоспособности алгоритма
Устанавливаем значение счетчика циклов равное количеству разрядов делимого, то есть 8, в нашем случае.
Сдвигаем содержимое делимого влево, вдвигая выдвигаемый старший разряд в остаток.
Вычитаем делитель из остатка. Фактически, это вычитание из старших разрядов делимого, которые мы постепенно перемещаем на место остатка. Как и в первом варианте алгоритма, если разность положительна, то мы вдвигаем в частное слева единицу, а разность помещаем на место остатка, замещая таким образом обработанные разряды делимого. Если разность отрицательна, то в частное слева вдвигаем ноль, а значение остатка оставляем без изменений.
Уменьшаем на единицу счетчик итераций цикла. Если он стал равен нулю, деление закончено. При этом и остаток, и частное уже на своих местах. Если счетчик еще не нулевой, то возвращаемся к шагу 2.
Наконец, текст программы.
В памяти данных занято по прежнему 5 байт. А вот сама процедура занимает только 15 слов. В два раза меньше! Посмотрим на быстродействие. Первый шаг всегда выполняется за 2 машинных цикла. На каждую итерацию цикла потребуется 11 или 13 машинных циклов. И два цикла на команду возврата. В худшем случае все потребуется 108 циклов, а в лучшем 92. А что насчет обработки ошибок? Если делитель равен нулю, то получим частное 255 и остаток равный делителю, что и позволит сделать вывод об ошибке.
Небольшой промежуточный итог
Можно подвести итоги. Второй вариант алгоритма занимает в два раза меньше места в памяти программ и быстрее первого в худшем случае. Зато гораздо медленнее в лучшем случае. В среднем, первый вариант алгоритма потребует порядка 80 машинных цикла, а второй около 100. Какой вариант лучше? Решать вам. Если критично занимаемое кодом место, то однозначно второй. А вот выбор по быстродействию не так прост и сильно зависит от обрабатываемых чисел. Большей частью от делителя. При критичности быстродействия имеет смысл попробовать оба варианта в реальных ситуациях и выбрать лучший.
А теперь, как и обещал, я вас распутаю. На самом деле эти два варианта абсолютно одинаково выполняют само деление. Сам цикл деления (шаги с 3 по 5) в первом варианте занимает 15 команд, как и во втором варианте. Оставшиеся 14 команд это проверка делителя на 0, обработка ошибки и нормализация. Только в первом варианте основной цикл выполняется от 1 до 8 раз, а во втором варианте всегда 8.
Так что алгоритм деления один, различаются только детали его реализации. Причем эти детали зависят от архитектуры процессора, в нашем случае, микроконтроллера. Например, в Extended MidRange PIC (не PIC18) есть команды сложения и вычитания с учетом переноса и арифметические сдвиги. А в PIC18 команды проверки условия и двухадресная команда пересылки. Поэтому различие двух вариантов реализации может быть как очень сильным, так и совсем незначительным.
В первом приближении можно считать первый вариант реализации попыткой оптимизации времени выполнения за счет увеличения длины программы. А второй вариант оптимизацией по размеру за счет увеличения времени выполнения.
А что она счет большей разрядности?
Я не ставлю целью статьи описание всех возможных ситуаций. Да и готовой универсальной библиотеки не будет. Но, пожалуй, затрону вопрос деления 16-разрядного числа на 8 разрядное. Необходимость в этом встречается не так редко. Но буду рассматривать только второй вариант реализации алгоритма, то есть, со сдвигом делимого.
На шаге 3 появилась проверка выхода остатка за границу байта, это можно определить по состоянию флага переноса, куда выдвигается старший разряд. А обработка этого случая выполняется на шаге 3а. Не смотря на то, что операция вычитания не учитывает выход уменьшаемого (остатка) за границу байта, ее результат будет правильным в пределах байта. Можете проверить сами. А вот знак разности будет ошибочным, что мы и исправляем принудительной установкой флага переноса. Размер программы увеличился незначительно. Увеличился и занимаемый размер памяти данных, что естественно.
А как быть с числами со знаком?
Числа со знаком, обычно, обрабатывают как числа без знака. При этом для отрицательных значений меняется знак (берется модуль числа). Как сменить знак числа, если немного забыли, можно почитать в упоминавшейся в начале статье о простых типах данных. Частное от деления знаковых чисел будет положительно, если делимое и делитель имеют одинаковые знаки. Иначе, частное будет отрицательно, то есть, ему придется еще раз сменить знак после деления (мы же делили числа без знака, то есть, положительные). Остаток всегда будет иметь знак делимого. И для отрицательного делимого знак остатка тоже придется подкорректировать.
Заключение
Деление считается самой сложной операцией из четырех арифметических. И в виде готовой команды микроконтроллера оно встречается реже всего. Но программная реализация оказалась вовсе не такой страшной, хотя и очень медленной по сравнению с аппаратно реализованными командами. Для деления на известные на этапе написания программы константы лучше использовать комбинации сдвигов/вычитаний/сложений. Увеличение разрядности делимого не вызывает особых проблем и не ведет к резкому увеличению размера программ. Увеличение разрядности делителя гораздо серьезнее, но непреодолимых трудностей тоже нет. Если же требуется делить числа с разрядностью многократно превышающей разрядность микроконтроллера, то действительно имеет смысл задуматься о его замене на более подходящий.
В 8 разрядных PIC команды деления нет, значит оно выполняется только программно. Как мы видели, при этом получается и частное, и остаток. Но в этой реализации остаток предпочитают получать еще раз, причем через умножение! Замечу, что команда умножения есть не во всех 8 разрядных PIC. Я не буду называть компилятор и его производителя. Но замечу, что это коммерческий компилятор, и совсем не дешевый. Поэтому, знать описанные в этой статье алгоритмы деления может быть полезно даже в том случае, если Вы используете другие контроллеры и всегда пишете программы только на языках высокого уровня.
Здравствуйте. Если вы собираетесь изучить язык программирования python или любой другой язык, Вам необходимо знать, как компьютер хранит и обрабатывает числа. В привычной для нас системе исчисления десять знаков от 0 до 9, и называется она десятичной. А почему именно десять цифр? Видимо потому, что первобытные люди, которые изобрели эту систему, пользовались для счета пальцами рук.
Существует так же восьмиричная система исчисления. Она имеет только восемь цифр от 0 до 7. Есть еще и шестнадцатиричная система исчисления. В ней используются шестнадцать цифр. Для обозначения первых десяти цифр применяются цифры от 0 до 10, а недостающие шесть цифр дополняют буквами A, B, C, D, E, F. Но мы на них останавливаться не будем.
Сегодня поговорим о двоичной системе исчисления. Для записи любого числа используются две цифры 0 и 1. Процессор компьютера состоит из миллиардов маленьких транзисторов, которые имеют состояние логического нуля 0 – когда напряжение на выходе отсутствует, и состояние логической единицы 1 – когда на выходе присутствует напряжение. Компьютеру удобно использовать данную систему.
В привычной для нас десятичной системе, если нам нужно записать число меньше десяти, мы используем всего одну цифру. Для записи числа от 10 и 99, мы вводим новый разряд, который сначала мы приравниваем единице. Подставляя в младший разряд те же цифры от 0 до 9, после 9 опять идет 0 и мы получаем новый десяток. Когда во втором разряде мы дойдем до 99, вводим третий разряд от 100 до 999, потом четвертый, пятый и т. д.
В двоичной системе действует то же правило, только для записи числа используются две цифры 0 и 1. Поэтому, при увеличении на один, после 1 снова идёт 0, и при этом вводим следующий разряд. В двоичной системе числа от 0 до 10 выглядят так: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001.
Для выполнения операций над числами компьютер:
Переводит число из десятичной системы в двоичную;
выполняет необходимые операции (например, сложение);
результат обратно переводит в десятичную систему и выдает нам.
Давайте рассмотрим несколько примеров как можно число из десятичной системы исчисления, перевести в двоичную систему исчисления:
Возьмем число 123 и воспользуемся методом последовательным делением на число 2
Читайте также: