9 dpoly::dpoly(int d
, ZZ
& degree
, int offset
)
14 if (degree
>= 0 && degree
< ZZ(INIT_VAL
, min
))
17 ZZ c
= ZZ(INIT_VAL
, 1);
20 for (int i
= 1; i
<= min
; ++i
) {
27 void dpoly::operator *= (dpoly
& f
)
29 assert(coeff
.length() == f
.coeff
.length());
31 coeff
= f
.coeff
[0] * coeff
;
32 for (int i
= 1; i
< coeff
.length(); ++i
)
33 for (int j
= 0; i
+j
< coeff
.length(); ++j
)
34 coeff
[i
+j
] += f
.coeff
[i
] * old
[j
];
37 void dpoly::div(dpoly
& d
, mpq_t count
, ZZ
& sign
)
39 int len
= coeff
.length();
42 mpq_t
* c
= new mpq_t
[coeff
.length()];
45 for (int i
= 0; i
< len
; ++i
) {
47 zz2value(coeff
[i
], tmp
);
50 for (int j
= 1; j
<= i
; ++j
) {
51 zz2value(d
.coeff
[j
], tmp
);
53 mpq_mul(qtmp
, qtmp
, c
[i
-j
]);
54 mpq_sub(c
[i
], c
[i
], qtmp
);
57 zz2value(d
.coeff
[0], tmp
);
59 mpq_div(c
[i
], c
[i
], qtmp
);
62 mpq_sub(count
, count
, c
[len
-1]);
64 mpq_add(count
, count
, c
[len
-1]);
68 for (int i
= 0; i
< len
; ++i
)
73 void dpoly_r::add_term(int i
, int * powers
, ZZ
& coeff
)
77 for (int k
= 0; k
< c
[i
].size(); ++k
) {
78 if (memcmp(c
[i
][k
]->powers
, powers
, dim
* sizeof(int)) == 0) {
79 c
[i
][k
]->coeff
+= coeff
;
83 dpoly_r_term
*t
= new dpoly_r_term
;
84 t
->powers
= new int[dim
];
85 memcpy(t
->powers
, powers
, dim
* sizeof(int));
90 dpoly_r::dpoly_r(int len
, int dim
)
95 c
= new vector
< dpoly_r_term
* > [len
];
98 dpoly_r::dpoly_r(dpoly
& num
, int dim
)
101 len
= num
.coeff
.length();
102 c
= new vector
< dpoly_r_term
* > [len
];
105 memset(powers
, 0, dim
* sizeof(int));
107 for (int i
= 0; i
< len
; ++i
) {
108 ZZ coeff
= num
.coeff
[i
];
109 add_term(i
, powers
, coeff
);
113 dpoly_r::dpoly_r(dpoly
& num
, dpoly
& den
, int pos
, int dim
)
116 len
= num
.coeff
.length();
117 c
= new vector
< dpoly_r_term
* > [len
];
121 for (int i
= 0; i
< len
; ++i
) {
122 ZZ coeff
= num
.coeff
[i
];
123 memset(powers
, 0, dim
* sizeof(int));
126 add_term(i
, powers
, coeff
);
128 for (int j
= 1; j
<= i
; ++j
) {
129 for (int k
= 0; k
< c
[i
-j
].size(); ++k
) {
130 memcpy(powers
, c
[i
-j
][k
]->powers
, dim
*sizeof(int));
132 coeff
= -den
.coeff
[j
-1] * c
[i
-j
][k
]->coeff
;
133 add_term(i
, powers
, coeff
);
140 dpoly_r::dpoly_r(dpoly_r
* num
, dpoly
& den
, int pos
, int dim
)
144 c
= new vector
< dpoly_r_term
* > [len
];
149 for (int i
= 0 ; i
< len
; ++i
) {
150 for (int k
= 0; k
< num
->c
[i
].size(); ++k
) {
151 memcpy(powers
, num
->c
[i
][k
]->powers
, dim
*sizeof(int));
153 add_term(i
, powers
, num
->c
[i
][k
]->coeff
);
156 for (int j
= 1; j
<= i
; ++j
) {
157 for (int k
= 0; k
< c
[i
-j
].size(); ++k
) {
158 memcpy(powers
, c
[i
-j
][k
]->powers
, dim
*sizeof(int));
160 coeff
= -den
.coeff
[j
-1] * c
[i
-j
][k
]->coeff
;
161 add_term(i
, powers
, coeff
);
169 for (int i
= 0 ; i
< len
; ++i
)
170 for (int k
= 0; k
< c
[i
].size(); ++k
) {
171 delete [] c
[i
][k
]->powers
;
177 dpoly_r
*dpoly_r::div(dpoly
& d
)
179 dpoly_r
*rc
= new dpoly_r(len
, dim
);
180 rc
->denom
= power(d
.coeff
[0], len
);
181 ZZ inv_d
= rc
->denom
/ d
.coeff
[0];
184 for (int i
= 0; i
< len
; ++i
) {
185 for (int k
= 0; k
< c
[i
].size(); ++k
) {
186 coeff
= c
[i
][k
]->coeff
* inv_d
;
187 rc
->add_term(i
, c
[i
][k
]->powers
, coeff
);
190 for (int j
= 1; j
<= i
; ++j
) {
191 for (int k
= 0; k
< rc
->c
[i
-j
].size(); ++k
) {
192 coeff
= - d
.coeff
[j
] * rc
->c
[i
-j
][k
]->coeff
/ d
.coeff
[0];
193 rc
->add_term(i
, rc
->c
[i
-j
][k
]->powers
, coeff
);
200 void dpoly_r::dump(void)
202 for (int i
= 0; i
< len
; ++i
) {
205 cerr
<< c
[i
].size() << endl
;
206 for (int j
= 0; j
< c
[i
].size(); ++j
) {
207 for (int k
= 0; k
< dim
; ++k
) {
208 cerr
<< c
[i
][j
]->powers
[k
] << " ";
210 cerr
<< ": " << c
[i
][j
]->coeff
<< "/" << denom
<< endl
;