Третья часть из серии статей про реализацию больших чисел на C/C++, в начале по традиции ссылки на предыдущие части.
Наконец я добрался до реализации самых интересных операций. В совокупности с предыдущими наработками наши большие числа уже можно использовать для реализации различных алгоритмов, например, из области криптографии. О них я тоже скорее всего напишу, но уже чуть позже.
Умножение больших чисел
читать далее «Умножение больших чисел — реализация на C/C++» →
Приветствую всех, это вторая статья из серии про реализацию больших чисел на языке C/C++. В прошлый раз я рассказывал про общую структуру класса BigNumber и способ хранения большого числа в памяти. Были реализованы функции нормирования большого числа для печати и две арифметические операции: сложение и вычитание.
Не знаю точно, сколько еще статей будет на эту тему, но с этих пор в начале каждой буду оставлять ссылки для навигации.
В прошлый раз я обещал, что следующим шагом станет реализация деления и умножения больших чисел, но потом понял, что они не выполнимы без возможности сравнивать два числа. Кроме того, большинство алгоритмов отпадает без этого функционала. Поэтому в этот раз я приведу реализации всех операторов сравнения: ==, !=, >, >=, <, <=.
Важно! Дабы не растягивать и без того длинный листинг исходного кода, я не буду здесь публиковать сам класс BigNumber, его вместе с реализацией сложения, вычитания и нормализации вы можете найти в прошлой статье.
читать далее «Операторы сравнения больших чисел — реализация на C/C++» →
Доброго времени суток и светлого неба над головой, дорогие друзья! Ни для кого из вас не секрет, что ограничение максимального и минимального значения целого числа, хоть и разнится на разных архитектурах, но существует. Например, для целого числа типа int диапазон его значений равен от –2147483647 – 1 до 2147483647. Казалось бы, 2 миллиарда в каждую сторону это целая гора, но как только вы займетесь настоящей криптографией, либо машинным обучением, теорией вероятностей или еще более крутой математикой, вы поймете, что это чертовски мало. Именно в таком случае на помощь приходят, так называемые, большие числа.
Идея большого числа в том, чтобы вылезти за рамки ограничений стандартных типов данных, оперировать бесконечно большими числами, размер которых будет ограничен только вычислительной мощностью «машины». Как этого достичь? Самый логичный способ заключается в том, чтобы записывать число в строку и конвертировать специальным образом в согласованный массив чисел стандартного типа.
Например, как можно хранить число 123456789123456789, в int оно не поместится. тогда мы поместим его в массив int`ов, mas[0] = 123456, mas[1] = 789123, mas[2] = 456789, напишем специальные алгоритмы, которые будут корректно складывать, вычитать, умножать и делить такие числа.
Как раз о таких алгоритмах инициализации, сложения и вычитания больших чисел я сейчас расскажу, поехали!
читать далее «Реализация больших чисел на C/C++ со сложением и вычитанием» →
Доброго времени суток! Сегодня мы посмотрим на реализацию совсем простой вещи — собственного стека на базе массива и на базе линейного списка. Код был мной написан на втором курсе, достаточно давно, перед написанием статьи я сдул с него пыль и немного подкорректировал страшные названия переменных, навел марафет. Теперь его можно показывать, хоть и осторожно.
Кратко о том, что такое стек. Это такой тип данных, в котором они организованны по принципу LIFO(last in — first out). По русски говоря, последним пришел, первым вышел. Отличный пример для визуализации это книжная стопка, верхняя книга последняя пришла и, если вы не собираетесь пугать кошку грохотом, первая ушла.
Реализация простейших структур данных — это отличный способ их изучить. Можно прочитать сотню книг про стек, но пока вы его не напишите самостоятельно, вы не подружитесь. Я писал реализацию на языке программирования С++, используя классы. Два стека — два класса и при большом желании можно запаковать их в отдельный файл и подключать к другим проектам.
Дорогие читатели, давайте заводить дружбу со стеком, поехали!
читать далее «Реализация стека на базе массива и на линейном списке» →
