Кто писал длинную арифметику - подскажите по умножению и делению
Что-то не могу найти, есть ли алгоритмы эффективнее наивного деления?Есть, но для их использования надо прекратить изобретать велосипед.
Есть много оптимизаций по работе с памятью напрямую (замена определенного байта, смещение байт, etc)
Статьи на Hacker's Delight в помощь.
И да, я в курсе реализаций BigInteger в до-диез/BouncyCastle или BIGNUM в OpenSSL
иногда перетащить чужое гораздо сложнее, чем сделать своё.
Но только не в случае качественной длинной арифметики.
GMP — хороший вариант с точки зрения "меньше тащить чужого/качественно сделано".
В данном случае я считаю тащить gmp не целесообразным.
вот кратко про алгоритмы.
И исходники гмп как референс имплементации нужного.
/*mini-gmp.h + mini-gmp.cpp ~ 90 кб. Тащить несцелесообразно, окок.*/
Ну тогда И исходники гмп как референс имплементации нужного.
/*mini-gmp.h + mini-gmp.cpp ~ 90 кб. Тащить несцелесообразно, окок.*/
иногда перетащить чужое гораздо сложнее, чем сделать своё.Так говорят все велосипедисты.
может ему гнутое нельзя использовать
Собственно, вопрос был про алгоритмы, а не про то, откуда можно стянуть рабочее.
методы нашёл, тему можно закрыть.
За ссылку спасибо.
Modern computer arithmetic тоже примерно вся про это, если понадобятся детали.
Стырь из Питона же имплементацию всей этой хрени. Оно под BSD даже и весьма оптимизировано.
весьма оптимизированои наверное именно поэтому использует GMP/MPIR при их наличии?
Оставить комментарий
yolki
Наивное умножение сделал, Карацубу тоже. что-то более сложное типа ШШ городить смысла нет, у меня числа не такие большие.Наивное деление сделал.
Что-то не могу найти, есть ли алгоритмы эффективнее наивного деления?
Есть ли методы нахождения остатка ( оператор % более эффективные, чем наивное деление?