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

[fr3ky]

Números Astronómicos

15 mensagens neste tópico

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?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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 :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
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 */
/*...*/

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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 ).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

boa ideia :D

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, uso o gcc.

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link 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