Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 10 ] |
|
Автор | Сообщение | |
---|---|---|
3axap |
|
|
https://hal.archives-ouvertes.fr/hal-02070778/document |
||
Вернуться к началу | ||
s_e_r_g |
|
|
По ссылке очень много букв
Не могли бы вы на пальцах обьяснить, чем оно отличается от например алгоритма умножения Карацубы ? |
||
Вернуться к началу | ||
3axap |
|
|
Заявленная скорость выше.
|
||
Вернуться к началу | ||
swan |
|
|
3axap писал(а): Прежде, чем применить, хотел бы поинтересоваться: то-нибудь знаком, насколько этот алгоритм достоверный? Простите, а где бы вы хотели его применить? Этот алгоритм превосходит классический способ только для ОЧЕНЬ больших чисел |
||
Вернуться к началу | ||
3axap |
|
|
swan
Насколько больших? У меня в одной из программ поиска совершенного кубоида, к примеру, числа от 60 десятичных разрядов и более постоянно изменяются и перемножаются. Если даже разница при однократном перемножении будет неуловима, то при многократном переборе это должно же дать какой-то выигрыш по времени? Вот ещё чего нашёл: https://habr.com/ru/post/451860/ http://users.math-cs.spbu.ru/~okhotin/t ... 019_l7.pdf http://kvant.mccme.ru/pdf/1999/02/kv0299belov.pdf Единственное, меня терзают сомнения, что никто не говорит про время, затраченное на преобразование числа в требуемый формат, и ещё, если в одном формате возможно быстро производить сложение и умножение, то где гарантия, что эффективность также возрастёт, а не упадёт с производством в новом формате других операций, например: извлечения корня, деления и др.? (интересует работа алгоритма в комплексной задаче) |
||
Вернуться к началу | ||
За это сообщение пользователю 3axap "Спасибо" сказали: bimol |
||
swan |
|
|
3axap писал(а): Насколько больших? У меня в одной из программ поиска совершенного кубоида, к примеру, числа от 60 десятичных разрядов и более постоянно изменяются и перемножаются. Это маленькие. Эффекта не будет или даже отрицательный |
||
Вернуться к началу | ||
swan |
|
|
Этот алгоритм - развитие уже классического алгоритма Шенхаге-Штрассена, основанного на быстром преобразовании Фурье. Попробуйте его реализовать для начала, посмотрите, будет ли эффект. Насколько я помню, там от нескольких тысяч бит начинает превосходить.
А для ваших 200 битных чисел... Ну вот считайте. 200 бит можно представить массивом из 7 32-битных чисел, если 64-битную арифметику использовать, то вообще из трёх. Ну какие там алгоритмы? На накладные расходы больше потеряете |
||
Вернуться к началу | ||
За это сообщение пользователю swan "Спасибо" сказали: 3axap, bimol |
||
swan |
|
|
3axap писал(а): Вот ещё чего нашёл: https://habr.com/ru/post/451860/ http://users.math-cs.spbu.ru/~okhotin/t ... 019_l7.pdf http://kvant.mccme.ru/pdf/1999/02/kv0299belov.pdf Я почитал ссылки. Они дают хороший обзор, но немного легковесно. Я рекомендую почитать Кнута "Искусство программирования. 2-й том". Там идеальный сплав строгости, понятности и практичности Но ещё раз повторю, вряд ли в данный момент это вам поможет Последний раз редактировалось swan 21 авг 2019, 21:32, всего редактировалось 1 раз. |
||
Вернуться к началу | ||
3axap |
|
|
swan писал(а): ...если 64-битную арифметику использовать, то вообще из трёх. Ну какие там алгоритмы? На накладные расходы больше потеряете Ну вот примерно так я и предполагал... Спасибо. |
||
Вернуться к началу | ||
upi |
|
|
Советую протестировать его на тех примерах, которые вы уже прорешали, а до этого пользоваться только старыми, но проверенными методами.
И вам станет понятно. |
||
Вернуться к началу | ||
[ Сообщений: 10 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Максимально быстрый способ нагреть ванную с водой
в форуме Дифференциальное исчисление |
8 |
2768 |
06 окт 2014, 22:34 |
|
Быстрый алгоритм регуляризации | 1 |
264 |
19 дек 2016, 17:36 |
|
Быстрый поиск элементов массива
в форуме Численные методы |
0 |
409 |
26 сен 2014, 14:14 |
|
Приращение по модулю, быстрый алгоритм
в форуме Теория чисел |
0 |
175 |
29 сен 2021, 21:49 |
|
Уравнение на Новый Год | 43 |
1910 |
03 янв 2019, 14:34 |
|
Новый калькулятор
в форуме Информатика и Компьютерные науки |
2 |
288 |
21 май 2020, 13:03 |
|
Новый инвариант СТО? Почему нет?
в форуме Палата №6 |
1 |
330 |
17 сен 2018, 13:06 |
|
Дан массив. Сформировать новый
в форуме Информатика и Компьютерные науки |
1 |
346 |
14 фев 2018, 09:09 |
|
Новый день — новая задача | 6 |
921 |
17 авг 2015, 13:15 |
|
Всемирный эфир: новый уровень?
в форуме Палата №6 |
0 |
138 |
29 сен 2022, 13:45 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |