для вывода графика целочисленной функции, значения которой находятся в диапазоне от imin до imax, и хотите, чтобы крайними значениями по оси ординат были наименьшие кратные 10 числа, включающие imin и imax. Эти крайние значения равны (дай+ 10)* 10 и

((/max+ 9)+ 10)* 10, если воспользоваться "модульным" делением или делением с округлением к меньшему значению. Если же использовать обычное деление, вам придется писать код наподобие следующего:

if (imin >= 0) gmin = (imin/10) *10 ,-

else gmin = ((imin - 9)/10)*10;

if (imax >= 0) gmax = ((imax + 9)/l0)*10;

else gmax = (imax/10)*10;

Помимо того что "модульное" деление и деление с округлением к меньшему значению практичнее деления с отсечением, следует отметить, что неотрицательный остаток от деления требуется, пожалуй, чаще, чем остаток, который может принимать отрицательные значения.

Сделать выбор между "модульным" делением и делением с округлением к меньшему значению непросто, поскольку они отличаются только в случае отрицательного делителя, что встречается довольно редко. Обращение к существующим языкам программирования высокого уровня в этой ситуации не поможет, поскольку практически везде деление знаковых целых чисел х/у означает деление с отсечением. Некоторые языки программирования при делении целых чисел возвращают число с плавающей точкой, т.е. рациональное. Ничуть не проще ситуация с остатками от деления. В Fortran 90 функция MOD дает остаток от деления с отсечением, а функция MODULO - остаток от деления с округлением к меньшему значению (который может быть отрицательным). Аналогично в Common Lisp и ADA функция REM дает остаток от деления с отсечением, а MOD - остаток от деления с округлением к меньшему значению. В PL/I значение MOD неотрицательно (остаток от модульного деления). В Pascal операция А mod в определена только для в > о, а ее результат всегда неотрицателен (т.е. это остаток от модульного деления либо от деления с округлением к меньшему значению).

Как бы то ни было, мы не можем изменить мир, даже если бы и хотели это сделать, так что далее, следуя за большинством, будем использовать обычное (отсекающее) определение деления х+у.

Самое ценное свойство отсекающего деления заключается в том, что для dO выполняются следующие соотношения:

(-и)+ t/ = n + (-t/) = -(« + £/).

Однако к подобным преобразованиям в программах следует подходить осторожно, так как если п или d представляют собой наибольшее (по модулю) отрицательное число, то -и или ~d не могут быть представлены 32 битами. Операция (-2")+(-1) вызывает переполнение (результат не может быть представлен в виде знаковой величины в дополнительном коде), и на большинстве компьютеров результат окажется неопределенным либо операция - невыполненной.

Впрочем, некоторые пытаются. Язык IBM PL.8 использует модульное деление, а команда деления в машине Кнута MMIX использует деление с округлением к меньшему значению [48].

Знаковое целое (отсекающее) деление связано с обычным рациональным делением следующим соотношением:

n + t/:

V/d\

tattidQ,nd>0\ если d*0,nd<0.

Беззнаковое целое деление, т.е. деление, при котором и п и d рассматриваются как беззнаковые целые числа, удовлетворяет верхней части (1).

В дальнейшем рассмотрении темы используется ряд элементарных арифметических свойств, которые приводятся здесь без доказательства. Функции, возвращающие наибольшее целое число, меньшее данного (floor - "пол"), и наименьшее, большее данного (ceil - "потолок"), подробно описаны в [18, 38].

Теорема D1. Для действительного х и целого к справедливы следующие соотношения:

w=-r-i

x-l<[xJSx [xj<x<[xj + l хгк<\ х\>к х>к=>\ х\>к x<:k=[x\<,kz х<к + \ х<к<А\ х\<к

x<\x\<x + l

\х-\-\<х\х-]

х<к<\х\<к

х<к\х\<к

x>k=>\x\-S.kzx>k-l

х>к<А\х\>к

Теорема D2. Для целых п и d(d>0) справедливы соотношения:

npud<0 справедливы соотношения

Теорема D3. Для действительного х и целого d? справедливы соотношения [lx]/d\ = lx/d] и \lx-]/d]=lx/d].

Следствие. Для действительных чисел а иЬ (Ь) и целого dfiOсправедливы соотношения

Теорема D4. Для целых nud (d;) и действительного х справедливы соотношения

9.1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

в приведенной ниже теореме rem(«,<i) обозначает остаток от деления п на d. Для о

рицательных значений d действует следующее определение: rem(n,-t/) = rem(n,</), как

случае деления с отсечением и модульного деления. При л<0 функция K.m{n,d) не ис

пользуется (таким образом, при нашем использовании данной функции efe значения все гда неотрицательны).

Теорема D5. Для п>0 и d справедливы соотношения:

2Km{n,d) или ,„ , ,

2гет(«.)-И « rem(2n + U) =

Km{2n,d) =

(причем каждое из значений больше или равно О и меньше \d ).

2rem(n,t/) + l или 2Tzm{n,d)-\d\ + l

Теорема D6. Для п>0 и d справедливо соотношение:

rem(2n,2rf) = 2rem(n,t/).

Теоремы D5 и D6 легко доказываются исходя из базового определения остатка, т.е. что для некоторого целого q он удовлетворяет соотношению

n=qd + Km(n,d), О й rem(n,t/) < \d\,

где nSO и dO (п и d могуг быть не целыми, однако будем применять наши теоремы только к целым числам).

9.2. Деление больших чисел

Как и в случае умножения, деление больших чисел можно осуществить традиционным школьным способом "в столбик". Однако детали реализации такого метода на удивление сложны. В листинге 9.1 приведен алгоритм Кнута [39, раздел 4.3.1], реализован-

ный на языке С. В его основе лежит беззнаковое деление типа 32+16 =* 32 (на самом деле частное при такой операции деления имеет длину не более 17 бит).

Листинг 9.1. Беззнаковое деление больших целых чисел

int divmnu(unsigned short q[], unsigned short r[], const unsigned short u[], const unsigned short v[], int m, int n)

const unsigned b = 65536; Основание чисел (16 битов)

unsigned short *un, *vn; Нормализованный вид u и v

unsigned qhat; Предполагаемая цифра частного

unsigned rhat; Остаток

unsigned p; Произведение двух цифр

int s, i, j, t, k;

if (m < n I I n <= 0 I I v[n-l] == 0)

return i; Возвращается при некорректном параметре if (n == 1) Частный случай делителя из одной цифры

к = 0;

for (j = m - 1; j >= 0; j--)