Деление на два
В математике деление на два, деление пополам — это математическая операция[1], частный случай деления. Древние египтяне отличали деление на два от деления на другие числа, поскольку их алгоритм умножения использовал деление на два как один из промежуточных этапов[2]. В XVI веке некоторые математики предложили рассматривать деление на два как операцию, отличающуюся от деления на другие числа[3][4]. В современном программировании также иногда выделяют деление именно на два[5].
Достаточно простой алгоритм деления на два действует в системах счисления с чётным основанием (в частности, в десятичной и двоичной).
Двоичная система счисления править
В двоичной арифметике деление на два выполняется с помощью сдвига битов: операции, которая сдвигает число на одну позицию вправо. Такой способ вычисления позволяет снизить стоимость операций. Например, число (запись « » означает число в двоичной системе счисления), равное числу 105 в десятичной системе счисления, можно разделить на два. Для этого сдвинем все разряды вправо на 1 разряд. Получится число (52 в десятичной системе). При делении методом сдвига битов единица в младшем разряде исчезает.
Точно так же выполняется деление на число 2k (k - натуральное); для его выполнения нужно сдвинуть разряды на k позиций. Поскольку сдвиги битов часто выполняются намного быстрее, чем деление, замена деления на сдвиги оптимизирует программу[5]. Однако подобная оптимизация может помешать совместимости и навредить читаемости кода, поэтому часто нужно использовать именно деление (а не сдвиг) и доверять операции компилятору[6].
Операция деления на 2k в Common Lisp выглядит так:
(setq number #b1101001) ; #b1101001 — 105
(ash number -1) ; #b0110100 — 105 >> 1 ⇒ 52
(ash number -4) ; #b0000110 — 105 >> 4 ≡ 105 / 2⁴ ⇒ 6
Сдвиг битов вправо на 1 позицию разделит число на два, однако результат при таком способе всегда будет округляться вниз (например, 3/2 = 1, а остаток 1 пропадает). В некоторых языках округление происходит не всегда вниз, а так, чтобы число было ближе к нулю (если число отрицательное, то это будет означать округление вверх). Например, в Java -3/2 должно привести к ответу-1.
Если же воспользоваться методам сдвига битов, то получится ответ, равный-2. Таким образом, в этом случае компилятор не может заменить деление на 2 сдвигом битов.
Двоичная система счисления (числа с плавающей запятой) править
В двоичной системе при работе с числами с плавающей запятой деление на два можно выполнить, уменьшив показатель степени на единицу (до тех пор, пока результат не будет являться денормализованным числом). Во многих языках есть функции, которые позволяют разделить число с плавающей запятой на два. Например, в языке программирования Java есть метод java.lang.Math.scalb, выполняющий подобные действия[7], в языке C можно выполнить эти операции с помощью функции ldexp[8].
Десятичная система счисления править
В десятичной системе есть алгоритм, позволяющий разделить число на 2.
Алгоритм можно перестроить так, что он будет действовать и при делении чисел на 2 в любой другой системе с чётным основанием.
Итак, пусть есть число N, которое нужно разделить на два.
- Нужно записать N и приписать слева от него 0.
- Затем нужно просмотреть всевозможные пары соседних чисел и по таблице сопоставить двум соседним цифрам новую.
| Первая цифра | чётная | чётная | чётная | чётная | чётная | нечётная | нечётная | нечётная | нечётная | нечётная |
|---|---|---|---|---|---|---|---|---|---|---|
| Вторая цифра | 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.
Результат равен 869.
При использовании алгоритма надо помнить, что 0 — чётное число.
Если последняя цифра числа N нечётная, к результату алгоритма нужно прибавить 0,5.
См. также править
Примечания править
- ↑ Robert Steele. The Earliest Arithmetics in English: Edited with Introduction (Classic Reprint). — Fb&c Limited, 2018-02-07. — 114 с. — ISBN 9780656047598. Архивировано 21 февраля 2019 года.
- ↑ Jean-Luc Chabert. A History of Algorithms: From the Pebble to the Microchip. — Springer Berlin Heidelberg, 1999-08-20. — 524 с. — ISBN 9783540633693. Архивировано 21 февраля 2019 года.
- ↑ Lambert Lincoln Jackson. The educational significance of sixteenth century arithmetic from the point of view of the present time. — Teachers college, Columbia university, 1906. — 238 с. Архивировано 21 февраля 2019 года.
- ↑ E. G. R. Waters. A Fifteenth Century French Algorism from Liége (англ.) // Isis. — 1929-5. — Vol. 12, iss. 2. — P. 194–236. — ISSN 1545-6994 0021-1753, 1545-6994. — doi:10.1086/346408. Архивировано 22 февраля 2019 года.
- ↑ 1 2 Kevin R. Wadleigh, Isom L. Crawford. Software Optimization for High-performance Computing. — Prentice Hall Professional, 2000. — 414 с. — ISBN 9780130170088. Архивировано 21 февраля 2019 года.
- ↑ Brian Hook. Write Portable Code: An Introduction to Developing Software for Multiple Platforms. — No Starch Press, 2005. — 274 с. — ISBN 9781593270568. Архивировано 21 февраля 2019 года.
- ↑ Элиот Гарольд. Часть 2. Числа с плавающей точкой. www.ibm.com (7 июля 2010). Дата обращения: 27 августа 2019. Архивировано 27 августа 2019 года.
- ↑ Поисов Дмитрий Александрович, Поисова Ирина Андреевна. ldexp, ldexpf, ldexpl – функции языка Си. "Все о Hi-Tech". all-ht.ru. Дата обращения: 27 августа 2019. Архивировано 13 сентября 2019 года.