Форум Протвино

28.10.2019 Совет депутатов


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

 
Вернуться   Форум города Протвино > Протвино - город > Наука
Регистрация Справка Пользователи Календарь Поиск Сообщения за день Все разделы прочитаны

Наука О науке в городе и за его пределами

Ответ
 
Опции темы Опции просмотра
  #1  
Старый 18.10.2019, 18:32
Аватар для xtovo
xtovo xtovo на форуме
Пишущий
 
Регистрация: 20.08.2007
Адрес: Protvino
Сообщения: 417
Вес репутации: 1972
xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть
Учимся умножению ...

https://www.sciencealert.com/mathema...-large-numbers


Сегодня учимся умножению.

Все из нас прошли через это ещё в начальной школе -
как перемножить два числа?

Сначала необходимо выучить Таблицу Умножения,
затем научится Умножать Столбиком
(этот способ умножения известенеще со времён шумеров, >4000 лет назад).

Умножение Столбиком двух чисел состоящих из N цифр,
содержит N^2 операций.

Можно ли это сделать как-то по-другому, быстрее?
Парадоксально, но эта казалось бы "элементарная операция"
породила серьёзные теоретические математические исследования,
и даже открыла целую область в математике - теорию быстрых вычислений.

В 1960-ом году ученик академика А.Н. Колмогорова
(мое поколение ещё помнит его учебники по математике для средней школы)
Анатолий Карацуба нашёл новый метод умножения двух
N-значных чисел с оценкой сложности N^1.58
и тем самым опроверг «гипотезу N^2».

https://ru.wikipedia.org/wiki/Умножение_Карацубы


И вот, совсем недавно математик Давид Харви и его австралийский коллега,
предложили алгоритм, который "убыстрил" алгоритм Карацубы,
и обладает N^log(N) степенью сложности.

autotranslated:

«Люди охотились за таким алгоритмом почти 50 лет.
Это не было заброшенным выводом,
что кто-то в конечном итоге будет успешным».

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

«Мы понятия не имеем», объясняют исследователи в FAQ,
хотя один пример, который они приводят в статье,
равен 10^214857091104455251940635045059417341952,
что является очень, очень, очень большим числом.

Мировое математическое сообщество все еще впитывает новые
открытия, которые еще не прошли рецензирование,
но уже набирают обороты.
«Я был очень удивлен, что это было сделано, -
сказал Science News ученый-теоретик Мартин Фюрер из Университета штата Пенсильвания.

Сам Фюрер пытался обновить алгоритм Шёнхаге-Штрассена более десяти лет назад,
но в итоге прекратил работу, сказав Science News:
«Это казалось мне совершенно безнадежным».

Но надежда была восстановлена,
если математики смогут проверить работу.

«Если результат верный, это главное достижение в теории
вычислительной сложности», -
сказал New Scientist математик и ученый Фредрик Йоханссон
из INRIA Bordeaux и Institut de Mathématiques de Bordeaux.

«Новые идеи в этой работе, вероятно, вдохновят дальнейшие
исследования и могут привести к практическим улучшениям в будущем».

Тем временем Харви и его соавтор Йорис ван дер Хувен из
Французской Политехнической Школы говорят,
что их алгоритм должен быть оптимизирован,
и они просто надеются, что они ничего не напутали в своем доказательстве.

«Большая часть работы убедила нас в том,
что это действительно правильно», - сказал Харви.
«Я все еще боюсь, что это может оказаться неправильно.»
__________________
vagabond hacker
Ответить с цитированием
  #2  
Старый 19.10.2019, 12:53
Аватар для All Eyez On Me
All Eyez On Me All Eyez On Me вне форума
big bro's watchin' ya
 
Регистрация: 09.07.2007
Адрес: out there
Сообщения: 4,018
Вес репутации: 3051
All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть All Eyez On Me . Такую репутацию нельзя пошатнуть
В библиотеку питона уже добавили?)
Ответить с цитированием
  #3  
Старый 19.10.2019, 16:24
Аватар для xtovo
xtovo xtovo на форуме
Пишущий
 
Регистрация: 20.08.2007
Адрес: Protvino
Сообщения: 417
Вес репутации: 1972
xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть xtovo . Такую репутацию нельзя пошатнуть
В библиотеку питона уже добавили?)

Умножение длинных чисел методом Карацубы :)
https://habr.com/ru/post/124258/
__________________
vagabond hacker
Ответить с цитированием
  #4  
Старый 19.10.2019, 17:53
Аватар для Владимир Аникеев
Владимир Аникеев Владимир Аникеев вне форума
ce est moi
(офицер)
 
Регистрация: 11.06.2008
Сообщения: 3,474
Вес репутации: 1895
Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее Владимир Аникеев , прекрасное будущее
Если я давно представляю себе, где может применяться алгоритм Фолькера Штрассена(1969) для быстрого умножения матриц большой размерности(>=64), то про то, что он является обобщением метода умножения многозначных чисел Карацубы на матрицы, я узнал недавно. Может кто-то знает, где применяется алгоритм Карацубы? Многозначные числа - это невероятная точность или невероятные события! Теория чисел - для меня непостижимая наука и кроме признаков деления целых чисел на 2,3,5 мне и предъявить нечего! :-(
__________________
Бритва Хэнлона: Никогда не приписывайте злому умыслу то, что вполне можно объяснить глупостью.
(англ. Hanlon's Razor «Never attribute to malice that which can be adequately explained by stupidity»).
Ответить с цитированием
Ответ


Здесь присутствуют: 1 (пользователей - 0 , гостей - 1)
 
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход

Праздники сегодня

 

 

Реклама на форуме

Помочь форуму:

Я-деньги № 4100154088247

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

 

 
Часовой пояс GMT +3, время: 20:50.


vBulletin v3.6.2, Copyright ©2000-2019, Jelsoft Enterprises Ltd.
Русский перевод: zCarot, Vovan & Co
Администрация форума не несет ответственности за содержание сообщений на форуме.