Essa é difícil (números super grandes)
Como eu faco para trabalhar com inteiros de tamanhos super grandes tipo numeros com 200 ou 300 digitos?
Neoramza
Curtidas 0
Respostas
Aroldo Zanela
25/03/2004
Colega,
Com inteiro não vai ser possível, veja:
Que tipo de trabalho precisa fazer exatamente?
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
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
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
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
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.
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
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
25/03/2004
Sim, é por aí mesmo (por partes), como mostra este trecho de um artigo sobre inteiros de 128 bits:
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.
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
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
25/03/2004
so por curiosidade, que tipo de programa necessita de nºs tao grandes
GOSTEI 0
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
25/03/2004
Algo para calcular coisas como essas:
http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
GOSTEI 0
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.
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.
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
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.
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
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]
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
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.
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
25/03/2004
Colega Apontador... se muder disponibilizar o código, seria interessante.
Se puder mandar por email... thomazs@pop.com.br
Se puder mandar por email... thomazs@pop.com.br
GOSTEI 0
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.
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