silnia z dużych liczb

0

Witam, napisałem program liczący silnie, który ma jednak ograniczenia jako że zmienne są w stanie przechować bardzo ograniczoną liczbę cyfr; w jaki sposób przy użyciu tablic można napisać program zdolny policzyć silnie z dużych liczb np 1000, 10000, 1000000, 1000000000? Chodzi mi o to, jak można dużą liczbę pofragmentować na krótkie ciągi liczb zapisywalne do tablicy, i jak je mnożyć?

1

gmplib.org albo podejrzyj źródła klasy BigInteger z Javy.

0

Chodziłoby mi raczej o niekorzystanie z żadnych bibliotek itp; tylko najbardziej podstawowe narzędzia tzn, normalne zmienne int, tablice, nic poza tym.

0

"prawie" elementarnie policzyłem 30'000! w mniej niż sekundę. Piwa do dziś nie przysłali.

0

Najprostszym sposobem (poza użyciem GMP czy innego bignuma) byłoby liczenie na tekstowej reprezentacji liczby. Działania robisz niemal jak na papierze. ;)
Innym, nieco lepszym jeśli chodzi o wykorzystaniem pamięci ale wymagającym podstawowej znajomości systemu binarnego sposobem byłoby działanie na tablicy bitów (choćby vector<bool>, dla wygody), traktując całość jako jedną wielką liczbę binarną. Wykorzystanie pamięci miałbyś takie samo jak zwykłe liczby w pamięci - bajt: 256 wartości, itd. Dodawanie byłoby dość proste, a mnożenie możesz zrobić jako dodawanie w pętli, jeśli innego pomysłu nie masz. ;)
Działać będzie, ale liczenie silni z miliona to raczej porządną "chwilę" potrwa. ;P

0

Prosta implementacja podstawowych działań na bardzo dużych liczbach w C:

 #include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct _liczba
{
  int  dlugosc;
  char *cyfry;
} Liczba;

#define ALOKUJ(CZEGO, ILE) (CZEGO*) malloc(sizeof(CZEGO) * ILE)
#define A_DLUZSZE_OD_B \
if(a->dlugosc < b->dlugosc)\
{\
  Liczba *temp = a;\
  a = b;\
  b = temp;\
}

#define MAKSYMALNY_ROZMIAR_LICZBY 100

#define ABS(LICZBA) (LICZBA<0)?-LICZBA:LICZBA
Liczba *Utworz(int liczbaCyfr);
Liczba *stdinNaLiczbe();
void   Usun(Liczba *liczba);
void   Wyswietl(Liczba *liczba);
Liczba *Dodaj(Liczba *a, Liczba *b);
Liczba *Odejmij(Liczba *a, Liczba *b);
Liczba *Pomnoz(Liczba *a, Liczba *b);
//Liczba *Podziel(Liczba *a, Liczba *b);

//-----------------------------------------------------------------------------
int main()
{
  char dzialanie;
  Liczba *skladnik1, *skladnik2, *wynik;
  while(1)
  {
    if((dzialanie = getchar()) == EOF)
      break;

    skladnik1 = stdinNaLiczbe();
    skladnik2 = stdinNaLiczbe();
    switch(dzialanie)
    {
    case '+':
      wynik = Dodaj(skladnik1, skladnik2);
      break;
    case '-':
      wynik = Odejmij(skladnik1, skladnik2);
      break;
    case '*':
      wynik = Pomnoz(skladnik1, skladnik2);
      break;
//    case '/':
//      wynik = Podziel(skladnik1, skladnik2);
//      break;
    }

    Wyswietl(wynik);
    Usun(wynik);
    Usun(skladnik1);
    Usun(skladnik2);
  }
  return 0;
}

//-----------------------------------------------------------------------------
Liczba *Utworz(int liczbaCyfr)
{
  Liczba *wynik = ALOKUJ(Liczba, 1);
  wynik->dlugosc = liczbaCyfr;
  wynik->cyfry = ALOKUJ(char, liczbaCyfr);
  return wynik;
}

//-----------------------------------------------------------------------------
Liczba *stdinNaLiczbe()
{
  char *bufor = ALOKUJ(char, MAKSYMALNY_ROZMIAR_LICZBY+1);
  char *kursor = bufor;
  unsigned int iloscCyfr = 1;
  while(1)
  {
    *kursor = getchar();
    if(*kursor != ' ' && *kursor != '0')
      break;
  }

  while(1)
  {
    *(++kursor) = getchar();
    if(*kursor == ' ' || *kursor == '\n')
      break;
    else iloscCyfr++;
  }

  Liczba *wynik = Utworz(iloscCyfr);
  memcpy(wynik->cyfry, bufor, iloscCyfr);
  free(bufor);
  return wynik;
}

//-----------------------------------------------------------------------------
void Usun(Liczba *liczba)
{
  free(liczba->cyfry);
  free(liczba);
}

//-----------------------------------------------------------------------------
void Wyswietl(Liczba *liczba)
{
  char *kursor = liczba->cyfry;
  for(unsigned int i = liczba->dlugosc; i>0; i--)
  {
    putchar(*(kursor++));
  }
  putchar('\n');
}

//-----------------------------------------------------------------------------
Liczba *Dodaj(Liczba *a, Liczba *b)
{
  A_DLUZSZE_OD_B
  char *bufor = ALOKUJ(char, a->dlugosc + 1);
  char *kursorW = bufor + a->dlugosc;
  char *kursorA = a->cyfry + a->dlugosc - 1;
  char *kursorB = b->cyfry + b->dlugosc - 1;
  unsigned int pamiec = 0;

  while(kursorB >= b->cyfry)
  {
    pamiec += (*(kursorA--)-'0') + (*(kursorB--)-'0');
    *(kursorW--) = pamiec % 10 + '0';
    pamiec /= 10;
  }

  while(kursorA >= a->cyfry)
  {
    pamiec += *(kursorA--)-'0';
    *(kursorW--) = pamiec % 10 + '0';
    pamiec /= 10;
  }

  Liczba *wynik;
  if(pamiec>0)
  {
    *kursorW = pamiec + '0';
    wynik = Utworz(a->dlugosc+1);
    memcpy(wynik->cyfry, bufor, wynik->dlugosc);
  }
  else
  {
    wynik = Utworz(a->dlugosc);
    memcpy(wynik->cyfry, bufor+1, a->dlugosc);
  }

  free(bufor);
  return wynik;
}

//-----------------------------------------------------------------------------
Liczba *Odejmij(Liczba *a, Liczba *b)
{
  A_DLUZSZE_OD_B
  char *bufor = ALOKUJ(char, a->dlugosc);
  char *kursorW = bufor + a->dlugosc - 1;
  char *kursorA = a->cyfry + a->dlugosc - 1;
  char *kursorB = b->cyfry + b->dlugosc - 1;
  int pamiec = 0;

  while(kursorB >= b->cyfry)
  {
    pamiec += (*(kursorA--)-'0') - (*(kursorB--)-'0');
    if(pamiec>=0)
    {
      *(kursorW--) = pamiec + '0';
      pamiec = 0;
    }
    else
    {
      *(kursorW--) = 10 + pamiec + '0';
      pamiec = -1;
    }
  }

  while(kursorA >= a->cyfry)
  {
    pamiec += *(kursorA--)-'0';
    if(pamiec>=0)
    {
      *(kursorW--) = pamiec + '0';
      pamiec = 0;
    }
    else
    {
      *(kursorW--) = 10 + pamiec + '0';
      pamiec = -1;
    }
  }

  while(*(++kursorW)=='0');

  unsigned int dlugoscWyniku = bufor + a->dlugosc - kursorW;
  if(dlugoscWyniku == 0)
  {
    kursorW--;
    dlugoscWyniku++;
  }
  Liczba *wynik = Utworz(dlugoscWyniku);
  memcpy(wynik->cyfry, kursorW, dlugoscWyniku);

  free(bufor);
  return wynik;
}

//-----------------------------------------------------------------------------
Liczba *Pomnoz(Liczba *a, Liczba *b)
{
  A_DLUZSZE_OD_B
  char *bufor = ALOKUJ(char, a->dlugosc + b->dlugosc);
  char *kursorW = bufor;
  for(unsigned int i = a->dlugosc+b->dlugosc; i>0; i--)
    *(kursorW++) = '0';
  char *kursorA;
  char *kursorB = b->cyfry + b->dlugosc - 1;
  unsigned int pamiec = 0;

  for(unsigned int i = b->dlugosc; i>0;)
  {
    i--;
    unsigned int liczbaB = *(kursorB--)-'0';
    kursorA = a->cyfry + a->dlugosc - 1;
    kursorW = bufor + a->dlugosc + i;
    for(unsigned int j = a->dlugosc; j>0;j--)
    {
      pamiec += (*(kursorA--)-'0') * liczbaB + (*kursorW - '0');
      *(kursorW--) = (pamiec % 10) + '0';
      pamiec /= 10;
    }

    while(pamiec>0)
    {
      *(kursorW--) = pamiec % 10 + '0';
      pamiec /= 10;
    }
  }

  kursorW++;

  unsigned int dlugoscWyniku = bufor + a->dlugosc + b->dlugosc - kursorW;
  Liczba *wynik = Utworz(dlugoscWyniku);
  memcpy(wynik->cyfry, kursorW, dlugoscWyniku);

  free(bufor);
  return wynik;
}

Aczkolwiek należy zaznaczyć, że jest to bardzo nieefektywne, na pewno nie dorasta gmp czy implementacjom z pythona czy innych języków. No, ale chyba lepszy rydz niż nic.

0

A może konkurs, kto lepiej to zrobi?

0

Proszę, silnia z dowolnie dużych liczb w scheme
(define (fact n) (if (> n 1) (* n (fact (- n 1))) 1))

Fajnie mieć w standardzie dowolnie duże liczby :P.

0

Już wspomniałem, że niektóre mają taki fajny ficzer, że liczą na każdych liczbach (ja akurat podałem pythona -- i tu prędzej człowiekowi spodoba składnia [aczkolwiek nic nie mam do schema]).

0

Hmmm, to może ja tak dam na szybko i chyba najprościej jak się da w paru językach:

  • Maxima: 1000000000!
  • Yacas: 10000000000!
    Jeśli ktoś przebije to bardzo chętnie zobaczę jak to zrobił.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0