Essa é difícil (números super grandes)

Delphi

25/03/2004

Como eu faco para trabalhar com inteiros de tamanhos super grandes tipo numeros com 200 ou 300 digitos?


Neoramza

Neoramza

Curtidas 0

Respostas

Aroldo Zanela

Aroldo Zanela

25/03/2004

Colega,

Com inteiro não vai ser possível, veja:

TypeRangeFormat
Shortint–128..127signed 8-bit
Smallint–32768..32767signed 16-bit
Longint–2147483648..2147483647signed 32-bit
Int64–2^63..2^63–1signed 64-bit
Byte0..255unsigned 8-bit
Word0..65535unsigned 16-bit
Longword0..4294967295unsigned 32-bit


Que tipo de trabalho precisa fazer exatamente?


GOSTEI 0
Neoramza

Neoramza

25/03/2004

Não....
Eu presciso de números muito maiores. Númedos de 600 bits mais ou menos que em decimal daria uns 180 caracteres. Um doule (64bits) nao chega nem perto.

Tem que ser números tipo esse:

518454657624648932618215834416921409264096042961492164930919309268083218396759326516...
...0191293475610942375192651645149057612390561093456019465123645015613275601293456145...
...609679609182364501723619240561039456139913745698761951345178657


GOSTEI 0
Beppe

Beppe

25/03/2004

Eu já implementei as operações +, -, *, not, neg, e mais algumas pra bigint(não ponto-flutuante), só naum fiz / ou mod. Pra q precisa dessa precisão toda?


GOSTEI 0
Rodriguesap

Rodriguesap

25/03/2004

Pelo que eu entendi, este tamanho de número não pode ser calculado pelo processador, apenas se for calculado em partes. Ao menos foi o que eu entendi, quando tive o mesmo problema com números, no meu casa, 32K ou 32768 dígitos. Neste caso eu desenvolvi umas funções capazes de calcular qualquer tamanho de número, o único problema é que demora, quanto maior o número mais demorado, exatamente porque tratase de cáculos em cima de String. As funções que desenvolvi são capazes de somar, dividir, subtrair e multiplicar números inteiros. Como necessitava apenas de números inteiros, não tentei fazer com números decimais, mais pela técnica que desenvolvi poderei fazer também, entre outras funções como, raiz, expoente e outras que se fizerem necessários.

Pois bem, o princípio que parti foi, do mesmo princípio que aprendemos nos primeiros anos de escola. Então montei as funções para fazer os cálculos como faziamos no papel.

Esta foi a única alternativa que consegui. Espero que ajude.


GOSTEI 0
Marco Salles

Marco Salles

25/03/2004

este tamanho de número não pode ser calculado pelo processador, apenas se for calculado em partes

Eu Acredito Que Seje Por Aí...


GOSTEI 0
Cebikyn

Cebikyn

25/03/2004

Sim, é por aí mesmo (por partes), como mostra este trecho de um artigo sobre inteiros de 128 bits:

type
  Hugeint: packed array [0..3] of LongWord;


Vê-se que, no caso do artigo, o número é composto por 3 partes. O artigo completo pode ser obtido nos link a baixo:

Inline Assembler in Delphi (VII) - 128-bit integer arithmetic
http://www.delphi3000.com/articles/article_3772.asp
ou a tradução p/ português:
http://www.latiumsoftware.com/br/pascal/0045.php5

Nunca vi nenhum exemplo com mais de 128bits, mas o artigo pode dar uma idéia do que pode ser feito e como pode ser feito.


GOSTEI 0
Neoramza

Neoramza

25/03/2004

Pelo que eu entendi, este tamanho de número não pode ser calculado pelo processador, apenas se for calculado em partes. Ao menos foi o que eu entendi, quando tive o mesmo problema com números, no meu casa, 32K ou 32768 dígitos. Neste caso eu desenvolvi umas funções capazes de calcular qualquer tamanho de número, o único problema é que demora, quanto maior o número mais demorado, exatamente porque tratase de cáculos em cima de String. As funções que desenvolvi são capazes de somar, dividir, subtrair e multiplicar números inteiros. Como necessitava apenas de números inteiros, não tentei fazer com números decimais, mais pela técnica que desenvolvi poderei fazer também, entre outras funções como, raiz, expoente e outras que se fizerem necessários. Pois bem, o princípio que parti foi, do mesmo princípio que aprendemos nos primeiros anos de escola. Então montei as funções para fazer os cálculos como faziamos no papel. Esta foi a única alternativa que consegui. Espero que ajude.


Se for possível me mostra esse códi go pois é exatamente o que eu estou procurando. Eu preciso somente das 4 operacoes basicas (adicao, subtracao, multiplicacao e divisao) e raiz quadrada.

Valeu galera.


GOSTEI 0
Anderson_blumenau

Anderson_blumenau

25/03/2004

so por curiosidade, que tipo de programa necessita de nºs tao grandes


GOSTEI 0
Beppe

Beppe

25/03/2004

so por curiosidade, que tipo de programa necessita de nºs tao grandes


Na maioria, programas com fins científicos...


GOSTEI 0
Neoramza

Neoramza

25/03/2004

Algo para calcular coisas como essas:

http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html


GOSTEI 0
Beppe

Beppe

25/03/2004

Tá querendo ganhar uma graninha, hein? :lol:

Todas as operações podem ser implementadas como no método papel-e-caneta, mas algumas exigem uma eficiência que só algoritmos melhor projetados podem resolver.

// Big Numbers by Beppe 27/03/2004

const
  DigitPrecision = 300; // deve ser ao menos 11

type
  BigNumber = array[1..DigitPrecision] of Byte;

var
  Zero, One: BigNumber;

function BigNumberToStr(const N: BigNumber): String;
var
  I: Integer;
begin
  I := Low(BigNumber);
  while (I <= High(BigNumber)) and (N[I] = 0) do Inc(I);
  SetString(Result, PChar(@N[I]), High(N) - I + 1);
  for I := 1 to Length(Result) do
    Inc(Result[I], Ord(´0´));
end;

function BigNumberToInt(const N: BigNumber): Integer;
begin
  Result := StrToInt(BigNumberToStr(N));
end;

function NewBigNumber(Value: Integer): BigNumber;
var
  I: Integer;
begin
  FillChar(Result, Length(Result), 0);
  I := High(BigNumber);
  repeat
    Result[I] := Value mod 10;
    Dec(I);
    Value := Value div 10;
  until Value = 0;
end;

function Equals(const Left, Right: BigNumber): Boolean;
begin
  Result := CompareMem(@Left, @Right, SizeOf(BigNumber));
end;

function Add(const Left, Right: BigNumber): BigNumber;
var
  I, Carry, Sum: Integer;
begin
  Result := NewBigNumber(0);
  Carry := 0;
  for I := High(BigNumber) downto Low(BigNumber) do
  begin
    Sum := Left[I] + Right[I] + Carry;
    Carry := Sum div 10;
    Result[I] := Sum mod 10;
  end;
end;

function DivideByTwo(const N: BigNumber): BigNumber;
var
  I, Carry, Quo: Integer;
begin
  Result := NewBigNumber(0);
  Carry := 0;
  for I := Low(BigNumber) to High(BigNumber) do
  begin
    Quo := Carry * 10 + N[I];
    Carry := Quo mod 2;
    Result[I] := Quo div 2;
  end;
end;

function IsOdd(const N: BigNumber): Boolean;
begin
  Result := Odd(N[DigitPrecision]);
end;

function Multiply(const Left, Right: BigNumber): BigNumber;
begin
  if Equals(Left, Zero) or Equals(Right, Zero) then
    Result := One
  else if Equals(Left, One) then
    Result := Right
  else if Equals(Right, One) then
    Result := Left
  else
  begin
    Result := Multiply(Left, DivideByTwo(Right));
    Result := Add(Result, Result);
    if IsOdd(Right) then
      Result := Add(Result, Left);
  end;
end;

function GreaterThan(const Left, Right: BigNumber): Boolean;
var
  I: Integer;
begin
  Result := False;
  for I := High(BigNumber) downto Low(BigNumber) do
  begin
    if Left[I] < Right[I] then
      Exit
    else if Left[I] > Right[I] then
    begin
      Result := True;
      Exit;
    end;
  end;
end;

function Power(const Left: BigNumber; Right: Cardinal): BigNumber;
begin
  case Right of
    0: Result := One;
    1: Result := Left;
  else
    Result := Power(Left, Right div 2);
    Result := Multiply(Result, Result);
    if Odd(Right) then
      Result := Multiply(Result, Left);
  end;
end;

function Mul(A, B: Cardinal): Cardinal;
begin
  case B of
    0: Result := 1;
    1: Result := A;
  else
    Result := Mul(A, B div 2);
    Result := Result + Result;
    if Odd(B) then
      Result := Result + A;
  end;
end;

function Pow(A, B: Cardinal): Cardinal;
begin
  case B of
    0: Result := 1;
    1: Result := A;
  else
    Result := Pow(A, B div 2);
    Result := Result * Result;
    if Odd(B) then
      Result := Result * A;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  A, B: BigNumber;
begin
  A := NewBigNumber(1220232);
  B := NewBigNumber(5012321);
  // cheque no calc.exe: 6116194478472
  Edit1.Text := BigNumberToStr(Multiply(A, B));
  // cheque no calc.exe: 2705278928837504201024262930432
  Edit2.Text := BigNumberToStr(Power(A, 5));
end;

initialization
  Zero := NewBigNumber(0);
  One := NewBigNumber(1);


a partir dessas pucas operações que escrevi, vc pode ir adiante. Subtração é ´straighforward´, divisão por números de um único dígito é simples, complica um pouco mais para outros só.

Eu usei divide-and-conquer para multiplicação e potência, pois tendem a ser mais eficientes. Para multiplicação existe um d-a-c melhor, mas é mais trabalhoso, e para números realmente grandes(milhares de casas), Fast Fourier Transform torna-se interessante.

Tem a questão de representação, também. Aqui usei array of Byte, onde cada byte fica de 0 a 9, de forma decimal. Mais eficiente seria trabalhar bináriamente, ie, array of Cardinal, usando complemento-de-2, para permitir números com sinais sem nenhum ajuste. Com representações decimais, o sinal precisa estar explícito, para facilidade no uso.


GOSTEI 0
Rodriguesap

Rodriguesap

25/03/2004

Caro

Desculpa mas devido a Ética, não poderei mostrar o código que usei. Este código tem proprietário. Ele foi usado para criar um algorítmo de Criptografia. É algo que nem eu que conheço o algoritmo seria capaz de quebrar a criptografia. Caso alguém coloca-se um computador dedicado para testar todas as possibilidades, ele levaria séculos para testar todas as possibilidades, e pode ser um computador parrudo. Mas eu posso enviar uma mini calculadora, que fiz para testar os cálculos. Nos testes para multiplicar um número ao quadrado (x^2) com mais de um milhão de dígitos, levou alguns minutos. Se tiver interesse, poste uma mensagem pessoal aqui no fórum.


GOSTEI 0
Apontador

Apontador

25/03/2004

aí, é o seguinte:
desenvolvi em pascal um tipo de dado que permite:
- entradas e saídas de números infinitos (desde que caibam na memória do pc);
- permite ponto (casas decimais infinitas (desde que caibam na memória do pc));
- permite sinal (positivo, negatido);
- permite cálculo de adição, subtração, multiplicação e divisão com esses números resultando em um número infinito.

veja se se interessa.
[color=red:1c0f63450e][/color:1c0f63450e][size=7:1c0f63450e][/size:1c0f63450e]


GOSTEI 0
Apontador

Apontador

25/03/2004

além do mais, esse código que lhe mostrarm acima em delphi, usa endereçamento de array via inteiro (integer), o que limita o comprimento do seu número ´longo´ a 32 mil e alguma coisa dígitos.
o código que desenvolvi nao trabalha em momento nenhum com inteiros, somente com ponteiros (apontadores), ou seja, um dígito é endereçado pelo pointer que o seu anterior (ou posterior, como queira) guardado na memória, fazendo com que o número seja ilimitado enquanto haja memória livre no pc...
favor retornar, pelo menos p/ dizer que nao está interessado.


GOSTEI 0
Thomaz_prg

Thomaz_prg

25/03/2004

Colega Apontador... se muder disponibilizar o código, seria interessante.
Se puder mandar por email... thomazs@pop.com.br


GOSTEI 0
Godmylife

Godmylife

25/03/2004

Prezados Senhores,

A maneira mais eficiente de realizar a multiplicação de inteiros grandes é realizá-la como é feita a multiplicação de polinômios. Entretanto, existe um ponto de ineficiência que a implementação trivial deste algoritmo (o que resulta numa complexidade O(n2)) apresenta que é a multiplicação de quatro polinômios.

Este problema pode ser resolvido com alum embasamento teórico aplicado, diminuindo o número de multiplicações de polinômios de quatro para três, o que faria a complexidade do algoritmo passar de O(n2) para O(n1,58), um ganho considerável.

Se alguém tiver interesse, é só falar. Não tenho implementado mas tenho o pseudo-código e a base teórica em ppt para a implementação.

Abs.


GOSTEI 0
POSTAR