Деление на два

В математике деление на два, деление пополам — это математическая операция[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, которое нужно разделить на два.

  1. Нужно записать N и приписать слева от него 0.
  2. Затем нужно просмотреть всевозможные пары соседних чисел и по таблице сопоставить двум соседним цифрам новую.
Первая цифра чётная чётная чётная чётная чётная нечётная нечётная нечётная нечётная нечётная
Вторая цифра 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.

См. также

Примечания
  1. Robert Steele. The Earliest Arithmetics in English: Edited with Introduction (Classic Reprint). — Fb&c Limited, 2018-02-07. — 114 с. — ISBN 9780656047598.
  2. Jean-Luc Chabert. A History of Algorithms: From the Pebble to the Microchip. — Springer Berlin Heidelberg, 1999-08-20. — 524 с. — ISBN 9783540633693.
  3. 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 с.
  4. 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.
  5. Kevin R. Wadleigh, Isom L. Crawford. Software Optimization for High-performance Computing. — Prentice Hall Professional, 2000. — 414 с. — ISBN 9780130170088.
  6. Brian Hook. Write Portable Code: An Introduction to Developing Software for Multiple Platforms. — No Starch Press, 2005. — 274 с. — ISBN 9781593270568.
  7. Элиот Гарольд. Часть 2. Числа с плавающей точкой. www.ibm.com (7 июля 2010). Дата обращения: 27 августа 2019.
  8. Поисов Дмитрий Александрович, Поисова Ирина Андреевна. ldexp, ldexpf, ldexpl – функции языка Си. "Все о Hi-Tech". all-ht.ru. Дата обращения: 27 августа 2019.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.