Подскажите понятный алгоритм деления
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 14.05.21 21:40
Оценка:
Здравствуйте!

Развлекаюсь написанием класса десятичных чисел.

Умножение и деление реализовал столбиком — получилось весьма, весьма медленно. Потом для умножения нашел алгоритм Фюрера — https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D1%8E%D1%80%D0%B5%D1%80%D0%B0

Умножение ускорилось на порядок. Хотя я в математике весьма слаб, но там алгоритм очень простой. Пример в вики на самом деле не очень — мне было подозрителен момент, когда в линейной свёртке могли бы появится трёх или более значные числа. Я на бамажке такой пример прорешал — сработало. Потом реализовал, и все тесты, которые были для столбика, с этим алгоритмом тоже проходят.

Вот теперь хочется для деления найти что-то подобное — простое, чтобы я смог понять хоть немного, что там делается, чтобы запилить реализацию, и, как минимум, более эффективное, чем столбик.

Вижу два варианта: 1) собсно быстрый алгоритм самого деления; 2) быстрый алгоритм нахождения обратного — 1/N, что потом дополнится уже работающим достаточно быстрым умножением

Пока всё, что нашел — какая-то заумь .

В принципе, это мои развлечения — развлечения бухгалтерией на C++, и можно не особо париться — операция деления там используется на порядок реже, чем +/-/*, и никаких корней и прочих логарифмов извлекать не надо, но во мне проснулся перфекционист . Ну и, как бонус — таки для вычислений каких-то численными методами мой decimal поудобнее будет — точность результата можно задавать абсолютной дельтой хоть в 150ом знаке после точки


ЗЫ Изначально побыстрому наколбасил версию decimal с фиксированной плавающей точкой (хз как это назвать, когда все цифры числа хранятся точно, но десятичная точка двигается влево-вправо) на базе int64_t, но потом, когда дошел до этапа, где надо складывать, а тем более умножать и делить, решил, что int64_t зело маловат, а проверять переполнения и тп на каждом шаге совсем не хочется, а int128_t в стандарт не завезли, поэтому решил переколбасить на произвольное количество десятичных знаков.


ЗЗЫ Про GMP слышал, да. Но что-то собирать её лень Потыкал boost::multiprecision — большая часть там обёртка над GMP, но есть и такое, что ничего дополнительного не требует — cpp_dec_float.


Посоревновался с ним в скорости ради интереса — оказалось, что моё в ~2.5 раза медленнее на сложениях и вычитаниях, и в 4.5 раза медленнее на умножении (но в 40 раз медленнее на делении ). По сравнению с double — +/- — моё в 8 раз медленнее, * — в 20. Не так уж и плохо для дилетанта, на мой дилетантский взгляд . Кстати, обнаружил, что сложение и вычитание для IEE-шных double'ов на порядок медленнее умножения и деления.


И да. Смотреть реализацию cpp_dec_float было лень, но судя по всему, там принцип примерно такой же, как и у IEE-шных float/double'ов. Как я это определил?
Очень просто. В процессе блуждания наткнулся на интересный тест для плавающих чисел — Muller's Recurrence — https://latkin.org/blog/2014/11/22/mullers-recurrence-roundoff-gone-wrong/
Так вот. cpp_dec_float идёт вразнос практически также, как и float/double, а мои десятичные числа колбасит более предсказуемо:

  double
Muller's Recurrence Test for double
Execution time: 0 ms

Test results:

      1: 4
      2: 4.25
      3: 4.47059
      4: 4.64474
      5: 4.77054
      6: 4.8557
      7: 4.91085
      8: 4.94554
      9: 4.96696
     10: 4.98004
     11: 4.98791
     12: 4.99136
     13: 4.96746
     14: 4.42969
     15: -7.81724
     16: 168.939
     17: 102.04
     18: 100.1
     19: 100.005
     20: 100
     21: 100
     22: 100
     23: 100
     24: 100

  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<50> >
Muller's Recurrence Test for cpp_float_normal
Execution time: 0 ms

Test results:

      1: 4
      2: 4.25
      3: 4.47059
      4: 4.64474
      5: 4.77054
      6: 4.8557
      7: 4.91085
      8: 4.94554
      9: 4.96696
     10: 4.98005
     11: 4.98798
     12: 4.99277
     13: 4.99566
     14: 4.99739
     15: 4.99843
     16: 4.99906
     17: 4.99944
     18: 4.99966
     19: 4.9998
     20: 4.99988
     21: 4.99993
     22: 4.99996
     23: 4.99997
     24: 4.99998
     25: 4.99999
     26: 4.99999
     27: 5
     28: 5
     29: 5
     30: 5
     31: 5
     32: 5
     33: 5
     34: 5
     35: 5
     36: 5
     37: 5
     38: 5
     39: 5
     40: 5
     41: 5
     42: 5
     43: 5
     44: 5
     45: 5
     46: 5
     47: 5
     48: 5
     49: 5
     50: 5
     51: 5
     52: 5
     53: 4.99998
     54: 4.99969
     55: 4.99372
     56: 4.87424
     57: 2.41992
     58: -101.618
     59: 109.92
     60: 100.451
     61: 100.022
     62: 100.001
     63: 100
     64: 100

  marty::Decimal
Muller's Recurrence Test for marty::Decimal with precision 18
Execution time: 16 ms

Test results:

      1: 4
      2: 4.25
      3: 4.470588235294117648
      4: 4.6447368421052631797
      5: 4.770538243626062793
      6: 4.8557007125890834795
      7: 4.910847499082995841
      8: 4.945537404128041607
      9: 4.966962581846087948
     10: 4.980045703034239931
     11: 4.987979482182271972
     12: 4.992770963730048777
     13: 4.995669424021221376
     14: 4.997662148342565097
     15: 5.003854017975645666
     16: 5.1073773467996033591
     17: 7.120227860738999395
     18: 34.785040996080490562
     19: 90.626653085283330423
     20: 99.482880706901437152
     21: 99.974010280944796624
     22: 99.9987001956356138898
     23: 99.999935009519299219
     24: 99.999996750491321346
     25: 99.999999837525084836
     26: 99.999999991876269951
     27: 99.9999999995938139692
     28: 99.999999999979690713
     29: 99.999999999998984537
     30: 99.999999999999949227
     31: 99.999999999999997462
     32: 99.999999999999999874
     33: 99.999999999999999994
     34: 99.9999999999999999997
     35: 99.99999999999999999999
     36: 99.9999999999999999999996
     37: 99.99999999999999999999998
     38: 99.999999999999999999999999
     39: 99.99999999999999999999999995
     40: 99.999999999999999999999999997
     41: 99.9999999999999999999999999999
     42: 99.999999999999999999999999999996


Как я понял, cpp_dec_float<50> просто гарантирует, что может хранить гарантированно 50 десятичных знаков, как double может гарантировать 15. А реализовано там видимо как-то аналогично — с двоичной мантиссой и экспонентой. А я храню всё десятичные знаки, сколько бы их ни было, а точность — это просто количество знаков результата после запятой (а не всего) при делении
Маньяк Робокряк колесит по городу
Отредактировано 15.05.2021 1:35 Marty . Предыдущая версия . Еще …
Отредактировано 15.05.2021 1:33 Marty . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.