1. Python / Говнокод #27347

    −1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    def karatsuba_multiplication(x : int, y : int) -> int:
    sx, sy = map(lambda x: '0' + str(x) if len(str(x)) % 2 != 0 else str(x), (x, y))
    return _karatsuba_multiplication(sx, sy, max(len(sx), len(sy)))

def _prepend_nils(string : str, amount_of_nils : int) -> str:
    return ('0' * amount_of_nils + string)

def _karatsuba_multiplication(x : str, y : str, n : int) -> int:
    x, y = map(lambda x: _prepend_nils(x, (n - len(x))), (x, y))

    if (n == 1):
        return (int(x) * int(y))

    mid = n // 2
    a, b = int(x[:mid]), int(x[mid:])
    c, d = int(y[:mid]), int(y[mid:])

    p = a + b
    q = c + d
    ac = _karatsuba_multiplication(str(a), str(c), max(len(str(a)), len(str(c))))
    bd = _karatsuba_multiplication(str(b), str(d), max(len(str(b)), len(str(d))))
    pq = _karatsuba_multiplication(str(p), str(q), max(len(str(p)), len(str(q))))
    adbc = pq - ac - bd
    return 10**n * ac + 10**(mid + n % 2) * adbc + bd

    Как-то не очень получилось...

    Запостил: JloJle4Ka, 10 Апреля 2021

    Комментарии (24) RSS

    • ava JloJle4Ka 10.04.2021 13:39 # 0

      CEO post: Оно еще и не работает.
      Ответить

      • ava gologub 10.04.2021 14:19 # +1

        омг, директор говнокода в треде, все в кьюбиклы!
        Ответить

        • ava booratihno 10.04.2021 14:22 # 0

          Director -- директор
          CEO -- seo
          Ответить

          • ava bootcamp_dropout 10.04.2021 14:25 # +1

            director это режиссер, я в титрах видел
            Ответить

          • ava gologub 10.04.2021 15:28 # +4

            Artist -- артист
            Drug -- друг
            Examine -- экзамен
            Faggot -- фагот
            Most -- мост
            Piston -- пистон
            Resin -- резина
            Sewer -- север
            Tort -- торт
            Velvet -- вельвет
            Ответить

    • ava bormand 10.04.2021 14:05 # +1

      Зачем? Зачем? Что-то мне намекает, что питон сам умеет юзать эти умножения когда числа достаточно длинные. Или нет?
      Ответить

      • ava JloJle4Ka 10.04.2021 14:07 # 0

        Я изучаю алгоритм.
        Ответить

        • ava bormand 10.04.2021 14:11 # +1

          Ну тогда стоит его изучать на сишке или крестах где числа фиксированной длины, имхо.
          Ответить

          • ava j123123 10.04.2021 17:05 # 0

            Числа фиксированной длины можно из NumPy взять https://numpy.org/doc/stable/user/basics.types.html
            Ответить

      • ava JloJle4Ka 12.04.2021 16:52 # +1

        Интересный факт: в языке программирования Python встроенная подпрограмма умножения целочисленных объектов использует алгоритм начальной школы для целых чисел с не более чем 70 знаками и алгоритм Karatsuba в противном случае.
        Ответить

    • ava guest6 10.04.2021 14:16 # +1

      Советую использовать фоурьера. Поупарываться над пирформансом можно.
      Ответить

      • ava bormand 12.04.2021 16:56 # +1

        Ну это для совсем больших чисел, емнип, в GMP он подключается в районе тысячезначных чисел.
        Ответить

        • ava guest6 12.04.2021 17:09 # 0

          А до этого за О(n^2)?
          Если хранить числа по 9 десятичных знаков (только тут не уверен, что норм хранить в десятичных), то около ста интов получится.
          Ответить

          • ava bormand 12.04.2021 17:11 # +2

            Ну вроде да -- для мелочи наивно в столбик, потом карацуба, потом что-то ещё, и в самом конце FFT. Погугли табличку с порогами, она у них для каждой архитектуры вроде своя.

            У FFT оверхед адовый, оно не окупается для мелочи.
            Ответить

            • ava DypHuu_niBEHb 12.04.2021 17:17 # +1

              А ведь фурри этого вашего можно запускать на спец процессоре (вроде для dsp), он же тогда всех порвет?
              Ответить

              • ava bormand 12.04.2021 17:22 # 0

                Не уверен. Порог пониже будет, но всяко не с нуля.
                Ответить

          • ava gologub 12.04.2021 17:44 # 0

            тут примерно такая же херня, из-за которой в $(ТВОЕЙ ЛЮБИМОЙ RTL) поиск подстроки наивный, несмотря на...
            Ответить

      • ava guest6 12.04.2021 17:10 # 0

        Вот эту задачу советую решить https://www.spoj.com/problems/VFMUL/
        Ответить

    • ava booratihno 10.04.2021 14:42 # +2

      Карацуба это частный случай битойобства, и странно битойобить на питоне
      Ответить

      • ava bormand 12.04.2021 17:00 # 0

        Ну да, даже пирфоманс померить не получится. А это ведь самое интересное в таких алгоритмах.
        Ответить

    Добавить комментарий