Como imprimir realmente grandes números em C ++
https://stackoverflow.com/questions/240876
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho esse código
#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;
}
Como você pode ver os números são enormes, mas quando eu faço a matemática não fico com esta: 18446744073709551496
Em tempo de compilação eu recebo essas advertências:
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|
...
Solução
O resultado é maior do que o long long tipo - você precisa olhar para um BigInteger ou arbitrária biblioteca de precisão , algo como gmp
Outras dicas
Esses números não se encaixam em nenhum tipos de dados de C ++. Se você quiser apenas para imprimi-los, guarde os números em uma string. Se você quiser fazer contas sobre ele, encontrar uma biblioteca precisão matemática arbitrária e usar isso.
Se você quiser literais esta grandes em seu código, você vai ter que inseri-los como strings literais e carregá-los em uma classe BigInt de algum tipo. Não há nenhuma maneira de expressar inteiro literais que grande no código-fonte agora (embora C ++ 0x esperamos endereço que défice).
Se você estiver usando a biblioteca BigInteger , dê uma olhada na função stringToBigUnsigned em BigIntegerUtils.hh para a construção um grande número inteiro de uma string.
#include "BigUnsigned.hh"
#include "BigIntegerUtils.hh"
BigUnsigned num1 = stringToBigUnsigned (
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999999999999999999999999999999999999999999999999"
"99999999999999999999999999999999999995"
);
O que é que você está tentando fazer? Você entende o básico de números binários e decimais? Por 8 bits só mantém os valores de 0 a 255, 12 bits 0 - 4095, etc? Quantos bits são necessários para manter o número que você está interessado? Ou melhor, como de um grande número você está interessado em criar? E você está usando 9s para fazer o número maior? E sobre hex 0xF ... em vez disso? Se você quer o maior número sem sinal (dentro de um dos tipos inteiros padrão) por que não:
unsigned long long, uma b;
a = -1; // que apenas parece mistura errada assinados e não assinados, mas é válido, o número é convertido para unsigned antes de armazenar
b = 0; B--; // faz a mesma coisa como acima
Você realmente precisa de precisão a este nível? Você percebe que multiplica pode exigir um resultado duas vezes o tamanho de cada operando? 0xFF * 0xFF = 0xFE01, se neste caso que você estava usando 8 bit inteiros você não poderia fazer a matemática. Ele só fica pior à medida que continuam a se multiplicar 0xFF * 0xFF * 0xFF = 0xFD02FF.
O que estamos tentando fazer?
Ao ver sua resposta:
Eu não vi Euler número 8 antes. Soa como uma boa pergunta da entrevista, uma vez que leva apenas algumas linhas de código para resolver.
A sua outra resposta:
Números ...
Provavelmente porque temos 10 dedos (e talvez 10 pés) que crescem com "base 10". Nossos relógios são base 60 para a maior parte, mas tem sido misturado com base 10 para torná-lo mais confuso. De qualquer forma, base 10, meios para cada número de marcador que você tem um de 10 dígitos únicos, quando você atingir o máximo nesse lugar que você rolar para o próximo lugar. Isso é tudo coisa de escola primária.
000
001
002
003
...
008
009
010
011
012
...
Veja como o direito mais dígito tem 10 símbolos (0,1,2,3,4,5,6,7,8,9) e quando atinge o último símbolo que começa uma e uma para a esquerda incrementa por um. Esta regra vale para todos os sistemas de numeração base.
É verdade para a base 2, exceto há apenas dois símbolos, 0 e 1
000
001
010
011
100
101
...
O mesmo é verdadeiro para octal, mas 8 símbolos (0,1,2,3,4,5,6,7)
000
001
002
003
004
005
006
007
010
011
012
013
...
E o mesmo é verdade para hexadecimal, 16 símbolos (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
00a
00b
00c
00d
00E
00f
010
011
012
013
...
Eu estava prestes a ir para os porquês de usar binário sobre outras bases (como 10) em computadores. A linha inferior é fácil ter dois estados ligado ou desligado, ou alta e baixa. Dois estados é como dois símbolos 1 e 0 em base 2. tentando manter eletrônicos ajustados para mais de dois estados dentro da tensão disponível é dura, pelo menos, que costumava ser, mantendo-a perto de zero volts ou acima algum pequeno número de volts é relativamente fácil, eletrônicos de modo digitais usam dois estados, binário.
Mesmo uma tarefa simples para um ser humano em binário é prolixo, matemática simples segunda série ainda é um monte de zeros e uns. Então octal tornou-se popular porque permitiu que você pense em grupos de três bits e você poderia usar símbolos que estão familiarizados com como números 0,1,2,3,4,5,6,7. Mas grupos de quatro, que é outra potência de 2, dá os seres humanos muito poder de computação mais mental do que octal, hexadecimal é baseado em 4 bits que também é uma potência de 2. Tivemos que acrescentar mais símbolos a 10 nós emprestado do traditial de base arábica 10, então utilizou-se o primeiro 6 do alfabeto. Octal é raramente ou nunca utilizado, você pode dizer alguém idade, se eles pensam octal em vez de hexadecimal. (Eu sou da geração hex mas tenho trabalhado com os da geração octal que luta com hex porque eles não podem obter a partir de octal para binário em hexadecimal em sua mente).
Base de Dados de 10 em um computador é comoo pensamento humano médio em hexadecimal. computadores não fazer base 10 (bem para os seres humanos preguiçosos que eles usaram para fazer BCD), eles fazem base 2. O número decimal 1234 em um computador é realmente 0x4D2 ou 0b010011010010. Isso é como um valor, digamos que você deseja adicionar 1.234 mais algum outro número que você precisa esse valor que não tem nada a ver com os SymbOS 1, 2, 3 e 4. Mas para postar esta resposta em stackoverflow nós não usar o que número uso ASCII, então 1234 em ASCII é 0x31, 0x32, 0x33, 0x34, que é importante saber para a sua solução Euler assumindo o número 1000 dígitos foi fornecida como uma string ASCII, que teria de ser ou você teria que convertê-lo de binário para ascii já que o problema é um problema de base 10 e não base 2 por definição.
Então, de volta para o que eu tinha pedido. Digamos que você teve 4 bits de memória para armazenar um número, como de um grande número que você pode armazenar? Se você acha base 10 só você pode pensar que o número é um 9, porque você são treinados para pensar em usar o maior símbolo em cada local de armazenamento, 99999 é o maior número, se você tem 5 locais de armazenamento em base 10. Voltar para quatro bits no entanto, o maior símbolo de um único bit é 1, colocar esse número em cada local de armazenamento que você começa 1111 (quatro ones). Basta olhar para esses quatro que você deve ser capaz de em sua mente facilmente ver a versão octal e hexadecimal do mesmo número 17 octal ou F hex. Para ver decimal leva matemática, ou neste caso, a memorização, esse número é de 15 decimal. Portanto, o número de quatro bits maior que você pode ter é 0xF ou 15 não 9. Que tal um número de 8 bits? 0xFF ou 255 (2 a 8 de energia menos um). Maior número de 16 bits? 65535, etc.
Então, quando eu perguntar quantos bits que você está tentando usar isso é o que quero dizer. Olhar para este número 99999. Novamente base 10 você pensaria que é o maior número, mas a um computador é apenas a maneira da parte lá, 99999 decimal é 0x1869F, que leva 17 bits de memória para armazenar, o número maior de 17 bit que puder loja é 0x1FFFF que é 131071 que é um pouco maior do que 99999. Então, quando você quer pensar grandes números e matemática em um computador você tem que pensar binário (ou hex).
Originalmente você estava fazendo multiplicações, que ainda é parte do problema de Euler, mas o que foi que eu estava perguntando sobre estava relacionada com precisão e armazenamento bit. Aqui estão alguns fundamentos, e eu não vou chegar a ele, mas você pode ver porque contamos com unidades flutuantes de ponto em computadores.
Leve o maior de 4 bits número 1111 (binário), que é 15 decimal. Acrescentar que, com o número maior de quatro bits e você terá 15 + 15 = 30 = 0x1E ou 11110 binário. Então, para adicionar dois números de quatro bits que você precisa cinco bits para manter a sua resposta. Computadores manter um bit "carry" para este bit extra. Essencialmente os subtrair / funções inteiro matemática adicionar no computador permitem que você tenha N + 1 bits. Então, se é um computador de 32 bits, você basicamente tem 33 bits para adicionar / sub matemática.
O problema é multiplicar e dividir, que hoje mesmo muitos processadores não suportam (sim muitos não têm fpu e só não somar e subtrair, por vezes, se multiplicam, mas dividir é raro. Multiplicar e dividir ter um monte de eletrônicos do off trade é que você pode fazê-los com soma e subtrai em software). Leve o pior caso multiplicar para um sistema de quatro bits 1111 * 1111 = 11.100.001 por isso leva 8 bits para armazenar o resultado de um 4 bits multiplicar, você vai descobrir rapidamente que se você tivesse um sistema de 4 bits a maioria dos multiplica você quer fazer vai resultar um número que não pode ser armazenado em 4 BITS. Então, quando eu vi você tomando 64 bit inteiros (o unsigned long long é muitas vezes 64 bits) e multiplicando por quatro vezes, isso significa que você precisa de 64 * 5 ou um número inteiro de 320 bit para armazenar a sua resposta, você estava tentando colocar essa resposta em um 64 grande resultado, que, muitas vezes, dependendo do compilador e computador terá todo o prazer fazer e irá truncar os bits superiores deixando-o com os mais baixos 64 bits do resultado que pode facilmente olhar menor do que qualquer um dos seus operandos, que é o que eu pensava vocêspoderia ter feito em primeiro lugar.
ponto flutuante não é muito mais do que a notação científica, mas em binário, se você quisesse multiplicar o número 1234 e 5678 usando a notação científica você levaria 1.234 * 10 ^ 3 vezes 5.678 * 10 ^ 3 e obter 7,007 * 10 ^ 6 . Você mantém sua precisão e são capazes de representar uma ampla gama de números. Eu não vou entrar em como isso funciona em binário. Mas ele não funciona para sua pergunta original.
Ahh, a última coisa a esclarecer o que eu estava fazendo na minha pergunta / resposta. inteiros negativos em binário. Por causa das relações entre adição e subtração e sistemas de base você pode jogar alguns truques. Digamos que eu queria subtrair 1 a partir do número 7 (decimal) usando binário. Bem, não há tal coisa como um circuito subtração, você, em vez adicionar um número negativo então ao invés de 7-1 é realmente 7 + (-1), ele faz a diferença:
0111 + ???? = 0110
O número que você pode adicionar a 7 para obter 6 ... em binário?
0111 + 1111 = 0110
Os números negativos em binário são chamados de "complemento de dois", longa história curta, a resposta é "invertido e adicionar 1". Como você representar menos 1 em binário? tomar mais um 0001, em seguida, invertê-lo significa faz esses zeros e os zeros (também conhecido como complemento para um) 1110, em seguida, adicionar um 1111. Menos um é um número especial em computadores (bem em todos os lugares) como não importa quantos bits você tem isso é representado como todos os queridos. Então, quando você vê alguém fazer isso:
unsigned char a;
a = 1;
O compilador primeiros olhares em que -1 e pensa ... 11111 (binário), então ele olha para o sinal de igual eo outro lado, oh, você quer um ser todos aqueles, ele vê que você tem um inteiro assinado e um sem assinatura, mas a conversão é apenas para mover os bits mais para que você está dizendo acima que você quer a = 0xFF; (Assumindo uma 8 bits sem sinal carvão animal).
Alguns compiladores podem queixar-se de que você está tentando armazenar um número negativo em um número sem sinal. Outros compiladores vai olhar para isso -1 e vê-lo como um 32 bits ou nos dias de hoje talvez 64 bits constante inteiro assinado e, em seguida, quando se avalia os iguais em um 8 bits sem sinal você receberá um aviso de que você não pode armazenar -1 em um assinado ou de char não assinado sem um estereotipado. Mas se você fizer isso:
A = 0; a -;
Todos os compiladores vai gostar disso. e não vai reclamar, ele só queima ciclos de computação em tempo de execução em vez de tempo de compilação.
Agora, em algum lugar um amigo me falou de um livro que faz matemática binária em série. Por exemplo, para negar um número, geralmente você fazer o truque invertido e um anúncio, mas com lápis e papel alguns podem dizer-lhe o outro truque. A partir da direita copiar os zeros até e incluindo o primeiro 1, então invertido depois disso, então menos 2
0010
1110
A partir da direita copiar o 0, em seguida, o primeiro, em seguida, invertido os bits restantes como você vá para a esquerda.
menos 6
0110
1010
menos 4
0100
1100
Supostamente existem truques para fazer somar e subtrair (bem duh, aqueles são fáceis), mas também multiplicar e dividir. Se você fazê-las em série, em seguida, você pode fazer infinitamente longo de matemática em binário com o mesmo alu. Se você fosse para saber como fazer isso você poderia implementar isso em software e sua pergunta original de multiplicar grandes constantes (com o pressuposto de reter toda a precisão) é trivial em qualquer computador.
A resposta que você tem, 18446744073709551496, é devido ao seu 999 ... 9s sendo truncado quando atribuído a um longo, mais as múltiplas operações transbordar. Sua determinista, mas efetivamente apenas uma coleção aleatória de bits.
unsigned int representa uma palavra sistema. Hoje, essa palavra vai máximo para fora em ambos os 2 ^ 32 -1 ou 2 ^ 64-1, dependendo se seu sistema é de 32 bits ou 64 bits. Você está batendo a tampa.
Você tem que escrever uma classe bignum ou usar um off 'na rede.
Por que você está fazendo este problema, afinal?
Os números não podem se encaixar na faixa unsigned long long por isso ou você poderia usar GMP biblioteca ou uso corda para representar números grandes como eu fiz para o cálculo fatorial de número como 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;
}
