Как вывести длинное число c

Реализация длииииииинной арифметики на C++

Структура класса

Первое, что нужно решить — это то, как хранить наше число. Я храню его в виде массива цифр, в обратном порядке (это позволяет проще реализовывать все операции), сразу по 9 цифр в одном элементе массива (что позволяет сэкономить память):

В моей реализации будет сразу два представления нуля — в виде пустого вектора и в виде вектора с одним-единственным нулём.

Создание числа

Первое, что нужно научиться делать — это создавать число. Вот так оно преобразуется из строки, содержащей цифры:

Код процедуры удаления ведущих нулей прост до безобразия:

Также нам нужно уметь преобразовывать обычные числа в длинные:

Код преобразования из остальных типов еще проще, я не стал приводить его здесь.

Вывод числа

Теперь нам нужно научиться печатать наше число в поток и преобразовывать его в строку:

Сравнение чисел

Теперь нам нужно научиться сравнивать два числа друг с другом. Теория говорит, что для этого достаточно всего двух операций, остальные могут быть выведены на их основе. Итак, сначала научимся сравнивать два числа на равенство:

Теперь проверим, меньше ли одно число другого:

Здесь мы используем унарное отрицание, чтобы сменить знак числа. Также я для симметрии ввел унарный плюс:

Знания о том, почему нужно возвращать const big_integer, а не просто big_integer, а также о правилах выбора между дружественной функцией-оператором и оператором-членом класса, я подчерпнул из этой статьи.

Дальше все совсем просто:

Арифметические операции

Сложение

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

Здесь я избежал «дорогой» операции деления в случае, когда получившаяся «цифра» больше основания, по которому я работаю, путем простого сравнения.

Вычитание

В принципе, вычитание аналогично сложению. Нужно лишь рассмотреть случай, когда уменьшаемое меньше вычитаемого:

Инкремент и декремент

Перед реализацией этих двух операций нам нужно реализовать сложение и вычитание с присвоением:

Тогда префиксные версии операций реализуются в одну строчку, а постфиксные — лишь немногим сложнее:

Умножение

Я не стал писать быстрое умножение Карацубы, а снова использовал «школьную» арифметику:

Деление

Поскольку я не нашел в Интернете быстрых способов деления, воспользуемся школьным делением уголком. Начнем делить со старших разрядов. Нам нужно уменьшить текущее значение делимого на максимально возможное число делимым. Это максимальное значение будем искать двоичным поиском. Но сначала нам нужно определить функцию «сдвига» числа вправо, которая позволит нам перебирать разряды последовательно:

Теперь опишем само деление:

Здесь big_integer::divide_by_zero это пустой класс, унаследованный от std::exception .

Взятие остатка

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

Возведение в степень

Я использовал алгоритм быстрого возведения в степень. Он требует проверки числа на нечетность. Поскольку вычислять остаток от деления на 2, мягко говоря, было бы затратно, введем такие операции:

Теперь напишем само возведение:

Всё! Теперь можно вычислить, к примеру, 2 1000 , либо факториал 100:

Источник

Вывод больших чисел

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Вывод больших чисел
Играл с этой программой и решил увеличить вывод факториала выше 21. В 7й строке изменил (long.

Вывод больших чисел
Неправильно выводится номер телефона (номер телефона с 11 цифрами).Помогите исправить class.h.

Фиксированный вывод больших чисел
Надо вывести большое число, например, 12345678901234560000000000000000000000000000, причём, 16 цифр.

Некорректный вывод больших чисел
Добрый день Беда в том что программа переводит некорректно числа в двоичную систему от 1000 и выше.

Решение

Комментарий модератора

Используйте теги форматирования кода!

Форматированный вывод больших чисел с использованием _stprintf_s
Можно ли при преобразования больших чисел в строку с помощью функции _stprintf_s приводить их к.

Вывод больших чисел
Ситуация такая: вводится число и это число возводится в степень 15. Как я знаю longint самый.

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

Ввод и вывод больших чисел
Столкнулся с проблемой ввода и вывода чисел. Нужно ввести и вывести числа -0.9589243e26 и.

Вывод больших чисел в консоль Eclipse
Всем привет! Не знал как правильно сформулировать вопрос в поисковик, поэтому пишу сюда. Когда.

Вывод больших чисел, используя print/printf
Как вывести большое число полностью, а не XXXe+YYY, используя print, и почему printf выводит -1?

Источник

Реализация больших чисел на 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++

Теперь непосредственно сама реализация с комментариями.

Источник

Длинная арифметика

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

Класс BigNumber

Рассмотрим реализацию арифметических операций и операций сравнения для знаковых больших чисел. Для хранения знака числа будем использовать перечисление:

Для простоты будем разбивать длинное число на отдельные цифры, которые будут хранится в списке:

Создадим набор конструкторов для инициализации больших чисел:

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

Также в класс необходимо добавить методы:

Сравнение больших чисел

Сравнение длинных чисел производится в три этапа:

• по знаку;
• по длине;
• сравнение цифр числа.

Метод Comparison возвращает:

При этом в самом начале числа сравниваются по знаку, если знаки равны, сравниваем длину, если и она равна, то сравниваем последовательно все цифры длинных чисел.

Перегрузка операторов сравнения

Сложение длинных чисел

Используется метод вычисления в столбик знакомый нам с детства.

Вычитание двух больших чисел

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

Умножение двух больших чисел

Реализация операции умножения отличается от стандартного умножения в столбик, однако сам принцип сохраняется. Каждая цифра числа перемножается на цифру другого с последующим суммированием.

Деление одного длинного числа на другое

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

Вычисление остатка от деления больших чисел

Остаток от деления вычисляется подобным к предыдущему методом.

Перегрузка арифметических операторов

Для удобства перегрузим арифметические операторы класса BigNumber.

Источник

Длинная арифметика от Microsoft

Введение

Известно, что компьютер может оперировать числами, количество бит которых ограниченно. Как правило, мы привыкли работать с 32-х и 64-х разрядными целыми числами, которым на платформе .NET соответствуют типы Int32 (int) и Int64 (long) соответственно.

А что делать, если надо представить число, такое как, например, 29! = 8841761993739701954543616000000? Такое число не поместится ни в 64-х разрядный, ни тем более 32-х разрядный тип данных. Именно для работы с такими большими числами существует длинная арифметика.

Длинная арифметика — в вычислительной технике операции (сложение, умножение, вычитание, деление, возведение в степень и т.д.) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, используя базовые аппаратные средства работы с числами меньших порядков.

Длинную арифметику также можно считать одним из разделов олимпиадного программирования, поскольку очень часто при решении задач, разрядности стандартных типов не хватает для представления конечного результата. При выборе языка программирования для олимпиадных нужд не маловажным является встроенный в него набор средств (готовых библиотек, реализованных классов). Многие языки (Java, Ruby, Python) имеют встроенную поддержку длинной арифметики, что в разы может сократить время написания программы.

Платформа .NET вплоть до 4.0 версии не имела встроенной поддержки работы с длинными числами. В 4-той же версии .NET обзавелась не только длинными, но и комплексными числами. Этот функционал доступен через сборку System.Numerics и типы BigInteger и Complex определенные в одноимённом с названием сборки пространстве имён.

Следует сказать, что структура BigInteger должна была появиться ещё в .NET 3.5, однако на тот момент она не была полностью готова, её реализация не отвечала всем потребностям (сюда можно отнести и проблемы производительности), поэтому было принято решение отложить её выход до .NET 4.0.

В данной статье я бы хотел рассмотреть подробности реализации длинной арифметики от Microsoft.

Общие понятия

Идея представления длинных чисел в памяти компьютера достаточно проста. Рассмотрим число 123456789 в десятеричной системе счисления. Очевидно, его можно представить следующим образом:

123456789₁₀ = 1*10 8 + 2*10 7 + 3*10 6 + 4*10 5 + 5*10 4 + 6*10 3 + 7*10 2 + 8*10 1 + 9*10 0

В общем случае, любое число можно представить в виде:

A = a_n-1β n-1 + a_n-2β n-2 +…+a₁β + a₀
где β – основание системы счисления, в которой мы представляем число, а коэффициенты a_i удовлетворяют двойному неравенству 0 ≤ a_i 2 + … + a_nx n удобно представлять в виде массива, элементы которого представляют коэффициенты a_i, а индекс i — определяет соответствующую степень x. Длинное число хранится аналогично, осталось определиться с выбором основания β.

Например, то же самое число 123456789 можно представить в десятитысячной (β = 10 4 ) системе счисления следующим образом:

123456789₁₀ = 1*(10 4 ) 2 + 2345*(10 4 ) 1 + 6789*(10 4 ) 0

Представляя число 123456789 в десятитысячной системе счисления, мы получаем сразу два преимущества: во-первых, сокращаем количество потребляемой памяти, так как вместо массива из 9 чисел нам достаточно хранить массив из 3 чисел (1, 2345 и 6789), во-вторых, значительно уменьшаем время выполнения стандартных операций над длинными числами, поскольку за раз обрабатываем 4 разряда числа. В общем, компьютер одинаково быстро складывает одноразрядные и 32-разрядные числа, поэтому этим следует воспользоваться.

Основание системы счисления β обычно зависит от максимального размера базового типа данных на компьютере, и выбирается, исходя из следующих соображений:

1. основание должно подходить под один из базовых типов данных;
2. основание должно быть как можно больше, чтобы уменьшить размер представления длинного числа и увеличить скорость операций с ними, но достаточно малого размера, чтобы все операции с коэффициентами использовали базовый тип данных;
3. для удобства вывода и отладки можно выбрать β как степень 10, β — степень двойки позволяет проводить быстрые операции на низком уровне.

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

BigInteger от Microsoft

Если посмотреть на структуру BigInteger через декомпилятор Reflector или dotPeek, то увидим следующие поля:

Структура содержит всего два экземплярных поля (_sign и _bits), остальные поля представляют собой константы и статические поля для чтения представляющие значения структуры для чисел -1, 0 и 1.

Можно предположить, что в переменной _sign хранится знак числа, а массив _bits содержит коэффициенты a_i. Учитывая, что массив _bits имеет тип uint[], можно так же предположить, что в качестве основания β взята степень двойки 2 32 (поскольку uint — 32 разрядное беззнаковое число).

Итак, попробуем подтвердить или опровергнуть наши предположения.

Конструктор, принимающий int, в качестве аргумента выглядит так:

Его реализация может рассказать немного больше о назначении переменной _sign. Как видно, если длинное число помещается в int диапазон (от -2 31 до 2 31 -1), то оно хранится в переменной _sign, а массив _bits при этом не используется, он равен null. Эта оптимизация, должна ускорить работу типа BigInteger, а так же снизить размер потребляемой памяти когда число на самом деле не является большим.

Конструктор, принимающий uint в качестве аргумента, выглядит следующим образом:

В зависимости от того помещается ли число в int диапазон, оно записывается либо в переменную _sign, либо в массив _bits.

Следующий конструктор, принимающий 64-х разрядное число со знаком (long) поможет ответить на вопрос о выборе основания системы счисления:

Если число не помещается в int диапазон, то, как мы видим переменная _sign содержит знак числа (-1 – для отрицательного и 1 – для положительного), а массив _bits содержит те самые коэффициенты a_i и заполняется следующим образом:

В данном случае 64-х разрядное число num разбивается на два 32-х разрядных: (uint)num и (uint)(num >> 32). Первое число представляет собой последние 32 бита числа num, в то время как второе первые 32 бита (смещение вправо на n бит равносильно целочисленному делению на 2 n ).

Давайте определим, как будет храниться число long.MaxValue = 2 63 -1 = 9223372036854775807 в структуре BigInteger. Для этого поделим его на 2 32 :

Фактически (uint)long.MaxValue = 4294967295, (uint)(long.MaxValue >> 32) = 2147483647.

Значит, 9223372036854775807 = 2147483647*(2 32 ) 1 + 4294967295*(2 32 ) 0 , и BigInteger
будет представлен парой:

_sign = 1
_bits = <4294967295, 2147483647>// вспоминаем, что число храниться задом наперёд

Для длинного числа -1234567891011121314151617181920 имеем:

То есть число раскладывается по степеням 2 32 следующим образом:
1234567891011121314151617181920 = 15*(2 32 ) 3 + 2501550035*(2 32 ) 2 + 3243814879*(2 32 ) 1 + 4035623136*(2 32 ) 0

Значит, BigInteger будет представлен парой:

_sign = -1 // знак числа
_bits =

Число, помещающееся в int диапазон, скажем, 17 будет храниться следующим образом:

_sign = 17
_bits = null

Исследовав конструкторы структуры BigInteger можно заключить:

1. если число помещается в int диапазон, то оно хранится в переменной _sign;
2. если число не помещается в int диапазон, то его знак хранится в переменной _sign (-1 – для отрицательного и 1 – для положительного), а массив _bits содержит коэффициенты a_i разложения длинного числа с основанием 2 32 .

Основание β = 2 32 , является неплохим выбором, поскольку со степенью двойки легче работать на низком уровне (умножение и деление на степень двойки соответствует битовым сдвигам влево и вправо), а так же за раз будут обрабатываться целых 32 разрядов числа, что позволяет достаточно быстро совершать операции над ними.

В общем, структура BigInteger является полноценной реализацией длинной арифметики на платформе .NET. При этом Microsoft постаралась максимально близко приблизить её к примитивным числовым типам: экземпляр BigInteger можно использовать точно так же, как и любой другой целочисленный тип. BigInteger перегружает стандартные числовые операторы для выполнения основных математических операций, таких как сложение, вычитание, деление, умножение, вычитания, отрицание и унарное отрицание. Можно также использовать стандартные числовые операторы для сравнения двух значений BigInteger друг с другом. Как и другие типы целого числа, BigInteger поддерживает битовые операторы And, Or, XOR, сдвиг влево и сдвиг вправо.

Для языков, не поддерживающих пользовательские операторы, структура BigInteger также предоставляет эквивалентные методы для выполнения математических операций. Это относится к методам Add, Divide, Multiply, Negate, Subtract и некоторым другим. Точно так же Microsoft поступило в реализации структуры Decimal.

Многие члены структуры BigInteger напрямую соответствуют членам других целых типов. Кроме того, BigInteger добавляет такие элементы как:

• IsEven – определяет является ли число чётным;
• IsPowerOfTwo — определяет является ли число степенью двойки;
• Sign — возвращает значение, указывающее знак числа BigInteger;
• Abs — возвращает абсолютное значение числа BigInteger;
• DivRem — возвращает частное и остаток от операции деления;
• GreatestCommonDivisor — возвращает наибольший общий делитель для двух чисел;
• Log — возвращает логарифм указанного числа в системе счисления с указанным основанием;
• Max / Min — возвращает наибольшее / наименьшее из двух чисел;
• ModPow — выполняет модульное деление числа, возведенного в степень другого числа;
• Pow — возводит значение BigInteger в заданную степень.

Пару слов о BigInteger в Mono и Java

Следует отметить, что Mono так же обладает поддержкой длинной арифметики. Реализация структуры BigInteger в Mono практически ничем не отличается от реализации Microsoft, кроме как, того что в ней нет оптимизации для чисел представимых типом int.

То есть число 17 в Mono будет представлено парой:

_sign = 1 // знак числа
_bits =

Аналогичная реализация BigInteger представлена в Java:

Поскольку в Java отсутствуют беззнаковые типы, то массив mag имеет тип int[]. Соответственно представления длинного числа в Java и .NET будут отличаться. В .NET представление будет немного эффективнее, поскольку тип uint охватывает больший диапазон:

В Java, так же как и в Mono нет оптимизации для чисел, представимых типом int.

Производительность BigInteger

Работая с длинным числом BigInteger, необходимо помнить о возможных проблемах связанных с производительностью. Например, казалось бы, безобидный оператор ++ может оказать существенное влияние на производительность:

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

В данном примере, можно поступить следующим образом: выполнить промежуточные операции, используя обычные числовые типы, а затем использовать BigInteger:

Другие числовые типы .NET Framework также являются неизменяемыми. Однако поскольку тип BigInteger не имеет верхней или нижней границы, его значения могут расти до очень больших значений и иметь измеримое влияние на производительность.

Вместо заключения

Подводя итог, можно сказать, что платформа .NET, начиная с 4 версии, обзавелась полноценной реализацией целочисленной длинной арифметики. Возможно, для полного счастья осталось реализовать структуру BigRational, которая уже достаточно давно присутствует в статусе бета в .NET BCL.

Описание структуры BigRational: структура BigRational основывается на типе BigInteger, который был представлен в .NET Framework 4 и позволяет создавать рациональные числа произвольной точности. Рациональное число представляет собой отношение двух целых чисел, и в этой реализации структуры BigRational в качестве делимого (числителя) и делителя (знаменателя) используется тип BigInteger.

За замечание спасибо пользователям: gouranga

Источник