18 mpz_init_set_ui(coef[0],0);
23 int_poly::int_poly(
int n, mpz_t *
a)
28 for (
int i=0;
i<=n;
i++)
30 mpz_init_set(coef[
i],
a[
i]);
54 void int_poly::poly_add(
const int_poly
a,
const int_poly
b)
61 for (
int i=0;
i<=
b.deg;
i++)
63 mpz_add(coef[
i],
a.coef[
i],
b.coef[
i]);
66 for (
int i=
b.deg+1;
i<=
a.deg;
i++)
68 mpz_init_set(coef[
i],
a.coef[
i]);
73 while(mpz_sgn(coef[
i])==0 &&
i>=0)
77 else {poly_add(
b,
a); }
83 void int_poly::poly_add_to(
const int_poly
g)
85 this->poly_add(*
this,
g);
89 void int_poly::poly_add_const(int_poly
f,
const mpz_t
a)
96 mpz_add(coef[0],coef[0],
a);
98 if (deg==0 && mpz_sgn(coef[0])==0)
107 void int_poly::poly_add_const_to(
const mpz_t
a)
109 this->poly_add_const(*
this,
a);
113 void int_poly::poly_add_mon(int_poly
f, mpz_t
a,
int i)
117 if (
i<=deg && is_zero()==0)
119 mpz_add(coef[
i],coef[
i],
a);
121 if (deg==
i && mpz_sgn(coef[
i])==0)
124 else if (is_zero()==1)
127 for(
int j=0;
j<=
i;
j++)
129 mpz_init_set_ui(coef[
j],0);
131 mpz_add(coef[
i],coef[
i],
a);
136 for(
int j=
i;
j>deg;
j--)
138 mpz_init_set_ui(coef[
j],0);
140 mpz_add(coef[
i],coef[
i],
a);
146 void int_poly::poly_add_mon_to(mpz_t
a,
int i)
148 if (
i<=deg && is_zero()==0)
150 mpz_add(coef[
i],coef[
i],
a);
152 else if (is_zero()==1)
155 for(
int j=0;
j<=
i;
j++)
157 mpz_init_set_ui(coef[
j],0);
159 mpz_add(coef[
i],coef[
i],
a);
164 for(
int j=
i;
j>deg;
j--)
166 mpz_init_set_ui(coef[
j],0);
168 mpz_add(coef[
i],coef[
i],
a);
173 while(mpz_sgn(coef[
k])==0 &&
k>=0)
180 void int_poly::poly_sub(
const int_poly
a,
const int_poly
b)
190 while(mpz_sgn(coef[
i])==0 &&
i>=0)
198 void int_poly::poly_sub_to(
const int_poly
b)
200 this->poly_sub(*
this,
b);
204 void int_poly::poly_sub_const(int_poly
f,
const mpz_t
a)
214 mpz_sub(coef[0],coef[0],
a);
219 while(mpz_sgn(coef[
i])==0 &&
i>=0)
227 void int_poly::poly_sub_const_to(
const mpz_t
a)
229 this->poly_sub_const(*
this,
a);
234 void int_poly::poly_sub_mon(
const int_poly
f , mpz_t
a,
int i)
238 if (
i<=deg && is_zero()!=1)
240 mpz_sub(coef[
i],coef[
i],
a);
242 if (deg==
i && mpz_sgn(coef[
i])==0)
245 else if (is_zero()==1)
247 for(
int j=0;
j<=
i;
j++)
249 mpz_init_set_ui(coef[
j],0);
251 mpz_sub(coef[
i],coef[
i],
a);
256 for(
int j=
i;
j>deg;
j--)
258 mpz_init_set_ui(coef[
j],0);
260 mpz_sub(coef[
i],coef[
i],
a);
266 void int_poly::poly_sub_mon_to(mpz_t
a,
int i)
269 if (
i<=deg && is_zero()!=1)
271 mpz_sub(coef[
i],coef[
i],
a);
273 if (deg==
i && mpz_sgn(coef[
i])==0)
276 else if (is_zero()==1)
278 for(
int j=0;
j<=
i;
j++)
280 mpz_init_set_ui(coef[
j],0);
282 mpz_sub(coef[
i],coef[
i],
a);
287 for(
int j=
i;
j>deg;
j--)
289 mpz_init_set_ui(coef[
j],0);
291 mpz_sub(coef[
i],coef[
i],
a);
300 void int_poly::poly_mon_mult(
const int_poly
f,
int n)
309 for (
int i=deg;
i>=n;
i--)
311 mpz_init_set(coef[
i],
f.coef[
i-n]);
313 for (
int i=n-1;
i>=0;
i--)
315 mpz_init_set_ui(coef[
i],0);
320 void int_poly::poly_mon_mult_to(
const int n)
322 this->poly_mon_mult(*
this,n);
328 void int_poly::poly_scalar_mult(
const int_poly
g,
const mpz_t n)
336 mpz_init_set_ui(temp,0);
337 for(
int i=0;
i<=deg;
i++)
339 mpz_mul(temp,n,
g.coef[
i]);
340 mpz_init_set(coef[
i],temp);
347 void int_poly::poly_scalar_mult(
const mpz_t n,
const int_poly
g)
355 mpz_init_set_ui(temp,0);
356 for(
int i=0;
i<=deg;
i++)
358 mpz_mul(temp,n,
g.coef[
i]);
359 mpz_init_set(coef[
i],temp);
365 void int_poly::poly_scalar_mult_to(
const mpz_t n)
367 this->poly_scalar_mult(*
this,n);
374 void int_poly::poly_neg()
376 for (
int i=0;
i<=deg;
i++)
378 mpz_neg(coef[
i],coef[
i]);
383 void int_poly::poly_mult_n(int_poly
a,int_poly
b)
386 if (
a.is_zero()==1 ||
b.is_zero()==1)
393 mpz_init_set_ui(temp,0);
397 int_poly atemp, btemp;
400 for(
int i=
a.deg+1;
i<=deg;
i++)
402 mpz_init_set_ui(atemp.coef[
i],0);
404 for(
int i=
b.deg+1;
i<=deg;
i++)
406 mpz_init_set_ui(btemp.coef[
i],0);
412 for (
int k=0;
k<=deg;
k++)
414 mpz_init_set_ui(coef[
k],0);
415 for (
int i=0;
i<=
k;
i++)
417 mpz_mul(temp,atemp.coef[
i],btemp.coef[
k-
i]);
418 mpz_add(coef[
k],coef[
k],temp);
427 void int_poly::poly_mult_n_to(
const int_poly
g)
429 this->poly_mult_n(*
this,
g);
434 void int_poly::poly_mult_ka( int_poly
A, int_poly
B)
437 if (
A.is_zero()==1 ||
B.is_zero()==1)
445 if(
A.deg>=
B.deg){n=
A.deg+1;}
448 n =
static_cast<int>(ceil(
log(n)/
log(2)));
449 n =
static_cast<int>(
pow(2,n));
454 mpz_mul(AB,
A.coef[0],
B.coef[0]);
460 int_poly Au, Al, Bu, Bl;
461 Au.poly_mon_div(
A,n/2);
462 Al.poly_mon_div_rem(
A,n/2);
463 Bu.poly_mon_div(
B,n/2);
464 Bl.poly_mon_div_rem(
B,n/2);
470 int_poly D0, D1, D01;
471 D0.poly_mult_ka(Al,Bl);
472 D1.poly_mult_ka(Au,Bu);
473 D01.poly_mult_ka(Alu,Blu);
479 D01.poly_mon_mult_to(n/2);
480 D1.poly_mon_mult_to(n);
492 void int_poly::poly_scalar_div(
const int_poly
g,
const mpz_t n)
496 mpz_init_set_ui(temp,0);
497 for(
int i=0;
i<=deg;
i++)
499 mpz_divexact(temp,
g.coef[
i],n);
500 mpz_init_set(coef[
i],temp);
505 void int_poly::poly_scalar_div_to(
const mpz_t n)
507 this->poly_scalar_div(*
this,n);
511 void int_poly::poly_mon_div(
const int_poly
f,
const int n)
520 for (
int i=0;
i<=
f.deg-n;
i++)
522 mpz_init_set(coef[
i],
f.coef[n+
i]);
528 void int_poly::poly_mon_div_rem(
const int_poly
f,
const int n)
537 for (
int i=0;
i<=n-1;
i++)
539 mpz_init_set(coef[
i],
f.coef[
i]);
548 void int_poly::poly_div(int_poly &
Q,int_poly &
R, int_poly
A, int_poly
B)
557 mpz_init_set_ui(
a,0);
563 mpz_divexact(
a,
R.coef[
R.deg],
B.coef[
B.deg]);
566 temp.poly_mon_mult(
B,
i);
567 temp.poly_scalar_mult_to(
a);
570 Q.poly_add_mon_to(
a,
i);
579 void int_poly::poly_div_to(int_poly &
Q,int_poly &
R,
const int_poly
B)
581 this->poly_div(
Q,
R,*
this,
B);
586 void int_poly::poly_pseudodiv_rem( int_poly
A, int_poly
B)
598 temp.poly_mon_mult(
B,
R.deg-
B.deg);
599 temp.poly_scalar_mult_to(
R.coef[
R.deg]);
600 R.poly_scalar_mult_to(
B.coef[
B.deg]);
606 mpz_init_set(q,
B.coef[
B.deg]);
608 R.poly_scalar_mult_to(q);
615 void int_poly::poly_pseudodiv_rem_to(
const int_poly
B)
617 this->poly_pseudodiv_rem(*
this,
B);
624 void int_poly::poly_pseudodiv(int_poly &
Q, int_poly &
R, int_poly
A, int_poly
B)
634 int k =
A.deg -
B.deg;
638 for (
int i=0;
i<=
k;
i++)
640 mpz_init_set_ui(
Q.coef[
i],0);
648 mpz_set(
Q.coef[
k],
R.coef[
R.deg]);
650 temp.poly_mon_mult(
B,
k);
651 temp.poly_scalar_mult_to(
R.coef[
R.deg]);
653 R.poly_scalar_mult_to(
B.coef[
B.deg]);
662 mpz_init_set_ui(dummy,0);
664 for (
int i=0;
i<=
A.deg-
B.deg;
i++)
666 if (mpz_cmp_ui(
Q.coef[
i],0)!=0)
668 mpz_pow_ui(dummy,
B.coef[
B.deg],
delta);
669 mpz_mul(
Q.coef[
i],
Q.coef[
i],dummy);
683 void int_poly::poly_pseudodiv_to(int_poly &
Q, int_poly &
R, int_poly
B)
685 this->poly_pseudodiv(
Q,
R,*
this,
B);
691 void int_poly::poly_multadd_to(
const int_poly
b,
const int_poly c)
698 void int_poly::poly_multsub_to(
const int_poly
b,
const int_poly c)
720 void int_poly::poly_cont(mpz_t& cont)
724 mpz_init_set_ui(cont,0);
730 mpz_init_set(temp,coef[0]);
731 while (mpz_cmp_ui(temp,1)!=0 &&
i<=deg)
733 mpz_gcd(temp,temp,coef[
i]);
736 mpz_init_set(cont,temp);
746 void int_poly::poly_pp(int_poly
f)
751 if (mpz_cmp_ui(cont,1)==0)
756 for (
int i=0;
i<=deg;
i++)
758 mpz_init_set_ui(coef[
i],0);
759 mpz_divexact(coef[
i],
f.coef[
i],cont);
768 void int_poly::poly_horner(mpz_t erg,
const mpz_t u)
770 mpz_init_set(erg,coef[deg]);
771 for (
int i=deg;
i>=1;
i--)
774 mpz_add(erg,erg,coef[
i-1]);
780 void int_poly::poly_horner_int_poly(
const int_poly
A,
const int_poly
B)
782 poly_set(
A.coef[
A.deg]);
783 for (
int i=
A.deg;
i>=1;
i--)
786 poly_add_const_to(
A.coef[
i-1]);
796 void int_poly::poly_set(
const int_poly
b)
799 for(
int i=0;
i<=deg;
i++)
801 mpz_init_set(coef[
i],
b.coef[
i]);
807 void int_poly::poly_set(
const mpz_t
b)
810 mpz_init_set(coef[0],
b);
815 void int_poly::poly_set_zero()
823 int int_poly::is_equal(
const int_poly
g)
const 829 for (
int i=deg;
i>=0;
i--)
831 if (mpz_cmp(coef[
i],
g.coef[
i])!=0)
839 int int_poly::is_zero()
const 848 int int_poly::is_one()
const 852 if (mpz_cmpabs_ui(coef[0],1)==0) {
return 1; }
858 int int_poly::is_monic()
const 860 if (mpz_cmpabs_ui(coef[deg],1)==0)
868 void int_poly::poly_gcd( int_poly
A, int_poly
B)
872 else if (
B.is_zero()==1)
874 else if (
B.is_monic()==0)
888 while (Bpp.is_zero()==0)
890 R.poly_div(
Q,
R,App,Bpp);
903 void int_poly::poly_ppgcd(int_poly
A,int_poly
B)
910 else if(
B.is_zero()==1)
919 mpz_init_set_ui(
a,0);
921 mpz_init_set_ui(
b,0);
923 mpz_init_set_ui(d,0);
935 R.poly_pseudodiv_rem(App,Bpp);
943 R.poly_pseudodiv_rem(App,Bpp);
949 mpz_init_set(coef[0],d);
954 poly_scalar_mult_to(d);
961 void int_poly::poly_ppgcd_to(int_poly
B)
963 this->poly_ppgcd(*
this,
B);
970 void int_poly::poly_subgcd(int_poly
A, int_poly
B)
978 else if(
B.is_zero()==1)
986 mpz_init_set_ui(
a,0);
988 mpz_init_set_ui(
b,0);
990 mpz_init_set_ui(d,0);
992 mpz_init_set_ui(
h,1);
994 mpz_init_set_ui(
g,1);
996 mpz_init_set_ui(temp1,0);
998 mpz_init_set_ui(temp2,0);
1012 R.poly_pseudodiv_rem(App,Bpp);
1018 delta =App.deg-Bpp.deg;
1020 mpz_pow_ui(temp1,
h,
delta);
1021 mpz_mul(temp2,temp1,
g);
1024 Bpp.poly_scalar_div_to(temp2);
1026 mpz_set(
g,App.coef[App.deg]);
1027 mpz_pow_ui(temp1,
h,1-
delta);
1028 mpz_pow_ui(temp2,
g,
delta);
1029 mpz_mul(
h,temp1,temp2);
1034 R.poly_pseudodiv_rem(App,Bpp);
1041 mpz_init_set(coef[0],d);
1047 poly_scalar_mult_to(d);
1048 poly_scalar_div_to(temp1);
1055 void int_poly::poly_subgcd_to(int_poly
B)
1057 this->poly_subgcd(*
this,
B);
1063 void int_poly::poly_extsubgcd(int_poly&
r, int_poly& t,int_poly &
g,int_poly
A,int_poly
B)
1066 poly_extsubgcd(t,
r,
g,
B,
A);
1067 else if (
B.is_zero()==1)
1073 mpz_init_set_ui(temp,1);
1089 mpz_init_set_ui(temp,1);
1090 mpz_init_set_ui(
base,1);
1091 mpz_init_set_ui(base2,1);
1092 mpz_init_set_ui(base3,1);
1093 mpz_init_set_ui(psi,1);
1099 dummy.poly_set_zero();
1102 dummy2.poly_set_zero();
1129 mpz_set_si(temp,-1);
1132 mpz_init_set_ui(temp2,0);
1133 mpz_pow_ui(temp2,f2.coef[f2.deg],
alpha);
1134 f.poly_scalar_mult(f1,temp2);
1137 A.poly_div(q,f3,
f,f2);
1139 f3.poly_scalar_mult_to(
base);
1143 mpz_pow_ui(base2,f2.coef[f2.deg],
alpha);
1144 r3.poly_scalar_mult_to(base2);
1149 t3.poly_mult_n_to(q);
1165 delta2=f1.deg-f2.deg;
1169 while (f2.is_zero()==0)
1175 mpz_pow_ui(temp2,f2.coef[f2.deg],
alpha);
1176 f.poly_scalar_mult(f1,temp2);
1177 A.poly_div(q,f3,
f,f2);
1181 mpz_pow_ui(base2,f1.coef[f1.deg],
delta);
1184 mpz_mul(base2,base2,psi);
1185 mpz_divexact(psi,base2,
base);
1190 mpz_pow_ui(base2,psi,delta2);
1191 mpz_mul(base2,base2,f1.coef[f1.deg]);
1192 f3.poly_scalar_div_to(base2);
1193 f3.poly_scalar_mult_to(
base);
1198 mpz_pow_ui(base3,f2.coef[f2.deg],
alpha);
1201 dummy.poly_mult_n(q,r2);
1202 dummy2.poly_scalar_mult(r1,base3);
1203 r3.poly_sub(dummy2,dummy);
1204 r3.poly_scalar_mult_to(
base);
1205 r3.poly_scalar_div_to(base2);
1208 dummy.poly_mult_n(q,t2);
1209 dummy2.poly_scalar_mult(t1,base3);
1210 t3.poly_sub(dummy2,dummy);
1211 t3.poly_scalar_mult_to(
base);
1212 t3.poly_scalar_div_to(base2);
1226 delta2=f1.deg-f2.deg;
1245 void int_poly::poly_insert()
1248 cout <<
"Bitte geben Sie ein int_polynom ein! Zunächst den Grad: " << endl;
1252 for (
int i=0;
i<=deg;
i++)
1254 mpz_init_set_ui(coef[
i],0);
1255 printf(
"Geben Sie nun f[%i] ein:",
i);
1256 mpz_inp_str(coef[
i],stdin, 10);
1263 void int_poly::poly_print()
1267 cout <<
"0" <<
"\n" <<endl;
1270 for (
int i=deg;
i>=1;
i--)
1272 mpz_out_str(stdout,10, coef[
i]);
1275 mpz_out_str(stdout,10, coef[0]);
gmp_float log(const gmp_float &a)
bool delta(X x, Y y, D d)
Rational pow(const Rational &a, int e)