trikitrok avatar trikitrok committed 8a5247b Draft

Added p_mul and p_div. Added final P2 c file

Comments (0)

Files changed (2)

+/**
+// NOM:
+//
+// Els polinomis seran d'una sola incògnita (x) i estaran representats per dos vectors:
+//   v_coef: vector amb els coeficients de cada terme del polinomi
+//   v_exp : vector amb els exponents de cada terme del polinomi
+//   La posició i-essima de cada vector correspondrà a un mateix terme del polinomi,
+//   un terme del polinomi quedaria expressat d'aquesta forma: (v_coef[i]) · x^(v_exp[i])
+//
+//  Els coeficients de cada terme del polinomi seran nombres enters (diferents de 0).
+//  Els exponents de cada terme del polinomi seran nombres enters positius (inclòs el 0).
+//  Només representarem els termes del polinomi amb un coeficient diferent de 0.
+//  Les posicions dels vectors que no representen cap terme del polinomi tindran 
+//  coeficient 0 i exponent -1. (v_coef[i]=0; v_exp[i]=-1). Cal tenir present que 
+//  si un polinomi té 20 termes no tindrà cap posició del vector amb (v_coef[i]=0; v_exp[i]=-1).
+//  Per operar amb els termes d'un polinomi considerarem que estan ordenats segons l'exponent, 
+//  de més gran a més petit: v_exp[i] > v_exp[i+1]. A excepció de la subrutina on s'ordenen
+//  els termes d'un polinomi.
+//  Un polinomi no pot tenir mai dos termes amb el mateix exponent.
+//  
+//  Exemple:  polinomi p(x) = x^37 +3x^11 -2x^9 +5x^8 +x -1
+// 
+//  (índex)     0        1       2       3       4       5       6      7     ...   19
+//           *****************************************************************   ********
+//  v_coef = *  +1   *  +3   *  -2   *  +5   *  +2   *  -1   *   0  *   0   * ... *  0  *
+//           *****************************************************************   ********
+//  v_exp  = *  +37  *  +11  *  +9   *  +8   *  +1   *  +0   *  -1  *  -1   * ... * -1  *
+//           *****************************************************************   ********
+//  p(x)   = (+x^37)+(+3x^11)+(-2x^9)+(+5x^8)+(+2x^1)+(-1x^0)
+*/
+
+#include <stdio.h>
+
+/**
+ * 
+ * Funcions de la P2
+ * 
+ */
+ 
+// Funciones en ensamblador
+extern int p_term_add_c(int coef_term, int exp_term, int* coefs, int* exps);
+extern int p_add_sub(int *r_coef, int * r_exp, int* s_coef, int* s_exp, int suma_resta);
+extern void p_term_mul(int coef, int exp, int* v_coef, int* v_exp);
+
+/**
+ *  Esborrar el polinomi v, posa a 0 els coeficients i a -1 els exponents.
+ */
+void p_deleteC(int v_coef[], int v_exp[]) {
+    int i;
+    for (i=0; i<20; i++) 
+    {
+        v_coef[i]= +0;
+        v_exp[i] = -1;
+    }
+}
+
+/**
+ *  Copiar el polinomi v1 sobre el polinomi v2, posició a posició.
+ */
+void p_copyC(int v1_coef[], int v1_exp[], int v2_coef[], int v2_exp[]) {
+    int i;
+    for (i=0; i<20; i++) 
+    {
+        v2_coef[i] = v1_coef[i];
+        v2_exp[i] = v1_exp[i];
+    }
+}
+
+/**
+ *  Mostra el polinomi v.
+ *  Amb el següent format: +x^37 +3x^11 -2x^9 +5x^8 +2x^1 -1x^0
+ *  Si el polinomi no té cap terme indicar-ho amb el missatge 
+ *  "Polinomi sense termes"
+ */
+void p_print(int v_coef[], int v_exp[])
+{  
+    if (v_exp[0] == -1) 
+    {
+        printf ("el polinomi no te cap terme \n\n");
+    }
+    else 
+    {
+        int i = 0;
+        while (v_exp[i]!=-1 && i<20) 
+        {
+            if (v_coef[i]>=0) 
+                printf (" +"); 
+            else 
+                printf (" ");
+            
+            printf("%d*x^%d ",v_coef[i], v_exp[i]);
+            i++;
+        }
+        printf("\n\n");
+    }
+}
+
+/**
+ *  Multiplicar el polinomi p(x) pel polinomi q(x).
+ *  r(x)=p(x)*q(x).
+ *  Utilitzar les subrutines d'assemblador: p_term_mul i p_add_sub.
+ */
+void p_mul(int p_coef[], int p_exp[], int q_coef[], int q_exp[], int r_coef[], int r_exp[])
+{
+    int i;
+    int res;
+    
+    //polinomi s(x). Polinomi per guardar resultats parcials i així no modificar els polinomis originals.
+    //Vector amb els coeficients dels termes del polinomi s(x).
+    int s_coef[20]={ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+    //Vector amb els  exponents  dels termes del polinomi s(x). 
+    int s_exp [20]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+  
+    p_deleteC(r_coef, r_exp); // Esborrar el polinomi on guardarem el resultat de la multiplicació
+
+    
+    for(i=0; i<20; i++)
+    {
+        if(q_exp[i] == -1)
+            break;
+            
+        p_copyC(p_coef, p_exp, s_coef, s_exp);
+        
+        p_term_mul(q_coef[i], q_exp[i], s_coef, s_exp);
+        
+        //printf("s \n");
+        //p_print(s_coef, s_exp);
+        //printf("\n");
+        
+        res = p_add_sub(r_coef, r_exp, s_coef, s_exp, 0);
+        
+        //printf("r \n");
+        //p_print(r_coef, r_exp);
+        //printf("\n");
+        
+        if(res == -1)
+        {
+            p_deleteC(r_coef, r_exp);
+        }       
+    }
+}
+
+/**
+ *  Dividir el polinomi p(x) entre el polinomi d(x). p(x)/d(x)
+ *  El coeficient del terme de major grau del polinomi d(x) ha de ser 1.
+ *  Obtenim el polinomi quocient q(x) i el polinomi residu r(x).
+ *  p(x)=d(x)*q(x)+r(x).
+ *  Utilitzar les subrutines d'assemblador: p_term_add_C, p_term_mul i p_add_sub.
+ */
+void p_div(int p_coef[], int p_exp[], int d_coef[], int d_exp[], int q_coef[], int q_exp[], int r_coef[], int r_exp[])
+{
+    int res;
+    int coef;
+    int exp;
+
+    //polinomi s(x) 
+    int s_coef[20]={ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
+    int s_exp [20]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
+    
+    p_deleteC(q_coef, q_exp);  //esborrar el polinomi on guardarem el quocient de la divisió
+    p_deleteC(r_coef, r_exp);  //esborrar el polinomi on guardarem el residu  de la divisió
+    
+    
+    p_copyC(p_coef, p_exp, r_coef, r_exp);
+    
+    do 
+    {
+        coef = r_coef[0]/d_coef[0];
+        exp = r_exp[0] - d_exp[0];
+        
+        p_term_add_c(coef, exp, q_coef, q_exp);
+        
+        //printf("q(x): ");
+        //p_print(q_coef, q_exp);
+        //printf("\n");
+        
+        p_copyC(d_coef, d_exp, s_coef, s_exp);
+        
+        p_term_mul(coef, exp, s_coef, s_exp);
+        
+        res = p_add_sub(r_coef, r_exp, s_coef, s_exp, -1);
+
+        //printf("r(x): ");
+        //p_print(r_coef, r_exp);
+        //printf("\n");
+        
+        if(res == -1)
+        {
+            p_deleteC(r_coef, r_exp);
+            p_deleteC(q_coef, q_exp);
+            p_deleteC(s_coef, s_exp);
+            break;
+        }
+        
+    } while( d_exp[0] < r_exp[0] );
+}
+
+
+int main() 
+{  
+  
+  //polinomi p(x) = -16x^15 +10x^9 +18x^5 +2x -1
+  int p_coef[20]={-16,+10,+18,+2,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
+  int p_exp [20]={+15,+ 9,+ 5,+1,+0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+  
+  //polinomi q(x) = 11x^10 -12x^5 +4x^3 -8x
+  int q_coef[20]={+11,-12,+4,-2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
+  int q_exp [20]={+10, +5,+3,+1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+  
+  //polinomi r(x) = x^10 -8x +5x^2 +12x^7 -3 +x^18 -5x^17
+  int r_coef[20]={ +1,-8,+5,+12,-3, +1, -5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
+  int r_exp [20]={+10,+1,+2, +7,+0,+18,+17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+  
+  //polinomi d(x)= +1x^7 -1x +1
+  int d_coef[20]={+1,-1,+1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
+  int d_exp [20]={+7,+1,+0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+
+/**
+ * Programa Principal de la P2
+*/
+    system("clear");
+
+    int op = 1;
+
+    while(op != 0)
+    {
+        printf("1 - Multiplicar dos polinomis\n");
+        printf("2 - Dividir dos polinomis\n");
+        printf("Opció: ");
+        scanf("%d",&op);
+
+        switch(op)
+        {
+            case 1: //Multiplica dos polinomis. r(x)=p(x)*q(x)
+                printf("Polinomi p(x)\n");
+                p_print(p_coef, p_exp);
+                printf("Polinomi q(x)\n");
+                p_print(q_coef, q_exp);
+
+                p_mul(p_coef, p_exp, q_coef, q_exp, r_coef, r_exp);
+
+                printf("Polinomi r(x)=p(x)*q(x): \n");
+                p_print(r_coef, r_exp);
+                break;	
+
+            case 2: //Divideix dos polinomis. p(x)/d(x). p(x)=d(x)*q(x)+r(x)
+                printf("Polinomi p(x)\n");
+                p_print(p_coef, p_exp);
+                printf("Polinomi d(x)\n");
+                p_print(d_coef, d_exp);
+
+                p_div(p_coef, p_exp, d_coef, d_exp, q_coef, q_exp, r_coef, r_exp);
+
+                printf("p(x)/d(x): p(x)=d(x)*q(x)+r(x)\n");
+                printf("Polinomi q(x)\n");
+                p_print(q_coef, q_exp);
+                printf("Polinomi r(x)\n");
+                p_print(r_coef, r_exp);
+                break;	
+        }
+    }
+}
+#include <stdio.h>
+#include <assert.h>
+
+// Funciones en ensamblador
+extern int p_term_add_c(int coef_term, int exp_term, int* coefs, int* exps);
+extern int p_add_sub(int *r_coef, int * r_exp, int* s_coef, int* s_exp, int suma_resta);
+extern void p_term_mul(int coef, int exp, int* v_coef, int* v_exp);
+
+void printTerm(int coef, int exp)
+{
+    if(coef > 0)
+        printf("+%dx^%d ", coef, exp); 
+    else
+        printf("%dx^%d ", coef, exp); 
+}
+
+void p_print(int v_coef[], int v_exp[])
+{  
+    int i;
+    
+    for(i=0; i<20; i++)
+    {
+        printTerm(v_coef[i], v_exp[i]);
+    }
+    
+    printf("\n");   
+}
+
+int equalPolynomial(int *coef1, int * exp1, int *coef2, int *exp2)
+{
+    int i;
+    for(i=0; i<20; i++)
+    {
+        if(( coef1[i] != coef2[i] ) || ( exp1[i] != exp2[i] ))
+        {
+            //printf("%d - %d\n", coef1[i], coef2[i]);
+            //printf("%d - %d\n", exp1[i], exp2[i]);
+            return 0;
+        }
+    }
+    return 1;
+}
+
+/**
+ *  Copiar el polinomi v1 sobre el polinomi v2, posició a posició.
+ */
+void p_copyC(int v1_coef[], int v1_exp[], int v2_coef[], int v2_exp[]) 
+{
+    int i;
+    for (i=0; i<20; i++) 
+    {
+        v2_coef[i] = v1_coef[i];
+        v2_exp[i] = v1_exp[i];
+    }
+}
+
+/**
+ *  Esborrar el polinomi v, posa a 0 els coeficients i a -1 els exponents.
+ */
+void p_deleteC(int v_coef[], int v_exp[]) 
+{
+    int i;
+    for (i=0; i<20; i++) 
+    {
+        v_coef[i]= +0;
+        v_exp[i] = -1;
+    }
+}
+
+void p_div(int p_coef[], int p_exp[], int d_coef[], int d_exp[], int q_coef[], int q_exp[], int r_coef[], int r_exp[])
+{
+    int res;
+    int coef;
+    int exp;
+
+    //polinomi s(x) 
+    int s_coef[20]={ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
+    int s_exp [20]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
+    
+    p_deleteC(q_coef, q_exp);  //esborrar el polinomi on guardarem el quocient de la divisió
+    p_deleteC(r_coef, r_exp);  //esborrar el polinomi on guardarem el residu  de la divisió
+    
+    
+    p_copyC(p_coef, p_exp, r_coef, r_exp);
+    
+    do 
+    {
+        coef = r_coef[0]/d_coef[0];
+        exp = r_exp[0] - d_exp[0];
+        
+        p_term_add_c(coef, exp, q_coef, q_exp);
+        
+        //printf("q(x): ");
+        //p_print(q_coef, q_exp);
+        //printf("\n");
+        
+        p_copyC(d_coef, d_exp, s_coef, s_exp);
+        
+        p_term_mul(coef, exp, s_coef, s_exp);
+        
+        res = p_add_sub(r_coef, r_exp, s_coef, s_exp, -1);
+
+        //printf("r(x): ");
+        //p_print(r_coef, r_exp);
+        //printf("\n");
+        
+        if(res == -1)
+        {
+            p_deleteC(r_coef, r_exp);
+            p_deleteC(q_coef, q_exp);
+            p_deleteC(s_coef, s_exp);
+            break;
+        }
+        
+    } while( d_exp[0] < r_exp[0] );
+}
+
+void p_mul(int p_coef[], int p_exp[], int q_coef[], int q_exp[], int r_coef[], int r_exp[])
+{
+    int i;
+    int res;
+    
+    //polinomi s(x). Polinomi per guardar resultats parcials i així no modificar els polinomis originals.
+    //Vector amb els coeficients dels termes del polinomi s(x).
+    int s_coef[20]={ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+    //Vector amb els  exponents  dels termes del polinomi s(x). 
+    int s_exp [20]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+  
+    p_deleteC(r_coef, r_exp); // Esborrar el polinomi on guardarem el resultat de la multiplicació
+
+    
+    for(i=0; i<20; i++)
+    {
+        if(q_exp[i] == -1)
+            break;
+            
+        p_copyC(p_coef, p_exp, s_coef, s_exp);
+        
+        p_term_mul(q_coef[i], q_exp[i], s_coef, s_exp);
+        
+        //printf("s \n");
+        //p_print(s_coef, s_exp);
+        //printf("\n");
+        
+        res = p_add_sub(r_coef, r_exp, s_coef, s_exp, 0);
+        
+        //printf("r \n");
+        //p_print(r_coef, r_exp);
+        //printf("\n");
+        
+        if(res == -1)
+        {
+            p_deleteC(r_coef, r_exp);
+        }       
+    }
+}
+
+int main(void) 
+{
+    printf("Testing p_mul...\n");
+    
+    //polinomi p(x) = -16x^15 +10x^9 +18x^5 +2x -1
+    int p_coef[20]={-16,+10,+18,+2,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
+    int p_exp [20]={+15,+ 9,+ 5,+1,+0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+
+    printf("p(x): ");    
+    p_print(p_coef, p_exp);
+
+    //polinomi q(x) = 11x^10 -12x^5 +4x^3 -8x
+    int q_coef[20]={+11,-12,+4,-8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
+    int q_exp [20]={+10, +5,+3,+1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+
+    printf("q(x): ");
+    p_print(q_coef, q_exp);
+    printf("\n");
+
+    //polinomi r(x) = x^10 -8x +5x^2 +12x^7 -3 +x^18 -5x^17
+    int r_coef[20]={ +1,-8,+5,+12,-3, +1, -5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+    int r_exp [20]={+10,+1,+2, +7,+0,+18,+17,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; 
+
+    p_mul(p_coef, p_exp, q_coef, q_exp, r_coef, r_exp);     
+
+    int exp_r_coef[20]={-176,192,110,-64,128, 198, -120, 40, 22, -307, 72, -168, 12, 8, -4, -16, 8, 0, 0, 0};
+    int exp_r_exp [20]={25,20,19,18,16,15,14,12,11,10,8,6,5,4,3,2,1,-1,-1,-1};  
+    
+    assert(1 == equalPolynomial(exp_r_coef, exp_r_exp, r_coef, r_exp));  
+    
+    printf("r(x) = p(x) * q(x) = ");
+    p_print(r_coef, r_exp);
+    printf("Ok\n");
+    printf("\n");
+    //----------------------------------------------------------------------------------
+ 
+     printf("Testing p_div...\n");
+    
+    printf("p(x): ");    
+    p_print(p_coef, p_exp);
+
+    //polinomi d(x)= +1x^7 -1x +1
+    int d_coef[20]={+1,-1,+1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+    int d_exp [20]={+7,+1,+0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
+
+    printf("d(x): ");
+    p_print(d_coef, d_exp);
+    printf("\n");
+
+    p_div(p_coef, p_exp, d_coef, d_exp, q_coef, q_exp, r_coef, r_exp);
+    
+    int exp_r_div_coef[20]={18, -6, 22, -14, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+    int exp_r_div_exp [20]={5,3,2,1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};  
+
+    printf("r(x): ");
+    p_print(r_coef, r_exp);
+    
+    assert(1 == equalPolynomial(exp_r_div_coef, exp_r_div_exp, r_coef, r_exp));  
+
+    int exp_q_coef[20]={-16,-6,16,0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+    int exp_q_exp [20]={8,2,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};  
+    
+    assert(1 == equalPolynomial(exp_q_coef, exp_q_exp, q_coef, q_exp));  
+
+    printf("q(x): ");
+    p_print(q_coef, q_exp);
+    printf("Ok\n");
+    //----------------------------------------------------------------------------------
+    
+    printf("\nAll tests passed!!\n");
+      
+    return 0;  
+}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.