Комментарии 52
bignum::bignum()
Не знаток C++, но разве в нём не CamelCase для классов используют?
"_isNegative = other_value < 0 ? true : false;"
- это за пределами добра и зла.
За такое с технического собеседования сразу вылетают.
Моя задача была показать как можно больше вариантов написания кода. Описание логики через тернарный оператор является одним из таких способов. Данный пример показывает, что и в С++ можно такое реализовывать в одну строчку. +Если это не показывать, новички не будут знать о существовании таких методов.
А именовать локальную переменную начиная с "_" перед этим проговорив что с "_" начинают приватные члены класса?
Это намеренное введение в заблуждение.
Не каждый начинающий не забудет ставить this-> перед членом класса и будет долго думать почему его переменная присваивается не туда.
ИМХО, демонстрация какой-либо конструкции языка в месте где она не нужна, хуже чем отсутствие её демонстрации вообще. Новичок может решить что подобная запись является нормой и через неуоторое время ему будет сложно перестроиться.
del
А почему это плохо?
и что плохого в этой записи?
ну лично мне режет глаз _isNegative
я бы так написал:
const bool isNegative = other_value < 0 ? true : false;
На всякий случай, если кто вдруг подумает, что так пишут на C++. Это не так. Никто не будет хранить число в строке и конвертировать его туда и обратно. Есть, например, библиотека Boost.Multiprecision и, уверен, ещё несколько библиотек, которые позволяют работать с большими интами без оверхеда.
Похоже, вы невнимательно читали статью, если вообще читали. В самом начале, я написал, что библиотека реализована на string переменных и это не есть хорошо. Я написал, что гораздо лучше использовать вместо этого. Предупредил, что многое сделано для упрощения. Да и настоящие математические библиотеки всегда будут быстрее самодельных и я не стремился их обогнать. Моя задача предельно проста - начать с азов объяснять С++ и показывать разношёрстные примеры, как выполнить те или иные действия. Если вы считаете, что статья не подходит для начинающих, я готов вас выслушать.
Вы дважды упомянули public и private но ни слова не сказали о том, что стоит за этим, ни одного слова об инкапсуляции. А ведь это один из столпов ООП в С++.
Я же описал для чего мы используем поля public и private. И немного затронул тему геттеров. getValue() - является одним из таких, где возвращает поле _value прямиком из private. Возможно, нужно было создать 2 класс и показать наследование, чтобы углубиться в ООП, но мне показалось, что это будет перебором.
Инкапсуляция к наследованию никак не относится. И 2-й класс действительно будет лишним.
Ограничение доступа к членам класса это побочный эффект, основное их предназначение -- сокрытие деталей реализации, или инкапсуляция.
Вы могли бы описать public члены класса как некий интерфейс к реализации. Тогда детали реализации становятся не важны для пользователя класса. И модифицировать реализацию можно сколь угодно часто, при этом программа использующая этот класс не меняется, и ничего не знает об глубинных изменениях в классе.
Надо было написать вариант для чисел фиксированного размера на шаблонах, конечно. Волноваться не надо, у вас не получится невзначай математическая библиотека. Зато будет продемонстрирована идея, лежащая за такой библиотекой и показаны уникальные свойства C++. Если же вы не в силах сделать это, то разумнее было бы подобрать другой пример.
Ваше же решение написано на C с классами, может быть перенесено на массу языков типа Java, C#, а главное - идеологически неверно. Я бы сравнил его с поиском по отсортированному массиву последовательным перебором. Начинающих надо учить на упрощённых примерах, конечно, но не на неправильных.
Вы, наверное, и для is-even будете буст подключать?
Что же, сегодня, мы начнём писать собственную библиотеку больших чисел, полностью своими руками c 0, и узнаем, так ли страшен С++, как его малюют?
Полностью своими руками с 0. Так что о подключении сторонних библиотек и мысли не было. Да и статью хотелось сделать не такой сложной. А можно ли было бы сделать оптимизирование? Да, конечно, я это говорил прямым текстом в начале статьи.
За идею статьи ставлю плюс, а за реализацию - минус.
1) В std::string bignum::getValue() сразу стреляем себе в ногу создавая переменную _value перекрывающую поле класса.
2) Продолжаем рубрику вредные советы кидая исключение в конструкторе. Причем, с неинформативным сообщением. Вот что должен понять программист, увидев "-123 it's not a number"? Ведь, как раз -123 число.
3) Зачем перегружаем конструктор и для const char* и для std::string? Сами прямо задаете этот вопрос, но отвечаете мимо. Конструктора с std::string вполне хватило бы.
Я не совсем понял про перекрытие поле класса. Нам же нельзя позволить пользователю изменять данный параметр (поле). Получить его, он может, изменить - нет. На самом деле, эта функция заглушка, в 1 части я просто не успел рассказать про перегрузку операторов потокового вводы/вывода.
В первой ревизии ошибки кидались через специальную функцию my_exeption и было дополнительное поле _isNum. При каждой математической операции данное поле проверялось на true. Спустя время было решено отказаться от данной реализации, по причине громоздкости кода. P.S. вывод ошибки с минусом и правда неверный, я забыл добавить if(_isNegative) добавить минус в начало строки.
Честное слово, у меня такой же вопрос к моей Visual Studio. Ей недостаточно одного string конструктора. На самом деле, гораздо лучше было бы использовать функцию шаблон, но это уже во 2 части.
Спасибо за отзыв!
А вообще конечно поддержка длинных чисел должна быть встроена в язык на уровне литералов.
Для чисто учебного проекта норм. А вообще, хранить разряды в char-ах неэффективно, так только чуть удобнее для человеческого восприятия при отладке. Обычно переходят к системам счисления, основанным на длине машинного слова. Допустим, с основанием в 32 бита (половина от 64, чтобы было удобнее - избегать обработки переполнения при поразрядных операциях). Это быстрее и занимает меньше памяти.
О неэффективности данного подхода (реализация через string) было сказано в самом начале статьи. Я слышал, что лучше всего использовать булевую алгебру. Ваш подход звучит очень интересно, я бы с удовольствием изучил его.
Если основывать на системе счисления, не являющейся степенью десятки, то придётся переводить в десятичную систему и обратно. Наивный подход будет работать за квадратичное время, получим как в Python или Java: вычисления мгновенные, а вот вывод числа на миллион разрядов невозможен. Является ли это проблемой — зависит от задачи.
Ну, машинная математика, основанная на степени двойки вас же устраивает. =)
Устраивает, потому что вывод работает.
Если у меня задача, в которой надо зачем-то посчитать большое десятичное число (обычно в развлекательных/учебных целях), то перестаёт устраивать, потому что у меня перестаёт работать вывод ответа на экран. Например, запустите на питоне вот такой код:
x = 10 ** 1000000 + 4
print(x % 10)
print(x)Само число x из миллиона знаков посчиталось быстрее, чем за секунду, равно как и его остаток от деления на 10. А вот вывод этого числа целиком занимает некоторое время, потому что идёт перевод из двоичной системы в десятичную неэффективным способом.
Обычно все-таки вывод занимает незначительную долю в тех расчетах, для которых требуется bignum. И почему тормозит вывод еще нужно смотреть. Особенно в Питоне. Может быть, print зашился на аллокации памяти. Или тормозит какой-нибудь форматтер вывода для bignum. Или, банально, компилятор лениво вычислил x не в момент декларирования операций, а перед использованием, выполняя print(x % 10), а вы решили что это перевод в десятичную систему. Правильный тест зачастую сложнее алгоритма, который он тестирует.
Обычно все-таки вывод занимает незначительную долю в тех расчетах, для которых требуется bignum.
Да, зависит от задачи, всё верно.
И почему тормозит вывод еще нужно смотреть
Он не просто тормозит, он у меня минуту работает. А вот если выводить как print(bin(x)) — то пару секунд.
Я не спец в CPython, но файл с названием longintrepr выглядит многообещающе: вот тут нам сообщают, что всё действительно хранится в двоичной системе счисления (точнее, с основанием 2**30), а вот тут парой вложенных циклов переводят число из одной системы счисления в другую перед выводом в строку. Даже на Кнута сослались.
Вывод: вывод длинного числа в CPython работает за квадратичное от длины числа время. 10**12 операций — это не шутка, даже если соптимизировать в десяток-сотню раз.
во-первых, какой смысл в печати числа, занимающего несколько страниц? Человек все равно его воспринимает лишь на уровне "ух, какое большое".
во-вторых, библиотека GMP, которую уже упоминали в комментариях, доступна и в питоне. Добавление к Вашему кодуimport gmpy2
print(gmpy2.mpz(x))
творит чудеса - все преобразуется и печатается "мгновенно" )
во-первых, какой смысл в печати числа, занимающего несколько страниц? Человек все равно его воспринимает лишь на уровне "ух, какое большое".
Для развлечения или сверки реализации с какой-нибудь эталонной. Наверное, для принятия бизнес-решений действительно не нужно больше десятка-другого точных знаков, хотя я не специалист.
во-вторых, библиотека GMP, которую уже упоминали в комментариях, доступна и в питоне.
Так я же не против библиотек. Я против догмы "в двоичной системе всё точно будет быстрее" — нет, не всегда будет.
А в GMP просто используют более сложный алгоритм перевода между системами счисления с разделяй-и-властвуй и наверняка быстрым делением из того же GMP: https://github.com/alisw/GMP/blob/2bbd52703e5af82509773264bfbd20ff8464804f/mpn/generic/get_str.c#L307 . Я ожидаю O(n log^2 n) и ещё кучу неасимптотических оптимизаций сверху. Так что результат вполне ожидаемый.
Как по мне, "библиотека для работы с большими числами" очень плохой пример для демонстрации возможностей С++. Вам осознано придется упускать кучу важных моментов/нюансов, приследую "обазовательные" цели.
Теперь по статье/коду:
доступа по умолчанию public, а в class — private
При объявлении шаблонных параметров мы можем использовать class, а struct нет. Какой посыл то в этой информации?
#pragma once — нестандартная, но широко распространённая препроцессорная директива
Что значит нестандартная? Не описанная в ISO/IEC 14882? Что такое препроцессор? В чем разница между #pragma once и #ifndef #define #endif ? Статья же для "новичков", правда?
Всё просто, чтобы подключить внешний код, необходимо использовать именно заголовок.
Нет.
Итак, для начала нам необходимо создать класс и его поля:
Большинство проектов на C++ используют последовательность из public/protected/private.
size_t _size;
Зачем нам хранить size, кода он есть в std::string? Еще одна возможность стрельнуть себе в ногу или создать неконсистентность?
Приватные переменные, как правило, пишутся через ‘_’.
Заклинаю вас, никогда так не делайте и не давайте таких советов.
https://eel.is/c++draft/lex.name#3.2
Далее нам необходимо создать перегрузку конструктора класса
Кому необходимо? Почему необходимо? Почему именно long long int?
Перегрузка конструктора \ функции \ оператора
Подводные камни? Неявные преобразования типов? AFAIK не во всех языках есть перегрузки операторов, конвертирующие конструкторы, конвертирующие операторы и т.д. Неплохо было бы хоть немного описать что это за зверь.
parsStringToBigNumParams()
Почему бы не показать как сделать сразу хороши и рассказать про delegating constructor?
Заклинаю вас, никогда так не делайте и не давайте таких советов.
https://eel.is/c++draft/lex.name#3.2
В данном случае нарушения нет, такие символы как члены класса, локальные переменные, методы и переменные внутри блока namespace - не являются находящимися в "global namespace".
Мне кажется, в реализации много мест, которые можно и нужно сделать гораздо аккуратнее. Даже если считать, что хранение по десятичным разрядам — это окей с точки зрения быстродействия и поддержания инвариантов.
Из алгоритмического:
Убрать поле
_size— либо оно всегда равно_value.size(), либо это что-то непонятное. Незачем усложнять инвариант класса. Можно забыть случайно обновить, а так код короче станет.Строго описать допустимые комбинации значений для оставшихся полей. При наивной реализации очень легко огрести от ведущих нулей, знакового нуля, вычитания чисел похожей длины.
Из C++-специфичного:
Использовать member initialization list в конструкторе вместо переприсваивания полей.
Не начинать переменные с
_— это допустимо для полей, но, например, для глобальных переменных — неопределённое поведение (undefined behavior, UB).Принимать строки по константным ссылкам, где можно. Или по значению и перемещать. В конструкторе, например, сейчас лишнее копирование.
Можно сделать user-defined literal.
Для тестов удобно взять какую-нибудь библиотеку юнит-тестов вроде onqtam doctest.
Дальше посмотрел на код вашей библиотеки на GitHub:
Вместо своих методов
swapможно использовать стандартныйstd::swap. К тому же их совершенно незачем делать методами, могли бы быть свободными функциями, причём видимыми только внутри.cpp. А для этого их стоит заключить в unnamed namespace.Функцию сравнения чисел можно написать гораздо короче и проще, если использовать паттерн вроде
if (x != y) return x < y;.Кажется, что есть много дублирования кода между разными функциями сравнения, сложения и вычитания. Концептуально случаев очень мало, но у вас, мне кажется, многовато получилось.
Спасибо за такой информативный отзыв. На счёт _size переменой. Она и правда является лишней, спасибо всем, кто подметил это. В своё время, я создал её, потому что думал, что взять значение из _size гораздо выгоднее, чем высчитать str.size().
Насчет кода на GitHub: проводится масштабна оптимизация. Swap функцию я решил написать в виде typedef функции.
По поводу if(x!=y) return x<y. Красивое элегантное решение, но оно мне не подойдёт, так как приходится сравнивать числа поцфыорно (если можно так сказать).
Спасибо большое за отзыв!
Красивое элегантное решение, но оно мне не подойдёт, так как приходится сравнивать числа поцфыорно (если можно так сказать).
Можно в цикле то же самое написать. Ну и раз уж у вас всё равно цифры хранятся как строчки — то можно сначала сравнить по длине, а потом просто как строчки при помощи <, он поддерживается std::string. Правда, тут надо аккуратно с инвариантами.
Можно в цикле то же самое написать. Ну и раз уж у вас всё равно цифры хранятся как строчки — то можно сначала сравнить по длине, а потом просто как строчки при помощи
<, он поддерживаетсяstd::string. Правда, тут надо аккуратно с инвариантами.
Можно сразу оператором. Не стоит недооценивать авторов имплементаций STL, сравнение размера там, конечно же, есть.
template <class _Traits>
constexpr bool _Traits_equal(_In_reads_(_Left_size) const _Traits_ptr_t<_Traits> _Left, const size_t _Left_size,
_In_reads_(_Right_size) const _Traits_ptr_t<_Traits> _Right, const size_t _Right_size) noexcept {
// compare [_Left, _Left + _Left_size) to [_Right, _Right + _Right_size) for equality using _Traits
return _Left_size == _Right_size && _Traits::compare(_Left, _Right, _Left_size) == 0;
}
Я, лет 15 назад, начинал писать подобный класс для работы с числами большой длины и операциями над ними. Уже и не помню на чём там остановился, но закончить не получилось из-за недостатка времени. Да, и делал просто для интереса. В таких классах, особое внимание нужно уделять оптимизации количества и сложности операций. Иначе, работа с переменными этих классов будет отнимать много времени. Критично для высоконагруженных систем. Хотя, в простых проектах, с небольшим числом вычислений, может подойти.
Чуть короче.
std::string bignum::getValue() const
{
if (_isNegative)
return "-" + _value;
return _value;
}А от пустой строки на входе падать не будет?
для учебного проекта вполне себе норм
Говорят, если на Хабре разделы комментариев и раздел статьи поменять местами, он станет намного информативнее./s
Создание статической библиотеки на С++ для работы с большими числами