OpenAI решила задачу умножения целых чисел быстрее, чем за n log n
Integer multiplication below n log n
В репозитории openai/math появился препринт «Integer multiplication below n log n». В нём утверждается, что классическая граница Шёнхаге — Штрассена для умножения целых чисел преодолена. Рядом лежат ещё сотни работ — от контрпримеров к гипотезам Капланского и Хадвигера до новых оценок для матричного умножения.
- TGower
Мы отрезали целых: 1/6129982163463555433433388108601236734474956488734408704 от nlogn
- shmoil
Я рассмеялся в голос над n lg n ^ (1 - 2^{-182}). Это так смешно.
- wk_end
Есть ли связанное с этим машинно-проверенное доказательство?
Мы полностью в режиме вайб-кодинга на работе, так что я понимаю и насколько мощными могут быть фронтирные модели, и как часто они могут самоуверенно утверждать тонко (или не очень тонко) неверные вещи, даже когда ты прилагаешь огромные усилия, чтобы этого не случилось.
Так что без разработки на Lean или обширной человеческой проверки, я, пожалуй, немного скептичен, и даже в некотором роде надеюсь, что это неверно — не только из-за моих не самых положительных чувств к ИИ, но и из-за моей склонности к красоте в математике. n log n — это гораздо приятнее, чем то, что у нас здесь есть.
- MinimalAction
Для непосвящённых, почему это интересно, учитывая, что это, похоже, не так уж сильно ниже порога?
- 12390asdjkas
это идеально подходит для случая, когда у меня есть массив из КАК МИНИМУМ 2^118000 элементов
мне НИКОГДА не будет дела до предложенных ускорений умножения, пока они не станут по-настоящему обобщёнными