Кто писал длинную арифметику - подскажите по умножению и делению

yolki

Наивное умножение сделал, Карацубу тоже. что-то более сложное типа ШШ городить смысла нет, у меня числа не такие большие.
Наивное деление сделал.
Что-то не могу найти, есть ли алгоритмы эффективнее наивного деления?
Есть ли методы нахождения остатка ( оператор % более эффективные, чем наивное деление?

Anturag

Что-то не могу найти, есть ли алгоритмы эффективнее наивного деления?
Есть, но для их использования надо прекратить изобретать велосипед.

kedr1983

Побаяню: Если делитель известен, то эффективней умножать на обратное число от делителя.
Есть много оптимизаций по работе с памятью напрямую (замена определенного байта, смещение байт, etc)
Статьи на Hacker's Delight в помощь.

yolki

иногда перетащить чужое гораздо сложнее, чем сделать своё.
И да, я в курсе реализаций BigInteger в до-диез/BouncyCastle или BIGNUM в OpenSSL

domovoj

иногда перетащить чужое гораздо сложнее, чем сделать своё.

Но только не в случае качественной длинной арифметики.
GMP — хороший вариант с точки зрения "меньше тащить чужого/качественно сделано".

yolki

В данном случае я считаю тащить gmp не целесообразным.

domovoj

Ну тогда вот кратко про алгоритмы.
И исходники гмп как референс имплементации нужного.
/*mini-gmp.h + mini-gmp.cpp ~ 90 кб. Тащить несцелесообразно, окок.*/

Papazyan

иногда перетащить чужое гораздо сложнее, чем сделать своё.
Так говорят все велосипедисты.

elenangel

может ему гнутое нельзя использовать

yolki

во-первых с++. во-вторых - да, гнутое нельзя.
Собственно, вопрос был про алгоритмы, а не про то, откуда можно стянуть рабочее.
методы нашёл, тему можно закрыть.

yolki

За ссылку спасибо.

domovoj

Modern computer arithmetic тоже примерно вся про это, если понадобятся детали.

bleyman

Стырь из Питона же имплементацию всей этой хрени. Оно под BSD даже и весьма оптимизировано.

ava3443

весьма оптимизировано
и наверное именно поэтому использует GMP/MPIR при их наличии?
Оставить комментарий
Имя или ник:
Комментарий: