17 mpz_init_set_ui(coef[0],0);
22 int_poly::int_poly(
int n, mpz_t *a)
27 for (
int i=0;
i<=n;
i++)
29 mpz_init_set(coef[
i], a[i]);
53 void int_poly::poly_add(
const int_poly a,
const int_poly
b)
60 for (
int i=0;
i<=b.deg;
i++)
62 mpz_add(coef[
i],a.coef[i],b.coef[i]);
65 for (
int i=b.deg+1;
i<=a.deg;
i++)
67 mpz_init_set(coef[
i],a.coef[i]);
72 while(mpz_sgn(coef[i])==0 && i>=0)
76 else {poly_add(b,a); }
82 void int_poly::poly_add_to(
const int_poly
g)
84 this->poly_add(*
this,g);
88 void int_poly::poly_add_const(int_poly
f,
const mpz_t a)
95 mpz_add(coef[0],coef[0],a);
97 if (deg==0 && mpz_sgn(coef[0])==0)
106 void int_poly::poly_add_const_to(
const mpz_t a)
108 this->poly_add_const(*
this,a);
112 void int_poly::poly_add_mon(int_poly f, mpz_t a,
int i)
116 if (i<=deg && is_zero()==0)
118 mpz_add(coef[i],coef[i],a);
120 if (deg==i && mpz_sgn(coef[i])==0)
123 else if (is_zero()==1)
126 for(
int j=0;
j<=
i;
j++)
128 mpz_init_set_ui(coef[
j],0);
130 mpz_add(coef[i],coef[i],a);
135 for(
int j=i;
j>deg;
j--)
137 mpz_init_set_ui(coef[
j],0);
139 mpz_add(coef[i],coef[i],a);
145 void int_poly::poly_add_mon_to(mpz_t a,
int i)
147 if (i<=deg && is_zero()==0)
149 mpz_add(coef[i],coef[i],a);
151 else if (is_zero()==1)
154 for(
int j=0;
j<=
i;
j++)
156 mpz_init_set_ui(coef[
j],0);
158 mpz_add(coef[i],coef[i],a);
163 for(
int j=i;
j>deg;
j--)
165 mpz_init_set_ui(coef[
j],0);
167 mpz_add(coef[i],coef[i],a);
172 while(mpz_sgn(coef[k])==0 && k>=0)
179 void int_poly::poly_sub(
const int_poly a,
const int_poly b)
189 while(mpz_sgn(coef[i])==0 && i>=0)
197 void int_poly::poly_sub_to(
const int_poly b)
199 this->poly_sub(*
this,b);
203 void int_poly::poly_sub_const(int_poly f,
const mpz_t a)
213 mpz_sub(coef[0],coef[0],a);
218 while(mpz_sgn(coef[i])==0 && i>=0)
226 void int_poly::poly_sub_const_to(
const mpz_t a)
228 this->poly_sub_const(*
this,a);
233 void int_poly::poly_sub_mon(
const int_poly f , mpz_t a,
int i)
237 if (i<=deg && is_zero()!=1)
239 mpz_sub(coef[i],coef[i],a);
241 if (deg==i && mpz_sgn(coef[i])==0)
244 else if (is_zero()==1)
246 for(
int j=0;
j<=
i;
j++)
248 mpz_init_set_ui(coef[
j],0);
250 mpz_sub(coef[i],coef[i],a);
255 for(
int j=i;
j>deg;
j--)
257 mpz_init_set_ui(coef[
j],0);
259 mpz_sub(coef[i],coef[i],a);
265 void int_poly::poly_sub_mon_to(mpz_t a,
int i)
268 if (i<=deg && is_zero()!=1)
270 mpz_sub(coef[i],coef[i],a);
272 if (deg==i && mpz_sgn(coef[i])==0)
275 else if (is_zero()==1)
277 for(
int j=0;
j<=
i;
j++)
279 mpz_init_set_ui(coef[
j],0);
281 mpz_sub(coef[i],coef[i],a);
286 for(
int j=i;
j>deg;
j--)
288 mpz_init_set_ui(coef[
j],0);
290 mpz_sub(coef[i],coef[i],a);
299 void int_poly::poly_mon_mult(
const int_poly f,
int n)
308 for (
int i=deg;i>=n;i--)
310 mpz_init_set(coef[i],f.coef[i-n]);
312 for (
int i=n-1;i>=0;i--)
314 mpz_init_set_ui(coef[i],0);
319 void int_poly::poly_mon_mult_to(
const int n)
321 this->poly_mon_mult(*
this,n);
327 void int_poly::poly_scalar_mult(
const int_poly
g,
const mpz_t n)
335 mpz_init_set_ui(temp,0);
336 for(
int i=0;i<=deg;i++)
338 mpz_mul(temp,n,g.coef[i]);
339 mpz_init_set(coef[i],temp);
346 void int_poly::poly_scalar_mult(
const mpz_t n,
const int_poly g)
354 mpz_init_set_ui(temp,0);
355 for(
int i=0;i<=deg;i++)
357 mpz_mul(temp,n,g.coef[i]);
358 mpz_init_set(coef[i],temp);
364 void int_poly::poly_scalar_mult_to(
const mpz_t n)
366 this->poly_scalar_mult(*
this,n);
373 void int_poly::poly_neg()
375 for (
int i=0;i<=deg;i++)
377 mpz_neg(coef[i],coef[i]);
382 void int_poly::poly_mult_n(int_poly a,int_poly b)
385 if (a.is_zero()==1 || b.is_zero()==1)
392 mpz_init_set_ui(temp,0);
396 int_poly atemp, btemp;
399 for(
int i=a.deg+1;i<=deg;i++)
401 mpz_init_set_ui(atemp.coef[i],0);
403 for(
int i=b.deg+1;i<=deg;i++)
405 mpz_init_set_ui(btemp.coef[i],0);
411 for (
int k=0; k<=deg; k++)
413 mpz_init_set_ui(coef[k],0);
414 for (
int i=0; i<=
k; i++)
416 mpz_mul(temp,atemp.coef[i],btemp.coef[k-i]);
417 mpz_add(coef[k],coef[k],temp);
426 void int_poly::poly_mult_n_to(
const int_poly g)
428 this->poly_mult_n(*
this,g);
433 void int_poly::poly_mult_ka( int_poly
A, int_poly
B)
436 if (A.is_zero()==1 || B.is_zero()==1)
444 if(A.deg>=B.deg){n=A.deg+1;}
448 n =
static_cast<int>(
pow(2,n));
453 mpz_mul(AB,A.coef[0],B.coef[0]);
459 int_poly Au, Al, Bu, Bl;
460 Au.poly_mon_div(A,n/2);
461 Al.poly_mon_div_rem(A,n/2);
462 Bu.poly_mon_div(B,n/2);
463 Bl.poly_mon_div_rem(B,n/2);
469 int_poly D0, D1, D01;
470 D0.poly_mult_ka(Al,Bl);
471 D1.poly_mult_ka(Au,Bu);
472 D01.poly_mult_ka(Alu,Blu);
478 D01.poly_mon_mult_to(n/2);
479 D1.poly_mon_mult_to(n);
491 void int_poly::poly_scalar_div(
const int_poly g,
const mpz_t n)
495 mpz_init_set_ui(temp,0);
496 for(
int i=0;i<=deg;i++)
498 mpz_divexact(temp,g.coef[i],n);
499 mpz_init_set(coef[i],temp);
504 void int_poly::poly_scalar_div_to(
const mpz_t n)
506 this->poly_scalar_div(*
this,n);
510 void int_poly::poly_mon_div(
const int_poly f,
const int n)
519 for (
int i=0;i<=f.deg-n;i++)
521 mpz_init_set(coef[i],f.coef[n+i]);
527 void int_poly::poly_mon_div_rem(
const int_poly f,
const int n)
536 for (
int i=0;i<=n-1;i++)
538 mpz_init_set(coef[i],f.coef[i]);
547 void int_poly::poly_div(int_poly &
Q,int_poly &
R, int_poly A, int_poly B)
556 mpz_init_set_ui(a,0);
562 mpz_divexact(a,R.coef[R.deg],B.coef[B.deg]);
565 temp.poly_mon_mult(B,i);
566 temp.poly_scalar_mult_to(a);
569 Q.poly_add_mon_to(a,i);
578 void int_poly::poly_div_to(int_poly &Q,int_poly &R,
const int_poly B)
580 this->poly_div( Q, R,*
this,B);
585 void int_poly::poly_pseudodiv_rem( int_poly A, int_poly B)
597 temp.poly_mon_mult(B,R.deg-B.deg);
598 temp.poly_scalar_mult_to(R.coef[R.deg]);
599 R.poly_scalar_mult_to(B.coef[B.deg]);
605 mpz_init_set(q,B.coef[B.deg]);
607 R.poly_scalar_mult_to(q);
614 void int_poly::poly_pseudodiv_rem_to(
const int_poly B)
616 this->poly_pseudodiv_rem(*
this,B);
623 void int_poly::poly_pseudodiv(int_poly &Q, int_poly &R, int_poly A, int_poly B)
633 int k = A.deg - B.deg;
637 for (
int i=0;i<=
k;i++)
639 mpz_init_set_ui(Q.coef[i],0);
647 mpz_set(Q.coef[k],R.coef[R.deg]);
649 temp.poly_mon_mult(B,k);
650 temp.poly_scalar_mult_to(R.coef[R.deg]);
652 R.poly_scalar_mult_to(B.coef[B.deg]);
661 mpz_init_set_ui(dummy,0);
663 for (
int i=0;i<=A.deg-B.deg;i++)
665 if (mpz_cmp_ui(Q.coef[i],0)!=0)
667 mpz_pow_ui(dummy,B.coef[B.deg],delta);
668 mpz_mul(Q.coef[i],Q.coef[i],dummy);
682 void int_poly::poly_pseudodiv_to(int_poly &Q, int_poly &R, int_poly B)
684 this->poly_pseudodiv(Q, R,*
this,B);
690 void int_poly::poly_multadd_to(
const int_poly b,
const int_poly c)
697 void int_poly::poly_multsub_to(
const int_poly b,
const int_poly c)
719 void int_poly::poly_cont(mpz_t& cont)
723 mpz_init_set_ui(cont,0);
729 mpz_init_set(temp,coef[0]);
730 while (mpz_cmp_ui(temp,1)!=0 && i<=deg)
732 mpz_gcd(temp,temp,coef[i]);
735 mpz_init_set(cont,temp);
745 void int_poly::poly_pp(int_poly f)
750 if (mpz_cmp_ui(cont,1)==0)
755 for (
int i=0;i<=deg;i++)
757 mpz_init_set_ui(coef[i],0);
758 mpz_divexact(coef[i],f.coef[i],cont);
767 void int_poly::poly_horner(mpz_t erg,
const mpz_t u)
769 mpz_init_set(erg,coef[deg]);
770 for (
int i=deg;i>=1;i--)
773 mpz_add(erg,erg,coef[i-1]);
779 void int_poly::poly_horner_int_poly(
const int_poly A,
const int_poly B)
781 poly_set(A.coef[A.deg]);
782 for (
int i=A.deg;i>=1;i--)
785 poly_add_const_to(A.coef[i-1]);
795 void int_poly::poly_set(
const int_poly b)
798 for(
int i=0;i<=deg;i++)
800 mpz_init_set(coef[i],b.coef[i]);
806 void int_poly::poly_set(
const mpz_t b)
809 mpz_init_set(coef[0],b);
814 void int_poly::poly_set_zero()
822 int int_poly::is_equal(
const int_poly g)
const 828 for (
int i=deg;i>=0; i--)
830 if (mpz_cmp(coef[i],g.coef[i])!=0)
838 int int_poly::is_zero()
const 847 int int_poly::is_one()
const 851 if (mpz_cmpabs_ui(coef[0],1)==0) {
return 1; }
857 int int_poly::is_monic()
const 859 if (mpz_cmpabs_ui(coef[deg],1)==0)
867 void int_poly::poly_gcd( int_poly A, int_poly B)
871 else if (B.is_zero()==1)
873 else if (B.is_monic()==0)
887 while (Bpp.is_zero()==0)
889 R.poly_div(Q,R,App,Bpp);
902 void int_poly::poly_ppgcd(int_poly A,int_poly B)
909 else if(B.is_zero()==1)
918 mpz_init_set_ui(a,0);
920 mpz_init_set_ui(b,0);
922 mpz_init_set_ui(d,0);
934 R.poly_pseudodiv_rem(App,Bpp);
942 R.poly_pseudodiv_rem(App,Bpp);
948 mpz_init_set(coef[0],d);
953 poly_scalar_mult_to(d);
960 void int_poly::poly_ppgcd_to(int_poly B)
962 this->poly_ppgcd(*
this,B);
969 void int_poly::poly_subgcd(int_poly A, int_poly B)
977 else if(B.is_zero()==1)
985 mpz_init_set_ui(a,0);
987 mpz_init_set_ui(b,0);
989 mpz_init_set_ui(d,0);
991 mpz_init_set_ui(h,1);
993 mpz_init_set_ui(g,1);
995 mpz_init_set_ui(temp1,0);
997 mpz_init_set_ui(temp2,0);
1011 R.poly_pseudodiv_rem(App,Bpp);
1017 delta =App.deg-Bpp.deg;
1019 mpz_pow_ui(temp1,h,delta);
1020 mpz_mul(temp2,temp1,g);
1023 Bpp.poly_scalar_div_to(temp2);
1025 mpz_set(g,App.coef[App.deg]);
1026 mpz_pow_ui(temp1,h,1-delta);
1027 mpz_pow_ui(temp2,g,delta);
1028 mpz_mul(h,temp1,temp2);
1033 R.poly_pseudodiv_rem(App,Bpp);
1040 mpz_init_set(coef[0],d);
1046 poly_scalar_mult_to(d);
1047 poly_scalar_div_to(temp1);
1054 void int_poly::poly_subgcd_to(int_poly B)
1056 this->poly_subgcd(*
this,B);
1062 void int_poly::poly_extsubgcd(int_poly& r, int_poly& t,int_poly &g,int_poly A,int_poly B)
1065 poly_extsubgcd(t,r,g,B,A);
1066 else if (B.is_zero()==1)
1072 mpz_init_set_ui(temp,1);
1088 mpz_init_set_ui(temp,1);
1089 mpz_init_set_ui(base,1);
1090 mpz_init_set_ui(base2,1);
1091 mpz_init_set_ui(base3,1);
1092 mpz_init_set_ui(psi,1);
1098 dummy.poly_set_zero();
1101 dummy2.poly_set_zero();
1128 mpz_set_si(temp,-1);
1131 mpz_init_set_ui(temp2,0);
1132 mpz_pow_ui(temp2,f2.coef[f2.deg],alpha);
1133 f.poly_scalar_mult(f1,temp2);
1136 A.poly_div(q,f3,f,f2);
1137 mpz_pow_ui(base,temp,alpha);
1138 f3.poly_scalar_mult_to(base);
1142 mpz_pow_ui(base2,f2.coef[f2.deg],alpha);
1143 r3.poly_scalar_mult_to(base2);
1146 mpz_pow_ui(base,temp,delta);
1148 t3.poly_mult_n_to(q);
1164 delta2=f1.deg-f2.deg;
1168 while (f2.is_zero()==0)
1174 mpz_pow_ui(temp2,f2.coef[f2.deg],alpha);
1175 f.poly_scalar_mult(f1,temp2);
1176 A.poly_div(q,f3,f,f2);
1179 mpz_pow_ui(base,psi,delta);
1180 mpz_pow_ui(base2,f1.coef[f1.deg],delta);
1183 mpz_mul(base2,base2,psi);
1184 mpz_divexact(psi,base2,base);
1188 mpz_pow_ui(base,temp,alpha);
1189 mpz_pow_ui(base2,psi,delta2);
1190 mpz_mul(base2,base2,f1.coef[f1.deg]);
1191 f3.poly_scalar_div_to(base2);
1192 f3.poly_scalar_mult_to(base);
1197 mpz_pow_ui(base3,f2.coef[f2.deg],alpha);
1200 dummy.poly_mult_n(q,r2);
1201 dummy2.poly_scalar_mult(r1,base3);
1202 r3.poly_sub(dummy2,dummy);
1203 r3.poly_scalar_mult_to(base);
1204 r3.poly_scalar_div_to(base2);
1207 dummy.poly_mult_n(q,t2);
1208 dummy2.poly_scalar_mult(t1,base3);
1209 t3.poly_sub(dummy2,dummy);
1210 t3.poly_scalar_mult_to(base);
1211 t3.poly_scalar_div_to(base2);
1225 delta2=f1.deg-f2.deg;
1244 void int_poly::poly_insert()
1247 cout <<
"Bitte geben Sie ein int_polynom ein! Zunächst den Grad: " << endl;
1251 for (
int i=0; i<=deg;i++)
1253 mpz_init_set_ui(coef[i],0);
1254 printf(
"Geben Sie nun f[%i] ein:",i);
1255 mpz_inp_str(coef[i],stdin, 10);
1262 void int_poly::poly_print()
1266 cout <<
"0" <<
"\n" <<endl;
1269 for (
int i=deg;i>=1;i--)
1271 mpz_out_str(stdout,10, coef[i]);
1274 mpz_out_str(stdout,10, coef[0]);
gmp_float log(const gmp_float &a)
bool delta(X x, Y y, D d)
const signed long ceil(const ampf< Precision > &x)
Rational pow(const Rational &a, int e)