РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Еще один способ быстро умножать простые числа

Умножение длинных чисел в уме — настоящая головная боль для всех детей с самой начальной школы. Однако математик разработал новый метод умножения больших чисел, который намного эффективнее привычного нам.
Еще один способ быстро умножать простые числа

Дэвид Харли, доцент из Университета Нового Южного Уэльса в Сиднее обратился к алгоритму Шёнхаге – Штрассена, разработанному двумя немецкими математиками. В период с 1971 года по 2007 это был самый быстрый способ умножения чисел, пока ему на смену не пришла альтернатива (справедливости ради стоит отметить, что используют ее крайне редко).

Не занимайтесь самолечением! В наших статьях мы собираем последние научные данные и мнения авторитетных экспертов в области здоровья. Но помните: поставить диагноз и назначить лечение может только врач.
youtube
Нажми и смотри
Нажми и смотри

Шенхаге и Штрассен предсказали существование алгоритма умножения n-значных чисел с использованием базовых операций формата n * log (n). С тех пор прошло несколько десятилетий, но лишь теперь появилось первое доказательство этой гипотезы.

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Так в чем же суть? Для примера Харви выбрал умножение чисел 314 и 159 — с подобными числами мы сталкиваемся каждый день. Обычно, чтобы решить подобное уравнение, большинство людей перемножает каждый отдельный номер, а затем складывают суммы. Так, 9 умножается на 4,1 и 3, затем 5 умножается на 4, 1 и 3, и так далее. В результате сложения всех результатов и получается искомое 9-значное число.

Этот метод называется n2, потому что число n умножается на n несколько раз. Получите ли вы правильный ответ? Безусловно. Однако еще в 1971 году немцы придумали, как ускорить процесс. Они записывали его как n * log (n). Напомним, что log — это сокращение от «логарифма», который помогает нам расшифровывать числа, возведенные в степень. Например, 2⁵ = 32, но если записать это уравнение логарифмически, то получится log₂ (32) = 5. Звучит просто, однако по-настоящему логарифмы начинают упрощать процесс в работе с крупными числами.

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Харви уверен, что метод Шёнхаге-Штрассена очень практичен. По его словам, если обычному компьютеру дать задачу перемножить между собой два числа с миллиардом знаков в каждом, используя «школьный» метод — это заняло бы месяцы. А если дать ему ту же задачу, но использовать при этом подход с логарифмами, то вся операция займет... от силы секунд 30.

Впрочем, и тут есть пределы. математик отмечает, что если число знаков будет составлять триллион и больше, то здесь пригодится алгоритм, разработанный Харви и его сотрудником Йорисом ван дер Хувеном в Политехнической школе во Франции в 2007 году. «С его помощью можно будет вычислить значение числа "пи" с еще большей точностью. Человечество 50 лет охотилось за таким удобным способом работы с огромными простыми числами — и теперь он наконец в нашем распоряжении», — говорит сам Харви.

oxba1da
oxba1da 20 Декабря 2019, 15:43
Напомнило занимательную математику Перельмана-старшего. Там описан фокус, по извлечению целых корней, подразумевающий использование логарифмов.
Дюха Пупкин
Дюха Пупкин 25 Октября 2019, 06:38
Вывод один - автор графоман-долбоеб !!!!
SergA
SergA 22 Октября 2019, 23:15
«Ужас, статья полностью не верна!» Вы, похоже, слабо знакомы с творчеством В.Макарова. Его статьи нужно оценивать не на верность, а на степень безумия.
Алексей Медведев
Алексей Медведев 22 Октября 2019, 23:05
Ужас, статья полностью не верна! Начиная с заголовка, не говоря уже о самом тексте. Первое - в работе чувака доказано, что такой алгоритм существует, но не найден сам алгоритм. Второе, про логарифмы... В видео говорится о "сложности алгоритмов", погуглите как оценивать сложность алгоритма. Алгоритм со сложностью n*log(n) тупо быстрее чем n^2 (меньше действий). А не о том, что "Однако еще в 1971 году немцы придумали, как ускорить процесс. Они записывали его как n * log (n)." (с). Существования такого алгоритма ценно для компьютера, который сможет быстрее умножать большие числа. В конце он говорит, что не знает насколько n должно быть большим, чтобы этот алгоритм был действительно быстрее чем предыдущие.
SergA
SergA 22 Октября 2019, 23:02
“Математик нашел новый способ быстро умножать простые числа” “Для примера Харви выбрал умножение чисел 314 и 159” Милый Вася, эти числа - не простые.
SergA
SergA 22 Октября 2019, 22:56
log — это сокращение от «логарифма», который помогает нам расшифровывать числа, возведенные в степень Весело у вас там. :)))
SergA
SergA 22 Октября 2019, 22:54
“Обычно, чтобы решить подобное уравнение, большинство людей перемножает каждый отдельный номер, а затем складывают суммы.  Речь идет о большинстве пациентов дурдома?
Загрузка статьи...