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);
const CanonicalForm int s
gmp_float log(const gmp_float &a)
const signed long ceil(const ampf< Precision > &x)
Rational pow(const Rational &a, int e)