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);
1137 f3.poly_scalar_mult_to(
base);
1141 mpz_pow_ui(base2,f2.coef[f2.deg],
alpha);
1142 r3.poly_scalar_mult_to(base2);
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);
1179 mpz_pow_ui(base2,f1.coef[f1.deg],
delta);
1182 mpz_mul(base2,base2,psi);
1183 mpz_divexact(psi,base2,
base);
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]);
Rational pow(const Rational &a, int e)
gmp_float log(const gmp_float &a)
bool delta(X x, Y y, D d)
const signed long ceil(const ampf< Precision > &x)