16 mpz_init_set_ui(denom,1);
17 mpz_init_set_ui(coef[0],0);
22 Q_poly::Q_poly(
int n,mpz_t d, mpz_t *a)
26 mpz_init_set(denom,d);
28 for (
int i=0;
i<=n;
i++)
30 mpz_init_set(coef[
i], a[
i]);
45 void Q_poly::Q_poly_reduce()
49 mpz_init_set_ui(denom,1);
54 mpz_init_set(d,denom);
56 while (mpz_cmp_ui(d,1)!=0 &&
i<=deg)
61 if (mpz_sgn(denom)==-1)
65 if (mpz_cmp_ui(d,1)!=0)
67 mpz_div(denom,denom,d);
68 for (
int j=0;
j<=deg;
j++)
70 mpz_div(coef[
j],coef[
j],d);
77 while(mpz_sgn(coef[
j])==0 &&
j>=0)
82 void Q_poly::Q_poly_extend(mpz_t
b)
84 mpz_mul(denom,denom,
b);
85 for (
int i=0;
i<=deg;
i++)
87 mpz_mul(coef[
i],coef[
i],
b);
98 void Q_poly::Q_poly_add(
const Q_poly a,
const Q_poly
b)
104 mpz_init_set_ui(atemp,0);
105 mpz_init_set_ui(btemp,0);
107 for (
int i=0;
i<=
b.deg;
i++)
109 mpz_mul(atemp,a.coef[
i],
b.denom);
110 mpz_mul(btemp,
b.coef[
i],a.denom);
111 mpz_add(coef[
i],atemp,btemp);
114 for (
int i=
b.deg+1;
i<=a.deg;
i++)
116 mpz_mul(coef[
i],a.coef[
i],
b.denom);
118 mpz_mul(denom,a.denom,
b.denom);
122 while(mpz_sgn(coef[
i])==0 &&
i>=0)
126 else {Q_poly_add(
b,a);}
132 void Q_poly::Q_poly_add_to(
const Q_poly
g)
134 this->Q_poly_add(*
this,
g);
138 void Q_poly::Q_poly_add_const(Q_poly
f,
const mpz_t a)
142 Q_poly_set(a,
f.denom);
148 mpz_mul(atemp,a,
f.denom);
149 mpz_add(coef[0],coef[0],atemp);
151 if (deg==0 && mpz_sgn(coef[0])==0)
159 void Q_poly::Q_poly_add_const_to(
const mpz_t a)
161 this->Q_poly_add_const(*
this,a);
165 void Q_poly::Q_poly_add_mon(
const Q_poly
f, mpz_t a,
int i)
168 if (
i<=deg && is_zero()==0)
171 mpz_init_set_ui(atemp,0);
172 mpz_mul(atemp,a,
f.denom);
173 mpz_add(coef[
i],coef[
i],atemp);
177 if (deg==
i && mpz_sgn(coef[
i])==0)
180 else if (is_zero()==1)
185 mpz_init_set_ui(coef[
j],0);
187 mpz_init_set(coef[
i],a);
188 mpz_init_set_ui(denom,1);
193 for(
int j=
i-1;
j>deg;
j--)
195 mpz_init_set_ui(coef[
j],0);
198 mpz_mul(atemp,a,
f.denom);
199 mpz_init_set(coef[
i],atemp);
204 void Q_poly::Q_poly_add_mon_to(mpz_t a,
int i)
206 this->Q_poly_add_mon(*
this,a,
i);
211 void Q_poly::Q_poly_sub(
const Q_poly a,
const Q_poly
b)
222 void Q_poly::Q_poly_sub_to(
const Q_poly
b)
224 this->Q_poly_sub(*
this,
b);
228 void Q_poly::Q_poly_sub_const(Q_poly
f,
const mpz_t a)
239 mpz_init_set_ui(atemp,1);
240 mpz_mul(atemp,a,
f.denom);
241 mpz_sub(coef[0],coef[0],atemp);
248 void Q_poly::Q_poly_sub_const_to(
const mpz_t a)
250 this->Q_poly_sub_const(*
this,a);
255 void Q_poly::Q_poly_sub_mon(
const Q_poly
f , mpz_t a,
int i)
258 mpz_init_set_ui(temp,0);
260 Q_poly_add_mon(
f,temp,
i);
264 void Q_poly::Q_poly_sub_mon_to(mpz_t a,
int i)
266 this->Q_poly_sub_mon(*
this,a,
i);
273 void Q_poly::Q_poly_mon_mult(
const Q_poly
f,
int n)
276 mpz_init_set(denom,
f.denom);
277 for (
int i=deg;
i>=n;
i--)
279 mpz_init_set(coef[
i],
f.coef[
i-n]);
281 for (
int i=n-1;
i>=0;
i--)
283 mpz_init_set_ui(coef[
i],0);
287 void Q_poly::Q_poly_mon_mult_to(
const int n)
289 this->Q_poly_mon_mult(*
this,n);
295 void Q_poly::Q_poly_scalar_mult(
const Q_poly
g,
const mpz_t n)
298 mpz_init_set(denom,
g.denom);
301 mpz_init_set_ui(temp,0);
302 for(
int i=0;
i<=deg;
i++)
304 mpz_mul(temp,n,
g.coef[
i]);
305 mpz_init_set(coef[
i],temp);
311 void Q_poly::Q_poly_scalar_mult(
const mpz_t n,
const Q_poly
g)
314 mpz_init_set(denom,
g.denom);
317 mpz_init_set_ui(temp,0);
318 for(
int i=0;
i<=deg;
i++)
320 mpz_mul(temp,n,
g.coef[
i]);
321 mpz_init_set(coef[
i],temp);
326 void Q_poly::Q_poly_scalar_mult_to(
const mpz_t n)
328 this->Q_poly_scalar_mult(*
this,n);
335 void Q_poly::Q_poly_neg()
337 mpz_neg(denom,denom);
341 void Q_poly::Q_poly_mult_n(Q_poly a,Q_poly
b)
344 if (a.is_zero()==1 ||
b.is_zero()==1)
349 mpz_init_set_ui(temp,0);
356 for(
int i=a.deg+1;
i<=deg;
i++)
358 mpz_init_set_ui(atemp.coef[
i],0);
360 for(
int i=
b.deg+1;
i<=deg;
i++)
362 mpz_init_set_ui(btemp.coef[
i],0);
368 for (
int k=0;
k<=deg;
k++)
370 mpz_init_set_ui(coef[
k],0);
371 for (
int i=0;
i<=
k;
i++)
373 mpz_mul(temp,atemp.coef[
i],btemp.coef[
k-
i]);
374 mpz_add(coef[
k],coef[
k],temp);
377 mpz_mul(denom,a.denom,
b.denom);
383 void Q_poly::Q_poly_mult_n_to(
const Q_poly
g)
385 this->Q_poly_mult_n(*
this,
g);
389 void Q_poly::Q_poly_mult_ka(
const Q_poly
A,
const Q_poly
B)
393 if(
A.deg>=
B.deg){n=
A.deg+1;}
397 n =
static_cast<int>(
pow(2,n));
402 mpz_mul(AB,
A.coef[0],
B.coef[0]);
403 Q_poly_set(AB,
A.denom);
408 Q_poly Au, Al, Bu, Bl;
409 Au.Q_poly_mon_div(
A,n/2);
410 Al.Q_poly_mon_div_rem(
A,n/2);
411 Bu.Q_poly_mon_div(
B,n/2);
412 Bl.Q_poly_mon_div_rem(
B,n/2);
414 Alu.Q_poly_add(Al,Au);
415 Blu.Q_poly_add(Bl,Bu);
419 D0.Q_poly_mult_ka(Al,Bl);
420 D1.Q_poly_mult_ka(Au,Bu);
421 D01.Q_poly_mult_ka(Alu,Blu);
425 D01.Q_poly_sub_to(D0);
426 D01.Q_poly_sub_to(D1);
427 D01.Q_poly_mon_mult_to(n/2);
428 D1.Q_poly_mon_mult_to(n);
429 D1.Q_poly_add_to(D01);
430 D1.Q_poly_add_to(D0);
439 void Q_poly::Q_poly_scalar_div(
const Q_poly
g,
const mpz_t n)
444 mpz_mul(denom,
g.denom,n);
449 void Q_poly::Q_poly_scalar_div_to(
const mpz_t n)
451 this->Q_poly_scalar_div(*
this,n);
455 void Q_poly::Q_poly_mon_div(
const Q_poly
f,
const int n)
464 mpz_init_set(denom,
f.denom);
466 for (
int i=0;
i<=
f.deg-n;
i++)
468 mpz_init_set(coef[
i],
f.coef[n+
i]);
474 void Q_poly::Q_poly_mon_div_rem(
const Q_poly
f,
const int n)
485 while(mpz_sgn(
f.coef[
j])==0 &&
j>=0)
489 mpz_init_set_ui(coef[
j],0);
491 for (
int i=
j;
i>=0;
i--)
493 mpz_init_set(coef[
i],
f.coef[
i]);
495 mpz_init_set(denom,
f.denom);
504 void Q_poly::Q_poly_div_rem(
const Q_poly
A,
const Q_poly
B)
510 mpz_init_set_ui(denom,1);
512 mpz_init_set_ui(Bint.denom,1);
513 int e =
A.deg -
B.deg + 1;
518 temp.Q_poly_mon_mult(Bint,deg-
B.deg);
519 temp.Q_poly_scalar_mult_to(coef[deg]);
521 Q_poly_scalar_mult_to(
B.coef[
B.deg]);
529 mpz_init_set(d,
B.coef[
B.deg]);
533 Q_poly_scalar_mult_to(q);
538 Q_poly_scalar_div_to(q);
541 mpz_pow_ui(d,d,
A.deg-
B.deg+1);
542 mpz_mul(denom,denom,d);
545 mpz_mul(denom,denom,
A.denom);
546 Q_poly_scalar_mult_to(
B.denom);
552 void Q_poly::Q_poly_div_rem_to(
const Q_poly
B)
554 this->Q_poly_div_rem(*
this,
B);
559 void Q_poly::Q_poly_div(Q_poly &
Q, Q_poly &
R,
const Q_poly
A,
const Q_poly
B)
565 mpz_init_set_ui(
R.denom,1);
568 mpz_init_set_ui(Bint.denom,1);
569 int e =
A.deg -
B.deg + 1;
574 temp.Q_poly_mon_mult(Bint,
R.deg-
B.deg);
575 temp.Q_poly_scalar_mult_to(
R.coef[
R.deg]);
577 Q.Q_poly_scalar_mult_to(
B.coef[
B.deg]);
578 Q.Q_poly_add_mon_to(
R.coef[
R.deg],
R.deg-
B.deg);
580 R.Q_poly_scalar_mult_to(
B.coef[
B.deg]);
581 R.Q_poly_sub_to(temp);
588 mpz_init_set(d,
B.coef[
B.deg]);
592 R.Q_poly_scalar_mult_to(q);
593 Q.Q_poly_scalar_mult_to(q);
598 R.Q_poly_scalar_div_to(q);
599 Q.Q_poly_scalar_div_to(q);
602 mpz_pow_ui(d,d,
A.deg-
B.deg+1);
603 mpz_mul(
R.denom,
R.denom,d);
604 mpz_mul(
Q.denom,
Q.denom,d);
607 mpz_mul(
R.denom,
R.denom,
A.denom);
608 mpz_mul(
Q.denom,
Q.denom,
A.denom);
609 R.Q_poly_scalar_mult_to(
B.denom);
610 Q.Q_poly_scalar_mult_to(
B.denom);
616 void Q_poly::Q_poly_div_to(Q_poly &
Q,Q_poly &
R,
const Q_poly
B)
618 this->Q_poly_div(
Q,
R,*
this,
B);
625 void Q_poly::Q_poly_multadd_to(
const Q_poly
b,
const Q_poly c)
632 void Q_poly::Q_poly_multsub_to(
const Q_poly
b,
const Q_poly c)
654 void Q_poly::Q_poly_horner(mpz_t erg,
const mpz_t u)
656 mpz_init_set(erg,coef[deg]);
657 for (
int i=deg;
i>=1;
i--)
660 mpz_add(erg,erg,coef[
i-1]);
669 void Q_poly::Q_poly_horner_Q_poly(
const Q_poly
A,
const Q_poly
B)
671 Q_poly_set(
A.coef[
A.deg],
A.denom);
672 for (
int i=
A.deg;
i>=1;
i--)
675 Q_poly_add_const_to(
A.coef[
i-1]);
688 void Q_poly::Q_poly_set(
const Q_poly
b)
691 mpz_init_set(denom,
b.denom);
693 for(
int i=0;
i<=deg;
i++)
695 mpz_init_set(coef[
i],
b.coef[
i]);
701 void Q_poly::Q_poly_set(
const mpz_t
b,
const mpz_t d)
704 mpz_init_set(denom,d);
705 mpz_init_set(coef[0],
b);
709 void Q_poly::Q_poly_set(
const mpz_t
b)
712 mpz_init_set_ui(denom,1);
713 mpz_init_set(coef[0],
b);
718 void Q_poly::Q_poly_set_zero()
726 int Q_poly::is_equal(Q_poly &
g)
736 for (
int i=deg;
i>=0;
i--)
738 if (mpz_cmp(coef[
i],
g.coef[
i])!=0)
746 int Q_poly::is_zero()
const
757 int Q_poly::is_one()
const
761 if (mpz_cmp(coef[0],denom)==0) {
return 1; }
767 int Q_poly::is_monic()
const
769 if (mpz_cmp(coef[deg],denom)==0)
777 void Q_poly::Q_poly_gcd(Q_poly
A, Q_poly
B)
782 else if (
B.is_zero()==1)
791 mpz_init_set_ui(App.denom,1);
792 mpz_init_set_ui(Bpp.denom,1);
794 while (Bpp.is_zero()==0)
796 R.Q_poly_div_rem(App,Bpp);
800 mpz_init_set(App.denom,App.coef[App.deg]);
808 void Q_poly::Q_poly_extgcd(Q_poly &
s,Q_poly &t,Q_poly &
g, Q_poly
A, Q_poly
B)
811 Q_poly_extgcd(t,
s,
g,
B,
A);
812 else if (
B.is_zero()==1)
818 mpz_init_set_ui(temp,1);
819 s.Q_poly_set(temp,
A.denom);
825 mpz_init_set_ui(temp,1);
834 S1.Q_poly_set(temp,
A.denom);
836 S2.Q_poly_set_zero();
840 T1.Q_poly_set_zero();
842 T2.Q_poly_set(temp,
A.denom);
847 while (R2.is_zero()!=1)
849 Q_poly_div(
Q,R3,R1,R2);
851 S3.Q_poly_mult_n(
Q,S2);
853 S3.Q_poly_add_to(S1);
855 T3.Q_poly_mult_n(
Q,
T2);
857 T3.Q_poly_add_to(
T1);
879 void Q_poly::Q_poly_insert()
882 cout <<
"Bitte geben Sie ein Q_polynom ein! Zunächst den Grad: " << endl;
884 mpz_init_set_ui(denom,1);
885 cout <<
"Jetzt den Hauptnenner: " << endl;
886 mpz_inp_str(denom,stdin, 10);
888 for (
int i=0;
i<=deg;
i++)
890 mpz_init_set_ui(coef[
i],0);
891 printf(
"Geben Sie nun f[%i] ein:",
i);
892 mpz_inp_str(coef[
i],stdin, 10);
899 void Q_poly::Q_poly_print()
903 cout <<
"0" <<
"\n" <<endl;
907 for (
int i=deg;
i>=1;
i--)
909 mpz_out_str(stdout,10,coef[
i]);
912 mpz_out_str(stdout,10,coef[0]);
914 mpz_out_str(stdout,10,denom);