„ | полезно, скоро пригодится цены в магазинах рассчитывать | “ |
Математики из Австралии и Франции создали высокоэффективный алгоритм, позволяющий быстро умножать числа, слишком большие для обычных способов. Ученые искали этот метод в течение почти 50 лет с тех пор, как в 1971 году был предложен алгоритм Шенхаге-Штрассена. Об этом пишет издание Science Alert.
Новый алгоритм выполняется за время, равное O(n log n), где n является порядком числа. Он может выполнять операцию умножения с числами, состоящими из более чем миллиарда знаков, в течение менее 30 секунд.
Обычные методы выполняют это действие за время, равное n в степени 1,58-2, и у компьютеров вычисление результата с большими множителями может занять месяцы. Это происходит потому, что, например, умножение двух трехзначных чисел требует девяти операций (каждая цифра одного числа перемножается с тремя другими), а двух четырехзначных чисел — уже 16 операций.
Высокоэффективный алгоритм полезен для вычисления произведений только очень больших чисел, например, 10 в степени 214857091104455251940635045059417341952. Теоретически он по скорости превосходит оригинальный метод Шенхаге-Штрассена, в основе которого лежит быстрое преобразование Фурье. Однако ученые опасаются, что в доказательстве их метода могли быть допущены ошибки, поэтому необходимы дальнейшие проверки для подтверждения его работоспособности.
Комментирование разрешено только первые 24 часа.
5 +0−0 | Владимир Владимирович | 15:07:21 09/04/2019 |
полезно, скоро пригодится цены в магазинах рассчитывать |
3 +0−0 | Alehandro09 | 15:11:27 09/04/2019 | ||||||
| ||||||||
"ОАЭ решили обвалить доллар" (с) Лента спустя какое то время "ОАЭ не собирались обваливать доллар" (с) Лента Почему здесь не сработает такая схема? Скоро ждем заголовок "Математик из Австралии неправильно решил загадку века (и пожалел)" |
2 +0−0 | Robert A. | 15:53:31 09/04/2019 |
Хорошая новость для подсчета американского госдолга |
1 +0−0 | Товарищ Чжаочжоу | 23:35:43 09/04/2019 | ||||||
| ||||||||
Не совсем так. Например, во вполне прикладной криптографии используются довольно большие числа, даже в масштабах вселенной. |
1 +0−0 | yes yes | 15:52:37 09/04/2019 | ||||||
| ||||||||
изобрел - неподходящее слово |
1 +0−0 | Отабек отабеков | 15:34:55 09/04/2019 | ||||||
| ||||||||
Не люблю евреев,но они как правило всегда все умножают и плюсуют,а не делят и вычитают. Какими методами - это уже другой вопрос. |
1 +0−0 | Эрик Босман | 15:31:46 09/04/2019 | ||||||
| ||||||||
Видео-карты еще быстрее будут считать 3d-графику. |
1 +0−0 | Баттхёрт Бугуртов | 15:14:00 09/04/2019 | ||||||
| ||||||||
При умножения трехзначных чисел в столбик, сложность будет O(n^3). В статье речь о O(n log n) |
1 +0−0 | Кремлёвская елбаса | 15:13:42 09/04/2019 | ||||||
| ||||||||
Математик из Австралии открестился от решения полувековой загадки |
1 +0−0 | Богдан Пургин | 15:12:53 09/04/2019 |
Так постепенно математики приближались к оценке состояния Путина. |
1 +0−0 | Баттхёрт Бугуртов | 15:07:52 09/04/2019 |
А где ссылка на статью? |
1 +0−0 | Pribor Sorok20 | 14:52:20 09/04/2019 |
Лента сама читает свои статьи? Загадка решена когда доказано что решение верно. |
0 +0−0 | Evgeniy Anisimov | 10:01:15 10/04/2019 |
Решена загадка века - но это не точно ))) |
0 +0−0 | Товарищ Чжаочжоу | 23:38:58 09/04/2019 | ||||||
| ||||||||
Не совсем вся. Одноразовые блокноты - наше все. |
0 +0−0 | Полиграф Шарткофф | 17:50:44 09/04/2019 | ||||||
| ||||||||
Судя по тому что я об них читал скорее второе. Они даже как будто не дадут выигрыша во времени на классических алгоритмах. |
0 +0−0 | Vasya Pupkin | 17:37:11 09/04/2019 |
квантовые компы кстати каким то образом могут увеличить скорость арифметических операций, таких как умножение? Или они скорее для ситаций с быстрым перебором возможных вариантов решений, как граф ходов в шахматах |
0 +0−0 | Octopus Osminogov | 16:44:04 09/04/2019 | ||||||
| ||||||||
Если эффективность проявляется только на указанных порядках чисел - то нет. Там сейчас, все-таки, числа поменьше гораздо (для 512-битного ключа, допустим, порядка 200 десятичных знаков) |
0 +0−0 | Octopus Osminogov | 16:42:07 09/04/2019 | ||||||
| ||||||||
Это ж вся криптография полетит к чертям собачьим. |
0 +0−0 | Вадим Ашдодский | 16:21:43 09/04/2019 | ||||||
| ||||||||
Ссылка под заметкой. |
0 +0−0 | Poploukhin Aleksandr | 16:21:18 09/04/2019 | ||||||
| ||||||||
А... ок. Чел с O(n^3) явно загнал, он принял O(n^2) + O(n) (сложение двух массивов) за O(n^3) :) Так-то в O- нотации меньшее О из слогаемых отбрасываем и оставляем O(n^2). Как и в твоем случае отбрасываем меньшее слагаемое O (log n) и получаем O(n^2) :) P.S. давненько я на умные темы на ленте не общался :) |