Обзор библиотек для работы с большими числами в 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

Мастер Йода рекомендует:  Недавний сбой в работе облачных сервисов Amazon был вызван опечаткой сотрудника компании

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. Благодаря ей из кода С можно вносить изменения в базу данных, добавлять и безвозвратно удалять данные, создавать и удалять таблицы.

Мастер Йода рекомендует:  Руководство по условным тегам WordPress Вступление

Существуют вариации 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.

Вам будет интересно:

Буду признателен если вы поделитесь данным постом

  1. Василий (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-й участок)

Пытаюсь найти очень большое(

200-300 десятичных символов) простое число для имплементациии протокола RSA.
Подскажите, пожалуйста, как это вообще делается. Может есть готовые библиотеки.

Заслуженный участник

Последний раз редактировалось venco 20.07.2014, 21:23, всего редактировалось 1 раз.

Для RSA обычно используют псевдо-простые числа, проверенные тестом Миллера-Рабина. Этот тест реализован во многих библиотеках для работы с большими числами, даже в java.math.BigInteger.probablePrime().

— Вс июл 20, 2014 14:23:46 —

Заслуженный участник

30/10/10
1481
Ереван(3-й участок)

Спасибо за ответы.

Мне реально нужно найти такие числа. Погуглив я нашел библиотеку C++ GMP. Там имеется функция mpz_probab_prime_p , которая по-ходу использует именно алгоритма Миилера-Рабина.

Собственно вопрос в следующем: уменя комп Intel Core i5 3.10GHz, RAM: 8Gb далее не важно.

Я беру с какое-нибудь 200-значное число и последовательно инкрементирую его, пока тест не выдаст true. Это серьезно? За какое время я найду парочку таких чисел?

Заслуженный участник

Заслуженный участник

30/10/10
1481
Ереван(3-й участок)


Уххх. Спасибо.
Я немного боюсь начинать, ибо не представляю сколько нахождение одного такого числа может продлиться. Может есть оценки?

И еще, есть еще какие-то критерии, которым должны удовлетворять простые числа для RSA. Например, не иметь вид и.т.д.
Где найти весь список этих условий. Может есть библиотека, которая это все проверяет?

Заслуженный участник

Последний раз редактировалось 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-й участок)

Последний раз редактировалось Bulinator 20.07.2014, 22:06, всего редактировалось 1 раз.

Его проверенную библиотеку нигде не нашел. Можете прокомментировать?

— Вс июл 20, 2014 21:06:23 —

#include
#include
#include
#include «gmp.h»
#include

using namespace std ;

/*
*
*/
int main ( int argc, char ** argv ) <

mpz_t a,b ;
mpz_init ( a ) ;
mpz_init ( b ) ;

mpz_set_str ( a, «1234567890» , 10 ) ;
//mpz_set_str(b,»0″,10);
//a=45;
mpz_nextprime ( b,a ) ;
char * x ;
cout mpz_get_str ( x, 10 ,b ) endl ;
cout mpz_probab_prime_p ( b, 35 ) endl ;
return 0 ;
>

Ответ на ноутбуке Intel® Core™2 Duo CPU T5470 @ 1.60GHz × 2 , RAM 3.9 GiB:

RUN FINISHED; exit value 0; real time: 0ms; user: 0ms; system: 0ms

Для числа «1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890»

RUN FINISHED; exit value 0; real time: 40ms; user: 0ms; system: 10ms

Добавить комментарий