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)