Как печатать действительно большие числа в C++
https://stackoverflow.com/questions/240876
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть этот код
#include <iostream>
using namespace std;
int main(int argc,char **argv) {
unsigned long long num1 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995LL;
unsigned long long num2 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999996LL;
unsigned long long num3 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997LL;
unsigned long long num4 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998LL;
unsigned long long num5 = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999LL;
cout << (unsigned long long)(num1 * num2 * num3 * num4 * num5) << endl;
return 0;
}
Как вы можете видеть, цифры огромны, но когда я делаю математические расчеты, я получаю следующее:18446744073709551496
Во время компиляции я получаю следующие предупреждения:
warning: integer constant is too large for its type|
In function `int main(int, char**)':|
warning: this decimal constant is unsigned only in ISO C90|
...
Решение
Ваш результат больше, чем тип long long - вам нужно взглянуть на BigInteger или библиотеку произвольной точности что-то вроде gmp
Другие советы
Эти числа не вписываются ни в какие типы данных C ++. Если вы просто хотите распечатать их, сохраните числа в строку. Если вы хотите заняться математикой, найдите математическую библиотеку произвольной точности и используйте ее.
Если вы хотите, чтобы литералы были такими большими в вашем коде, вам нужно будет ввести их как строковые литералы и загрузить их в некоторый класс BigInt. В настоящее время нет способа выразить такие большие целочисленные литералы в исходном коде (хотя, надеюсь, C ++ 0x устранит этот недостаток).
Если вы используете библиотеку BigInteger , взгляните на stringToBigUnsigned в BigIntegerUtils.hh для построения большого целого числа из строки.
#include "BigUnsigned.hh"
#include "BigIntegerUtils.hh"
BigUnsigned num1 = stringToBigUnsigned (
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999995"
);
Что вы пытаетесь сделать?Понимаете ли вы основы работы с двоичными и десятичными числами?Почему 8 бит содержат только значения от 0 до 255, 12 бит — от 0 до 4095 и т. д.?Сколько бит нужно для хранения интересующего вас числа?Или, лучше сказать, насколько большое число вы заинтересованы в создании?И вы используете девятки, чтобы увеличить число?А как насчет шестнадцатеричного 0xF...вместо?Если вам нужно самое большое беззнаковое число (в пределах одного из стандартных целочисленных типов), почему бы и нет:
беззнаковый длинный длинный a,b;
а = -1;//что кажется неправильным смешивать знаковые и беззнаковые числа, но это действительно так: перед сохранением число преобразуется в беззнаковое
б = 0;б--;//делает то же самое, что и выше
Вам действительно нужна точность на этом уровне?Вы понимаете, что для умножения может потребоваться результат, вдвое превышающий размер каждого операнда?0xFF * 0xFF = 0xFE01, если бы в этом случае вы использовали 8-битные целые числа, вы не смогли бы выполнить математические операции.Ситуация становится только хуже, если вы продолжаете умножать 0xFF * 0xFF * 0xFF = 0xFD02FF.
Что пытаетесь сделать?
Увидев ваш ответ:
Эйлера номер 8 я раньше не видел.Звучит как хороший вопрос для собеседования, поскольку для его решения требуется всего несколько строк кода.
Другой ваш ответ:
Числа...
Вероятно, потому, что у нас 10 пальцев на руках (и, возможно, 10 на ногах), мы растем с «основанием 10».Наши часы по большей части имеют систему счисления с основанием 60, но они были смешаны с основанием 10, чтобы сделать их более запутанными.В любом случае, основание 10 означает, что для каждого заполнителя номера у вас есть одна из 10 уникальных цифр, и когда вы достигаете максимума в этом месте, вы переходите на следующее место.Это всё из начальной школы.
000
001
002
003
...
008
009
010
011
012
...
Посмотрите, как самая правая цифра имеет 10 символов (0,1,2,3,4,5,6,7,8,9), и когда она достигает последнего символа, она начинается заново, а цифра слева от нее увеличивается на один.Это правило справедливо для всех базовых систем счисления.
Это верно для базы 2, за исключением того, что здесь только два символа: 0 и 1.
000
001
010
011
100
101
...
То же самое относится и к восьмеричным числам, но 8 символов (0,1,2,3,4,5,6,7).
000
001
002
003
004
005
006
007
010
011
012
013
...
То же самое верно и для шестнадцатеричных символов, 16 символов (0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f)
000
001
002
003
004
005
006
007
008
009
00а
00б
00с
00д
00е
00f
010
011
012
013
...
Я собирался рассказать, почему в компьютерах используется двоичная система счисления вместо других (например, 10).Суть в том, что легко иметь два состояния: включено или выключено, либо высокое и низкое.Два состояния — это как два символа 1 и 0 в базе 2.Попытка настроить электронику на более чем два состояния в пределах доступного напряжения является трудной задачей, по крайней мере, раньше, поддерживать напряжение около нуля вольт или выше некоторого небольшого количества вольт относительно легко, поэтому цифровая электроника использует два состояния, двоичные.
Даже простая задача для человека в двоичном формате сложна, простая математика для второго класса все еще содержит много единиц и нулей.Итак, восьмеричная система стала популярной, потому что она позволяла мыслить группами по три бита и использовать знакомые нам символы: числа 0,1,2,3,4,5,6,7.Но группы по четыре, что является еще одной степенью двойки, дают людям гораздо большую умственную вычислительную мощность, чем восьмеричная, шестнадцатеричная система основана на 4 битах, что также является степенью двойки.Нам пришлось добавить больше символов к 10, которые мы заимствовали из традиционной арабской основы 10, поэтому были использованы первые 6 букв алфавита.Восьмеричное число используется редко, если вообще когда-либо используется. Вы можете определить возраст человека, если он думает о восьмеричном формате, а не о шестнадцатеричном.(Я из шестнадцатеричного поколения, но работал с представителями восьмеричного поколения, которые борются с шестнадцатеричным, потому что не могут в уме перейти от восьмеричного к двоичному и шестнадцатеричному).
Система счисления с основанием 10 в компьютере — это то же самое, что среднестатистический человек думает в шестнадцатеричном формате.компьютеры не работают с основанием 10 (ну, для ленивых людей они использовали bcd), они используют основание 2.Десятичное число 1234 в компьютере на самом деле равно 0x4D2 или 0b010011010010.Это значение, скажем, вы хотите сложить 1234 плюс какое-то другое число, которое вам нужно, и которое не имеет ничего общего с символами 1, 2, 3 и 4.Но чтобы опубликовать этот ответ в stackoverflow, мы не используем число, которое мы используем ASCII, поэтому 1234 в ascii — это 0x31, 0x32, 0x33, 0x34, что важно знать для вашего решения Эйлера, предполагая, что 1000-значное число было предоставлено в виде строки ascii, каким оно должно быть, иначе вам придется преобразовать его из двоичного кода в ascii, поскольку проблема связана с базой 10, а не с базой 2 по определению.
Итак, вернемся к тому, о чем я спросил.Допустим, у вас есть 4 бита памяти для хранения числа. Насколько большое число вы можете сохранить?Если вы думаете только по основанию 10, вы можете подумать, что это число — это 9, потому что вы обучены использовать самый большой символ в каждом месте хранения, 99999 — это самое большое число, если у вас есть 5 мест хранения по основанию 10.Возвращаясь к четырем битам, самый большой символ для одного бита — это 1, поместите это число в каждое место хранения, и вы получите 1111 (четыре единицы).Просто взглянув на эти четыре, вы сможете легко представить себе восьмеричную и шестнадцатеричную версию того же восьмеричного числа 17 или шестнадцатеричного числа F.Чтобы увидеть десятичное число, нужны математические действия или, в данном случае, запоминание, это число равно 15 десятичному числу.Таким образом, самое большое четырехбитное число, которое вы можете иметь, — это 0xF или 15, а не 9.А как насчет 8-битного числа?0xFF или 255 (2 в 8-й степени минус один).Самое большое 16-битное число?65535 и т. д.
Поэтому, когда я спрашиваю, сколько бит вы пытаетесь использовать, я имею в виду именно это.Посмотрите на это число 99999.Опять же, вы можете подумать, что это самое большое число по основанию 10, но для компьютера это только часть пути: десятичное число 99999 — это 0x1869F, для хранения которого требуется 17 бит памяти, самое большое 17-битное число, которое вы можете сохранить, — это 0x1FFFF, что равно 131071. что немного больше 99999.Поэтому, когда вы хотите думать на компьютере о больших числах и математических вычислениях, вам нужно думать в двоичном (или шестнадцатеричном) формате.
Первоначально вы делали умножение, что по-прежнему является частью задачи Эйлера, но то, о чем я спрашивал, было связано с точностью и хранением битов.Вот некоторые основы, и я не буду вдаваться в них, но вы можете понять, почему мы полагаемся на единицы с плавающей запятой в компьютерах.
Возьмите самое большое 4-битное число 1111 (двоичное), которое имеет 15-значный вид.Добавьте это к самому большому четырехбитному числу, и вы получите 15+15 = 30 = 0x1E или 11110 двоичное число.Итак, чтобы сложить два четырехбитных числа, вам понадобится пять бит для хранения ответа.Компьютеры сохраняют бит «переноса» для этого дополнительного бита.По сути, математические функции сложения/вычитания целых чисел в компьютере позволяют вам иметь N+1 бит.Итак, если это 32-битный компьютер, у вас в основном есть 33 бита для математических вычислений сложения и добавления.
Проблема в умножении и делении, которые даже сегодня многие процессоры не поддерживают (да, у многих нет fpu, и они только складывают и вычитают, иногда умножают, но деление происходит редко.Умножение и деление требуют большого количества электроники, но компромисс в том, что вы можете выполнять их сложением и вычитанием в программном обеспечении).Возьмем умножение в худшем случае для четырехбитной системы 1111 * 1111 = 11100001 Таким образом, для хранения результата 4-битного умножения требуется 8 бит, вы быстро обнаружите, что если бы у вас была 4-битная система, БОЛЬШИНСТВО умножений, которые вы хотите сделать, привели бы к числу, которое не может быть сохранено в 4 битах.Итак, когда я увидел, как вы берете 64-битные целые числа (длинное число без знака часто составляет 64 бита) и умножаете четыре раза, это означает, что вам нужно 64 * 5 или 320-битное целое число для хранения ответа, вы пытались поместить этот ответ в 64 больших результата, который довольно часто, в зависимости от компилятора и компьютера, с радостью выполнит и обрежет старшие биты, оставив вам нижние 64 бита результата, которые могут легко выглядеть меньше, чем любой из ваших операндов, как я и думал. возможно, вы сделали это сначала.
Плавающая точка — это не что иное, как экспоненциальное представление, но в двоичном формате, если вы хотите умножить числа 1234 и 5678, используя экспоненциальное представление, вы должны взять 1,234*10^3 умножить на 5,678*10^3 и получить 7,007*10^6.Вы сохраняете точность и можете представлять более широкий диапазон чисел.Я не буду вдаваться в подробности, как это работает в двоичном формате.Но это не работает для вашего первоначального вопроса.
Ааа, последнее, что нужно уточнить, что я делал в своем вопросе/ответе.Отрицательные целые числа в двоичном формате.Из-за взаимосвязей между сложением и вычитанием и базовыми системами вы можете сыграть несколько трюков.Скажем, я хотел вычесть 1 из числа 7 (десятичного), используя двоичный код.Ну, не существует такой вещи, как схема вычитания, вместо этого вы добавляете отрицательное число, поэтому вместо 7 - 1 на самом деле получается 7 + (-1), это имеет значение:
0111 + ???? = 0110
Какое число можно прибавить к 7, чтобы получить 6... в двоичном формате?
0111 + 1111 = 0110
Отрицательные числа в двоичной системе называются «дополнением до двух», короче говоря, ответ — «инвертировать и прибавить 1».Как представить минус 1 в двоичном формате?возьмите плюс один 0001, затем инвертируйте его, что означает, что единицы станут нулями, а нули — единицами (также известными как дополнение единиц) 1110, а затем добавьте единицу 1111.Минус один — это особое число в компьютерах (ну, везде), поскольку независимо от того, сколько бит у вас есть, оно представлено как все единицы.Итак, когда вы видите, что кто-то делает это:
беззнаковый символ а;
а = -1;
Компилятор сначала смотрит на это -1 и думает ...11111(двоичный), затем он смотрит на знак равенства и другую сторону, о, вы хотите, чтобы все были единицами, он видит, что у вас есть целое число со знаком и целое число без знака но преобразование заключается в простом перемещении битов, поэтому выше вы говорите, что хотите = 0xFF;(при условии, что это 8-битный беззнаковый символ).
Некоторые компиляторы могут жаловаться, что вы пытаетесь сохранить отрицательное число в беззнаковом числе.Другие компиляторы будут смотреть на это -1 и видеть его как 32-битную или в наши дни, возможно, 64-битную целочисленную константу со знаком, а затем, когда он вычисляет равенство в 8-битную беззнаковую константу, вы получите предупреждение о том, что вы не можете сохранить -1 в знаковой константе. или беззнаковый символ без приведения типа.Но если вы сделаете это:
а = 0;а--;
Всем компиляторам это понравится.и не буду жаловаться, он просто сжигает вычислительные циклы во время выполнения, а не во время компиляции.
Где-то друг рассказал мне о книге, в которой последовательно выполняются двоичные математические операции.Например, чтобы отрицать число, обычно вы выполняете инвертирование и добавляете один трюк, но с карандашом и бумагой некоторые могут подсказать вам другой трюк.Начиная справа, скопируйте нули до первой 1 включительно, затем инвертируйте после этого, так что минус 2
0010
1110
Начиная справа, скопируйте 0, затем первый, затем инвертируйте оставшиеся биты по мере движения влево.
минус 6
0110
1010
минус 4
0100
1100
Предположительно, есть трюки для сложения и вычитания (ну, это просто), а также для умножения и деления.Если вы выполняете их последовательно, вы можете выполнять бесконечно длинные математические операции в двоичном формате с одним и тем же alu.Если бы вы знали, как это сделать, вы могли бы реализовать это в программном обеспечении, и ваш первоначальный вопрос об умножении больших констант (при условии сохранения всей точности) тривиален на любом компьютере.
Ответ, который вы получили, 18446744073709551496, связан с тем, что ваши 999 ... 9 были усечены при назначении на длинный long, а также переполнились несколько операций. Это детерминированный, но фактически просто случайный набор битов.
unsigned int представляет системное слово. Сегодня это слово будет максимум до 2 ^ 32 -1 или 2 ^ 64 - 1, в зависимости от того, является ли ваша система 32-битной или 64-битной. Ты бьешь по кепке.
Вы должны написать класс bignum или использовать его вне сети.
Почему вы все равно решаете эту проблему?
Числа не могут вписываться в диапазон longs unsigned long long , поэтому вы можете использовать библиотеку GMP или использовать строку для представления больших чисел, как я сделал для вычисления факториала числа, например, 50:
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
unsigned int nd, nz;
unsigned char *ca;
unsigned int j, n=50, q, temp;
int i;
double p;
p = 0.0;
for(j = 2; j <= n; j++)
{
p += log10((double)j);
}
nd = (int)p + 1;
ca = new unsigned char[nd+1];
if (!ca)
{
cout << "Could not allocate memory!!!";
exit(0);
}
for (i = 1; (unsigned)i < nd; i++)
{
ca[i] = 0;
}
ca[0] = 1;
p = 0.0;
for (j = 2; j <= n; j++)
{
p += log10((double)j);
nz = (int)p + 1;
q = 0;
for (i = 0;(unsigned) i <= nz; i++)
{
temp = (ca[i] * j) + q;
q = (temp / 10);
ca[i] = (char)(temp % 10);
}
}
cout << "\nThe Factorial of " << n << " is: ";
for( i = nd - 1; i >= 0; i--)
{
cout << (int)ca[i];
}
// delete []ca;
return 0;
}
