Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
 Заголовок сообщения: Новый быстрый способ умножения
СообщениеДобавлено: 17 авг 2019, 18:27 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июн 2016, 15:38
Сообщений: 6755
Откуда: Калининградская область
Cпасибо сказано: 992
Спасибо получено:
492 раз в 461 сообщениях
Очков репутации: 57

Добавить очки репутацииУменьшить очки репутации
Прежде, чем применить, хотел бы поинтересоваться: то-нибудь знаком, насколько этот алгоритм достоверный?

https://hal.archives-ouvertes.fr/hal-02070778/document

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 19 авг 2019, 12:49 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
По ссылке очень много букв
Не могли бы вы на пальцах обьяснить, чем оно отличается от например алгоритма умножения Карацубы ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 19 авг 2019, 12:54 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июн 2016, 15:38
Сообщений: 6755
Откуда: Калининградская область
Cпасибо сказано: 992
Спасибо получено:
492 раз в 461 сообщениях
Очков репутации: 57

Добавить очки репутацииУменьшить очки репутации
Заявленная скорость выше.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 20 авг 2019, 09:21 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
3axap писал(а):
Прежде, чем применить, хотел бы поинтересоваться: то-нибудь знаком, насколько этот алгоритм достоверный?

Простите, а где бы вы хотели его применить? Этот алгоритм превосходит классический способ только для ОЧЕНЬ больших чисел

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 21 авг 2019, 19:14 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июн 2016, 15:38
Сообщений: 6755
Откуда: Калининградская область
Cпасибо сказано: 992
Спасибо получено:
492 раз в 461 сообщениях
Очков репутации: 57

Добавить очки репутацииУменьшить очки репутации
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

Единственное, меня терзают сомнения, что никто не говорит про время, затраченное на преобразование числа в требуемый формат, и ещё, если в одном формате возможно быстро производить сложение и умножение, то где гарантия, что эффективность также возрастёт, а не упадёт с производством в новом формате других операций, например: извлечения корня, деления и др.? (интересует работа алгоритма в комплексной задаче)

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3axap "Спасибо" сказали:
bimol
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 21 авг 2019, 20:52 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
3axap писал(а):
Насколько больших? У меня в одной из программ поиска совершенного кубоида, к примеру, числа от 60 десятичных разрядов и более постоянно изменяются и перемножаются.

Это маленькие. Эффекта не будет или даже отрицательный

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 21 авг 2019, 20:56 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Этот алгоритм - развитие уже классического алгоритма Шенхаге-Штрассена, основанного на быстром преобразовании Фурье. Попробуйте его реализовать для начала, посмотрите, будет ли эффект. Насколько я помню, там от нескольких тысяч бит начинает превосходить.
А для ваших 200 битных чисел...
Ну вот считайте. 200 бит можно представить массивом из 7 32-битных чисел, если 64-битную арифметику использовать, то вообще из трёх. Ну какие там алгоритмы? На накладные расходы больше потеряете

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
3axap, bimol
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 21 авг 2019, 21:27 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
3axap писал(а):

Я почитал ссылки. Они дают хороший обзор, но немного легковесно. Я рекомендую почитать Кнута "Искусство программирования. 2-й том". Там идеальный сплав строгости, понятности и практичности
Но ещё раз повторю, вряд ли в данный момент это вам поможет


Последний раз редактировалось swan 21 авг 2019, 21:32, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 21 авг 2019, 21:30 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июн 2016, 15:38
Сообщений: 6755
Откуда: Калининградская область
Cпасибо сказано: 992
Спасибо получено:
492 раз в 461 сообщениях
Очков репутации: 57

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
...если 64-битную арифметику использовать, то вообще из трёх. Ну какие там алгоритмы? На накладные расходы больше потеряете

Ну вот примерно так я и предполагал... Спасибо.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Новый быстрый способ умножения
СообщениеДобавлено: 02 сен 2019, 06:34 
Не в сети
Начинающий
Зарегистрирован:
02 сен 2019, 05:44
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Советую протестировать его на тех примерах, которые вы уже прорешали, а до этого пользоваться только старыми, но проверенными методами.
И вам станет понятно.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 10 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Максимально быстрый способ нагреть ванную с водой

в форуме Дифференциальное исчисление

nybble

8

2768

06 окт 2014, 22:34

Быстрый алгоритм регуляризации

в форуме Математическая статистика и Эконометрика

edoq

1

264

19 дек 2016, 17:36

Быстрый поиск элементов массива

в форуме Численные методы

alex345

0

409

26 сен 2014, 14:14

Приращение по модулю, быстрый алгоритм

в форуме Теория чисел

registration

0

175

29 сен 2021, 21:49

Уравнение на Новый Год

в форуме Интересные задачи участников форума MHP

Fenix

43

1910

03 янв 2019, 14:34

Новый калькулятор

в форуме Информатика и Компьютерные науки

Macrodon

2

288

21 май 2020, 13:03

Новый инвариант СТО? Почему нет?

в форуме Палата №6

ivashenko

1

330

17 сен 2018, 13:06

Дан массив. Сформировать новый

в форуме Информатика и Компьютерные науки

mapsaaag

1

346

14 фев 2018, 09:09

Новый день — новая задача

в форуме Задачи со школьных и студенческих олимпиад

puzzlesdaily

6

921

17 авг 2015, 13:15

Всемирный эфир: новый уровень?

в форуме Палата №6

O Micron

0

138

29 сен 2022, 13:45


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved