16 mpz_init_set_ui(coef[0],0);
21 int_poly::int_poly(
int n, mpz_t *a)
26 for (
int i=0;
i<=n;
i++)
28 mpz_init_set(coef[
i], a[i]);
52 void int_poly::poly_add(
const int_poly a,
const int_poly
b)
59 for (
int i=0;
i<=b.deg;
i++)
61 mpz_add(coef[
i],a.coef[i],b.coef[i]);
64 for (
int i=b.deg+1;
i<=a.deg;
i++)
66 mpz_init_set(coef[
i],a.coef[i]);
71 while(mpz_sgn(coef[i])==0 && i>=0)
75 else {poly_add(b,a); }
81 void int_poly::poly_add_to(
const int_poly
g)
83 this->poly_add(*
this,g);
87 void int_poly::poly_add_const(int_poly
f,
const mpz_t a)
94 mpz_add(coef[0],coef[0],a);
96 if (deg==0 && mpz_sgn(coef[0])==0)
105 void int_poly::poly_add_const_to(
const mpz_t a)
107 this->poly_add_const(*
this,a);
111 void int_poly::poly_add_mon(int_poly f, mpz_t a,
int i)
115 if (i<=deg && is_zero()==0)
117 mpz_add(coef[i],coef[i],a);
119 if (deg==i && mpz_sgn(coef[i])==0)
122 else if (is_zero()==1)
125 for(
int j=0;
j<=
i;
j++)
127 mpz_init_set_ui(coef[
j],0);
129 mpz_add(coef[i],coef[i],a);
134 for(
int j=i;
j>deg;
j--)
136 mpz_init_set_ui(coef[
j],0);
138 mpz_add(coef[i],coef[i],a);
144 void int_poly::poly_add_mon_to(mpz_t a,
int i)
146 if (i<=deg && is_zero()==0)
148 mpz_add(coef[i],coef[i],a);
150 else if (is_zero()==1)
153 for(
int j=0;
j<=
i;
j++)
155 mpz_init_set_ui(coef[
j],0);
157 mpz_add(coef[i],coef[i],a);
162 for(
int j=i;
j>deg;
j--)
164 mpz_init_set_ui(coef[
j],0);
166 mpz_add(coef[i],coef[i],a);
171 while(mpz_sgn(coef[k])==0 && k>=0)
178 void int_poly::poly_sub(
const int_poly a,
const int_poly b)
188 while(mpz_sgn(coef[i])==0 && i>=0)
196 void int_poly::poly_sub_to(
const int_poly b)
198 this->poly_sub(*
this,b);
202 void int_poly::poly_sub_const(int_poly f,
const mpz_t a)
212 mpz_sub(coef[0],coef[0],a);
217 while(mpz_sgn(coef[i])==0 && i>=0)
225 void int_poly::poly_sub_const_to(
const mpz_t a)
227 this->poly_sub_const(*
this,a);
232 void int_poly::poly_sub_mon(
const int_poly f , mpz_t a,
int i)
236 if (i<=deg && is_zero()!=1)
238 mpz_sub(coef[i],coef[i],a);
240 if (deg==i && mpz_sgn(coef[i])==0)
243 else if (is_zero()==1)
245 for(
int j=0;
j<=
i;
j++)
247 mpz_init_set_ui(coef[
j],0);
249 mpz_sub(coef[i],coef[i],a);
254 for(
int j=i;
j>deg;
j--)
256 mpz_init_set_ui(coef[
j],0);
258 mpz_sub(coef[i],coef[i],a);
264 void int_poly::poly_sub_mon_to(mpz_t a,
int i)
267 if (i<=deg && is_zero()!=1)
269 mpz_sub(coef[i],coef[i],a);
271 if (deg==i && mpz_sgn(coef[i])==0)
274 else if (is_zero()==1)
276 for(
int j=0;
j<=
i;
j++)
278 mpz_init_set_ui(coef[
j],0);
280 mpz_sub(coef[i],coef[i],a);
285 for(
int j=i;
j>deg;
j--)
287 mpz_init_set_ui(coef[
j],0);
289 mpz_sub(coef[i],coef[i],a);
298 void int_poly::poly_mon_mult(
const int_poly f,
int n)
307 for (
int i=deg;i>=n;i--)
309 mpz_init_set(coef[i],f.coef[i-n]);
311 for (
int i=n-1;i>=0;i--)
313 mpz_init_set_ui(coef[i],0);
318 void int_poly::poly_mon_mult_to(
const int n)
320 this->poly_mon_mult(*
this,n);
326 void int_poly::poly_scalar_mult(
const int_poly
g,
const mpz_t n)
334 mpz_init_set_ui(temp,0);
335 for(
int i=0;i<=deg;i++)
337 mpz_mul(temp,n,g.coef[i]);
338 mpz_init_set(coef[i],temp);
345 void int_poly::poly_scalar_mult(
const mpz_t n,
const int_poly g)
353 mpz_init_set_ui(temp,0);
354 for(
int i=0;i<=deg;i++)
356 mpz_mul(temp,n,g.coef[i]);
357 mpz_init_set(coef[i],temp);
363 void int_poly::poly_scalar_mult_to(
const mpz_t n)
365 this->poly_scalar_mult(*
this,n);
372 void int_poly::poly_neg()
374 for (
int i=0;i<=deg;i++)
376 mpz_neg(coef[i],coef[i]);
381 void int_poly::poly_mult_n(int_poly a,int_poly b)
384 if (a.is_zero()==1 || b.is_zero()==1)
391 mpz_init_set_ui(temp,0);
395 int_poly atemp, btemp;
398 for(
int i=a.deg+1;i<=deg;i++)
400 mpz_init_set_ui(atemp.coef[i],0);
402 for(
int i=b.deg+1;i<=deg;i++)
404 mpz_init_set_ui(btemp.coef[i],0);
410 for (
int k=0; k<=deg; k++)
412 mpz_init_set_ui(coef[k],0);
413 for (
int i=0; i<=
k; i++)
415 mpz_mul(temp,atemp.coef[i],btemp.coef[k-i]);
416 mpz_add(coef[k],coef[k],temp);
425 void int_poly::poly_mult_n_to(
const int_poly g)
427 this->poly_mult_n(*
this,g);
432 void int_poly::poly_mult_ka( int_poly
A, int_poly
B)
435 if (A.is_zero()==1 || B.is_zero()==1)
443 if(A.deg>=B.deg){n=A.deg+1;}
447 n =
static_cast<int>(
pow(2,n));
452 mpz_mul(AB,A.coef[0],B.coef[0]);
458 int_poly Au, Al, Bu, Bl;
459 Au.poly_mon_div(A,n/2);
460 Al.poly_mon_div_rem(A,n/2);
461 Bu.poly_mon_div(B,n/2);
462 Bl.poly_mon_div_rem(B,n/2);
468 int_poly D0, D1, D01;
469 D0.poly_mult_ka(Al,Bl);
470 D1.poly_mult_ka(Au,Bu);
471 D01.poly_mult_ka(Alu,Blu);
477 D01.poly_mon_mult_to(n/2);
478 D1.poly_mon_mult_to(n);
490 void int_poly::poly_scalar_div(
const int_poly g,
const mpz_t n)
494 mpz_init_set_ui(temp,0);
495 for(
int i=0;i<=deg;i++)
497 mpz_divexact(temp,g.coef[i],n);
498 mpz_init_set(coef[i],temp);
503 void int_poly::poly_scalar_div_to(
const mpz_t n)
505 this->poly_scalar_div(*
this,n);
509 void int_poly::poly_mon_div(
const int_poly f,
const int n)
518 for (
int i=0;i<=f.deg-n;i++)
520 mpz_init_set(coef[i],f.coef[n+i]);
526 void int_poly::poly_mon_div_rem(
const int_poly f,
const int n)
535 for (
int i=0;i<=n-1;i++)
537 mpz_init_set(coef[i],f.coef[i]);
546 void int_poly::poly_div(int_poly &
Q,int_poly &
R, int_poly A, int_poly B)
555 mpz_init_set_ui(a,0);
561 mpz_divexact(a,R.coef[R.deg],B.coef[B.deg]);
564 temp.poly_mon_mult(B,i);
565 temp.poly_scalar_mult_to(a);
568 Q.poly_add_mon_to(a,i);
577 void int_poly::poly_div_to(int_poly &Q,int_poly &R,
const int_poly B)
579 this->poly_div( Q, R,*
this,B);
584 void int_poly::poly_pseudodiv_rem( int_poly A, int_poly B)
596 temp.poly_mon_mult(B,R.deg-B.deg);
597 temp.poly_scalar_mult_to(R.coef[R.deg]);
598 R.poly_scalar_mult_to(B.coef[B.deg]);
604 mpz_init_set(q,B.coef[B.deg]);
606 R.poly_scalar_mult_to(q);
613 void int_poly::poly_pseudodiv_rem_to(
const int_poly B)
615 this->poly_pseudodiv_rem(*
this,B);
622 void int_poly::poly_pseudodiv(int_poly &Q, int_poly &R, int_poly A, int_poly B)
632 int k = A.deg - B.deg;
636 for (
int i=0;i<=
k;i++)
638 mpz_init_set_ui(Q.coef[i],0);
646 mpz_set(Q.coef[k],R.coef[R.deg]);
648 temp.poly_mon_mult(B,k);
649 temp.poly_scalar_mult_to(R.coef[R.deg]);
651 R.poly_scalar_mult_to(B.coef[B.deg]);
660 mpz_init_set_ui(dummy,0);
662 for (
int i=0;i<=A.deg-B.deg;i++)
664 if (mpz_cmp_ui(Q.coef[i],0)!=0)
666 mpz_pow_ui(dummy,B.coef[B.deg],delta);
667 mpz_mul(Q.coef[i],Q.coef[i],dummy);
681 void int_poly::poly_pseudodiv_to(int_poly &Q, int_poly &R, int_poly B)
683 this->poly_pseudodiv(Q, R,*
this,B);
689 void int_poly::poly_multadd_to(
const int_poly b,
const int_poly c)
696 void int_poly::poly_multsub_to(
const int_poly b,
const int_poly c)
718 void int_poly::poly_cont(mpz_t& cont)
722 mpz_init_set_ui(cont,0);
728 mpz_init_set(temp,coef[0]);
729 while (mpz_cmp_ui(temp,1)!=0 && i<=deg)
731 mpz_gcd(temp,temp,coef[i]);
734 mpz_init_set(cont,temp);
744 void int_poly::poly_pp(int_poly f)
749 if (mpz_cmp_ui(cont,1)==0)
754 for (
int i=0;i<=deg;i++)
756 mpz_init_set_ui(coef[i],0);
757 mpz_divexact(coef[i],f.coef[i],cont);
766 void int_poly::poly_horner(mpz_t erg,
const mpz_t u)
768 mpz_init_set(erg,coef[deg]);
769 for (
int i=deg;i>=1;i--)
772 mpz_add(erg,erg,coef[i-1]);
778 void int_poly::poly_horner_int_poly(
const int_poly A,
const int_poly B)
780 poly_set(A.coef[A.deg]);
781 for (
int i=A.deg;i>=1;i--)
784 poly_add_const_to(A.coef[i-1]);
794 void int_poly::poly_set(
const int_poly b)
797 for(
int i=0;i<=deg;i++)
799 mpz_init_set(coef[i],b.coef[i]);
805 void int_poly::poly_set(
const mpz_t b)
808 mpz_init_set(coef[0],b);
813 void int_poly::poly_set_zero()
821 int int_poly::is_equal(
const int_poly g)
const 827 for (
int i=deg;i>=0; i--)
829 if (mpz_cmp(coef[i],g.coef[i])!=0)
837 int int_poly::is_zero()
const 846 int int_poly::is_one()
const 850 if (mpz_cmpabs_ui(coef[0],1)==0) {
return 1; }
856 int int_poly::is_monic()
const 858 if (mpz_cmpabs_ui(coef[deg],1)==0)
866 void int_poly::poly_gcd( int_poly A, int_poly B)
870 else if (B.is_zero()==1)
872 else if (B.is_monic()==0)
886 while (Bpp.is_zero()==0)
888 R.poly_div(Q,R,App,Bpp);
901 void int_poly::poly_ppgcd(int_poly A,int_poly B)
908 else if(B.is_zero()==1)
917 mpz_init_set_ui(a,0);
919 mpz_init_set_ui(b,0);
921 mpz_init_set_ui(d,0);
933 R.poly_pseudodiv_rem(App,Bpp);
941 R.poly_pseudodiv_rem(App,Bpp);
947 mpz_init_set(coef[0],d);
952 poly_scalar_mult_to(d);
959 void int_poly::poly_ppgcd_to(int_poly B)
961 this->poly_ppgcd(*
this,B);
968 void int_poly::poly_subgcd(int_poly A, int_poly B)
976 else if(B.is_zero()==1)
984 mpz_init_set_ui(a,0);
986 mpz_init_set_ui(b,0);
988 mpz_init_set_ui(d,0);
990 mpz_init_set_ui(h,1);
992 mpz_init_set_ui(g,1);
994 mpz_init_set_ui(temp1,0);
996 mpz_init_set_ui(temp2,0);
1010 R.poly_pseudodiv_rem(App,Bpp);
1016 delta =App.deg-Bpp.deg;
1018 mpz_pow_ui(temp1,h,delta);
1019 mpz_mul(temp2,temp1,g);
1022 Bpp.poly_scalar_div_to(temp2);
1024 mpz_set(g,App.coef[App.deg]);
1025 mpz_pow_ui(temp1,h,1-delta);
1026 mpz_pow_ui(temp2,g,delta);
1027 mpz_mul(h,temp1,temp2);
1032 R.poly_pseudodiv_rem(App,Bpp);
1039 mpz_init_set(coef[0],d);
1045 poly_scalar_mult_to(d);
1046 poly_scalar_div_to(temp1);
1053 void int_poly::poly_subgcd_to(int_poly B)
1055 this->poly_subgcd(*
this,B);
1061 void int_poly::poly_extsubgcd(int_poly& r, int_poly& t,int_poly &g,int_poly A,int_poly B)
1064 poly_extsubgcd(t,r,g,B,A);
1065 else if (B.is_zero()==1)
1071 mpz_init_set_ui(temp,1);
1087 mpz_init_set_ui(temp,1);
1088 mpz_init_set_ui(base,1);
1089 mpz_init_set_ui(base2,1);
1090 mpz_init_set_ui(base3,1);
1091 mpz_init_set_ui(psi,1);
1097 dummy.poly_set_zero();
1100 dummy2.poly_set_zero();
1127 mpz_set_si(temp,-1);
1130 mpz_init_set_ui(temp2,0);
1131 mpz_pow_ui(temp2,f2.coef[f2.deg],alpha);
1132 f.poly_scalar_mult(f1,temp2);
1135 A.poly_div(q,f3,f,f2);
1136 mpz_pow_ui(base,temp,alpha);
1137 f3.poly_scalar_mult_to(base);
1141 mpz_pow_ui(base2,f2.coef[f2.deg],alpha);
1142 r3.poly_scalar_mult_to(base2);
1145 mpz_pow_ui(base,temp,delta);
1147 t3.poly_mult_n_to(q);
1163 delta2=f1.deg-f2.deg;
1167 while (f2.is_zero()==0)
1173 mpz_pow_ui(temp2,f2.coef[f2.deg],alpha);
1174 f.poly_scalar_mult(f1,temp2);
1175 A.poly_div(q,f3,f,f2);
1178 mpz_pow_ui(base,psi,delta);
1179 mpz_pow_ui(base2,f1.coef[f1.deg],delta);
1182 mpz_mul(base2,base2,psi);
1183 mpz_divexact(psi,base2,base);
1187 mpz_pow_ui(base,temp,alpha);
1188 mpz_pow_ui(base2,psi,delta2);
1189 mpz_mul(base2,base2,f1.coef[f1.deg]);
1190 f3.poly_scalar_div_to(base2);
1191 f3.poly_scalar_mult_to(base);
1196 mpz_pow_ui(base3,f2.coef[f2.deg],alpha);
1199 dummy.poly_mult_n(q,r2);
1200 dummy2.poly_scalar_mult(r1,base3);
1201 r3.poly_sub(dummy2,dummy);
1202 r3.poly_scalar_mult_to(base);
1203 r3.poly_scalar_div_to(base2);
1206 dummy.poly_mult_n(q,t2);
1207 dummy2.poly_scalar_mult(t1,base3);
1208 t3.poly_sub(dummy2,dummy);
1209 t3.poly_scalar_mult_to(base);
1210 t3.poly_scalar_div_to(base2);
1224 delta2=f1.deg-f2.deg;
1243 void int_poly::poly_insert()
1246 cout <<
"Bitte geben Sie ein int_polynom ein! Zunächst den Grad: " << endl;
1250 for (
int i=0; i<=deg;i++)
1252 mpz_init_set_ui(coef[i],0);
1253 printf(
"Geben Sie nun f[%i] ein:",i);
1254 mpz_inp_str(coef[i],stdin, 10);
1261 void int_poly::poly_print()
1265 cout <<
"0" <<
"\n" <<endl;
1268 for (
int i=deg;i>=1;i--)
1270 mpz_out_str(stdout,10, coef[i]);
1273 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)