Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:
Гы. Оказывается умножение Шёнхаге-Штрассена (метод умножения больших чисел, основанный на быстром преобразовании фурье) уже не самый быстрый метод. Некто Мартин Фюрер чуть менее года назад придумал метод умножения, имеющий ещё существенно лучшую асимптотическую сложность — O(n · log n · 2slog n)

Интересно, а до нижней теоретической границы в O(n · log n) когда-нибудь доберутся?


_____
slog = суперлогарифм. Умножение является итерированием сложения. Возведение в степень — итерированием умножения. Тетрация — итерирование возведения в степень. Логарифм обычный — это обратное возведению в степень по второму аргументу. А слогарифм — обращение по второму аргументу тетрации. Растёт он медленнее, чем 1/функцию Аккермана. Его округление вверх задаётся красивой рекурсивной формулой, дающей представление о том, насколько медленно он растёт:
[^ slog x ^] = (x < 1) ? 0 : 1 + [^ slog x - 1 ^]
Subscribe

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments