2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Умножение целых чисел за O(n log n)
Сообщение13.04.2019, 13:19 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Кто-нибудь уже разбирался? https://hal.archives-ouvertes.fr/hal-02070778/document
Abstract писал(а):
We present an algorithm that computes the product of two n-bit integers in $O(n \log n)$ bit operations.

 Профиль  
                  
 
 Re: Умножение целых чисел за O(n log n)
Сообщение13.04.2019, 13:39 
Заслуженный участник


18/01/15
3073
В алгоритме Шенхаге-Штрассена было $O(n \log n \log\log n)$. Новый алгоритм, по сведениям ленты.ру, способен перещеголять ШШ на числах с порядка $10^{20}$ знаков. Ушло на это полвека. У меня такая игра в бисер восхищения не вызывает. Разбираться, естественно, не буду.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group