Деление на два
В математике два на пополам или посредничеством также называется димидиацией или . деление [1] Трактовка этой операции как операции, отличной от умножения и деления на другие числа, восходит к древним египтянам, чей алгоритм умножения использовал деление на два в качестве одного из своих основных этапов. [2] Некоторые математики еще в шестнадцатом веке продолжали рассматривать разделение пополам как отдельную операцию. [3] [4] его часто продолжают рассматривать отдельно и в современном компьютерном программировании . [5] Выполнить эту операцию просто в десятичной арифметике , в двоичной системе счисления, используемой в компьютерном программировании, и в других четных системах счисления . Чтобы разделить нечетное число на 2, используйте математическое решение ((N-1)÷2)+0,5. Например, если N=7, то ((7-1)÷2)+0,5=3,5, поэтому 7÷2=3,5.
Двоичный
[ редактировать ]В двоичной арифметике деление на два можно выполнить с помощью операции сдвига битов , которая сдвигает цифру на единицу вправо. Это форма оптимизации снижения прочности . Например, 1101001 в двоичном формате (десятичное число 105), сдвинутое на одну позицию вправо, равно 110100 (десятичное число 52): младший бит, 1, удаляется. Аналогично, деление на любую степень двойки 2 к позиций вправо может быть выполнено путем смещения k . Поскольку сдвиг битов часто выполняется гораздо быстрее, чем деление, замена деления на сдвиг таким образом может оказаться полезным шагом в оптимизации программы . [5] Однако ради переносимости и удобства чтения программного обеспечения часто лучше писать программы, используя операцию деления, и доверять компилятору выполнение этой замены. [6] Пример из Common Lisp :
(setq number #b1101001) ; #b1101001 — 105
(ash number -1) ; #b0110100 — 105 >> 1 ⇒ 52
(ash number -4) ; #b0000110 — 105 >> 4 ≡ 105 / 2⁴ ⇒ 6
Однако приведенные выше утверждения не всегда верны при делении со знаком двоичных чисел . Сдвиг вправо на 1 бит приведет к делению на два с всегда округлением в меньшую сторону. Однако в некоторых языках деление двоичных чисел со знаком округляется в сторону 0 (что, если результат отрицательный, означает округление в большую сторону). Например, Java является одним из таких языков: в Java -3 / 2 оценивается как -1, тогда как -3 >> 1 оценивается как -2. Таким образом, в этом случае компилятор не может оптимизировать деление на два, заменяя его битовым сдвигом, когда дивиденд может быть отрицательным.
Двоичная с плавающей запятой
[ редактировать ]В двоичной арифметике с плавающей запятой деление на два можно выполнить, уменьшив показатель степени на единицу (при условии, что результат не является субнормальным числом ). Многие языки программирования предоставляют функции, которые можно использовать для деления числа с плавающей запятой на степень двойки. Например, язык программирования Java предоставляет метод java.lang.Math.scalb для масштабирования в степени двойки, [7] а язык программирования C предоставляет функцию ldexp с той же целью. [8]
Десятичный
[ редактировать ]Следующий алгоритм предназначен для десятичных чисел. Однако его можно использовать в качестве модели для построения алгоритма взятия половины любого числа N в любом четном основании.
- Выпишите N , поставив слева от него ноль.
- Переберите цифры N в перекрывающихся парах, записывая цифры результата из следующей таблицы.
| Если первая цифра | Даже | Даже | Даже | Даже | Даже | Странный | Странный | Странный | Странный | Странный |
|---|---|---|---|---|---|---|---|---|---|---|
| И вторая цифра | 0 или 1 | 2 или 3 | 4 или 5 | 6 или 7 | 8 или 9 | 0 или 1 | 2 или 3 | 4 или 5 | 6 или 7 | 8 или 9 |
| Писать | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Пример: 1738/2=?
Напишите 01738. Теперь будем работать над поиском результата.
- 01: четная цифра, за которой следует 1, запишите 0.
- 17: нечетная цифра, за которой следует 7, напишите 8.
- 73: нечетная цифра, за которой следует 3, напишите 6.
- 38: нечетная цифра, за которой следует 8, напишите 9.
Результат: 0869.
Из примера видно, что 0 четно .
Если последняя цифра числа N нечетная , к результату следует добавить 0,5.
См. также
[ редактировать ]- Половина
- Медиана — значение, которое делит набор значений данных на два равных подмножества.
- Биссекция — разделение геометрического объекта на две равные половины.
- Димидиация — геральдический метод соединения двух гербов путем разделения их изображений пополам.
Ссылки
[ редактировать ]- ^ Стил, Роберт (1922), Самая ранняя арифметика на английском языке , Общество ранних английских текстов, том. 118, Издательство Оксфордского университета, с. 82 .
- ^ Шабер, Жан-Люк; Барбин, Эвелин (1999), История алгоритмов: от камешка до микрочипа , Springer-Verlag, стр. 16, ISBN 978-3-540-63369-3 .
- ^ Джексон, Ламберт Линкольн (1906), Образовательное значение арифметики шестнадцатого века с точки зрения настоящего времени , Вклад в образование, том. 8, Колумбийский университет, с. 76 .
- ^ Уотерс, EGR (1929), «Французский алгоритм пятнадцатого века из Льежа», Isis , 12 (2): 194–236, doi : 10.1086/346408 , JSTOR 224785 , S2CID 144157808 .
- ↑ Перейти обратно: Перейти обратно: а б Уодли, Кевин Р.; Кроуфорд, Исом Л. (2000), Оптимизация программного обеспечения для высокопроизводительных вычислений , Prentice Hall, стр. 92 , ISBN 978-0-13-017008-8 .
- ^ Хук, Брайан (2005), Написание переносимого кода: введение в разработку программного обеспечения для нескольких платформ , No Starch Press, стр. 133, ISBN 978-1-59327-056-8 .
- ^ "Матем.скальб" . Стандарт платформы Java, ред. 6 . Проверено 11 октября 2009 г.
- ^ Языки программирования — C, международный стандарт ISO/IEC 9899:1999 , раздел 7.12.6.6.