17 mpz_init_set_ui(denom,1);
18 mpz_init_set_ui(coef[0],0);
23 Q_poly::Q_poly(
int n,mpz_t d, mpz_t *
a)
27 mpz_init_set(denom,d);
29 for (
int i=0;
i<=n;
i++)
31 mpz_init_set(coef[
i], a[i]);
46 void Q_poly::Q_poly_reduce()
50 mpz_init_set_ui(denom,1);
55 mpz_init_set(d,denom);
57 while (mpz_cmp_ui(d,1)!=0 && i<=deg)
62 if (mpz_sgn(denom)==-1)
66 if (mpz_cmp_ui(d,1)!=0)
68 mpz_div(denom,denom,d);
69 for (
int j=0;
j<=deg;
j++)
71 mpz_div(coef[
j],coef[j],d);
78 while(mpz_sgn(coef[j])==0 && j>=0)
83 void Q_poly::Q_poly_extend(mpz_t
b)
85 mpz_mul(denom,denom,b);
86 for (
int i=0;i<=deg;i++)
88 mpz_mul(coef[i],coef[i],b);
99 void Q_poly::Q_poly_add(
const Q_poly a,
const Q_poly b)
105 mpz_init_set_ui(atemp,0);
106 mpz_init_set_ui(btemp,0);
108 for (
int i=0;i<=b.deg;i++)
110 mpz_mul(atemp,a.coef[i],b.denom);
111 mpz_mul(btemp,b.coef[i],a.denom);
112 mpz_add(coef[i],atemp,btemp);
115 for (
int i=b.deg+1;i<=a.deg;i++)
117 mpz_mul(coef[i],a.coef[i],b.denom);
119 mpz_mul(denom,a.denom,b.denom);
123 while(mpz_sgn(coef[i])==0 && i>=0)
127 else {Q_poly_add(b,a);}
133 void Q_poly::Q_poly_add_to(
const Q_poly
g)
135 this->Q_poly_add(*
this,g);
139 void Q_poly::Q_poly_add_const(Q_poly
f,
const mpz_t a)
143 Q_poly_set(a,f.denom);
149 mpz_mul(atemp,a,f.denom);
150 mpz_add(coef[0],coef[0],atemp);
152 if (deg==0 && mpz_sgn(coef[0])==0)
160 void Q_poly::Q_poly_add_const_to(
const mpz_t a)
162 this->Q_poly_add_const(*
this,a);
166 void Q_poly::Q_poly_add_mon(
const Q_poly f, mpz_t a,
int i)
169 if (i<=deg && is_zero()==0)
172 mpz_init_set_ui(atemp,0);
173 mpz_mul(atemp,a,f.denom);
174 mpz_add(coef[i],coef[i],atemp);
178 if (deg==i && mpz_sgn(coef[i])==0)
181 else if (is_zero()==1)
186 mpz_init_set_ui(coef[j],0);
188 mpz_init_set(coef[i],a);
189 mpz_init_set_ui(denom,1);
194 for(
int j=i-1;j>deg;j--)
196 mpz_init_set_ui(coef[j],0);
199 mpz_mul(atemp,a,f.denom);
200 mpz_init_set(coef[i],atemp);
205 void Q_poly::Q_poly_add_mon_to(mpz_t a,
int i)
207 this->Q_poly_add_mon(*
this,a,i);
212 void Q_poly::Q_poly_sub(
const Q_poly a,
const Q_poly b)
223 void Q_poly::Q_poly_sub_to(
const Q_poly b)
225 this->Q_poly_sub(*
this,b);
229 void Q_poly::Q_poly_sub_const(Q_poly f,
const mpz_t a)
240 mpz_init_set_ui(atemp,1);
241 mpz_mul(atemp,a,f.denom);
242 mpz_sub(coef[0],coef[0],atemp);
249 void Q_poly::Q_poly_sub_const_to(
const mpz_t a)
251 this->Q_poly_sub_const(*
this,a);
256 void Q_poly::Q_poly_sub_mon(
const Q_poly f , mpz_t a,
int i)
259 mpz_init_set_ui(temp,0);
261 Q_poly_add_mon(f,temp,i);
265 void Q_poly::Q_poly_sub_mon_to(mpz_t a,
int i)
267 this->Q_poly_sub_mon(*
this,a,i);
274 void Q_poly::Q_poly_mon_mult(
const Q_poly f,
int n)
277 mpz_init_set(denom,f.denom);
278 for (
int i=deg;i>=n;i--)
280 mpz_init_set(coef[i],f.coef[i-n]);
282 for (
int i=n-1;i>=0;i--)
284 mpz_init_set_ui(coef[i],0);
288 void Q_poly::Q_poly_mon_mult_to(
const int n)
290 this->Q_poly_mon_mult(*
this,n);
296 void Q_poly::Q_poly_scalar_mult(
const Q_poly
g,
const mpz_t n)
299 mpz_init_set(denom,g.denom);
302 mpz_init_set_ui(temp,0);
303 for(
int i=0;i<=deg;i++)
305 mpz_mul(temp,n,g.coef[i]);
306 mpz_init_set(coef[i],temp);
312 void Q_poly::Q_poly_scalar_mult(
const mpz_t n,
const Q_poly g)
315 mpz_init_set(denom,g.denom);
318 mpz_init_set_ui(temp,0);
319 for(
int i=0;i<=deg;i++)
321 mpz_mul(temp,n,g.coef[i]);
322 mpz_init_set(coef[i],temp);
327 void Q_poly::Q_poly_scalar_mult_to(
const mpz_t n)
329 this->Q_poly_scalar_mult(*
this,n);
336 void Q_poly::Q_poly_neg()
338 mpz_neg(denom,denom);
342 void Q_poly::Q_poly_mult_n(Q_poly a,Q_poly b)
345 if (a.is_zero()==1 || b.is_zero()==1)
350 mpz_init_set_ui(temp,0);
357 for(
int i=a.deg+1;i<=deg;i++)
359 mpz_init_set_ui(atemp.coef[i],0);
361 for(
int i=b.deg+1;i<=deg;i++)
363 mpz_init_set_ui(btemp.coef[i],0);
369 for (
int k=0;
k<=deg;
k++)
371 mpz_init_set_ui(coef[
k],0);
372 for (
int i=0; i<=
k; i++)
374 mpz_mul(temp,atemp.coef[i],btemp.coef[
k-i]);
375 mpz_add(coef[
k],coef[k],temp);
378 mpz_mul(denom,a.denom,b.denom);
384 void Q_poly::Q_poly_mult_n_to(
const Q_poly g)
386 this->Q_poly_mult_n(*
this,g);
390 void Q_poly::Q_poly_mult_ka(
const Q_poly
A,
const Q_poly
B)
394 if(A.deg>=B.deg){n=A.deg+1;}
397 n =
static_cast<int>(ceil(
log(n)/
log(2)));
398 n =
static_cast<int>(
pow(2,n));
403 mpz_mul(AB,A.coef[0],B.coef[0]);
404 Q_poly_set(AB,A.denom);
409 Q_poly Au, Al, Bu, Bl;
410 Au.Q_poly_mon_div(A,n/2);
411 Al.Q_poly_mon_div_rem(A,n/2);
412 Bu.Q_poly_mon_div(B,n/2);
413 Bl.Q_poly_mon_div_rem(B,n/2);
415 Alu.Q_poly_add(Al,Au);
416 Blu.Q_poly_add(Bl,Bu);
420 D0.Q_poly_mult_ka(Al,Bl);
421 D1.Q_poly_mult_ka(Au,Bu);
422 D01.Q_poly_mult_ka(Alu,Blu);
426 D01.Q_poly_sub_to(D0);
427 D01.Q_poly_sub_to(D1);
428 D01.Q_poly_mon_mult_to(n/2);
429 D1.Q_poly_mon_mult_to(n);
430 D1.Q_poly_add_to(D01);
431 D1.Q_poly_add_to(D0);
440 void Q_poly::Q_poly_scalar_div(
const Q_poly g,
const mpz_t n)
445 mpz_mul(denom,g.denom,n);
450 void Q_poly::Q_poly_scalar_div_to(
const mpz_t n)
452 this->Q_poly_scalar_div(*
this,n);
456 void Q_poly::Q_poly_mon_div(
const Q_poly f,
const int n)
465 mpz_init_set(denom,f.denom);
467 for (
int i=0;i<=f.deg-n;i++)
469 mpz_init_set(coef[i],f.coef[n+i]);
475 void Q_poly::Q_poly_mon_div_rem(
const Q_poly f,
const int n)
486 while(mpz_sgn(f.coef[j])==0 && j>=0)
490 mpz_init_set_ui(coef[j],0);
492 for (
int i=j;i>=0;i--)
494 mpz_init_set(coef[i],f.coef[i]);
496 mpz_init_set(denom,f.denom);
505 void Q_poly::Q_poly_div_rem(
const Q_poly A,
const Q_poly B)
511 mpz_init_set_ui(denom,1);
513 mpz_init_set_ui(Bint.denom,1);
514 int e = A.deg - B.deg + 1;
519 temp.Q_poly_mon_mult(Bint,deg-B.deg);
520 temp.Q_poly_scalar_mult_to(coef[deg]);
522 Q_poly_scalar_mult_to(B.coef[B.deg]);
530 mpz_init_set(d,B.coef[B.deg]);
534 Q_poly_scalar_mult_to(q);
539 Q_poly_scalar_div_to(q);
542 mpz_pow_ui(d,d,A.deg-B.deg+1);
543 mpz_mul(denom,denom,d);
546 mpz_mul(denom,denom,A.denom);
547 Q_poly_scalar_mult_to(B.denom);
553 void Q_poly::Q_poly_div_rem_to(
const Q_poly B)
555 this->Q_poly_div_rem(*
this,B);
560 void Q_poly::Q_poly_div(Q_poly &
Q, Q_poly &
R,
const Q_poly A,
const Q_poly B)
566 mpz_init_set_ui(R.denom,1);
569 mpz_init_set_ui(Bint.denom,1);
570 int e = A.deg - B.deg + 1;
575 temp.Q_poly_mon_mult(Bint,R.deg-B.deg);
576 temp.Q_poly_scalar_mult_to(R.coef[R.deg]);
578 Q.Q_poly_scalar_mult_to(B.coef[B.deg]);
579 Q.Q_poly_add_mon_to(R.coef[R.deg],R.deg-B.deg);
581 R.Q_poly_scalar_mult_to(B.coef[B.deg]);
582 R.Q_poly_sub_to(temp);
589 mpz_init_set(d,B.coef[B.deg]);
593 R.Q_poly_scalar_mult_to(q);
594 Q.Q_poly_scalar_mult_to(q);
599 R.Q_poly_scalar_div_to(q);
600 Q.Q_poly_scalar_div_to(q);
603 mpz_pow_ui(d,d,A.deg-B.deg+1);
604 mpz_mul(R.denom,R.denom,d);
605 mpz_mul(Q.denom,Q.denom,d);
608 mpz_mul(R.denom,R.denom,A.denom);
609 mpz_mul(Q.denom,Q.denom,A.denom);
610 R.Q_poly_scalar_mult_to(B.denom);
611 Q.Q_poly_scalar_mult_to(B.denom);
617 void Q_poly::Q_poly_div_to(Q_poly &Q,Q_poly &R,
const Q_poly B)
619 this->Q_poly_div(Q,R,*
this,B);
626 void Q_poly::Q_poly_multadd_to(
const Q_poly b,
const Q_poly c)
633 void Q_poly::Q_poly_multsub_to(
const Q_poly b,
const Q_poly c)
655 void Q_poly::Q_poly_horner(mpz_t erg,
const mpz_t u)
657 mpz_init_set(erg,coef[deg]);
658 for (
int i=deg;i>=1;i--)
661 mpz_add(erg,erg,coef[i-1]);
670 void Q_poly::Q_poly_horner_Q_poly(
const Q_poly A,
const Q_poly B)
672 Q_poly_set(A.coef[A.deg],A.denom);
673 for (
int i=A.deg;i>=1;i--)
676 Q_poly_add_const_to(A.coef[i-1]);
689 void Q_poly::Q_poly_set(
const Q_poly b)
692 mpz_init_set(denom,b.denom);
694 for(
int i=0;i<=deg;i++)
696 mpz_init_set(coef[i],b.coef[i]);
702 void Q_poly::Q_poly_set(
const mpz_t b,
const mpz_t d)
705 mpz_init_set(denom,d);
706 mpz_init_set(coef[0],b);
710 void Q_poly::Q_poly_set(
const mpz_t b)
713 mpz_init_set_ui(denom,1);
714 mpz_init_set(coef[0],b);
719 void Q_poly::Q_poly_set_zero()
727 int Q_poly::is_equal(Q_poly &g)
737 for (
int i=deg;i>=0; i--)
739 if (mpz_cmp(coef[i],g.coef[i])!=0)
747 int Q_poly::is_zero()
const 758 int Q_poly::is_one()
const 762 if (mpz_cmp(coef[0],denom)==0) {
return 1; }
768 int Q_poly::is_monic()
const 770 if (mpz_cmp(coef[deg],denom)==0)
778 void Q_poly::Q_poly_gcd(Q_poly A, Q_poly B)
783 else if (B.is_zero()==1)
792 mpz_init_set_ui(App.denom,1);
793 mpz_init_set_ui(Bpp.denom,1);
795 while (Bpp.is_zero()==0)
797 R.Q_poly_div_rem(App,Bpp);
801 mpz_init_set(App.denom,App.coef[App.deg]);
809 void Q_poly::Q_poly_extgcd(Q_poly &
s,Q_poly &t,Q_poly &g, Q_poly A, Q_poly B)
812 Q_poly_extgcd(t,s,g,B,A);
813 else if (B.is_zero()==1)
819 mpz_init_set_ui(temp,1);
820 s.Q_poly_set(temp,A.denom);
826 mpz_init_set_ui(temp,1);
835 S1.Q_poly_set(temp,A.denom);
837 S2.Q_poly_set_zero();
841 T1.Q_poly_set_zero();
843 T2.Q_poly_set(temp,A.denom);
848 while (R2.is_zero()!=1)
850 Q_poly_div(Q,R3,R1,R2);
852 S3.Q_poly_mult_n(Q,S2);
854 S3.Q_poly_add_to(S1);
856 T3.Q_poly_mult_n(Q,T2);
858 T3.Q_poly_add_to(T1);
880 void Q_poly::Q_poly_insert()
883 cout <<
"Bitte geben Sie ein Q_polynom ein! Zunächst den Grad: " << endl;
885 mpz_init_set_ui(denom,1);
886 cout <<
"Jetzt den Hauptnenner: " << endl;
887 mpz_inp_str(denom,stdin, 10);
889 for (
int i=0; i<=deg;i++)
891 mpz_init_set_ui(coef[i],0);
892 printf(
"Geben Sie nun f[%i] ein:",i);
893 mpz_inp_str(coef[i],stdin, 10);
900 void Q_poly::Q_poly_print()
904 cout <<
"0" <<
"\n" <<endl;
908 for (
int i=deg;i>=1;i--)
910 mpz_out_str(stdout,10,coef[i]);
913 mpz_out_str(stdout,10,coef[0]);
915 mpz_out_str(stdout,10,denom);
const CanonicalForm int s
gmp_float log(const gmp_float &a)
Rational pow(const Rational &a, int e)