Pull to refresh

Comments 69

Странную вы базу для чисел выбрали...

Есть прекрасная книга по арифметическим операциям - В.К.Злобин В.Л.Григорьев Программирование арифметических операций в микропроцессорах

> Странную вы базу для чисел выбрали…

У Decimal типа в .NET точно такая же — миллиард как 9 десятичных цифр в одном uint32, всего в числе 3 таких составляющих и ещё одна цифра отдельно. Так что выбор не уникальный.

Мне стало интерсно, я пошел в документацию -

The binary representation of a Decimal value is 128-bits consisting of a 96-bit integer number, and a 32-bit set of flags representing things such as the sign and scaling factor used to specify what portion of it is a decimal fraction.

там нет никаких двоично - десятичных представлений (да и странно это). Обычное 96 битное число.

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

В советской традиции, да, 0 не натуральное. В американской, для сравнения, 0 входит в натуральные, а положительные у них 𝐙⁺. Не знаю про другие страны посредине ;)
Иногда это обозначают 𝐍⁺ и 𝐍₀.

> Будет использоваться алгоритм Анатолия Алексеевича Карацубы. Это не сложный алгоритм, он основан на парадигме «разделяй и влавствуй».

Один коллега писал, что алгоритм Фюрера получился очень легко. Я не пробовал, но можно сравнить.

> В этом алгоритме ничего примечательного нет, стандартное деление уголком.

Вот тут можно было как раз сэкономить по максимуму через промежуточный делитель и предвычисление обратного множителя. В «Hackersʼ delight» описано в подробностях.

> LongInt operator /(LongInt number_thirst, LongInt number_second) {

Почти мелочь, но точно thirst — то есть «жажда»? Я ожидал first.

> Единственное, что стоит заметить, так это то, что остаток, согласно математическим правилам всегда натурален.

Термин для такого — E-деление (евклидово). Ссылка.

В общем, конечно, «ещё одна 100500-я реализация», но выглядит корректно.

Дополнительно замечу, что для целых десятичная арифметика обычно не используется, потому что эффективность «так себе». А вот для плавающей точки десятичная реализация имеет супер-смысл там в финансово-экономических расчётах. Но там ещё надо тщательно следить за точностью в цифрах после запятой.

Спасибо за комментарий! Учел и некоторые незначительные моменты (вроде "thirst" вместо "first" (-: ) исправил.

Я извиняюсь, но что этот пост делает на хабре? Подобные изыскания проживают на geeksforgeeks и тому подобных сайтах. Очень здорово, что вы познаете C++, но задание не является чем-то сверхсложным или необычным, длинную арифметику реализуют все студенты к концу первого курса.

Понимаю, что задача не сверхсложная, но все-таки попытаюсь объяснить причину публикации именно на Хабре. Прошерстив русскоязычный интернет мне не удалось найти нормально описанных библиотек длинных чисел с реализациями быстрых алгоритмов и хоть немного насыщенным набором функций, так что материал, смею предположить, по-своему уникальный.

P.S. Под "мне не удалось найти нормально описанных библиотек длинных чисел с реализациями быстрых алгоритмов и хоть немного насыщенным набором функций", естественно, имеется ввиду не удалось найти среди доступно описанных библиотек на русском языке.

Библиотек для работы с длинными числами очень много. Можно привести в пример тот же GMP. Но я уточнил, что имею ввиду именно доступно объясненные библиотеки на русском языке. Далеко не всякий человек может и хочет читать сухой английский в файлах с кодом, а статья с форматированием на Хабре - довольно доступный и легкий способ получения информации.

Быть может помогает Хабру остаться Хабром, а не сборником переводной публицистики.

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

Прежде всего, такие библиотеки надо начинать писать с unit тестов - потому что гарантированно будет куча труднонаходимых ошибок.

Вместо зоопарка операторов сравнения - лучше использовать operator <=>, современные стандарты очень упрощают жизнь.

Конструкторы из int - лишние, достаточно самого большого типа long long.

Спасибо за комментарий!

Про необходимость тестирования - полностью согласен. Жаль, что писал код без чего-то подобного. Но все-таки я потратил довольно много времени на ручное тестирование, рассматривая все проблемные варианты, что пришли в голову, а также сверяя результаты сложных операций с результатами аналогичных операций с другими материалами, где уже реализованы длинные числа.

Про оператор <=> - изучу. Не знал о такой возможности.

Про возможность минимизировать количество конструкторов тоже не знал. Попробую что-нибудь подобное.

Дополню про сравнения — вместо сравнения массивов данных ручками есть std::lexicographical_compare.

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

добавления заголовка с алгоритмами, а это немного увеличивает вес бинарника

вы похоже плохо знакомы с C++
блокирует использование подобного класса во многих олимпиадах по программированию

а где было в посте что-то про олимпиады? олимпиадное программирование это «ненормальное» программирование, в том плание что его правила никак нельзя применять к здоровому обучению хорошим практикам. А современное их состояние — использовать алгоритмы так где они дают более чистый и лаконичный код.

Вы несомненно правы и, вероятно, куда больше знаете о C++, нежели я (ни в коем случае не сарказм), но все-таки основная задача этой статьи показать людям что примерно находится под капотом библиотек для длинных чисел, а не создать что-то совершенное, поэтому, ручное сравнение мне кажется более логичным в рамках этой статьи.

Хорошо, я вашу позицию, намерения и способ их реализации теперь понял. Хочу сказать что со способом донесения до читателей (раз вы делаете образовательный контент) в принципе не согласен.
Я бы если бы делал тоже самое, постарался бы объяснить базовые операции, а не вываливал код циклов (т.е. даже в принципе не приводил бы этот код).
Но мы тут в этом не сойдемся, боюсь.

Спасибо в любом случае за труд; но постарайтесь сами тоже после написанного критично оценить результаты (не сейчас, может быть позже).
Ну и неконстантный рекурсивный оператор сравнения это уже г-код, извините.

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

mapron имеет в виду, что вместо
friend bool operator ==(LongInt number_first, LongInt number_second);

должно быть
  friend bool operator ==(const LongInt& number_first, const LongInt& number_second);

ну, или для функции-члена
bool operator ==(const LongInt& number_second) const;

const — потому что вы не меняете аргументы, а без указания const вы не сможете принимать, ну, константы.
ссылки — чтобы не копировать вектора, ибо зачем?
Вам сейчас ответят что это все для новичков С++, чтобы они суть поняли, зачем им все эти ссылки да константы. У автора одна шарманка на все советы)

Почему же на все советы? Действительно, так будет лучше, не заметил. Просто сначала не понял о чем речь.

Имеется в виду что достаточно определить один строгий и один нестрогий оператор сравнения, или же действительно есть некий operator <=> , выполняющий эту роль? Запрос c++ operator +"<=>" мне ничего не выдал.

гуглить надо spaceship operator c++20

Я не совсем специалист по C++, но зачем операторы определять как friend?

Объект помеченный как "friend", то есть дружественный, в отличии от объекта не отмеченного как "friend" имеет доступ к приватной части класса. В данном случае, нам нужен доступ к приватной части класса ради доступа к знаку числа и вектору разрядов.

А зачем так извращаться, если можно просто объявить оператор как член класса?
Единственное исключение — это


std::ostream& operator <<(std::ostream& ostream, const LongInt& number)

, но в нём вы не используете доступ к приватным полям.


P.S. Вам бы получше с C++ разобраться: в половине случаев у вас передача аргумента идёт по значению. Зачем?

UFO just landed and posted this here
Код должен содержать необходимый набор функций, чтобы используя его можно было спокойно проводить проверки на простоту и выполнять некоторые другие необходимые и популярные операции

И где этот необходимый набор? Как вы имеющимся классом на простоту проверять собираетесь? Обычно a^(p-1) % p используют для проверок где p-как раз то самое число что проверяют.

ps: Какие операции популярны в 2021?

Спасибо за комментарий!

Проверять числа на простоту собираюсь самым простейшим способом - перебором всех (или не всех, есть много несложных способов исключить ненужные делители) делителей до sqrt(n) + 1.

Под "популярным операциями" может выразился не слишком корректно. Я имел ввиду, чтобы с классом можно было работать почти так же комфортно, как и со стандартным типом int. То есть чтобы можно было одной строчкой возводить в степень, считать факториал, считать корень, считать НОД и НОК (на случай, если программисту вдруг понадобится сделать обыкновенные дроби), получать максимальное / минимальное из двух чисел (а не писать блок условий на 5 строк) и так далее.

Самое плохое для автора - когда читатель-комментатор, видя малёхонький косяк, задаёт вопрос автору и получая естественный ответ, начинает умничать. По итогу демотивированный автор навсегда покидает поле.

Автор молодец! Не пожалел времени на реализацию и написание статьи. Всяко лучше, чем переводной науч-поп. По коду тоже всё норм. Код можно улучшать бесконечно и всё-равно найдётся какой-нибудь ворчун

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

Здесь творится такой мрак, что спасает его только то, что компилятор смог его оптимизировать из-за расположения всего и вся в одном файле

Здесь творится не мрак, здесь видно, что есть пробелы. Если автору будет интересна тема, то со временем он сам всё поправит и порадует новыми статьями с более высоким уровнем владения плюсов. Хз кого там хантят, но если человек не понимает очевидную психологию, то с ним трудно работать из-за отравления среды

Для автора: если тебе интересна математическая тема, тот вот тут https://leetcode.com/problemset/all/ есть интересные задачки

На основе int64_t работало бы быстрее. А то и на основе __int128, если он доступен.

Ну и заявляется быстрота, но нет сравнения хотя бы с тем же multiprecision.

Пока не перешли на модули, работу со строками, а тем более с потоками лучше было вынести в отдельный заголовочный файл, iostream — тяжёлый для компиляции. Иначе если у вас тип используется а большой части проекта, это будет заметно.

Спасибо за комментарий!

Немного не понял, что значит "на основе int64_t работало бы быстрее". Имеется ввиду, вектор стоит делать из 64-битного типа данных и, соответственно, увеличить базу? Но как тогда выполнять, скажем, умножение в столбик? В каком типе переменной хранить результат умножения?

Конкретно для умножения можно оперировать половинами, через >>32 и 0xffffffff.

На основе int64_t работало бы быстрее

Не факт, ой не факт. Если сами вычисления не очень тяжелые, но нужно много выводить результаты, то int64_t повесится на этой операции (вам придется делать % 10 для каждой выводимой десятичной цифры). А у автора как раз всё отлично.

Да ну? И чем же перевод в десятичную форму N uint64_t (давайте про беззнаковые, чтобы не усложнять всё) тяжелее, чем N*2 uint32_t? Ровно то же число операций.

Не говоря уже о том, что вычисления всё-таки для таких типов - более частый кейс, чем вывод. А в вырожденных случаях можно и кэшировать.

Тем, что здесь каждые 9 цифр независимы. Нужно 2*9*N 32-битных операций всего. Для вашего варианта с лонгами нужно для каждой цифры:
1. Взять остаток от деления длинного числа на 10 (это N * N / 2 операций, упс)
2. Вычесть остаток из числа
3. Поделить на 10 (еще N * N / 2 операций)
И так lg N раз, где lg = log10
Итого N2 lg N, овердофига. Если «математический» алгоритм, который вы считаете, имеет сложность M log M или быстрее, у вас печать конечного результата может занять больше времени, чем расчет.

Вы ошибаетесь про квадрат. Ошибка в том, что для получения остатка от деления вам не нужны все части, нужно только младшее. Для перевода достаточно переводить части и правильно обрабатывать случай "на стыке". И сложность тут линейная.

Нет, это вы ошибаетесь. 2 ни в какой целой степени не кратно 10.
В любом случае, делить на 10 всё равно придётся.

Ну ок, для остатка. Для деления, да, нужно N^2.
Но всё равно называть это "преимуществом" странно, т.к. вырожденный случай. Например, перевод в hex-представление (тоже весьма распространённое) в варианте автора будет сложнее.

Откуда у вас там N^2?

В реальности (не смотрите на алгоритм в этой статье) результат деления - это сразу и остаток и частное.

Поэтому:

while (n != 0) {

// r - остаток ( это цифра для текстового представления), q - частное

div_mod(n, 10, q, r)

n = q

}

Пусть N — длина числа. Итераций цикла while будет O(N). Каждое деление — O(длина числа). Длина каждый раз уменьшается максимум на 1. Общее время выполнения — N+N-1+...+2+1 = O(N^2).

Алгоритм деления выглядит так (пусть делимое и делитель хранятся блоками):

  1. Цикл (количество блоков делимого минус количество блоков делителя) раз

  2. Стадия определения очередного блока часного - по двум старшим блокам делимого и одного блока делителя определить блок частного)

  3. Стадия получения частичного остатка - цикл по всем блокам делителя - умножаем блок делителя на текущий блок часного и вычитаем из соответсующего блока текущего частичного остатка

  4. Результат - у нас есть частное и остаток

Как можно увидеть, деление зависит только от размеров блоков. Поэтому чем больше размер блока, тем быстрее алгоритм.

Реальных операций: (разница количества блоков делимого и делителя) умножить на количество блоков делителя)

Как можно увидеть, деление зависит только от размеров блоков.

Что? Вы же сами написали:


Реальных операций: (разница количества блоков делимого и делителя) умножить на количество блоков делителя)

Оно зависит от длины ответа и длины делителя в блоках. Да — больше база — меньше блоков — быстрее алгоритм. Но длина блока — она же константа, потому что процессоры не могут работать со сколь угодно большими числами (именно поэтому и возникает задача вот этих вот длинных чисел). А значит эта длина блока, как константа, не влияет на O-большое.


Кстати, поскольу мы делим на 10, которое занимает 1 блок, то вот и получается, что одна операция деления будет занимать O(N), где N длина числа, как я и сказал.

  1. Взять остаток от деления длинного числа на 10 (это N * N / 2 операций, упс)

Неверно. Для взятия остатка на 10 надо всего O(N) операций.


И так lg N раз, где lg = log10

Берется логарифм самого числа — он пропорционален длине. Т.е. это самое N.


Но, да, если числа хранятся с двоичной базой, то операция вывода всего числа будет O(N^2), когда как для десятичных чисел это делается за O(N).


Но, если вывод в десятичной системе — редкая операция, то имеет смысл иметь базу 2^32 — ускоряются вычисления.

> Для вашего варианта с лонгами нужно для каждой цифры:

Пусть у нас в int64_t (uint64_t, неважно) число от 0 до 10^18-1. Разделив его на миллиард, получим частное и остаток оба от 0 до 10^9-1, которые влезают в int и с которыми можно дальше обращаться получением цифр по одной, как у автора. Само деление, так как оно на константу, компиляторы заменяют на обратное умножение и операция занимает, грубо говоря, 4 такта.
Точно так же можно и дальше. Если надо получить 9 цифр, можно, например, разделить дважды на 1000, и группы по 3 цифры выводить отдельными средствами — было бы зачем.
Часть таких библиотек конверсии представления (сейчас не помню названия) делят не на 10, а на 100, а потом по массиву в памяти получают сразу по 2 выходных цифры.

Вот если бы было действительно представление по основанию 2^N и между лимбами, то есть лимб с индексом 0 имел бы вес 1, 1 — 2^32, 2 — 2^64 и так далее, то тут перевод в десятичный вид был бы действительно сложнее в разы (алгоритмы есть, но они громоздкие и требуют дополнительных объяснений). Но вы ж вроде не об этом говорили?

Буду краток:apt-get install libgmp-dev

Во-вторых, база должна быть меньше типа int, то есть быть меньше 2^31-1.

На всякий случай, стандарт предписывает, что размер int должен быть не меньше 16 бит.

LongInt::LongInt(signed int number) {
    if (number < 0) {
        number = number * -1;

Что будет, если number здесь равен INT_MIN (в дополнительном коде)?

Спасибо за комментарий!

Действительно, есть такая проблема, недоглядел. Уже исправил.

Есть несколько комментариев:


  • вместо флага natural лучше использовать какой-нибудь флаг sign, который или положителен, или отрицателен, ну или назвать is_negative на худой конец. natural как-то уж глаз режет слишком.


  • Иногда полезные операции — прибавление/умножение/деление/остаток от деления на обычный int. Вам стоит их реализовать в библиотеке. Это довольно простые функции и реализованные напрямую они кратно быстрее операции с маленьким длинным числом.


  • Про факториал вы перемудлири. Во-первых, если входное число действительно большое, то ждать выполнения кода можно вечность. Ибо вы там, как ни крути, выполняете n длинных умножений. Если n не влезает в int64 — смысла в этой операции нет вообще. Там и результат будет занимать экзобайты какие-нибудь, и считаться он будет вечность. Во-вторых вы там округляете tmp вниз, поэтому перекос происходит в правую сторону, выдавая сильно большие числа там. На самом деле можно даже не середину брать, а, скажем, делить в отношении 3:2 — тогда числа в умножении будут более сбалансированные.


  • при извлечении корня вместо сравнения n/x < x лучше делать n < x*x. Более того, можно обойтись практически без длинных умножений. Вам надо поддерживать длинные значения l, r, l^2, r^2, l*r. Через них сложениями и делениями на 2 можно получить m = (l+r)/2, m^2, m*l и m*r (m^2 надо вычислить в любом случае, чтобы сравнить его с входным числом, а из ml и mr можно считать уже только одно, когда уже поняли l или r заменяется на m). То же самое относится и к кубическому корню.


  • Вы в нескольких местах передаете LongInt по значению. Это недопустимо, если вы заботитесь о скорости. В нескольких местах вы это делаете только чтобы поменять знак операндов. Можно это обойти если реализовать приватные функции, которые вообще игнорируют знак чисел. Потом публичные функции смотрят на знаки и в зависимости от них вызывают нужную приватную функцию (например, функция сложения, если видит, что одно из слагаемых отрицательно — вызывает вычитание без проверок на знаки. Если оба отрицательны — вызвыает сложение и меняет знак у результата).


  • Пробовали умножение через быстрое преобразование Фурье? У него ассимптотика лучше, чем у карацубы. В сравнении, что и когда работает быстрее была бы ценность. Если длины чисел не слишком большие (миллионы цифр), то хватает точности double и умножение через FFT не требует даже никаких рекурсивных разбиений и работает за O((n+m) log (n+m)).


Спасибо за комментарий!

  • По поводу флага natural - тут, как бы это и абсурдно и смешно не было - надо думать. Слово signed - служебное, если назвать sign - не до конца понятно, что значит true, а что false, а is_negative немного путает, ибо положительные числа ассоциируются скорее с true, чем false.

  • Возможно это действительно стоит сделать! Я подумаю.

  • По поводу использования long long / unsigned long long вместо LongInt в аргументе функции факториала - можно, но лично я не вижу в этом особого смысла. Почти все время вычисления факториала в этой функции - сухие умножения. Остальные расчеты (по крайней мере как я понимаю, поправьте, если не прав) занимают на столько мало времени, что их можно с легкостью записать в погрешность при замерах даже на больших значениях факториала.

  • Тут полностью согласен. Сам что-то не додумался. Попробую, и, возможно, исправлю.

  • Тут тоже согласен. Так же попробую исправить.

  • Умножение через Фурье сделать пытался, но столкнулся с рядом сложностей. Во-первых, доступного материала в интернете по этой теме не так много как хотелось бы. Во-вторых, алгоритм все-таки сложный и требует довольно много времени на понимание.

Про фурье — вот даже на хабре есть статья: https://habr.com/ru/post/113642/


Cуть в том, что вы представляете цифры вашего длинного — это коэффициенты многочлена. Далее, перемножить 2 числа — то же самое, что перемножить такие многочлены и сделать переносы.

А вы не проводили случайно замеры, как быстро будет работать ваша реализация деления в столбик, особенно для очень длинных целых, как заявлено в заголовке ?!
Дело в том, что я писал похожую реализацию для своей библиотеки slimcpplib, но не для больших целых, размер которых фактически ограничен размером доступной памяти, а для длинных, которые не помещаются в нативный размер платформы. Так вот реализация деления в виде класcического столбика, даже для 128-битных целых, для меня уже была очень медленной и неприемлемой по скорости, а это относительно небольшие числа. В итоге я остановился на алгоритме Дональда Кнута. Основная идея: мы можем разбить делимое ровно на две части и частное считать независимо оперируя только его половинами. В итоге, как только мы рекурсивно разбиваем число до приемлемого размера, мы можем использовать обычное аппаратное деление.

Еще не дочитал, но однозначно лайк.

Тут на днях вышла другая "обучающая" статья про длинные числа на С++, где числа хранились в строке. Боль.

Как хорошо, что на хабре еще есть и статьи вроде этой. Код глянул по-диагонали, но уже лайкнул, продолжай писать!

Окей, а теперь вещи, которые мне в реализации не нравятся.

* Про десятичную базу уже писали, но тут замечу, что это может быть оправдано в некоторых случаях, но тогда об этой необходимости стоило бы упомянуть.
* В каждом конструкторе - конвертер в строку - это мрак. Ну чем не устраивают просто арифметические операции? Это получается, что мы при прибавлении к длинному числу простого инта будем неявно вызывать конструктор который внутри каст к строке вызывает. У нас `d += 2` будет тормозить адски. Замерьте время цикла `for (LonfInt i(0); i < LongInt(10000000); i += 2)` . Не удивлюсь, если в этой реализации окажется медленнее чем возведение в степень.
* Число имеет смысл хранить в обратном порядке: младший разряд в v[0], старший в v.back() . И проще операции некоторые делать, и на четность проверять и т.п. Например, в вашей же реализации _zeros_leading_remove числа удаляются из начала вектора, а не конца (О(n) вместо O(1)). А теперь посмотрим на shift_right, который k раз вставляет 0 в начало вектора (каждая операция - O(n)). А эта операция вызывается при каждом (!!!!) сложении. Тут оптимальностью, уж простите, даже не пахнет. При записи числа в обратном порядке новые знаки добавлялись бы в конец вектора строго по необходимости, а надобность в удалении ведущих нулей просто бы отпала.
* Оператор << который сначала преобразует в строку, а потом по символу выводит - это трусы поверх колготок. Удобнее сделать сначала оператор, а каст в строку через stringstream . Хотя тут не все так однозначно, но текущая запись в строку... Да там одних аллокаций памяти - на каждый элемент вектора по одной.
* Давайте поговорим про аллокации памяти. Сама по себе операция долгая - системный вызов, а в многопоточном сценарии еще и требующий от ОС контроля параллельных операций (heap он как СССР - на всех один). Каждый возврат по значению числа LongInt будет требовать аллокации памяти для нового вектора, а также копирования оного. Даже если вектор небольшой, аллокация - уже дорогостоящая операция. И, внимание, вопрос: зачем у внутренних функций, типа shift_<side>, remove_zeros, mult_kara возврат по значению? Сделать их inplace не сложно, а если мне понадобится копия, я явно вызову `LongInt b = a;` и у него shift . К чему всегда делать полное копирование числа? А оно много раз вызывается в рекурсивной реализации умножения, и я не уверен, что компилятор это сумеет оптимизировать.

Ну и еще вагон претензий мест для улучшения.
Самая главная глобальная претензия: нельзя использовать строки как промежуточное состояние арифметических операций. Никогда. Ну и за копированием векторов надо следить: это очень частая причина деградации скорости кода.

А вообще, статья неплохая. На фоне сегодняшнего хабра - даже сильно выше среднего. К тому же, есть о чем подискутировать. Удачи в дальнейшем!

Спасибо за комментарий!

Согласен, что есть уйма вещей, над которыми надо поработать.

Но вот по поводу хранения числа в обратном порядке есть некоторые вопросы. Про удобство с точки зрения понятности кода не говорю, дело субъективное, но вот с точки зрения скорости реализации - хочу кое-что уточнить. Да, действительно, функции сдвига, используемые при сложении и вычитании, а также функции удаления лидирующих нулей будут так работать быстрее, но есть одно НО.

В реализации используется алгоритм Карацубы, который использует сдвиги в другую сторону. При хранении в "правильном" порядке, то есть в текущем, эти сдвиги делаются как раз за О(1), а если хранить в зеркальном - то как раз О(n). Соответственно, зеркальное хранение замедлит выполнение алгоритма умножения, а алгоритм умножения, ГОРАЗДО БОЛЕЕ зависим от сдвигов, чем вычитание и сложение. И я это еще не говорю о том, что на практике, работа с длинным умножением, длинным делением и извлечением длинных корней (а последние два активно используют умножение) гораздо более чаще встречается, чем необходимость складывать огромное количество огромных чисел. Поправьте, если не прав.

reverse в начале операции умножения, reverse в конце операции умножения - 2 операции O(n). Мне это видится куда более элегантным решением, а на фоне общей сложности умножения эти две операции будут незаметны.
Зато сложение длинного числа с маленьким (aka `x += 2`) будет выполняться почти всегда за время пропорциональное длине меньшего числа, а не делать shift по размеру большего числа.

Кстати, раз уж я снова тут, в cppreference в разделе Binary arithmetic operators делают operator+ через operator+=, а не наоборот и второй аргумент передают по константной ссылке. Тоже в качестве предложений по улучшению кода: избегаем лишнего копирования.

По поводу умножения. У вас там кстати, не работающий совсем код написан. Во-первых в части, где вы делаете наивное умножение вы должны не присваивать ячейке |number_first_position + number_second_position + 1|, а добавлять туда. Потому что одно и та же сумма индесов может быть получена кучей вариантов. Например 0+3=1+2=2+1=3+0. Далее, вы там пытаетесь делать нормализацию, перекидывая в следующий разряд, но вы можете его сделать больше базы. Надо после перемножения всех цифр нормализовать число. Практически все настоящие библиотеки длинной арифметики содержат метод Normalize — который делает переносы. Потому что этот код нуджен везде.


Далее, никаких сдвигов в карацубе не надо делать и ничего копировать из входных чисел. Просто функция должна принимать в качестве параметров не Longint, а итераторы на интервал цифр в каком-то входном числе.


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

всегда восхищали люди требующие для минимального конфига на сmake последнего (ну уже почти последнего) cmake

Поставил эту версию только потому что компилировал при помощи нее. Ставить более старую не стал, так как черт его знает, какие ошибки могут возникнуть на более старых версиях. Если есть необходимость - можно легко заменить циферку в файле.

Этот конфиг своего рода "hello world" только на cmake, отсюда и удивление к жесткому требованию))

Прошло очень много времени и я, вспоминая этот проект, случайно задумался об оптимизации работы с памятью. Оптимизировал, после чего операции связанные с умножением (на других не тестировал) стали выполняться многократно быстрее. 1 000 000! теперь считается всего за 16 секунд, а 2 в степени 10 000 000 - за 4. Если кому интересно, то все так же в репозитории на гитхабе.

Only those users with full accounts are able to leave comments. Log in, please.