Inmultirea numerelor mari

[•rEbyTer]

Cod:

void mul(int A[], int B[])  
 {  
       int i, j, t, C[NR_CIFRE];  
       memset(C, 0, sizeof(C));  
       for (i = 1; i <= A[0]; i++)  
       {  
               for (t=0, j=1; j <= B[0] || t; j++, t/=10)  
                       C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;  
               if (i + j - 2 > C[0]) C[0] = i + j - 2;  
       }  
       memcpy(A, C, sizeof(C));  
 }  

Cum pot inmulti mai exact doua numere mari ? adica de unde stiu dimensiunea vectorului in care este pastrat rezultatul ?
teoretic daca un numar are 4 cifre si celalalt 2 , produsul nu poate avea mai mult de 6 cifre....

[•filipb]

Vectorii A si B retin numerele mari in ordine inversa, adica pe pozitia 1 din vector se va gasi ultima cifra a numarului mare, pe a 2a pozitia penultima cifra, etc. In plus, pozitia 0 din vector retine numarul de cifre ale numarului. De exemplu, numarul 14078 este reprezentat astfel: (5, 8, 7, 0, 4, 1).
Functia de mai sus simuleaza inmultirea: ia fiecare cifra din A (deci de la 1 la numarul de cifre din A, A[0]), inmulteste cifra cu numarul mare B, si aduna acest rezultat la rezultatul partial, avand grija sa faca translatiile necesare.

[•rEbyTer]

Cod:

#include <stdio.h>
#include <string.h>
#define NR_CIFRE 200
void mul(int A[], int B[], int &m)  
 {  
       int i, j, t, C[NR_CIFRE];  
       memset(C, 0, sizeof(C));  
       for (i = 1; i <= A[0]; i++)  
       {  
               for (t=0, j=1; j <= B[0] || t; j++, t/=10)  
                       C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;  
               if (i + j - 2 > C[0]) C[0] = i + j - 2;  
       }  
       memcpy(A, C, sizeof(C));  
 m=int(sizeof(C));
}
int main()
{
int a[3]={2,0,1};
int b[3]={2,1,2};
int m=-1;
mul(a,b,m);
for(int i=1;i<=m;++i)
   printf("%d",a[i]);
printf("\n");
return 0;
}
  

defapt.. ce am gresit in acest program ...
am inteles cum functioneaza ... dar de exemplu de unde stiu cat o sa fie m(nr de cifre ale rezultatului) in for cand afisez rezultatul ?

[•toni2007]

pai numarul de cifre al rezultatului este retinut in rez[0]

[•rEbyTer]

rez[0] fiind cine

ma bulvearseaza cu vectorul C ...
apoi e functia memcpy la sfarsit .. deci rezultatul inmultirii este copiat in vectorul A , nu ?

un exemplu de inmultire(sursa) e binevenit...
poate asa o sa ma lamuresc.

L.E.: Rezultatul este tot pe invers ?

[•filipb]

mul(A, B) calculeaza A * B, iar rezultatul va fi retinut in parametrul A. Ai nevoie de un vector auxiliar, sa ii spunem C, ca sa calculezi sumele partiale.
De exemplu, cand inmultesti 912 cu 17 ai urmatorii pasi:
* iei ultima cifra pentru 912 ( care va fi prima in vectorul A ), si inmultesti 2*17 = 34. C va contine 34. Nu poti retine acest produs partial in vectorul A pentru ca mai ai nevoie de el in pasii urmatori.
* iei cifra 1 si faci 1 * 17 = 17. 17 trebuie decalat cu o pozitie, deci aduni la 34 pe 170 si obtii 204. Acest rezultat iar nu se poate pastra in A, caci ai nevoie de el la pasul urmator, si te folosesti de vectorul auxiliar C ca sa retii rezultatul.
La sfarsit apelezi memcpy ca sa copiezi rezultatul din vectorul auxiliar C in A.
Numarul de cifre ale rezultatului se vor gasi in A[0].

Sursa de mai sus e destul de complicata si scurta, incerca sa faci inmultirea a doua numere mari modular, in care scrii cate o functie pentru adunarea a doua numere mari, produsului unui numar mare cu un nr. mic, si sa te folosesti de aceste functii cand faci inmultirea a doua numere mari.

L.E.: Rezultatul este tot pe invers ?

Da.

[•gabitzish1]

L.E.: Rezultatul este tot pe invers ?

Saracutzu' de el  ...

[•rEbyTer]

multumesc, m-ati ajutat foarte mult ....

acum ... am dat copy paste(copy paste adica am scris exact ce era in articolul de pe infoarena) la functia care face inmultirea, si   primesc o eroare(cand rulez programul) Segmentation fault (core dumped) .

Original

Cod:

void mul(int A[], int B[])
 {
      int i, j, t, C[NR_CIFRE];
      memset(C, 0, sizeof(C));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=10)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > C[0]) C[0] = i + j - 2;
      }
      memcpy(A, C, sizeof(C));
}

Neoriginal:

Cod:

void mul(int A[], int B[])
{
      int i, j, t, *C;
      C=new int[200];
      memset(C, 0, sizeof(C));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=10)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > C[0]) C[0] = i + j - 2;
      }
      memcpy(A, C, sizeof(C));
}

am modificat la declararea lui C ... initial era int C[NR_CIFRE]
eu am pus int *C;
C=new int[200];

acuma functioneaza fara probleme (aparent)

nu sunt prea sigur de modificarea int *C;
C=new int[200]; .. am citit pe google .. era pe la alocare dinamica..

se poate comporta anormal in anumite situatii ?

Multumesc inca odata... mi-ati fost de ajutor.

[•stef2n]

Cand lucrezi cu numere mari, trebuie sa prevezi pe la ce lungime poate ajunge numarul tau. In cazul asta au fost suficiente 200 de cifre, dar in alte cazuri poate varia. De obicei e indicat sa-ti faci un calcul cat poate sa fie maxim aceasta lungime.

[•rEbyTer]

  ms , a ajutat

Acu', next question (nu cred ca are rost sa deschid un topic nou pentru asta) ...

Ce este un bubble sort optimizat ?

L.E.: La ONI pot scrie ce vreau in sursa cpp...?

Adica de exemplu:

int animal (int eu)
  { if (n<0) {eu=-eu return 1;}
  return 0;
  }

int main()
{
int eu;
if (eu==animal) ; //ahaha am fost aici }
}

nu se ia nimeni de sursa mea, nu ? asa m-am cam obisnuit ... si retin destul de usor numele la variabile :-/

L.E.2: Care este faza cu Segmentation fault (core dumped)
ma dispera..  .... asta este din cauza la vectorul C din functia mul ...

defapt ... daca am int C[N] , unde N>15 primesc eroarea aia... de ce ?
L.E.3: defapt depinde de dimensiunea vectorilor A si B .... nu stiu ce sa fac...

L.E.4: dupa ce m-am chinuit atata..cred ca am mai invatat cateceva... spre exemplu am adaugat linia

Cod:

const int NR_CIFRE=A[0]+B[0];

si nu mai primesc eroarea
si teoretic cred ca functioneaza pe numere cu cifre mai putine sau egale cu 2^32 (asta depinde de compilator .alea alea ) ..desi exagerez un pic ... imi cam scapa ceva

spre exemplu daca ambele numere A si B ar avea 2^32 cifre. .. rezultatul ar avea cel mult 2^33cifre ... deci imposibil de calculat pentru ca nu poti retine intr-un vector elementu A[2^33] 

[•alexthero]

1. La ONI poti scrie ce vrei in sursa.. nu prea se uita nimeni in sursa ta atat timp cat nu depui contestatie. Daca depui contestatie exista posibilitatea ca cineva din comisie sa se uite peste sursa ta.

2. Segmentation Fault apare in unul dintre urmatoarele cazuri:
a. Incerci sa accesezi o zona de memorie nealocata. De exemplu:

Cod:

int a[100]; 
printf("%d\n", a[101]);

b. Folosesti prea multa memorie. In Linux poti verifica daca iti depaseste memoria folosind comanda ulimit.
De exemplu, pentru a verifica daca programul test ruleaza ok cu mai putin de 1 mega memorie folosesti:

ulimit -v 1024
./test

In cazul in care programului nu ii ajunge 1 mega memorie, iti va afisa un mesaj de eroare.

3. Bubble sort este o metoda de sortare, pe care nu ti-o recomand datorita complexitatii mari (N^2). Metode de sortare mai rapide sunt:

-> QuickSort - complexitatea in cel mai rau caz este N^2, dar daca alegi pivotul random va merge mult mai bine. La fiecare pas alegi un pivot, si interschimbi elementele astfel incat toate elementele < pivot sa se afle in stanga pivotului, iar cele >= ca pivotul sa se afle in dreapta. Apelezi recursiv functia de sortare pentru cele 2 regiuni.

-> MergeSort - N log N - un vector cu N valori este impartit in doi vectori de dimensiune N / 2. Se apeleaza recursiv functia de sortare si apoi interclasezi cei 2 vectori sortati.

-> HeapSort - N log N - bagi toate elementele intr-un heap si extragi la fiecare pas minimul (sau maximul)

O implementare foarte buna a functiei de sortare este functia sort() din STL.

[•rEbyTer]

rebyter@rebyter:/media/BJAWYNM$ ulimit -v 1024
rebyter@rebyter:/media/BJAWYNM$ ./a.out
./a.out: error while loading shared libraries: libstdc++.so.6: failed to map segment from shared object: Cannot allocate memory

folosesc ultima versiune de xubuntu...

QuickSort - complexitatea in cel mai rau caz este N^2, dar daca alegi pivotul random va merge mult mai bine. La fiecare pas alegi un pivot, si interschimbi elementele astfel incat toate elementele < pivot sa se afle in stanga pivotului, iar cele >= ca pivotul sa se afle in dreapta. Apelezi recursiv functia de sortare pentru cele 2 regiuni.

Da, quicksort incerc sa invat si eu... faza e ca daca sa spunem se intampla sa il uit mai ramane bubble sort-u ... am auzit pe alocuri de bubble sort optimizat si sunt curios ce inseamna.

ptr quicksort folosesc functia asta:

Cod:

void q_sort(int numbers[], int left, int right)
{
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = numbers[left];
   while (left < right)
   {
      while ((numbers[right] >= pivot) && (left < right))
      right--;
      if (left != right)
      {
	 numbers[left] = numbers[right];
	 left++;
      }
      while ((numbers[left] <= pivot) && (left < right))
	 left++;
      if (left != right)
      {
	  numbers[right] = numbers[left];
	  right--;
      }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
      q_sort(numbers, left, pivot-1);
   if (right > pivot)
      q_sort(numbers, pivot+1, right);
}

nu prea pare a fi "random".

daca imi poti da functia quicksort despre care spui tu ca este random as fi foarte multumit.
multumesc pentru ajutor

si un exemplu cu sort-ul din STL e binevenit , problema e ca s-ar putea sa am nevoie sa fac sortarea dupa mai multe criterii..si se complica treaba cu quicksort-u .. asta nu-mi place

[•alexthero]

In primul rand nu trebuie sa rulezi .out-ul. Corect este:

ulimit -v 1024
./a

Ti-am modificat functia ta sa aleaga pivotul random. Da niste teste mari, de genul 20000, 19999, 19998 .. 1 si vezi diferentele de timp.

Cod:

void q_sort(int numbers[], int left, int right)
{
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   if(left != right)
   {
   	int aux = numbers[left], randompoz = left + rand() % (left - right);
   	numbers[left] = numbers[randompoz];
   	numbers[randompoz] = aux;
   }
   pivot = numbers[left];
   while (left < right)
   {
      while ((numbers[right] >= pivot) && (left < right))
      right--;
      if (left != right)
      {
	 numbers[left] = numbers[right];
	 left++;
      }
      while ((numbers[left] <= pivot) && (left < right))
	 left++;
      if (left != right)
      {
	  numbers[right] = numbers[left];
	  right--;
      }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
      q_sort(numbers, left, pivot-1);
   if (right > pivot)
      q_sort(numbers, pivot+1, right);
}

[•sima_cotizo]

In primul rand nu trebuie sa rulezi .out-ul. Corect este:

ulimit -v 1024
./a

Daca la g++ nu mentionezi niciun output cu flagul "-o", atunci iti compileaza in a.out direct... deci ce a facut el cred ca e corect

Poti, te rog, explica de ce nu alegi pivotu direct random? De gen

Cod:

pivot=numbers[rand()%...]

 

PS: am inteles, doar ca eu as fi pus direct return daca am capetele egale

[•alexthero]

Daca la g++ nu mentionezi niciun output cu flagul "-o", atunci iti compileaza in a.out direct... deci ce a facut el cred ca e corect

imi cer scuze, nu am stiut.

Poti, te rog, explica de ce nu alegi pivotu direct random?

In functia lui am incercat sa fac asta prima data. Alegand pivotul random direct, pentru N = 5 si sirul: 1 2 3 4 5 da uneori rezultatul: 2 3 4 4 5. Am mai vazut implementari care tin cont de faptul ca pivotul se afla pe prima pozitie, dar nu am avut rabdare sa ma uit pe functia lui. Cel mai sigur e sa interschimbi prima pozitie cu un pivot random, si merge pe toate cazurile pe care merge qs implementat normal.

[•sima_cotizo]

Ah, e bine de stiut...    Multumesc de explicatie! 

[•rEbyTer]

va multumesc inca odata pentru explicatiile voastre. mi-au fost intr-adevar de folos