3.4 «MOD»: БИНАРНАЯ ОПЕРАЦИЯ

Если тип — целые положительные числа, то частное от деления на равно Полезно обзавестись достаточно простым обозначением и для остатка от этого деления — обозначим его через Основная формула

позволяет выразить в виде Это можно распространить на целые отрицательные числа, а фактически — на произвольные вещественные числа:

Тем самым оказывается бинарной операцией точно так же, как являются бинарными операции сложения и вычитания. Неформально математики издавна использовали понятие вычисляя разные величины по модулю 10, по модулю и т.п., но оно утвердилось лишь в последние двадцать лет формально. Понятие — старое, обозначение — новое.

Когда х и у — вещественные положительные числа, смысл х mod у можно легко уловить интуитивно. Вообразим себя бегущими по кругу с длиной окружности у, точкам которой приписаны вещественные числа из интервала Если, взяв старт в точке 0, пробежать некоторое расстояние х по окружности, мы остановимся в точке . (А пока мы бегаем, точка 0 встретится нам раз.)

Когда же х или у отрицательны, нужно внимательно вникнуть в определение, с тем чтобы точно выяснить, что в этом

случае означает Вот некоторые примеры с целыми х и у:

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

А как насчет ? Определение (3.21) оставляет этот вопрос открытым, с тем чтобы избежать деления на нуль, но для полноты можно положить

Подобное соглашение сохраняет свойство всегда отличаться от х на величину, кратную у. (Может показаться более естественным сделать эту функцию непрерывной в 0, полагая . Однако в гл. 4 увидим, что это сделало бы ее менее полезной. Непрерывность — не самая важная сторона операции

Мы уже сталкивались с одним замаскированным частным случаем операции когда записывали число х в виде суммы его целой и дробной частей: Дробная часть может быть записана также как потому что

Обратите внимание, что в этой формуле круглые скобки не нужны: считается, что знак связывает операнды сильнее, чем знаки сложения или вычитания.

При определении операции использовалась функция пол, в то время как функция потолок не удостоилась равного внимания. Быть может, стоило бы воспользоваться функцией потолок для определения аналога операции типа операции

(mumble — нечто невразумительное. — Ред.), в случае нашей аналогии с кругом это соответствует расстоянию, которое нужно добежать бегуну, преодолевшему расстояние х, чтобы попасть в исходную точку 0. Конечно же, необходимо более подходящее название, нежели ‘mumble’. Но нашлось бы подходящее приложение — наверняка найдется и соответствующее название.

Самым важным алгебраическим свойством операции является распределительный закон:

при любых вещественных с, х и у. (Те, кто предпочитает, чтобы знак mod связывал операнды слабее, чем знак умножения, могут и здесь убрать круглые скобки в правой части.) Этот закон легко получается из определения (3.21), так как

если (случаи с нулевыми модулями тривиальны). Четыре предыдущих примера с ±5 и ±3 дважды иллюстрируют этот закон при Тождество типа (3.23) действует успокаивающе, ибо оно позволяет надеяться, что операция определена надлежащим образом.

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

Предположим, например, что мы располагаем короткими строками текста которые хотелось бы разместить в колонках. По эстетическим соображениям желательно, чтобы по высоте эти колонки располагались в убывающем порядке (фактически — в невозрастающем порядке), причем высота колонок должна быть примерно одинаковой — никакие две колонки не должны отличаться друг от друга более чем на одну строку текста. Если 37 строк текста разбиваются на пять колонок, то предпочтительно такое их размещение, как справа:

К тому же желательно распределить строки по колонкам следующим образом: вначале решается, сколько строк войдет в первую колонку, затем мы переходим ко второй, третьей и так далее — ведь именно таков порядок чтения. Распределение строк текста ряд за рядом обеспечило бы нас требуемым числом строк в каждой колонке, однако порядок их чтения оказался бы нарушенным. (Мы получили бы нечто подобное размещению справа, но в 1-й колонке оказались бы строки 1, 6, 11, ..., 36 вместо строк 2, 3,..., 8.)

Хотя план размещения ряд-за-рядом неприемлем, он позволяет выяснить, сколько строк поместится в каждой колонке. Если

не кратно то в процессе размещения ряд-за-рядом выясняется, что удлиненные колонки должны вмещать а укороченные строк каждая; в результате будет ровно удлиненных колонок (и, как выясняется, ровно n mumble m укороченных).

Теперь обобщим терминологию и поговорим о ‘предметах’ и ‘группах’ вместо ‘строк’ и ‘колонок’. Только что мы выяснили, что первая группа должна вмещать предметов; следовательно, можно попробовать следующую схему последовательного распределения: для распределения предметов по группам при поместить предметов в одну группу, а затем рекурсивно применить ту же самую процедуру для того, чтобы разместить оставшихся предметов в прочих группах.

К примеру, если то распределение происходит по такой схеме:

Схема работает — мы получаем группы практически неизменного размера, несмотря на то, что делитель изменяется.

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

Сколько же предметов окажется в группе? Для ответа на этот вопрос нам нужна формула, которая бы давала при в противном случае. Нетрудно убедиться, что требуемым условиям удовлетворяет формула

поскольку она сводится к если, как и в предыдущем абзаце, записать в виде (здесь ). Получаем, что если

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

Это тождество справедливо при любом целом положительном и при любом целом (положительном, отрицательном или равном нулю). Мы уже сталкивались со случаем в (3.17), правда, записанном в несколько ином виде:

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

Тождества (3.25) и (3.24) можно обращать одно в другое, пользуясь либо соотношением либо тождеством из упр. 12.

Теперь, если в (3.25) заменить на и применить правило (3.11) для удаления полов внутри полов, то получится тождество, которое справедливо при любом вещественном

Это до некоторой степени удивительный результат, ибо функция пол является целочисленной аппроксимацией вещественнозначной величины — тем не менее, отдельное приближение слева равняется сумме их целой компании справа. Если считать, что — это, грубо говоря, в среднем, то левая часть, грубо говоря, равна примерно - в то время как правая часть — это приблизительно

Но сумма всех этих грубых приближений оказывается величиной точной!