произведение чисел порядка 10^9 по модулю

[miramentis]

Столкнулся с задачей вычисления произведения двух разных чисел a,b по модулю n(не обязательно простому):
10^9 < a,b <= n.
Собственно, простой вариант:

c=(a*b)%n;

(еще раз замечу, что всегда a,b <= n)
не подходит, ибо, при a,b > 4.294967296*10^9, произведение a*b >2^64.
Подскажите, пожалуйста, как реализовать подобную операцию.
Естественно, чем быстрее она будет выполняться, тем лучше.
Заранее спасибо всем откликнувшимся!

P.S. не уверен, что правильно выбрал раздел(раздела с общими вопросами по программированию, не привязанными к конкретному языку, увы, не нашел), так что скажите, пожалуйста, если тему стоит перенести в другой раздел.

[-glykaman-]

Сообщение от miramentis

Столкнулся с задачей вычисления произведения двух разных чисел a,b по модулю n(не обязательно простому):
10^9 < a,b <= n.
Собственно, простой вариант:

c=(a*b)%n;

(еще раз замечу, что всегда a,b <= n)
не подходит, ибо, при a,b > 4.294967296*10^9, произведение a*b >2^64.

Может я чего-то не понял, но посути проблема лишь в том что результат умножения a и b выходит слишком большой и выходит за пределы вашего числового типа? В противном случае я не вижу проблем почему при а*b= 2^64 нельзя сделать операцию вычисления остатка.

[UaKot]

Сообщение от miramentis

Столкнулся с задачей вычисления произведения двух разных чисел a,b по модулю n(не обязательно простому):
10^9 < a,b <= n.
Собственно, простой вариант:

c=(a*b)%n;

(еще раз замечу, что всегда a,b <= n)
не подходит, ибо, при a,b > 4.294967296*10^9, произведение a*b >2^64.
Подскажите, пожалуйста, как реализовать подобную операцию.
Естественно, чем быстрее она будет выполняться, тем лучше.
Заранее спасибо всем откликнувшимся!

P.S. не уверен, что правильно выбрал раздел(раздела с общими вопросами по программированию, не привязанными к конкретному языку, увы, не нашел), так что скажите, пожалуйста, если тему стоит перенести в другой раздел.

Если не ошибаюсь, то ((a mod n)*(b mod n)) mod n = (a*b) mod n. Так не должно быть переполнения... ну еще же есть навалом алгоритмов длинной арифметики

[Somebody]

Сообщение от UaKot

Если не ошибаюсь, то ((a mod n)*(b mod n)) mod n = (a*b) mod n. Так не должно быть переполнения...

Тут a,b <= n, так что a mod n = a, b mod n = b.

[miramentis]

Сообщение от -glykaman-

Может я чего-то не понял, но посути проблема лишь в том что результат умножения a и b выходит слишком большой и выходит за пределы вашего числового типа?

именно это я и имел ввиду, говоря, что

не подходит, ибо, при a,b > 4.294967296*10^9, произведение a*b >2^64.

[miramentis]

Сообщение от UaKot

ну еще же есть навалом алгоритмов длинной арифметики

не могли бы вы оставить тут один из них.
сам, к сожалению, не нашел, иначе не писал бы здесь

[-glykaman-]

Сообщение от miramentis

не могли бы вы оставить тут один из них.
сам, к сожалению, не нашел, иначе не писал бы здесь

Скажите что за язык и система разработки - может хватит просто стандартных типов большего объема? long double например.

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

[UaKot]

Сообщение от miramentis

не могли бы вы оставить тут один из них.
сам, к сожалению, не нашел, иначе не писал бы здесь

Готовые алгоритмы на С++:
http://cppalgo.blogspot.ru/2010/05/blog-post.html

Здесь тоже есть решение и можно протестировать, но здесь заранее гарантируется, что делитель вмещается в целочисленный тип..

Можно вообще на джаве) Там встроенный тип длинных чисел есть

[miramentis]

Сообщение от UaKot

Готовые алгоритмы на С++:
http://cppalgo.blogspot.ru/2010/05/blog-post.html

Здесь тоже есть решение и можно протестировать, но здесь заранее гарантируется, что делитель вмещается в целочисленный тип..

спасибо за ссылки, почитаю на досуге.

[miramentis]

Сообщение от -glykaman-

Скажите что за язык и система разработки - может хватит просто стандартных типов большего объема? long double например.

Сообщение от UaKot

Можно вообще на джаве) Там встроенный тип длинных чисел есть

необходим был именно алгоритм. я специально не стал размещать вопрос в разделе по конкретному языку.