Обзор библиотек для работы с большими числами в C++
Работа с большими числами в Qt
Считайте, что у меня есть этот номер: 123456789012345.
И хочу показать это, используя этот полукод:
Он показывает неправильное число (отрицательное число) и работает хорошо только до 10 цифр.
Как заставить работать до 15 цифр правильно пожалуйста?
Решение
Как уже упоминалось, int слишком мал, чтобы содержать значение с таким количеством цифр. Я лично предпочитаю четко указывать, что я хочу, поэтому я бы использовал либо quint64 или же uint64_t , Вам также не нужен текстовый поток только для того, чтобы поместить число в строку, для этого есть функция:
Другие решения
Просто укажите тип данных, который может содержать такое количество цифр, как unsigned long long :
QTextStream должен вести себя так же, как std::ostream делает.
Реализация больших чисел на C/C++ со сложением и вычитанием
Доброго времени суток и светлого неба над головой, дорогие друзья! Ни для кого из вас не секрет, что ограничение максимального и минимального значения целого числа, хоть и разнится на разных архитектурах, но существует. Например, для целого числа типа int диапазон его значений равен от –2147483647 – 1 до 2147483647. Казалось бы, 2 миллиарда в каждую сторону это целая гора, но как только вы займетесь настоящей криптографией, либо машинным обучением, теорией вероятностей или еще более крутой математикой, вы поймете, что это чертовски мало. Именно в таком случае на помощь приходят, так называемые, большие числа.
Идея большого числа в том, чтобы вылезти за рамки ограничений стандартных типов данных, оперировать бесконечно большими числами, размер которых будет ограничен только вычислительной мощностью «машины». Как этого достичь? Самый логичный способ заключается в том, чтобы записывать число в строку и конвертировать специальным образом в согласованный массив чисел стандартного типа.
Например, как можно хранить число 123456789123456789, в int оно не поместится. тогда мы поместим его в массив int`ов, mas[0] = 123456, mas[1] = 789123, mas[2] = 456789, напишем специальные алгоритмы, которые будут корректно складывать, вычитать, умножать и делить такие числа.
Как раз о таких алгоритмах инициализации, сложения и вычитания больших чисел я сейчас расскажу, поехали!
Другие статьи по теме
Как реализовать большие числа на C/C++
Сейчас я расскажу о том, как будет работать написанный нами специальный класс BigNumber с реализованной инициализацией числа из строки, сложением, вычитанием и выводом в поток. А после приведу полный листинг исходного кода с этим классом, снабженный комментариями. Вы можете читать описания, поглядывая на код. Я специально не стал дублировать функции, чтобы не нагромождать и без того длинный текст статьи.
Инициализация большого числа
Конструктор класса BigNumber(string str) , принимающий на вход строку, работает следующим образом. Начиная с конца строки отсекаются подстроки длины BASE , конвертируются в числа и закидываются в вектор chunks . В зависимости от наличия минуса в строке инициализируется еще одно приватное поле класса — sign . BASE это статическое константное поле, одинаковое для всех объектов класса, чтобы не было конфликтов в нормализации.
Сложение больших чисел
Для сложения мы перегрузим оператор + , он в свою очередь будет вызывать метод _plus() , который сложит два больших числа «почанково». Кроме того, перед самим сложением необходимо сделать одинаковыми размеры векторов chunks обоих чисел. А после сложения нормализовать результат функцией _normalizationChunks() . Нормализовать — значит сделать так, чтобы во всех чанках лежали BASE-разрядные числа (если BASE = 2, то только двузначные числа).
Вычитание больших чисел
Вычитание работает аналогично сложению, перегружается оператор — , используется метод _minus() .
Вывод большого числа в поток
Вывод происходит благодаря перегрузке оператора , но перед самим выводом, число нужно нормализовать функцией _normalizationSigns() . Она почистит все нулевые чанки, отрицательные числа в чанках, корректно установит знак числа.
Исходный код реализации больших чисел на C/C++
Теперь непосредственно сама реализация с комментариями.
С++: работа с большими числами?
мне нужно использовать в с++ числа с 10 символами. символы после точки мне не нужны. я бы использовал массив но мне необходимо нужно получить корень из 3 степени. с int у меня все работает
А мне так кажется, что у вас полная каша в голове . и никакие тут краткие советы не помогут:
— корень (хоть «из 3 степени», хоть из любой) — не извлекается
— вам нужны вещественные числа, а нужны вам символы после точки или не очеь — это уже не имеет значения
— в новых стандартах C++ есть вещественный тип long double, точность которого куда выше ваших требуемых 10-ти знаков.
Алёна C++
программирование для прагматиков
среда, марта 21, 2007
Работа с большими числами
Бывает так, что нужно работать ну с очень большими числами. Настолько большими, что они никак не влезают во встроенные типы. Можно для этого реализовать собственный класс, например из динамического массива целых чисел. И работать с большими числами старым добрым способом, знакомым еще со школы — имитировать умножение в столбик и т.д. Единственным ограничением на размер такого числа будет размер памяти компьютера.
Как обычно, можно не реализовывать это самостоятельно, а взять уже готовую библиотеку.
Вышеупомянутая имитация умножения в столбик — это, конечно, корректно, но как-то медленно. Поэтому люди пытаются этот момент разогнать. Для этого применяются алгоритмы, которые используются для быстрого умножения полиномов. Если вы возьмете уже готовую библиотеку работы с большими числами, то там, скорее всего, реализован такой алгоритм, а то и не один. Я чаще всего встречала упоминание Fast Fourier Transforms (сокращенно FFT) и умножение Карацубы.
Когда увидела словосочетание «Karatsuba multiplication» у меня в голове создался образ сурового японца. Ан нет, это совсем даже и не японец, его полное имя Карацуба Анатолий Алексеевич. Прямо даже как-то приятно стало.
Интересная область применения больших чисел — это работа с числами повышенной точности. Представление чисел с плавающей точкой неточно, ошибки накапливаются. Можно попытаться представить их в виде дроби, работать уже с дробями и таким образом исключить неточности.
В заключение несколько ссылок по большим числам. Из библиотек для работы с большими числами я выбрала те, которые чаще всего упоминаются. Работать я с ними не работала, поэтому более подробно о них рассказать не могу.
С++ библиотеки для работы с числами высокой точности: Arageli, NTL, GMP
Crypto++ — библиотека для криптографии, в ней предусмотрена работа с большими числами
Multiplication algorithm — страница из Википедии с описаниями различных алгоритмов умножения
General Decimal Arithmetic
9 коммент.:
А-а-афигенно. Спасибо! В мемориз!
Я собаку когда-то съел в www.risc.uni-linz.ac.at на подобных вычислениях. Мы писали ядро параллельшых вычислений для системы компютерной алгебры — STURM
Есть еще алгоритм Тоома-Кука. Андрей Тоом — это тоже наш человек 🙂 хотя уже давно работает за границей
Если честно, я немного удивлён: преобразование Фурье используется для перемножения больших чисел!?
Обычно применяется для «спектрального» анализа данных: в Фурье-плоскости многие задачи обработки изображений решаются проще. И существенно ускоряет расчёты. Но чтобы числа перемножать. а можно ссылочку на алгоритм?
Если честно, я немного удивлён: преобразование Фурье используется для перемножения больших чисел!?
Обычно применяется для «спектрального» анализа данных: в Фурье-плоскости многие задачи обработки изображений решаются проще. И существенно ускоряет расчёты. Но чтобы числа перемножать. а можно ссылочку на алгоритм?
Я смотрела про него в Википедии здесь: Multiplication algorithm. Есть отдельная страничка Fast Fourier transform. Хороший алгоритм, много где применяется.
Насколько мне известно, то алгоритмы использующие FFT для умножнения чисел имеют самую лучшую оценку трудоёмкости. Например в той же GMP реализован алгоритм Шёнхаге-Штрассена, а в Arageli в ближайшее время появится алгоритм основанный на идее Полларда, тоже использующий FFT. Эти алгоритмы проигрывают алгоритму Карацубы на числах маленькой длинны, но начиная с некоторого придельного значения работают быстрее. Соотвественно просто умножение в вышеупомянутых библиотеках работает по след. принципу: весь интервал премножаемых чисел делится на подинтервалы, в которых применяется наибыстрейший алгоритм. Т.е. с некоторой долей вероятности можно утверждать, что вы всегда перемножаете числа самым быстрым способом.
Хм, а чего мучиться, заморачиваться?
Хаскелл неплохо интегрируется с программами на том же С++ — можно модули, работающие с задачами, где нужны сверхбольшие числа, просто написать на Хаскелле и подвязать к основной программе на С++.
Или вообще обойтись без С++. :о))
Или вообще обойтись без С++. :о))
Кстати да. В Питоне вот работа с большими числами происходит вообще прозрачно для программиста.
Эх. Сейчас пытаюсь сделать шаблон для длинного целого, параметризуемый типом своих половинок. Чтобы можно было длинное целое любой размерности создать потом .
13 библиотек С++, о которых нужно знать
Помимо стандартной библиотеки, содержащей основные модули языка С++, разработаны десятки, а то и сотни дополнительных библиотек. Каждая из этих библиотек содержит программы и подпрограммы, производящие ряд действий.
Использование сторонних библиотек сокращает объём кода и оптимизирует работу программы, поскольку решения, использован ные разработчиками библиотеки и оттестированные сотнями программистов в разноплановых проектах, после нескольких лет шлифовки достигают лучших показателей по всем параметрам.
Знание и использование ряда полезных библиотек сильно упрощает работу программиста. По этому признаку работодатели легко отличают уверенного профессионала от неопытного новичка.
В этой статье Вы сможете познакомиться с рядом полезных библиотек, которые активно используются разработчиками по всему миру.
Веб-разработка
V8
Если Вам нужен удобный инструмент для работы с JavaScript, V8 подойдёт идеально.
Свои функции V8 реализует, используя специальные классы, написанные на с++ и объявленные в namespace V8. Работать с джава скрипт — структурами можно через привычную оболочку с++.
Схема взаимодействия объектов с++ и V8 реализована посредством использования v8::Handle (template-классов).
Установка V8 обычно не занимает много времени, а польза для тех, кому периодически приходится работать с JavaScript’ом, неоценима.
Кроме того, о библиотеках, с помощью которых могут взаимодействовать C++ и JavaScript очень любят спрашивать на собеседованиях. Поэтому даже, если вы не собираетесь работать с js , с V8 или другими подобными библиотеками лучше познакомиться.
WebKit
Так или иначе, почти все разработчики на разных этапах сталкиваются с необходимостью отображать web – элементы. Чтобы всё выглядело красиво и в коде, и в конечном отображении, а выполнение этой задачи не отнимало слишком много времени и сил, существует библиотека WebKit.
Некоторые программисты называют WebKit «чёрным ящиком», органично перерабатывающим html, css и JavaScript в полноценные веб-страницы.
Awesomium
Awesomium — это библиотека для интеграции браузера (на базе Chromium) в своё приложение. Библиотека имеет 2 режима работы: Offscreen и Windowed.
В режиме Offscreen отрисовка и работа скриптов на экране не отображается.
В режиме Windowed средствами библиотеки эффективно выполняется отрисовка в «окне приписки» и обработка активности мыши и клавиатуры.
Awesomium активно применяется в десятках разных приложений. Описаны случаи интеграции этой библиотеки в 3D игры.
Существенный минус – отсутствие активного сообщества, способного познакомить новичка с библиотекой, ответить на вопросы и исправить ошибки. А документация, доступная для работы с Awesomium на с++, даёт довольно смутное представление о принципах работы библиотеки.
Тем не менее, Awesomium остаётся очень удобным инструментом, завоевавшим признание сотен разработчиков по всему миру.
Работа с сервером
Libcurl
Хотите упростить взаимодействие с сервером? – используйте Libcurl.
Libcurl помогает передавать данные (изображения, файлы и пр.) приложениям. Libcurl поддерживает 13 основных протоколов FTP, FTPS, HTTP, HTTPS, TFTP, SCP, SFTP, Telnet, DICT, LDAP, а также POP3, IMAP и SMTP.
Изначально cUrl предназначался для использования на языке С. Сейчас для работы с Libcurl разработаны модули интеграции к 30 языкам программирования. Что говорит о высокой популярности библиотеки в среде разработчиков. На это же указывает высокий рейтинг продукта.
Сжатие данных
Библиотек для сжатия данных довольно много, одна из самых удобных и популярных
Zlib
Сжатие любых объёмов данных (даже превышающих объём памяти) с помощью zlib проводится предельно легко.
Zlib написана на языке С и применяется в тысячах проектов. Использование некоторых других библиотек невозможно без использования zlib. Примером такой библиотеки является основная библиотека для работы с растровой графикой в формате .png — libpng.
Работа с изображениями
Libpng и libjpg
Libpng, написанная на C с использованием ассемблера, предназначена для работы с изображениями в формате .png.
Для работы с изображениями в формате .jpg существует библиотека libjpg (также написанная на С с использованием Ассемблера)
Обе библиотеки имеют подробные инструкции и множество примеров использования как в С, так и в С++.
Работа с PDF
Периодически возникает необходимость конвертировать файлы в формат pdf. Для этого процесса разработана динамическая библиотека DynaPDF.
DynaPDF
DynaPDF – удобный гибкий инструмент. Формат .dll хотя и открывает достаточно широкие возможности, периодически становится причиной возникновения ошибок.
Для успешного устранения ошибок в сети есть много пошаговых инструкций.
Используется для программирования на языках C/C++, C#, Delphi, Lazarus, PHP, VB, VBA, and VB .Net.
Работа с базами данных
Большая часть приложений нуждается во взаимодействии с базами данных. Оттуда получаются и туда передаются потоки необходимой информации. Поэтому большинство работодателей интересует умение соискателей работать с базами данных.
Libpq
Libpq – удобная библиотека для взаимодействия С и PosgreSQL. Благодаря ей из кода С можно вносить изменения в базу данных, добавлять и безвозвратно удалять данные, создавать и удалять таблицы.
Существуют вариации libpq для C++, Python’a, Perl’a, Tcl, ECPG.
Отладка и тестирование
Ещё один важный пласт знаний для программиста – отладка и тестирование кода. Знание специфических библиотек, существенно упростит Вам решение этой задачи, а коллегам наглядно продемонстрирует уровень вашего профессионализма.
Check
Библиотека Check предназначена для модульного тестирования всех возможностей программ, написанных на языке С. Существенным плюсом использования Check’а служит возможность запуска тестов в отдельных процессах для более точной диагностики причин возникновения ошибок, снижения скорости и т.п
Для модульного тестирования на языке С++ используется Google C++ Testing Framework (Google Test).
Pcap
С помощью этой библиотеки создаются программы, отслеживающие трафик, поступающий на сетевую карту компьютера. Это может быть очень полезно для отладки программ, составления мониторинговых отчётов и т.п.
Pcap предназначена для работы с С и С++. Существуют обёртки, делающие эту библиотеку доступной для работы на других языках программирования.
Ещё Вам может пригодиться…
Libusb
Libusb — это библиотека, которая позволяет обмениваться данными с USB-устройствами прямо из кода программы.
В библиотеке поддерживаются все типы передачи (управление / объем / прерывание / изохронность). Важный элемент библиотеки – журнал сообщений. Он помогает правильно расшифровать коды ошибок, поступающие от USB- устройств.
Предназначена для работы с С. Для других языков программирования разработаны обёртки. Для С++ — Libusbpp
ZBar
Библиотека ZBar предназначена для распознавания штрихкодов из изображений.
ZBar имеет предельно простую и логичную документацию без «тёмной магии» и необъяснимых функций.
Работать с ней легко и удобно. Можно использовать из программных интерфейсов С, С++, Питона и других языков программирования.
Заключение
Большинство описанных библиотек работают и под Windows, и под Linux, и под macOS, и под BSD. Разработчики библиотек предоставляют подробную техническую документацию, а комьюнити готово поделиться пошаговыми инструкциями по установке и ответить на любые рабочие вопросы.
Умение работать с библиотеками – важный навык для любого программиста. Это своеобразный показатель его профессионального уровня и понимания процесса разработки.
Библиотеки помогают решить множество сложных задач, возникающих при разработке кода. Чем теснее Вы с ними «подружитесь», тем шире будет круг ваших профессиональных возможностей.
Не бойтесь новых задач – ищите их решение.
Пишите код, тестируйте и оттачивайте его до блеска. А команда progtips.ru всегда придёт Вам на помощь!
АНОНС
Вы думаете, это все полезные библиотеки? Нет! На десерт мы оставили самое интересное.
В следующем выпуске Вас ждут:
— лучшие графические библиотеки для С++;
— чем пользуются разработчики компьютерных игр в России и на Западе;
и как по графической библиотеке отличить любителя от профессионала.
Библиотека больших чисел в С++
Я делаю проект, который требует действительно больших чисел, до 100 цифр. Я прочитал, что java поддерживает большие целые числа ( java.Math.BigInteger ), и я хочу знать, есть ли что-то подобное в С++. Итак, вот мой вопрос: есть ли стандартная или нестандартная библиотека С++, которая реализует большие целые числа?
Примечание: Если стандартной реализации для больших целых чисел нет, я бы хотел просто нестандартный. Спасибо заранее.
Библиотека многоточечной арифметики GNU делает то, что вы хотите https://gmplib.org/
Gnu MP является библиотекой C, но имеет интерфейс класса С++, и если вас интересуют только большие целые числа, вы можете просто иметь дело с mpz_class . Посмотрите на образец ниже, который я взял на странице Общий интерфейс С++
К сожалению, нет стандартной библиотеки для больших чисел. Вы сказали, что ищете «простую» библиотеку, самая простая из известных мне библиотек — InfInt. Он состоит только из одного заголовочного файла. Его использование довольно просто. Вот пример кода:
Работа с большими числами в Qt
Считайте, что у меня есть этот номер: 123456789012345.
И хочу показать это, используя этот полукод:
Он показывает неправильное число (отрицательное число) и работает хорошо только до 10 цифр.
Как заставить работать до 15 цифр правильно пожалуйста?
Решение
Как уже упоминалось, int слишком мал, чтобы содержать значение с таким количеством цифр. Я лично предпочитаю четко указывать, что я хочу, поэтому я бы использовал либо quint64 или же uint64_t , Вам также не нужен текстовый поток только для того, чтобы поместить число в строку, для этого есть функция:
Другие решения
Просто укажите тип данных, который может содержать такое количество цифр, как unsigned long long :
QTextStream должен вести себя так же, как std::ostream делает.
Записки инженера
Доступным языком заметки по IT технологиям
Библиотеки для 2D графики (C/С++)
В один из моментов, я задался вопросом как мне вывести графику используя C++ (С). Я не хотел использовать такие популярные среды Builder или MS Visual с их библиотеками окон. Мне была нужна просто библиотека для работы с простой графикой в консоли.
Если судить по запросам в интернете и на форумах, этот вопрос возникал не только у меня.
После нескольких дней поиска ответа на данный вопрос, я подготовил подбороку данных библиотек. Возможно они пригодятся и вам.
Список библиотек
1. WinBGIm — портированная «старая» библиотека от компании Borland для Windows. Изначально она разрабатывалась для отображения графики под DOS.
2. Cairo — библиотека под лицензий GNU, поддерживается многими языками программирования (Delphi, Factor, Haskell, Lua, Perl, PHP, Python, Ruby, Scheme, Smalltalk и т.п.). Также поддержка большого количество операционных систем.
3. SDL — кроссплатформенная мультимедийная библиотека под лицензий GNU реализующая единый программный интерфейс к графической подсистеме, звуковым устройствам и средствам ввода для широкого спектра платформ.
Данная библиотека активно используется при написании кроссплатформенных мультимедийных программ (в основном игр). Поддерживается большим количеством языков программирования (C, C++, C#, VB.NET, D, Ada, Vala, Eiffel, Haskell, Erlang, Euphoria, Java, Lisp, Lua, ML, Pascal, Perl, PHP, Pike, PureBasic, Python и Ruby) и операционных систем (Linux, Microsoft Windows, Mac OS X, iOS и Android).
Из интересной особенности библиотеки, она позволяет работать с джостиком, CD-ROM и сетью.
4. SFML — простая и быстрая кроссплатформенная мультимедийная библиотека, доступная на языках: С++, C, D, Java, Python, Ruby, OCaml, .Net и Go. Является объектно ориентированный аналог SDL. Позволяет работать с аудио, сетью и окнами.
5. Allergo — кроссплатформенная библиотека позволяющая работать с 2D графикой, аудиофайлами, окнами, файловой системой, 3D графикой. Помимо этого библиотека предоставляет дополнительные функции по работе с числами с фиксированной, плавающей запятой и матрицами.
Изначально создавалась для разработки игр под Atari (Allergo расшифровывается как Atari Low-Level Game Routines), сейчас библиотека поддерживается языками: C, C++, Pascal, Python, Lua, Scheme, D, Go, Ada, Lisp, Mercury, Perl, Scheme. Есть поддержка под следующие платформы: Windows, macOS, Unix-подобные системы, Android и iOS.
6. SKIA — компактная графическая библиотека. Её использует в Google Chrome, Chrome OS, Chromium OS, Mozilla Firefox, Android (до 3.0), Firefox OS и Sublime Text 3. Библиотека работает на С и Python.
7. OpenGL (или glut) — библиотека на которой основываются некоторые из выше указанных. Я заявил о ней в самом конце списка, т.к. многие о ней слышали и она достаточно мощна для простых задач вроде 2D графики, но реализовывать она это может. Точнее даже сказать, OpenGL это спецификация, т.е. набор правил описывающих интерфейс, а разработчик оборудования (видеокарты) на её основе разрабатывает библиотеку. Реализуется на большом количество операционных систем и языков программирования.
8. DirectX — библиотека от компании Microsoft только для Windows. Изначально разрабатывалась именно для игр, является конкурентов OpenGL. Позволяет работать с большим количество периферии, сеть, звук, видео, 3D графика, 2D графика, клавиатура, джостик и т.п.
9. Direct2D — библиотека от Microsoft появилась с DirectX v.10. Задача библиотеки отображать 2D графику с использованием аппаратного ускорения, изначально реализовывалась для Windows 7.
Вам будет интересно:
Буду признателен если вы поделитесь данным постом
- Василий (iklife.ru) пишет:
Достаточно широкий список. С ходу и не соображу чем можно добавить. Вроде из популярного всё предложено, выбирай на свой вкус.
Реализация больших чисел на C/C++ со сложением и вычитанием
Доброго времени суток и светлого неба над головой, дорогие друзья! Ни для кого из вас не секрет, что ограничение максимального и минимального значения целого числа, хоть и разнится на разных архитектурах, но существует. Например, для целого числа типа int диапазон его значений равен от –2147483647 – 1 до 2147483647. Казалось бы, 2 миллиарда в каждую сторону это целая гора, но как только вы займетесь настоящей криптографией, либо машинным обучением, теорией вероятностей или еще более крутой математикой, вы поймете, что это чертовски мало. Именно в таком случае на помощь приходят, так называемые, большие числа.
Идея большого числа в том, чтобы вылезти за рамки ограничений стандартных типов данных, оперировать бесконечно большими числами, размер которых будет ограничен только вычислительной мощностью «машины». Как этого достичь? Самый логичный способ заключается в том, чтобы записывать число в строку и конвертировать специальным образом в согласованный массив чисел стандартного типа.
Например, как можно хранить число 123456789123456789, в int оно не поместится. тогда мы поместим его в массив int`ов, mas[0] = 123456, mas[1] = 789123, mas[2] = 456789, напишем специальные алгоритмы, которые будут корректно складывать, вычитать, умножать и делить такие числа.
Как раз о таких алгоритмах инициализации, сложения и вычитания больших чисел я сейчас расскажу, поехали!
Другие статьи по теме
Как реализовать большие числа на C/C++
Сейчас я расскажу о том, как будет работать написанный нами специальный класс BigNumber с реализованной инициализацией числа из строки, сложением, вычитанием и выводом в поток. А после приведу полный листинг исходного кода с этим классом, снабженный комментариями. Вы можете читать описания, поглядывая на код. Я специально не стал дублировать функции, чтобы не нагромождать и без того длинный текст статьи.
Инициализация большого числа
Конструктор класса BigNumber(string str) , принимающий на вход строку, работает следующим образом. Начиная с конца строки отсекаются подстроки длины BASE , конвертируются в числа и закидываются в вектор chunks . В зависимости от наличия минуса в строке инициализируется еще одно приватное поле класса — sign . BASE это статическое константное поле, одинаковое для всех объектов класса, чтобы не было конфликтов в нормализации.
Сложение больших чисел
Для сложения мы перегрузим оператор + , он в свою очередь будет вызывать метод _plus() , который сложит два больших числа «почанково». Кроме того, перед самим сложением необходимо сделать одинаковыми размеры векторов chunks обоих чисел. А после сложения нормализовать результат функцией _normalizationChunks() . Нормализовать — значит сделать так, чтобы во всех чанках лежали BASE-разрядные числа (если BASE = 2, то только двузначные числа).
Вычитание больших чисел
Вычитание работает аналогично сложению, перегружается оператор — , используется метод _minus() .
Вывод большого числа в поток
Вывод происходит благодаря перегрузке оператора , но перед самим выводом, число нужно нормализовать функцией _normalizationSigns() . Она почистит все нулевые чанки, отрицательные числа в чанках, корректно установит знак числа.
Исходный код реализации больших чисел на C/C++
Теперь непосредственно сама реализация с комментариями.
Научный форум dxdy
Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
| Вход Регистрация | Donate FAQ Правила Поиск |
Как находят большие простые числа?
| Заслуженный участник |
30/10/10
1481
Ереван(3-й участок)
| Заслуженный участник |
Последний раз редактировалось venco 20.07.2014, 21:23, всего редактировалось 1 раз.
Для RSA обычно используют псевдо-простые числа, проверенные тестом Миллера-Рабина. Этот тест реализован во многих библиотеках для работы с большими числами, даже в java.math.BigInteger.probablePrime().
— Вс июл 20, 2014 14:23:46 —
| Заслуженный участник |
30/10/10
1481
Ереван(3-й участок)
| Заслуженный участник |
| Заслуженный участник |
30/10/10
1481
Ереван(3-й участок)
| Заслуженный участник |
Последний раз редактировалось Xaositect 20.07.2014, 21:42, всего редактировалось 1 раз.
У меня полторы секунды прошло, я сделал случайное число от до и вызвал на нем mpz_nextprime. Процессор Intel i5-3570K, 3.4 GHz.
— Вс июл 20, 2014 22:42:40 —
Вообще есть библиотеки криптографии, напр. openssl, libgcrypt, nettle.
Вот, например, код из nettle, с комментариями и ссылками на Handbook of Applied Cryptography: https://git.lysator.liu.se/nettle/nettl . om-prime.c
| Заслуженный участник |
| Заслуженный участник |
Для RSA обычно используют псевдо-простые числа, проверенные тестом Миллера-Рабина. Этот тест реализован во многих библиотеках для работы с большими числами, даже в java.math.BigInteger.probablePrime().
— Вс июл 20, 2014 14:23:46 —
| Заслуженный участник |
30/10/10
1481
Ереван(3-й участок)
