Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

[fr3ky]

Números Astronómicos

Mensagens Recomendadas

[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?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
lordnins

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.