Новости робототехники

[Перевод] Математики до сих пор не уверены, как быстрее всего перемножать числа

[Перевод] Математики до сих пор не уверены, как быстрее всего перемножать числа
[Перевод] Математики до сих пор не уверены, как быстрее всего перемножать числа

Ученики начальной школы могут заучивать таблицу умножения однозначных чисел, но простого запоминания будет недостаточно, когда учитель задаст задачу на умножение трёхзначных чисел. Здесь требуется алгоритм: учеников учат выстраивать числа друг над другом и умножать каждую цифру нижнего числа на каждую цифру верхнего. На протяжении тысячелетий математики считали это самым быстрым способом умножения, пока в 1960 году 23-летний молодой человек не сделал шокирующее открытие, которое привело к загадке, остающейся неразгаданной до сих пор.

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

Чтобы понять суть этого «узкого места», обратите внимание на то, как «школьный» алгоритм справляется с увеличением размера чисел. При умножении двух двузначных чисел выполняется четыре однозначных умножения. Если перейти к паре трёхзначных чисел, то потребуется девять однозначных умножений. Нагрузка растёт пропорционально квадрату количества разрядов (n², где n — количество разрядов в умножаемых числах). При анализе подобного алгоритма компьютерные учёные не измеряют скорость в секундах, поскольку она зависит от аппаратного обеспечения. Вместо этого они подсчитывают количество вычислительных шагов. Они также игнорируют второстепенные детали, такие как время, необходимое для переноса единицы при умножении. Когда числа становятся достаточно большими, эти низкоуровневые операции перестают иметь значение, поскольку их полностью затмевают более ресурсоёмкие операции. Информатики обозначают количество шагов с помощью так называемой нотации «большого O»: например, алгоритм, который учат в начальной школе, требует O(n²) шагов, что читается как «порядка n в квадрате». В общих чертах, если числа в два раза длиннее, для выполнения алгоритма требуется в четыре раза больше вычислительной работы. Если числа в тысячу раз длиннее, требуется в миллион (1 000 в квадрате) раз больше работы.

>>

Источник: habr.com

❌ Нет тегов для этой статьи

Оцените материал:

Поделиться
Понравилась статья? Расскажите другим
ВКонтакте
Читайте также
Архив рубрики ~Лента новостей~ Signal ограничивает возможность делать скриншоты на мобильных устройствах, поскольку сталкивается с «экзистенциальной угрозой» слежки со стороны искусственного интеллекта. Архив рубрики ~Лента новостей~ Конец кислотным градиентам и эмодзи. Скилл unslop-ui вычищает ИИ-мусор из вайбкодинга Архив рубрики ~Лента новостей~ GPTunneL и SKILLOUT проведут хакатон ИИ‑рекламы в Москве 28–29 ноября. Открыта регистрация для онлайн‑участников Архив рубрики ~Лента новостей~ Позднетриасовый зауроподоморф из ЮАР набрал 400 килограмм уже на третьем году жизни. Взрослые особи этого вида могли весить несколько тонн Архив рубрики ~Лента новостей~ Стартап подал в суд на Apple в Индии из-за функции обмена контактами одним касанием. Архив рубрики ~Лента новостей~ «Впервые не ощущается как та „Gemini“»: Google выпустила Gemini 4 Neon, тестировщики сравнили её с Opus 5.5 Архив рубрики ~Лента новостей~ Чат-боты стали экспертами в убеждении людей Архив рубрики ~Лента новостей~ Иммунитет для сайтов. Как устроена защита онлайн-сервисов Архив рубрики ~Лента новостей~ Баг процессора за $475 миллионов: ошибка Intel Pentium Архив рубрики ~Лента новостей~ В мире большой науки в 2026-м случилось событие, одновременно воодушевляющее и слегка конфузное Архив рубрики ~Лента новостей~ Эксперты предупреждают: практически каждый в сфере ИИ сейчас уязвим для мошеннических схем с использованием «медовой ловушки». Архив рубрики ~Лента новостей~ Американский бизнесмен подал в суд на Meta* из-за блокировки страниц его компании на Facebook* — иск он подготовил с помощью ИИ-агента Muse, разработанного Meta* Архив рубрики ~Лента новостей~ Город, который читают машины: как я сделал API для нейросетей на одном PHP‑файле Архив рубрики ~Лента новостей~ О статистической механике жизни: пересмотренный Шрёдингер Архив рубрики ~Лента новостей~ Signal ограничивает возможность делать скриншоты на мобильных устройствах, поскольку сталкивается с «экзистенциальной угрозой» слежки со стороны искусственного интеллекта. Архив рубрики ~Лента новостей~ Конец кислотным градиентам и эмодзи. Скилл unslop-ui вычищает ИИ-мусор из вайбкодинга Архив рубрики ~Лента новостей~ GPTunneL и SKILLOUT проведут хакатон ИИ‑рекламы в Москве 28–29 ноября. Открыта регистрация для онлайн‑участников Архив рубрики ~Лента новостей~ Позднетриасовый зауроподоморф из ЮАР набрал 400 килограмм уже на третьем году жизни. Взрослые особи этого вида могли весить несколько тонн Архив рубрики ~Лента новостей~ Стартап подал в суд на Apple в Индии из-за функции обмена контактами одним касанием. Архив рубрики ~Лента новостей~ «Впервые не ощущается как та „Gemini“»: Google выпустила Gemini 4 Neon, тестировщики сравнили её с Opus 5.5 Архив рубрики ~Лента новостей~ Чат-боты стали экспертами в убеждении людей Архив рубрики ~Лента новостей~ Иммунитет для сайтов. Как устроена защита онлайн-сервисов Архив рубрики ~Лента новостей~ Баг процессора за $475 миллионов: ошибка Intel Pentium Архив рубрики ~Лента новостей~ В мире большой науки в 2026-м случилось событие, одновременно воодушевляющее и слегка конфузное Архив рубрики ~Лента новостей~ Эксперты предупреждают: практически каждый в сфере ИИ сейчас уязвим для мошеннических схем с использованием «медовой ловушки». Архив рубрики ~Лента новостей~ Американский бизнесмен подал в суд на Meta* из-за блокировки страниц его компании на Facebook* — иск он подготовил с помощью ИИ-агента Muse, разработанного Meta* Архив рубрики ~Лента новостей~ Город, который читают машины: как я сделал API для нейросетей на одном PHP‑файле Архив рубрики ~Лента новостей~ О статистической механике жизни: пересмотренный Шрёдингер

Оставить комментарий