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);
1138 f3.poly_scalar_mult_to(
base);
1142 mpz_pow_ui(base2,f2.coef[f2.deg],
alpha);
1143 r3.poly_scalar_mult_to(base2);
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);
1180 mpz_pow_ui(base2,f1.coef[f1.deg],
delta);
1183 mpz_mul(base2,base2,psi);
1184 mpz_divexact(psi,base2,
base);
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]);
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)