Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
[fr3ky]

Números Astronómicos

Recommended Posts

[fr3ky]

Boas.

Tenho um trabalho para entregar que consiste em ultrapassar (pelo menos parcialmente) a

limitação imposta pelo tipo de dados integer quanto à magnitude (maxint) dos

inteiros representáveis.

Tem de ser definir de forma adequada o tipo de dados astronómico e implementar as

operações aritméticas.

Tava a pensar guardar os numeros inteiros "astronomico" inseridos num array (um digito em cada posição do array) e a partir dai viriam as operações aritmeticas, mas gostava de saber a vossa opiniãp uma vez que pus a hipotese de factorizar o numero mas pareceume estar a complicar. :confused:

O que acham?

Share this post


Link to post
Share on other sites
pmg

A opção dum char[] com um dígito por elemento do array é a mais fácil de implementar.

Começa por aí e se, quando estiver a funcionar, vires a necessidade de melhorar a performance ou uso de memória das tuas funções então complica :)


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
lufinima

No ano passado fiz algo do género em Lisp, em que tinha que multiplicar números muito grandes, a a abordagem que segui foi desse género, só que em Lisp em vez de arrays usam-se listas (lisp é tudo listas) em que cada posição na lista era um dígito do numero.

Se puder ajudar em mais qualquer coisa é só dizer.

Share this post


Link to post
Share on other sites
Warrior

Essa é a opção mais simples. (Cuidado ao implementar a divisão)

Outra alternativa é considerares arrays de long long's por exemplo, e olhares para o array como um conjunto enorme de bits, poupas MUITO em memória.

Share this post


Link to post
Share on other sites
pmg
Outra alternativa é considerares arrays de long long's

Porquê long long's?

Tens exactamente a mesma poupança e capacidades com um array de unsigned int's ou de unsigned char's ... e o tratamento da informação com char's ou int's torna-se mais fácil.

/*...*/
long long array_l[200];      /* 12800 bits na minha máquina */
unsigned array_i[400];       /* 12800 bits na minha máquina */
unsigned char array_c[1600]; /* 12800 bits na minha máquina */
/*...*/


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
mogers

Eu também costumo usar arrays de int's. Uma das vantagens de um array de long longs é o facto de serem precisas menos posições no array para representar o número e, consequentemente, os calculos são mais rápidos. Por outro lado, é mais dificil de tratar possíveis overflows nas multiplicações (costumo usar ints no array e usar long longs nas multiplicações, ou seja, representar o número na base 1.000.000.000 ).


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Warrior

Exactamente pela razão que o mogers referiu, podes tratar 64 bits de cada vez, o que é mais rápido.

Share this post


Link to post
Share on other sites
pmg

Pois, pois ... nunca pensei :|

Um teste que eu fiz (passar um bit 'on' do bit 0 ao bit 65535 (65536 multiplicações por 2)) com vários tipos de unsigned deu-me resultados surpreendentes:

Sem optimização

time with chars:      4.22

time with shorts:     2.05

time with ints:       1.02

time with longs:      0.51

time with long longs: 0.52

Com optimização -O2

time with chars:      1.21

time with shorts:     1.82

time with ints:       2.12

time with longs:      2.28

time with long longs: 0.15

!!!!!!!!!! :D

Ah! Pus o source no Pastebin por um dia:

http://paste.portugal-a-programar.org/pastebin.php?show=2989 (pus o código com syntax highlight e para sempre --djthyrax)


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
mogers

boa ideia :D

Olha... usas o gcc não? Os ints não são iguais aos longs no teu pc? (4 bytes)


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
pmg

Sim, uso o gcc.

No meu AMD64, os ints têem 4 bytes, os longs têem 8, e os long longs 8.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
[fr3ky]

Fiz este procedure para guardar o numero, ta a funcionar bem:)

const
max = 30;

type
indice = 1..max;
digito = 0..9;
inteiro = array[indice] of digito; 

var                              
  num:inteiro;
  n:integer;
  
Procedure Le_Inteiro(var num:inteiro);
Var     
c:char;
k,i:integer;
Begin
writeln('Escreva um número inteiro : ');
write('> ');
i:=1;
while (i<=max) and (not eoln)
do begin
     read(c);
     if (ord(c)>=ord('0')) and (ord(c)<=ord('9'))
     then begin
          num[i]:=ord(c)-ord('0');
          i:=i+1;
          end
     else begin
          readln;
          writeln('Enganou-se! Tente novamente!');
          Le_inteiro(num);
          end;
   end;
n:=i;
if n<max 
then begin
     for k:=n+1 to max do num[k]:=0;
     end;
End;

o numero é guardado no array e caso nao tenha o numero maximo de digitos do array o espaço restante será preenchido com zeros, tendo este aspecto: ex. 12234560000000000000000; agr th de fazer um procedure ou function pra por o numero da seguinte forma: 000000000123456. algum conselho?

cumps

Share this post


Link to post
Share on other sites
mogers

Tás a usar um array de digitos por isso é simplesmente reverter o array...

edit: ops, não tinha percebido bem a dúvida


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Warrior

Não é bem isso, o que tu queres é contar quantos zeros tens no final da string e deslocar todos os caracteres esse numero de zeros para o lado direito.

Share this post


Link to post
Share on other sites
pmg

E porque é que não preeenches o array a começar do fim?

Em vez de inicializres o i com 1, inicializa com o tamanho do array; e em vez de somares 1 no ciclo, subtrai 1.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
TheDark

Não é bem isso, o que tu queres é contar quantos zeros tens no final da string e deslocar todos os caracteres esse numero de zeros para o lado direito.

E se o utilizador tiver introduzido zeros no fim do número?

E porque é que não preeenches o array a começar do fim?

Em vez de inicializres o i com 1, inicializa com o tamanho do array; e em vez de somares 1 no ciclo, subtrai 1.

Ficava com o número ao contrário.

Podes é, no fim do while, copiar os algarismos que foram lidos para o fim do array. Tens o índice do último número lido, é simples.


Desaparecido.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.