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

    0

    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

    • CEO post: Оно еще и не работает.
      Ответить
      • омг, директор говнокода в треде, все в кьюбиклы!
        Ответить
        • Director -- директор
          CEO -- seo
          Ответить
          • director это режиссер, я в титрах видел
            Ответить
          • Artist -- артист
            Drug -- друг
            Examine -- экзамен
            Faggot -- фагот
            Most -- мост
            Piston -- пистон
            Resin -- резина
            Sewer -- север
            Tort -- торт
            Velvet -- вельвет
            Ответить
    • Зачем? Зачем? Что-то мне намекает, что питон сам умеет юзать эти умножения когда числа достаточно длинные. Или нет?
      Ответить
      • Я изучаю алгоритм.
        Ответить
        • Ну тогда стоит его изучать на сишке или крестах где числа фиксированной длины, имхо.
          Ответить
          • Числа фиксированной длины можно из NumPy взять https://numpy.org/doc/stable/user/basics.types.html
            Ответить
      • Интересный факт: в языке программирования Python встроенная подпрограмма умножения целочисленных объектов использует алгоритм начальной школы для целых чисел с не более чем 70 знаками и алгоритм Karatsuba в противном случае.
        Ответить
    • Советую использовать фоурьера. Поупарываться над пирформансом можно.
      Ответить
      • Ну это для совсем больших чисел, емнип, в GMP он подключается в районе тысячезначных чисел.
        Ответить
        • А до этого за О(n^2)?
          Если хранить числа по 9 десятичных знаков (только тут не уверен, что норм хранить в десятичных), то около ста интов получится.
          Ответить
          • Ну вроде да -- для мелочи наивно в столбик, потом карацуба, потом что-то ещё, и в самом конце FFT. Погугли табличку с порогами, она у них для каждой архитектуры вроде своя.

            У FFT оверхед адовый, оно не окупается для мелочи.
            Ответить
            • А ведь фурри этого вашего можно запускать на спец процессоре (вроде для dsp), он же тогда всех порвет?
              Ответить
              • Не уверен. Порог пониже будет, но всяко не с нуля.
                Ответить
          • тут примерно такая же херня, из-за которой в $(ТВОЕЙ ЛЮБИМОЙ RTL) поиск подстроки наивный, несмотря на...
            Ответить
      • Вот эту задачу советую решить https://www.spoj.com/problems/VFMUL/
        Ответить
    • Карацуба это частный случай битойобства, и странно битойобить на питоне
      Ответить
      • Ну да, даже пирфоманс померить не получится. А это ведь самое интересное в таких алгоритмах.
        Ответить

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