15 mpz_init_set_ui(denom,1);
16 mpz_init_set_ui(coef[0],0);
21 Q_poly::Q_poly(
int n,mpz_t d, mpz_t *a)
25 mpz_init_set(denom,d);
27 for (
int i=0;
i<=n;
i++)
29 mpz_init_set(coef[
i], a[
i]);
44 void Q_poly::Q_poly_reduce()
48 mpz_init_set_ui(denom,1);
53 mpz_init_set(d,denom);
55 while (mpz_cmp_ui(d,1)!=0 &&
i<=deg)
60 if (mpz_sgn(denom)==-1)
64 if (mpz_cmp_ui(d,1)!=0)
66 mpz_div(denom,denom,d);
67 for (
int j=0;
j<=deg;
j++)
69 mpz_div(coef[
j],coef[
j],d);
76 while(mpz_sgn(coef[
j])==0 &&
j>=0)
81 void Q_poly::Q_poly_extend(mpz_t
b)
83 mpz_mul(denom,denom,
b);
84 for (
int i=0;
i<=deg;
i++)
86 mpz_mul(coef[
i],coef[
i],
b);
97 void Q_poly::Q_poly_add(
const Q_poly a,
const Q_poly
b)
103 mpz_init_set_ui(atemp,0);
104 mpz_init_set_ui(btemp,0);
106 for (
int i=0;
i<=
b.deg;
i++)
108 mpz_mul(atemp,a.coef[
i],
b.denom);
109 mpz_mul(btemp,
b.coef[
i],a.denom);
110 mpz_add(coef[
i],atemp,btemp);
113 for (
int i=
b.deg+1;
i<=a.deg;
i++)
115 mpz_mul(coef[
i],a.coef[
i],
b.denom);
117 mpz_mul(denom,a.denom,
b.denom);
121 while(mpz_sgn(coef[
i])==0 &&
i>=0)
125 else {Q_poly_add(
b,a);}
131 void Q_poly::Q_poly_add_to(
const Q_poly
g)
133 this->Q_poly_add(*
this,
g);
137 void Q_poly::Q_poly_add_const(Q_poly
f,
const mpz_t a)
141 Q_poly_set(a,
f.denom);
147 mpz_mul(atemp,a,
f.denom);
148 mpz_add(coef[0],coef[0],atemp);
150 if (deg==0 && mpz_sgn(coef[0])==0)
158 void Q_poly::Q_poly_add_const_to(
const mpz_t a)
160 this->Q_poly_add_const(*
this,a);
164 void Q_poly::Q_poly_add_mon(
const Q_poly
f, mpz_t a,
int i)
167 if (
i<=deg && is_zero()==0)
170 mpz_init_set_ui(atemp,0);
171 mpz_mul(atemp,a,
f.denom);
172 mpz_add(coef[
i],coef[
i],atemp);
176 if (deg==
i && mpz_sgn(coef[
i])==0)
179 else if (is_zero()==1)
184 mpz_init_set_ui(coef[
j],0);
186 mpz_init_set(coef[
i],a);
187 mpz_init_set_ui(denom,1);
192 for(
int j=
i-1;
j>deg;
j--)
194 mpz_init_set_ui(coef[
j],0);
197 mpz_mul(atemp,a,
f.denom);
198 mpz_init_set(coef[
i],atemp);
203 void Q_poly::Q_poly_add_mon_to(mpz_t a,
int i)
205 this->Q_poly_add_mon(*
this,a,
i);
210 void Q_poly::Q_poly_sub(
const Q_poly a,
const Q_poly
b)
221 void Q_poly::Q_poly_sub_to(
const Q_poly
b)
223 this->Q_poly_sub(*
this,
b);
227 void Q_poly::Q_poly_sub_const(Q_poly
f,
const mpz_t a)
238 mpz_init_set_ui(atemp,1);
239 mpz_mul(atemp,a,
f.denom);
240 mpz_sub(coef[0],coef[0],atemp);
247 void Q_poly::Q_poly_sub_const_to(
const mpz_t a)
249 this->Q_poly_sub_const(*
this,a);
254 void Q_poly::Q_poly_sub_mon(
const Q_poly
f , mpz_t a,
int i)
257 mpz_init_set_ui(temp,0);
259 Q_poly_add_mon(
f,temp,
i);
263 void Q_poly::Q_poly_sub_mon_to(mpz_t a,
int i)
265 this->Q_poly_sub_mon(*
this,a,
i);
272 void Q_poly::Q_poly_mon_mult(
const Q_poly
f,
int n)
275 mpz_init_set(denom,
f.denom);
276 for (
int i=deg;
i>=n;
i--)
278 mpz_init_set(coef[
i],
f.coef[
i-n]);
280 for (
int i=n-1;
i>=0;
i--)
282 mpz_init_set_ui(coef[
i],0);
286 void Q_poly::Q_poly_mon_mult_to(
const int n)
288 this->Q_poly_mon_mult(*
this,n);
294 void Q_poly::Q_poly_scalar_mult(
const Q_poly
g,
const mpz_t n)
297 mpz_init_set(denom,
g.denom);
300 mpz_init_set_ui(temp,0);
301 for(
int i=0;
i<=deg;
i++)
303 mpz_mul(temp,n,
g.coef[
i]);
304 mpz_init_set(coef[
i],temp);
310 void Q_poly::Q_poly_scalar_mult(
const mpz_t n,
const Q_poly
g)
313 mpz_init_set(denom,
g.denom);
316 mpz_init_set_ui(temp,0);
317 for(
int i=0;
i<=deg;
i++)
319 mpz_mul(temp,n,
g.coef[
i]);
320 mpz_init_set(coef[
i],temp);
325 void Q_poly::Q_poly_scalar_mult_to(
const mpz_t n)
327 this->Q_poly_scalar_mult(*
this,n);
334 void Q_poly::Q_poly_neg()
336 mpz_neg(denom,denom);
340 void Q_poly::Q_poly_mult_n(Q_poly a,Q_poly
b)
343 if (a.is_zero()==1 ||
b.is_zero()==1)
348 mpz_init_set_ui(temp,0);
355 for(
int i=a.deg+1;
i<=deg;
i++)
357 mpz_init_set_ui(atemp.coef[
i],0);
359 for(
int i=
b.deg+1;
i<=deg;
i++)
361 mpz_init_set_ui(btemp.coef[
i],0);
367 for (
int k=0;
k<=deg;
k++)
369 mpz_init_set_ui(coef[
k],0);
370 for (
int i=0;
i<=
k;
i++)
372 mpz_mul(temp,atemp.coef[
i],btemp.coef[
k-
i]);
373 mpz_add(coef[
k],coef[
k],temp);
376 mpz_mul(denom,a.denom,
b.denom);
382 void Q_poly::Q_poly_mult_n_to(
const Q_poly
g)
384 this->Q_poly_mult_n(*
this,
g);
388 void Q_poly::Q_poly_mult_ka(
const Q_poly
A,
const Q_poly
B)
392 if(
A.deg>=
B.deg){n=
A.deg+1;}
396 n = static_cast<int>(
pow(2,n));
401 mpz_mul(AB,
A.coef[0],
B.coef[0]);
402 Q_poly_set(AB,
A.denom);
407 Q_poly Au, Al, Bu, Bl;
408 Au.Q_poly_mon_div(
A,n/2);
409 Al.Q_poly_mon_div_rem(
A,n/2);
410 Bu.Q_poly_mon_div(
B,n/2);
411 Bl.Q_poly_mon_div_rem(
B,n/2);
413 Alu.Q_poly_add(Al,Au);
414 Blu.Q_poly_add(Bl,Bu);
418 D0.Q_poly_mult_ka(Al,Bl);
419 D1.Q_poly_mult_ka(Au,Bu);
420 D01.Q_poly_mult_ka(Alu,Blu);
424 D01.Q_poly_sub_to(D0);
425 D01.Q_poly_sub_to(D1);
426 D01.Q_poly_mon_mult_to(n/2);
427 D1.Q_poly_mon_mult_to(n);
428 D1.Q_poly_add_to(D01);
429 D1.Q_poly_add_to(D0);
438 void Q_poly::Q_poly_scalar_div(
const Q_poly
g,
const mpz_t n)
443 mpz_mul(denom,
g.denom,n);
448 void Q_poly::Q_poly_scalar_div_to(
const mpz_t n)
450 this->Q_poly_scalar_div(*
this,n);
454 void Q_poly::Q_poly_mon_div(
const Q_poly
f,
const int n)
463 mpz_init_set(denom,
f.denom);
465 for (
int i=0;
i<=
f.deg-n;
i++)
467 mpz_init_set(coef[
i],
f.coef[n+
i]);
473 void Q_poly::Q_poly_mon_div_rem(
const Q_poly
f,
const int n)
484 while(mpz_sgn(
f.coef[
j])==0 &&
j>=0)
488 mpz_init_set_ui(coef[
j],0);
490 for (
int i=
j;
i>=0;
i--)
492 mpz_init_set(coef[
i],
f.coef[
i]);
494 mpz_init_set(denom,
f.denom);
503 void Q_poly::Q_poly_div_rem(
const Q_poly
A,
const Q_poly
B)
509 mpz_init_set_ui(denom,1);
511 mpz_init_set_ui(Bint.denom,1);
512 int e =
A.deg -
B.deg + 1;
517 temp.Q_poly_mon_mult(Bint,deg-
B.deg);
518 temp.Q_poly_scalar_mult_to(coef[deg]);
520 Q_poly_scalar_mult_to(
B.coef[
B.deg]);
528 mpz_init_set(d,
B.coef[
B.deg]);
532 Q_poly_scalar_mult_to(q);
537 Q_poly_scalar_div_to(q);
540 mpz_pow_ui(d,d,
A.deg-
B.deg+1);
541 mpz_mul(denom,denom,d);
544 mpz_mul(denom,denom,
A.denom);
545 Q_poly_scalar_mult_to(
B.denom);
551 void Q_poly::Q_poly_div_rem_to(
const Q_poly
B)
553 this->Q_poly_div_rem(*
this,
B);
558 void Q_poly::Q_poly_div(Q_poly &
Q, Q_poly &
R,
const Q_poly
A,
const Q_poly
B)
564 mpz_init_set_ui(
R.denom,1);
567 mpz_init_set_ui(Bint.denom,1);
568 int e =
A.deg -
B.deg + 1;
573 temp.Q_poly_mon_mult(Bint,
R.deg-
B.deg);
574 temp.Q_poly_scalar_mult_to(
R.coef[
R.deg]);
576 Q.Q_poly_scalar_mult_to(
B.coef[
B.deg]);
577 Q.Q_poly_add_mon_to(
R.coef[
R.deg],
R.deg-
B.deg);
579 R.Q_poly_scalar_mult_to(
B.coef[
B.deg]);
580 R.Q_poly_sub_to(temp);
587 mpz_init_set(d,
B.coef[
B.deg]);
591 R.Q_poly_scalar_mult_to(q);
592 Q.Q_poly_scalar_mult_to(q);
597 R.Q_poly_scalar_div_to(q);
598 Q.Q_poly_scalar_div_to(q);
601 mpz_pow_ui(d,d,
A.deg-
B.deg+1);
602 mpz_mul(
R.denom,
R.denom,d);
603 mpz_mul(
Q.denom,
Q.denom,d);
606 mpz_mul(
R.denom,
R.denom,
A.denom);
607 mpz_mul(
Q.denom,
Q.denom,
A.denom);
608 R.Q_poly_scalar_mult_to(
B.denom);
609 Q.Q_poly_scalar_mult_to(
B.denom);
615 void Q_poly::Q_poly_div_to(Q_poly &
Q,Q_poly &
R,
const Q_poly
B)
617 this->Q_poly_div(
Q,
R,*
this,
B);
624 void Q_poly::Q_poly_multadd_to(
const Q_poly
b,
const Q_poly c)
631 void Q_poly::Q_poly_multsub_to(
const Q_poly
b,
const Q_poly c)
653 void Q_poly::Q_poly_horner(mpz_t erg,
const mpz_t u)
655 mpz_init_set(erg,coef[deg]);
656 for (
int i=deg;
i>=1;
i--)
659 mpz_add(erg,erg,coef[
i-1]);
668 void Q_poly::Q_poly_horner_Q_poly(
const Q_poly
A,
const Q_poly
B)
670 Q_poly_set(
A.coef[
A.deg],
A.denom);
671 for (
int i=
A.deg;
i>=1;
i--)
674 Q_poly_add_const_to(
A.coef[
i-1]);
687 void Q_poly::Q_poly_set(
const Q_poly
b)
690 mpz_init_set(denom,
b.denom);
692 for(
int i=0;
i<=deg;
i++)
694 mpz_init_set(coef[
i],
b.coef[
i]);
700 void Q_poly::Q_poly_set(
const mpz_t
b,
const mpz_t d)
703 mpz_init_set(denom,d);
704 mpz_init_set(coef[0],
b);
708 void Q_poly::Q_poly_set(
const mpz_t
b)
711 mpz_init_set_ui(denom,1);
712 mpz_init_set(coef[0],
b);
717 void Q_poly::Q_poly_set_zero()
725 int Q_poly::is_equal(Q_poly &
g)
735 for (
int i=deg;
i>=0;
i--)
737 if (mpz_cmp(coef[
i],
g.coef[
i])!=0)
745 int Q_poly::is_zero()
const
756 int Q_poly::is_one()
const
760 if (mpz_cmp(coef[0],denom)==0) {
return 1; }
766 int Q_poly::is_monic()
const
768 if (mpz_cmp(coef[deg],denom)==0)
776 void Q_poly::Q_poly_gcd(Q_poly
A, Q_poly
B)
781 else if (
B.is_zero()==1)
790 mpz_init_set_ui(App.denom,1);
791 mpz_init_set_ui(Bpp.denom,1);
793 while (Bpp.is_zero()==0)
795 R.Q_poly_div_rem(App,Bpp);
799 mpz_init_set(App.denom,App.coef[App.deg]);
807 void Q_poly::Q_poly_extgcd(Q_poly &
s,Q_poly &t,Q_poly &
g, Q_poly
A, Q_poly
B)
810 Q_poly_extgcd(t,
s,
g,
B,
A);
811 else if (
B.is_zero()==1)
817 mpz_init_set_ui(temp,1);
818 s.Q_poly_set(temp,
A.denom);
824 mpz_init_set_ui(temp,1);
833 S1.Q_poly_set(temp,
A.denom);
835 S2.Q_poly_set_zero();
839 T1.Q_poly_set_zero();
841 T2.Q_poly_set(temp,
A.denom);
846 while (R2.is_zero()!=1)
848 Q_poly_div(
Q,R3,R1,R2);
850 S3.Q_poly_mult_n(
Q,S2);
852 S3.Q_poly_add_to(S1);
854 T3.Q_poly_mult_n(
Q,
T2);
856 T3.Q_poly_add_to(
T1);
878 void Q_poly::Q_poly_insert()
881 cout <<
"Bitte geben Sie ein Q_polynom ein! Zunächst den Grad: " << endl;
883 mpz_init_set_ui(denom,1);
884 cout <<
"Jetzt den Hauptnenner: " << endl;
885 mpz_inp_str(denom,stdin, 10);
887 for (
int i=0;
i<=deg;
i++)
889 mpz_init_set_ui(coef[
i],0);
890 printf(
"Geben Sie nun f[%i] ein:",
i);
891 mpz_inp_str(coef[
i],stdin, 10);
898 void Q_poly::Q_poly_print()
902 cout <<
"0" <<
"\n" <<endl;
906 for (
int i=deg;
i>=1;
i--)
908 mpz_out_str(stdout,10,coef[
i]);
911 mpz_out_str(stdout,10,coef[0]);
913 mpz_out_str(stdout,10,denom);