Если простое решение не годится, то можно немного его усложнить...
А что если создать новый тип (что-то вроде BigNum) заданный как массив чисел (каждый элемент задает один разряд числа), определить для него операцию возведения в степень, вычитания и сравнения (поразрядного). Тогда ты возводишь 240 в степень 109, а затем вычитаешь 1008 до тех пор, пока результат не будет меньше 1008. Полученный результат и будет искомым значением, которое тебе необходимо получить...
В принципе, если слишком трудно определить операцию возведения в степень, то можно ее определить через умножение... а умножение через сложение...
Я как-то давно делал что-то подобное... Попробуй, если есть желание - в принципе, результат должен быть корректным...
остаток от деления очень больших чисел
Код: Выделить всё
my $num = 240;
my $power = 109;
my $mod = 1008;
my $rest = 1;
for (my $i = 0; $i < $power; $i++) {
$rest = $rest * $num;
$rest = $rest % $mod;
}
print $rest;
Аднака длинная арифметика здесь не покатит =)) 1008 отнимать от числа порядка 10^259 будешь до посинения или до позеления, эт уж как повезет =). Решение действительно тривиально, его привел chur. Основывается на том, что если (A конгруэнтно B по модулю T) и (C конгруэнтно D по модулю T), то (AС конгруэнтно BD по модулю С),
в данном случае используется ((A === B (mod C)) <=> (A*A === A*B (mod C))). Фактичекски, все что требуется - это 109 раз умножать 240 и если результат при умножении больше 1008, брать по модулю(это проверять не обязательно кстати, сразу брать по модулю
)
А вообще говоря, если бы надо было бы возводить не в 109 степень, а скажем в 1'000'000'000-ую, тогда это делать нужно проще. Кол-во остатков от деления на 1008 - фиксировано(их 1008), каждый следующий остаток зависит от предыдущего, отсюда получаем, что остатки будут зацикливаться(причем обычно намного раньше, чем 1008). Достаточно найти этот цикл и его длинну, ну а сам остаток найти - дело техники(его индекс в массиве цикла будет равен степени по модулю длинны цикла или около того
). Но тут также есть несколько подводных камней, которые нужно учитывать(вроде ро-зацикливания, или получение ряда нулей в остатках начиная с какой-то степени)
в данном случае используется ((A === B (mod C)) <=> (A*A === A*B (mod C))). Фактичекски, все что требуется - это 109 раз умножать 240 и если результат при умножении больше 1008, брать по модулю(это проверять не обязательно кстати, сразу брать по модулю
)А вообще говоря, если бы надо было бы возводить не в 109 степень, а скажем в 1'000'000'000-ую, тогда это делать нужно проще. Кол-во остатков от деления на 1008 - фиксировано(их 1008), каждый следующий остаток зависит от предыдущего, отсюда получаем, что остатки будут зацикливаться(причем обычно намного раньше, чем 1008). Достаточно найти этот цикл и его длинну, ну а сам остаток найти - дело техники(его индекс в массиве цикла будет равен степени по модулю длинны цикла или около того
). Но тут также есть несколько подводных камней, которые нужно учитывать(вроде ро-зацикливания, или получение ряда нулей в остатках начиная с какой-то степени)-
®B!N
- Сообщения: 19
- Зарегистрирован: 10 мар 2005, 20:52
- Откуда: Ужгород, Украина
- Контактная информация:
дам дельный совет! такая операция используется в реализации алгоритма RSA, так что советую посмотреть ее... Думаю, там это реализовано само правильно и само быстро, потому что используются очень большие числа. Удачи!
А если просто 2 больших числа от которых надо найти остаток от деления, например:
123456789123456789123456789123456789123456789 % 987654321987654321987654321987654321987654321
каким алгоритмом лучше воспользоватся в этой ситуации?
123456789123456789123456789123456789123456789 % 987654321987654321987654321987654321987654321
каким алгоритмом лучше воспользоватся в этой ситуации?