Как получить остаток огромного числа?
Но у меня есть ограничение в 1 секунду, а подобная итерация огромных чисел занимает больше.
Поэтому я вывел «формулу», что если N — четное число, то остаток 0, а если нечетное, то остаток — среднее число, которое вроде как можно получить разделив N на 2.
Но то как я написал это работает не так, и выводит слишком большое число, код:
Так вот вопрос:
Как я могу по-другому быстро получить остаток от деления с такими огромными числами как 10¹⁰⁰ и подобными?
Большие числа на C99: операция деления с остатком
Уже достаточно большое количество статей на сайте было посвящено разработке библиотеки big_int, предназначенной для работы с большими числами. Таковыми я называю целые неотрицательные числа формально неограниченного размера. Наиболее распространённое название таких чисел — длинные целые. А операции с такими числами называют, обычно, длинной арифметикой.
Я насчитал шесть таких статей. Привожу ссылки на них: первая, вторая, третья, четвёртая, пятая, шестая. Из четырёх основных арифметических операций пока реализованы три: сложение, умножение, вычитание. Возможность деления одних больших чисел на другие до сих пор отсутствует, хотя определённые шаги в направлении её появления уже предпринимались: были написаны функции, осуществляющие «неполноценное» деление, в котором в качестве делителей могли использоваться лишь степени числа 2.
И вот, наконец, дошли руки до деления. Сразу скажу, что, поскольку рассматриваемая нами арифметика — целочисленная, речь будет идти только о делении с остатком одних больших чисел на другие. Результатом такой операции будут 2 числа: так называемое «частичное частное» (т. е. целая часть от «обычного» частного) и остаток. Но других частных мы рассматривать не будем, поэтому, говоря в этой статье о частном, всегда будем понимать под этим именно «частичное частное».
Кстати, при реализации деления с остатком мы будем активно использовать написанную ранее функцию division2pow(), осуществляющую деление на степени двойки.
Ну что ж, приступим!
Построение алгоритма
Операция деления в нашем исполнении будет принципиально отличаться от остальных трёх арифметических операций. Чтобы объяснить отличие, обратимся к выполнению арифметических операций «в столбик», знакомому каждому из нас.
В чём заключается суть деления в столбик? Мы подбираем десятичные цифры в записи частного в направлении слева направо. Пусть, например, нам нужно разделить число 987654 на 123. Для начала необходимо подобрать такое однозначное положительное число k, которое удовлетворяет неравенствам
123 k ≤ 987 < 123 (k + 1).
Как только мы найдём k, так сразу же, тем самым, установим первую цифру в записи частного. Предположим, что интуиция подсказала нам, что k = 7. Найдём разность:
987 — 123 · 7 = 987 — 861 = 126.
Но 126 > 123, из чего можно сделать вывод о том, что мы ошиблись, и в действительности k = 8.
Таким образом, мы подбираем цифры частного методом «проб и ошибок». В этом и заключается отличие деления от остальных операций, в которых не нужно ничего подбирать. Например, при выполнении умножения в столбик достаточно знать таблицы сложения и умножения однозначных чисел. Эти таблицы избавляют нас от всякого «угадывания», а в случае деления аналогичных таблиц нет.
В нашем случае реализации деления на компьютере тоже будет иметь место некий «подбор», но об этом чуть позже.
Теперь давайте сформулируем метод получения частного и остатка при делении одного натурального числа m на другое натуральное число n. Он будет опираться, как раз, на деление в столбик, но в нём будет больше «свободы».
- Шаг 1. Полагаем: p = 0, q = m.
- Шаг 2. Если q < n, то заканчиваем работу.
- Шаг 3. Подбираем положительное число r, удовлетворяющее неравенству nr ≤ q.
- Шаг 4. Полагаем: p = p + r, q = q — nr, после чего переходим к шагу 2.
В результате выполнения этого алгоритма в переменной p будет находиться частное, а в q — остаток от деления. Заметим, что в ходе выполнения алгоритма значение p постепенно увеличивается, приближаясь к частному, а значение q — наоборот, уменьшается, приближаясь к остатку. Таким образом, данный метод можно назвать «методом последовательных приближений».
Ясно, что на 3-ем шаге число r можно подбирать достаточно произвольно (в рамках сформулированных в 3-м шаге условий, разумеется). В случае деления в столбик такой «свободы выбора» нет. Необходимость последовательного нахождения цифр в десятичной записи частного накладывает на r дополнительные ограничения: каждый раз r должно быть наибольшим из чисел вида 10 s k, где k — натуральное однозначное число, а s — целое.
Но нас такие ограничения не волнуют. Разумеется, от выбора r на каждой итерации зависит количество итераций. Чем произведение n r каждый раз ближе к q, тем лучше. От этого и будем отталкиваться.
Итак, как мы будем выбирать r? Вот тут-то нам и пригодится умение делить произвольные числа на степени числа 2. Начнём с того, что если число n окажется представимым в виде степени числа 2, то деление мы выполнять не будем, а «делегируем» его уже упоминавшейся выше функции division2pow().
А если n не является степенью двойки, то округлим его сверху до ближайшей степени числа 2. Другими словами, подберём такое число t, которое удовлетворяет неравенству
2 t — 1 < n < 2 t .
Несложно заметить, что t — это число знаков, требующихся для двоичной записи числа n.
Так вот, возвращаемся к выбору r. В качестве r на каждой итерации будем брать [q / 2 t ] (квадратные скобки означают целую часть числа, в них заключённого). И в этом случае будем использовать имеющуюся у нас возможность деления на степени двойки.
Легко показать, что число r, выбираемое таким способом, всегда будет удовлетворять неравенству n r ≤ q. Однако тут мы сталкиваемся с небольшой проблемой. Как только значение q станет меньше, чем 2 t , или, что то же самое, количество знаков в двоичной записи q станет меньше, чем t, так сразу же r, вычисленное по формуле r = [q / 2 t ], обратится в 0. Но ведь при этом всё ещё возможна ситуация, при которой q ≥ n, т. е. в качестве r можно было бы взять единицу (но не число, превышающее 1, ибо равенство q ≥ 2n невозможно)!
Проблема решается весьма просто. Как только перестанет выполняться неравенство q ≥ 2 t , так сразу же прекращаем итерации и выясняем, выполняется ли неравенство q < n. Если да, то заканчиваем работу. А если нет, то увеличиваем значение p на 1, а значение q уменьшаем на n, после чего также завершаем работу.
А теперь давайте рассмотрим получившийся в результате алгоритм, который мы и будем реализовывать в дальнейшем. Напомню, что мы делим m на n и предполагаем, что n не совпадает со степенью двойки, а количество знаков в двоичной записи n равно t.
- Шаг 1. Полагаем: p = 0, q = m.
- Шаг 2. Если q < 2 t , то переходим к шагу 4.
- Шаг 3. Полагаем: r = [q / 2 t ], p = p + r, q = q — nr, после чего переходим к шагу 2.
- Шаг 4. Если q ≥ n, то полагаем: p = p + 1, q = q — n.
- Шаг 5. Завершаем работу.
Как и ранее, после завершения работы алгоритма в переменных p и q будут содержаться частное и остаток от деления соответственно.
А теперь переходим к программированию. Но начнём мы с создания двух вспомогательных функций.
Вспомогательная функция from_byte()
Нередко при работе с большими числами возникает необходимость создать объекты типа big_int , содержащие числа байтового размера, например, 0 (чаще всего) или 1. Можно создавать такие числа через функцию create() , но для этого предварительно нужно объявить и инициализировать переменную, чей адрес затем передать функции create() . Ноль, например, можно создать так:
Это не очень удобно.
Второй вариант — использовать одну из функций dcreate() или hcreate() :
Этот вариант тоже не очень хорош, поскольку приходится привлекать и обрабатывать текстовый формат, без посредничества которого хотелось бы обойтись.
Так что я решил создать новую функцию from_byte() , которую можно вызвать так:
Прототип функции помещаем в заголовочный файл big_int.h:
Функция принимает в качестве параметра целочисленное значение байтового размера, после чего динамически создаёт большое число, равное этому значению. Функция возвращает адрес построенного объекта.
Вот её код, который мы вставляем в файл big_int.c:
Полагаю, что код понятен без комментариев.
В функции division2pow() нулевые большие числа создавались с помощью функции create() . После написания функции from_byte() я внёс изменения в division2pow() , заменив фрагменты кода, генерирующие нулевые числа посредством вызовов create() , фрагментами, в которых для создания таких чисел вызывается функция from_byte() .
Вспомогательная функция simple_division2pow()
Функция simple_division2pow() — это упрощённая версия функции division2pow(). Можно было без неё обойтись, но я решил, что лучше будет её создать.
На шаге 3 нашего алгоритма выполняется целочисленное деление на 2 t . Его можно выполнить, вызвав функцию division2pow() . Но у данного подхода есть два недостатка.
Во-первых, из division2pow() вызывается функция count_bits() для нахождения числа знаков, использующихся в двоичной записи делимого. Но на тот момент, когда нам понадобится выполнить целочисленное деление на степень двойки, это число знаков уже будет получено вызовом той же самой функции count_bits() . Так что последняя функция будет вызываться дважды для одного и того же числа.
Чтобы избежать этого, в функцию simple_division2pow() мы будем передавать количество бит, требующихся для хранения делимого, в виде параметра.
Во-вторых, возможности функции division2pow() по нахождению остатка от деления нам не нужны. Оговорюсь, что все действия, связанные с вычислением остатка в этой функции выполняются только при условии, что остаток необходимо найти (напомню, что о такой необходимости свидетельствует ненулевой адрес, переданный функции в качестве 3-го параметра). Тем не менее, лучше всё, что связано с нахождением остатка, из функции убрать.
Указанные изменения привели к созданию функции simple_division2pow() , имеющей следующий код.
Функция simple_division2pow() выполняет целочисленное деление большого числа на число, представимое в виде целой неотрицательной степени числа 2. Результат формируется динамически в виде объекта типа big_int . Функция возвращает адрес этого объекта.
Смысл формальных параметров следующий:
- bi — указатель на переменную типа big_int , содержащую делимое;
- power — степень, при возведении в которую числа 2 получается делитель;
- count — количество знаков, использующихся при двоичной записи делимого (или, что то же самое, число битов, необходимых для хранения делимого).
Код комментировать не буду, поскольку он получен сокращением подробно прокомментированного кода функции division2pow().
Прототип функции simple_division2pow() помещать в заголовочный файл big_int.h не будем, поскольку не предполагаются непосредственные вызовы этой функции пользователями библиотеки big_int. Код функции simple_division2pow() будет, как обычно, располагаться в файле big_int.c.
Деление с остатком: функция division()
Подходим к описанию ключевой функции нашей статьи — division() . Вот её прототип, помещаемый в файл big_int.h:
Функция пытается выполнить деление с остатком одного большого числа на другое. В случае неудачи, т. е. нулевого делителя, функция возвращает нулевой адрес. В противном случае она возвращает адрес динамически сформированного частного. Что касается остатка, то он возвращается через третий формальный параметр функции (при условии, что остаток требуется коду, вызвавшему функцию).
Ниже приведён список формальных параметров функции division() :
- bi1 — указатель на переменную типа big_int , содержащую делимое;
- bi2 — указатель на переменную типа big_int , содержащую делитель;
- remainder — указатель на переменную типа big_int * . Если его значение отлично от нуля, то по адресу, содержащемуся в remainder , функция division() записывает адрес динамически сформированной переменной типа big_int , содержащей остаток от деления. В противном случае эта переменная уничтожается и пользователь функции после окончания её работы получает доступ только к частному, но не к остатку.
Таким образом, если пользователя функции не интересует остаток от деления, он должен в качестве третьего фактического аргумента передать ей нулевой адрес. Если же остаток пользователю нужен, он должен заранее объявить указатель на переменную типа big_int и адрес этого указателя передать функции division() третьим аргументом. Тогда по окончании работы функции в этом указателе окажется адрес переменной big_int , содержащей остаток.
А вот и код функции division() , который должен находиться в файле big_int.c:
Сначала мы сохраняем значения полей объектов, адресуемых указателями bi1 и bi2 , в отдельных переменных для упрощения доступа к этим значениям (стр. 3, 4). Далее выясняем, равен ли делитель нулю (стр. 5). Если равен, то сразу возвращаем нулевой адрес и прекращаем работу (стр. 6).
Сохраняем в переменной count2 количество битов, необходимых для хранения делителя (стр. 7).
В строках с 8-й по 22-ю мы выясняем, не представим ли делитель в виде степени числа 2; если представим, то делегируем всю работу по делению с остатком функции division2pow() . Теперь более подробно.
Если делитель представим в указанном виде, то его старший байт содержит число 2 r где r — номер первого ненулевого бита (биты байта нумеруем справа налево, начиная с нуля). Зная количество знаков делителя, найти r несложно: мы делаем это в строках 8-10 и записываем результат в переменную r .
Далее проверяем этот старший байт на совпадение его значения с 2 r (стр. 11). Если совпадает, то остальные байты проверяем на равенство нулю. Для этого перебираем их в цикле for (стр. 14-19). Как только очередной байт оказывается отличным от 0, так сразу же присваиваем переменной zero , изначально содержащей единицу, ненулевое значение и прерываем цикл (стр. 17, 18).
Если после завершения цикла (неважно, по какой причине), значение zero остаётся равным единице, т. е. делитель оказывается представимым в виде степени двойки, то вызываем функцию division2pow() , передавая ей в качестве фактических аргументов адрес делимого, степень, в которую нужно возвести 2, чтобы получить делитель, и значение параметра remainder . Результат, возвращённый division2pow() , (т. е. адрес частного) тут же возвращаем из функции division() и прекращаем работу (см. стр. 20-21).
Таким образом, реализация нашего алгоритма начинается только со строки 23. Создаём копию делимого и сохраняем её адрес в переменной rem (стр. 23). Создаём нулевое большое число и его адрес помещаем в переменную quot (стр. 24). Теперь значения, содержащиеся в переменных, адресуемых rem и quot , будут постепенно приближаться к результатам — остатку и частному соответственно. Будем, в дальнейшем, называть значения этих переменных, являющихся аналогами переменных q и p нашего алгоритма, «текущим остатком» и «текущим частным».
Записываем в count1 количество битов делимого (стр. 25) и переходим к циклу while . Итерации цикла выполняются до тех пор, пока количество битов текущего остатка превышает количество битов делителя (см. стр. 26).
Тело цикла (стр. 27-33) соответствует шагу 3 алгоритма. Увеличиваем значение переменной, адресуемой quot , на частное от деления текущего остатка на число 2, возведённое в степень, совпадающую с количеством битов делителя (см стр. 28-29). Уменьшаем текущий остаток на произведение упомянутого частного и делителя (стр. 30). Обновляем значение счётчика битов текущего остатка (стр. 32).
После окончания цикла пытаемся вычесть делитель из текущего остатка с помощью функции deduct() (стр. 34). Эта функция, в случае успеха, записывает результат вычитания в переменную, в момент вызова содержащую уменьшаемое, и возвращает адрес этой переменной. В случае неуспеха, т. е. в случае, если вычитаемое больше уменьшаемого, функция возвращает ноль. Так что мы проверяем возвращенный результат на неравенство нулю (стр. 34); если он нулю не равен, то увеличиваем текущее частное на единицу (стр. 35-39).
А что, если результат равен нулю? Это означает, что после окончания цикла текущие частное и остаток уже совпадают с окончательными частным и остатком соответственно, и никаких дополнительных операций производить не требуется.
Выясняем, нужен коду, вызвавшему функцию division() , остаток, т. е. отлично ли от нуля значение переменной remainder (стр. 40). Если да, то сохраняем адрес объекта, содержащего остаток, по адресу, содержащемуся в remainder (стр. 41). А если нет, то удаляем этот объект (см. стр. 42, 43).
Остаётся лишь вернуть из функции адрес переменной, содержащей частное (стр. 44).
Деление с остатком: функция divide()
Как мы помним, каждой реализованной нами арифметической операции соответствуют две функции. Не будет исключением и операция деления с остатком. Для функции division() парной будет функция divide() . Вот её прототип, который мы помещаем в файл big_int.h:
Отличие функции divide() от division() заключается в том, что первая, в отличие от второй, помещает частное от деления в переменную, на момент вызова функции divide() содержащую делимое. Адрес этой переменной, т. е. значение формального параметра bi1 и возвращается функцией divide() в качестве результата (при условии, разумеется, что делитель отличен от 0; в противном случае функция возвращает нулевой адрес).
Смысл формальных параметров функции divide() — тот же, что и функции division() .
Вот код функции divide() , помещаемый в файл big_int.c:
Код очень простой: сначала выполняем само деление с остатком, вызывая функцию division() , а потом помещаем полученное частное в переменную, адресуемую указателем bi1 . Полагаю, что этого комментария достаточно, тем более что ранее мы уже неоднократно создавали функции аналогичного типа (при реализации других арифметических операций с большими числами).
Тестирующая программа
Протестируем функции, описанные в этой статье. Для этого создадим файл test.c, к которому подключим заголовочный файл библиотеки big_int с помощью директивы #include . Поместим в файл 2 функции: gets_s() , отвечающую за чтение строк с консоли, и main() , непосредственно выполняющую тестирование.
Содержимое файла test.c приведено ниже.
Тестирующая программа работает по традиционной схеме, уже неоднократно использовавшейся нами при тестировании других функций библиотеки big_int. Пользователю предлагается ввести на консоль сначала делимое, затем — делитель. Если операнды введены корректно, то далее программы вычисляет частное и остаток и выводит их на консоль. Помимо этого, программа осуществляет самоконтроль: перемножает частное и делитель, после чего добавляет к произведению остаток, предоставляя пользователю возможность убедиться в том, что результат совпадает с делимым.
После выполнения деления и проверки результатов программа предлагает пользователю вести очередную пару чисел. Работа программы завершается лишь после того, как вместо делимого пользователь введёт символ ‘q’ . Разумеется, пользователь может ввести этот символ и сразу же после запуска программы. Тогда программа завершится, не выполнив ни одного деления.
Из 4-х описанных в статье функций непосредственно из main() вызывается только одна из них — функция divide() . Однако и оставшиеся 3 функции тоже не останутся непротестированными, поскольку функция division() вызывается из divide() , а функции from_byte() и simple_division2pow() — из division() .
Подробно комментировать содержимое файла test.c я не буду, поскольку код функции main() достаточно прост, а функции gets_s() даже была посвящена отдельная статья.
В результате выполнения программы может состояться, например, следующий диалог с пользователем:
Здесь мы протестировали также случаи, когда делитель представим в виде степени числа 2, предложив программе разделить 123456789 на 4096 (т. е. 2 12 ), и 1234567 на 1 (т. е. 2 0 ). Мы знаем, что в таких случаях из division() вызывается функция division2pow() . Как мы видим, оба раза операции деления с остатком были выполнены корректно.
Заключение
Реализовать операцию деления с остатком для больших чисел оказалось достаточно просто. Но это благодаря тому, что ранее уже была реализована операция деления с остатком на числа, представимые в виде степени числа 2, т. е. создана функция division2pow() . Она, напомню, вызывается из функции division() , написанию которой, в первую очередь, и посвящена данная статья. А вот построение функции division2pow() было весьма непростым. По сути, большая часть работы по реализации деления с остатком была проделана именно в ходе создания division2pow() .
Итак, теперь все 4 основные арифметические операции над большими числами реализованы. Тем самым завершён важный этап в развитии библиотеки big_int.
Остаток от деления числа в большой степени
Как можно быстро вычислить (x^n)mod y. Уже когда-то копал этот вопрос и обнаружил теорему Эйлера (теория чисел).
Не относится к вопросу: Но вся проблема в том, что я учусь в школе, и мы не проходили еще подобных выражений, найденных мною на wiki, и теории чисел. Объясните пожалуйста:
- Как использовать эту теорему на практике(например, реализация на C).
- (Не так важно, но просто интересно)Кратко значение формулировки на
wiki. Буду рад какой-нибудь статье, etc для тех, кто еще не знаком с теорией чисел и математикой >9 классов.
Наприклад ми хочемо обчислити 7 222 (mod 10). Маємо, що 7 і 10 є взаємно простими і φ(10) = 4 . Одже згідно з теоремою Ейлера 7 4 ≡ 1 (mod 10) і як наслідок
7 222 ≡ 7 4×55 + 2 ≡ (7 4 ) 55 x 7 2 ≡ 1 55 x 7 2 ≡ 49 ≡ 9 (mod 10).
Моя попытка перевода:
Например мы хотим вычислить "7 222 (mod 10)". 7 и 10 являются взаимно-простыми и φ(10) = 4 (это число натуральных чисел не больших чем 10 и являющихся взаимнопростыми по отношению к 10 . Это следующие числа: 1,3,7,9 и всего их 4 ).
Следовательно согласно теореме Эйлера 7 4 ≡ 1 (mod 10) и как следствие:
7 222 ≡ 7 4×55 + 2 ≡ (7 4 ) 55 x 7 2 ≡ 1 55 x 7 2 ≡ 49 ≡ 9 (mod 10).
Следствия из теоремы:
если a φ(n) ≡ 1 (mod n), то и (a φ(n) ) k ≡ 1 (mod n) для любого положительного k , т.к.
(a φ(n) ) k ≡ a φ(n) mod n * (a φ(n) ) k — 1 mod n ≡ (a φ(n) ) k — 1 (mod n) и т.д.
теория-чисел — Поиск остатка при делении большого числа.
Достаточно найти остатки от деления на 16, 5 и 11 по отдельности. Начнём с последнего: остаток от деления на 11 равен 0.
Теперь по модулю 5: мы заменяем 77 на 2 по этому модулю, и достаточно знать остаток для показателя степени от деления на ф(5)=4. Здесь очевидно, что показатель делится на большую степень двойки. Значит, по модулю 4 от равен 0, и тогда наше число сравнимо с 2^0=1 по модулю 5.
Теперь по модулю 16 заменяем 77 на 13. У показателя надо знать остаток от деления на ф(16)=8. Здесь также понятно, что он равен нулю. Поскольку 13 взаимно просто с 16, по теореме Эйлера 13^<ф(16)>=1. Но показатель делится на 8=ф(16), и 13^<8m>=1 mod 16. Таким образом, при делении на 16 остаток нашего числа равен 1.
Если x — число в ответе, то x-1 делится на 16 и на 5, то есть делится на 80. То есть x=80q+1 для некоторого q. Нам нужно, чтобы это число делилось на 11. Решая линейное уравнение по модулю 11, или просто подбором, выясняем, что подходит x=561. Это ответ.
