Статья дня
David Harvey, Joris Van Der Hoeven, “Integer multiplication in time O(n log n)”.
https://hal.archives-ouvertes.fr/hal-02070778/document
В школе рассказывают, как перемножать n-значные числа «в столбик» за O(n^2) операций. Когда Колмогоров (в 1960 году) предложил доказать, что это асимптотически лучший способ, быстро выяснилось, что это не так: метод Карацубы имеет сложность O(n^(ln(3)/ln(2))) и основан на равенстве (ax+b)(cx+d)= acx^2 + ((a+b)(c+d)-ac-bd)x + bd. В 1971 году был найден алгоритм Шёнхаге–Штрассена сложности O(n ln(n) ln(ln(n))). В статье излагается алгоритм сложности O(n ln(n)). Хочется верить, что такова и нижняя оценка сложности, но пока что это не доказано (впрочем, есть доказательства, которые сводят это к другим нерешенным задачам).
David Harvey, Joris Van Der Hoeven, “Integer multiplication in time O(n log n)”.
https://hal.archives-ouvertes.fr/hal-02070778/document
В школе рассказывают, как перемножать n-значные числа «в столбик» за O(n^2) операций. Когда Колмогоров (в 1960 году) предложил доказать, что это асимптотически лучший способ, быстро выяснилось, что это не так: метод Карацубы имеет сложность O(n^(ln(3)/ln(2))) и основан на равенстве (ax+b)(cx+d)= acx^2 + ((a+b)(c+d)-ac-bd)x + bd. В 1971 году был найден алгоритм Шёнхаге–Штрассена сложности O(n ln(n) ln(ln(n))). В статье излагается алгоритм сложности O(n ln(n)). Хочется верить, что такова и нижняя оценка сложности, но пока что это не доказано (впрочем, есть доказательства, которые сводят это к другим нерешенным задачам).
Article of the day
David Harvey, Joris Van Der Hoeven, “Integer multiplication in time O (n log n)”.
https://hal.archives-ouvertes.fr/hal-02070778/document
The school tells how to multiply n-digit numbers "in a column" in O (n ^ 2) operations. When Kolmogorov (in 1960) proposed proving that this was the asymptotically best way, it quickly became clear that this was not the case: Karatsuba's method has complexity O (n ^ (ln (3) / ln (2))) and is based on the equality (ax + b) (cx + d) = acx ^ 2 + ((a + b) (c + d) -ac-bd) x + bd. In 1971, the Schönhage – Strassen algorithm of complexity O (n ln (n) ln (ln (n))) was found. The article describes an algorithm of complexity O (n ln (n)). I would like to believe that this is also the lower bound for complexity, but so far this has not been proven (however, there is evidence that reduces this to other unsolved problems).
David Harvey, Joris Van Der Hoeven, “Integer multiplication in time O (n log n)”.
https://hal.archives-ouvertes.fr/hal-02070778/document
The school tells how to multiply n-digit numbers "in a column" in O (n ^ 2) operations. When Kolmogorov (in 1960) proposed proving that this was the asymptotically best way, it quickly became clear that this was not the case: Karatsuba's method has complexity O (n ^ (ln (3) / ln (2))) and is based on the equality (ax + b) (cx + d) = acx ^ 2 + ((a + b) (c + d) -ac-bd) x + bd. In 1971, the Schönhage – Strassen algorithm of complexity O (n ln (n) ln (ln (n))) was found. The article describes an algorithm of complexity O (n ln (n)). I would like to believe that this is also the lower bound for complexity, but so far this has not been proven (however, there is evidence that reduces this to other unsolved problems).
У записи 30 лайков,
6 репостов,
3005 просмотров.
6 репостов,
3005 просмотров.
Эту запись оставил(а) на своей стене Александр Лузгарев
