Como implementar grande int em C ++

Question

Eu gostaria de implementar uma classe int grande em C ++ como uma programação de exercício de uma classe que pode lidar com números maiores do que um long int. Eu sei que existem várias implementações de código aberto lá fora já, mas eu gostaria de escrever minha própria. Eu estou tentando obter uma sensação de que a abordagem correta é.

Eu entendo que a estratégia geral é obter o número como uma string, e depois dividi-lo em números menores (um dígito, por exemplo), e colocá-los em uma matriz. Neste ponto, deve ser relativamente simples de implementar os vários operadores de comparação. A minha principal preocupação é como eu iria implementar coisas como adição e multiplicação.

Eu estou procurando uma abordagem geral e aconselhamento em oposição ao código de trabalho real.

Answer 1

As coisas a considerar para uma classe int grande:

1. Matemática operadores: +, -, /, *,% Não se esqueça de que sua classe pode estar em ambos os lados da operador, que os operadores podem estar acorrentado, que um dos operandos poderia ser um int, float, double, etc.

2. i operadores / o: >>, << Este é onde você descobrir como fazer corretamente criar sua classe de entrada do usuário, e como formatá-lo para a saída também.

3. Conversões / moldes: Descobrir Que tipos / classes seu grande int classe deve ser conversível para e como lidar corretamente com o conversão. Uma lista rápida faria incluem dupla e flutuador, e pode incluem int (com limites adequados verificação) e complexo (supondo que ele pode lidar com a gama).

Answer 2

Um desafio divertido. :)

Eu suponho que você quer inteiros de comprimento arbitrário. Eu sugiro a seguinte abordagem:

Considere a natureza binária da "int" tipo de dados. Pense em usar operações binárias simples para imitar o que os circuitos em sua CPU fazem quando adicionar coisas. No caso você está interessado mais em profundidade, considere a leitura este artigo da Wikipedia sobre meio-somadores e full-somadores . Você estará fazendo algo semelhante a isso, mas você pode ir para baixo tão baixo nível que - mas ser preguiçoso, eu pensei que tinha acabado, renunciar e encontrar uma solução ainda mais simples.

Mas antes de entrar em quaisquer detalhes algorítmicos cerca de adição, subtração, multiplicação, vamos encontrar alguma estrutura de dados. Uma maneira simples, é claro, para guardar coisas em um std :: vector.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

Você pode querer considerar se você quiser fazer o vetor de um tamanho fixo e se preallocate-lo. Razão é que para diversas operações, você terá que passar por cada elemento do vetor - O (n). Você pode querer saber improviso quão complexa uma operação vai ser e um fixo n faz exatamente isso.

Mas agora a alguns algoritmos sobre a operação sobre os números. Você poderia fazê-lo em um de nível lógico, mas vamos usar esse poder CPU mágica para resultados calcular. Mas o que vai assumir a partir da lógica de ilustração de meia pensão e FullAdders é a forma como ele lida com carrega. Como exemplo, considere como você implementar o + = operador . Para cada número em BigInt <> :: value_, você adicionar os e veja se o resultado produz alguma forma de transporte. Não vamos estar fazendo isso mordeu-wise, mas dependem da natureza do nosso BaseType (seja ele longo ou int ou curto ou qualquer outro): ele transborda.

Com certeza, se você adicionar dois números, o resultado deve ser maior do que a maior um desses números, certo? Se não for, então o resultado transbordou.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

A outra operação aritmética ir análoga. Heck, você pode até mesmo usar os STL-functors std :: plus e std :: menos, std :: vezes e std :: divide, ..., mas mente a carry. :) Você também pode implementar multiplicação e divisão usando suas mais e menos operadores, mas isso é muito lento, porque isso iria recalcular os resultados já calculados em chamadas anteriores a mais e menos em cada iteração. Há um monte de bons algoritmos lá fora, para esta tarefa simples, uso wikipedia ou na web

.

E, claro, você deve implementar operadores padrão, tais como operator<< (basta mudar cada valor em value_ para a esquerda para n bits, começando no value_.size()-1 ... oh e lembrar o carry :), operator< - você pode até mesmo otimizar um pouco aqui, verificando o número bruto de dígitos com size() primeiro. E assim por diante. Então faça sua classe útil, por befriendig std :: ostream operator<<.

Hope esta abordagem é útil!

Answer 3

Há uma seção completa sobre este: [The Art of Computer Programming, vol.2:. Seminumerical Algoritmos, secção 4.3 Multiple Precision Aritmética, pp 265-318 (ed.3)]. Você pode encontrar outro material interessante no capítulo 4, Aritmética.

Se você realmente não quer olhar para outra aplicação, você já pensou o que é que você está fora de aprender? Existem inúmeros erros a serem feitas e descobrindo aqueles é instrutivo e também perigoso. Há também desafios na identificação de economias computacionais importantes e ter estruturas de armazenagem adequadas para evitar problemas de desempenho graves.

Um Desafio pergunta para você: Como você pretende testar sua implementação e como você propõe para demonstrar que é aritmética é correto?

Você pode querer outra implementação de teste contra (sem olhar como ele faz isso), mas vai demorar mais do que isso para ser capaz de generalizar sem esperar um nível excrutiating de testes. Não se esqueça de considerar os modos de falha (fora de problemas de memória, fora da pilha, correndo muito tempo, etc.).

Divirta-se!

Answer 4

Além provavelmente teria de ser feito no padrão de tempo linear algoritmo
mas para a multiplicação você poderia tentar http://en.wikipedia.org/wiki/Karatsuba_algorithm

Answer 5

Depois de ter os dígitos do número em uma matriz, você pode fazer adição e multiplicação exatamente como você faria deles escrita comum.

Answer 6

Não se esqueça de que você não precisa restringir-se a 0-9 como dígitos, ou seja, o uso bytes como dígitos (0-255) e você ainda pode fazer aritmética mão longo da mesma forma que faria para dígitos decimais. Você poderia até usar uma matriz de comprimento.

Answer 7

Eu não estou convencido usando uma string é o caminho certo a seguir - embora eu nunca tenha escrito código de mim mesmo, eu acho que usando uma matriz de um tipo numérico de base pode ser uma solução melhor. A idéia é que você simplesmente estender o que você já tem a mesma forma que a CPU se estende um único bit em um inteiro.

Por exemplo, se você tem uma estrutura

typedef struct {
    int high, low;
} BiggerInt;

Você pode então executar manualmente operações nativas em cada um dos "dígitos" (alta e baixa, neste caso), sendo consciente de condições de transbordo:

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

É um pouco de um exemplo simplista, mas deve ser bastante óbvio como estender a uma estrutura que tinha um número variável de qualquer classe base numérica que você está usando.

Answer 8

Como outros disseram, fazê-lo de forma formado longo mão de idade, mas ficar longe de fazer isso tudo em base 10. Eu sugiro fazer tudo em base de 65536, e armazenar coisas em uma matriz de longs.

Answer 9

Use os algoritmos que você aprendeu na 1ª à 4ª série.
Comece com a coluna queridos, em seguida, as dezenas, e assim por diante.

Answer 10

Se o seu alvo BCD arquitetura suporta (Binary Coded decimal) representação de números, você pode obter algum suporte de hardware para a escrita comum multiplicação / disso que você precisa fazer. Obtendo o compilador para instrução emitem BCD é algo que você vai ter que ler sobre ...

Os chips da série Motorola 68K tinha isso. Não que eu sou amargo ou nada.

Answer 11

O meu início seria ter uma matriz de tamanho arbitrário de inteiros, usando 31 bits e o 32n'd como estouro.

O op partida seria ADD, e em seguida, certifique-negativo, utilizando complemento de 2. Depois disso, subtração flui trivialmente, e uma vez que você tem add / sub, tudo o resto é factível.

Há provavelmente abordagens mais sofisticadas. Mas esta seria a abordagem ingênua de lógica digital.

Answer 12

Pode tentar implementar algo como isto:

http://www.docjar.org/html/ api / java / matemática / BigInteger.java.html

Você só precisaria de 4 bits para um único dígito 0-9

Assim, um valor int permitiria até 8 dígitos cada. Eu decidi que eu ia ficar com uma matriz de caracteres para que eu use o dobro da memória, mas para mim ele só está sendo usado um tempo.

Além disso, quando o armazenamento de todos os dígitos em um único int-o-complica e se alguma coisa pode mesmo retardá-lo.

Eu não tenho quaisquer testes de velocidade, mas olhando para a versão Java BigInteger parece que ele está fazendo uma enorme quantidade de trabalho.

Para mim, fazer o abaixo

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

Answer 13

subtrair 48 a partir de sua seqüência de inteiro e imprimir para obter o número de dígitos grandes. em seguida, executar a operação matemática básica. Caso contrário, vou fornecer a solução completa.