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);
1138 mpz_pow_ui(base,temp,alpha);
1139 f3.poly_scalar_mult_to(base);
1143 mpz_pow_ui(base2,f2.coef[f2.deg],alpha);
1144 r3.poly_scalar_mult_to(base2);
1147 mpz_pow_ui(base,temp,delta);
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);
1180 mpz_pow_ui(base,psi,delta);
1181 mpz_pow_ui(base2,f1.coef[f1.deg],delta);
1184 mpz_mul(base2,base2,psi);
1185 mpz_divexact(psi,base2,base);
1189 mpz_pow_ui(base,temp,alpha);
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)