source: git/factory/int_intdiv.cc @ fc732a9

spielwiese
Last change on this file since fc732a9 was fc732a9, checked in by Jens Schmidt <schmidt@…>, 26 years ago
***** merge from branch `factory-gcd' to main trunk git-svn-id: file:///usr/local/Singular/svn/trunk@1251 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 10.2 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id: int_intdiv.cc,v 1.2 1998-03-17 15:57:00 schmidt Exp $ */
3
4//{{{ docu
5//
6// int_intdiv.cc - `InternalInteger' division algorithms.
7//
8//}}}
9
10#include <config.h>
11
12#include "imm.h"
13#include "int_cf.h"
14#include "int_int.h"
15#include "int_rat.h"
16#include "cf_gmp.h"
17#include "gmpext.h"
18#include "ftmpl_functions.h"
19
20#include "stdio.h"
21
22//{{{ InternalCF * InternalInteger::dividesame, dividecoeff ( InternalCF * c )
23// docu: see CanonicalForm::operator /()
24InternalCF *
25InternalInteger::dividesame ( InternalCF * c )
26{
27    ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
28            "type error: InternalInteger expected" );
29
30    if ( c == this ) {
31        if ( deleteObject() ) delete this;
32        return int2imm( 1 );
33    }
34
35    if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
36        MP_INT n, d;
37        mpz_init_set( &n, &thempi );
38        mpz_init_set( &d, &MPI( c ) );
39        if ( deleteObject() ) delete this;
40        InternalRational * result = new InternalRational( n, d );
41        return result->normalize_myself();
42    }
43
44    if ( getRefCount() > 1 ) {
45        decRefCount();
46        MP_INT mpiResult;
47        mpz_init( &mpiResult );
48        if ( mpz_sgn( &MPI( c ) ) > 0 )
49            mpz_fdiv_q( &mpiResult, &thempi, &MPI( c ) );
50        else
51            mpz_cdiv_q( &mpiResult, &thempi, &MPI( c ) );
52        return normalizeMPI( mpiResult );
53    } else {
54        if ( mpz_sgn( &MPI( c ) ) > 0 )
55            mpz_fdiv_q( &thempi, &thempi, &MPI( c ) );
56        else
57            mpz_cdiv_q( &thempi, &thempi, &MPI( c ) );
58        return normalizeMyself();
59    }
60}
61
62InternalCF *
63InternalInteger::dividecoeff ( InternalCF * c, bool invert )
64{
65    ASSERT( ::is_imm( c ) == INTMARK,
66            "type error: immediate integer expected" );
67    ASSERT( invert || imm2int( c ) != 0,
68            "math error: divide by zero" );
69
70    int intC = imm2int( c );
71
72    if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
73        MP_INT n, d;
74        if ( invert ) {
75            mpz_init_set_si( &n, intC );
76            mpz_init_set( &d, &thempi );
77        }
78        else {
79            mpz_init_set_si( &d, intC );
80            mpz_init_set( &n, &thempi );
81        }
82        if ( deleteObject() ) delete this;
83        InternalRational * result = new InternalRational( n, d );
84        return result->normalize_myself();
85    }
86
87    if ( invert ) {
88        int mpiSign = mpz_sgn( &thempi );
89        if ( deleteObject() ) delete this;
90        if ( intC > 0 )
91            return int2imm( 0 );
92        else
93            return int2imm( -mpiSign );
94    } else if ( getRefCount() > 1 ) {
95        decRefCount();
96        MP_INT mpiResult;
97        mpz_init( &mpiResult );
98        if ( intC > 0 )
99            mpz_fdiv_q_ui( &mpiResult, &thempi, intC );
100        else {
101            mpz_fdiv_q_ui( &mpiResult, &thempi, -intC );
102            mpz_neg( &mpiResult, &mpiResult );
103        }
104        return normalizeMPI( mpiResult );
105    } else {
106        if ( intC > 0 )
107            mpz_fdiv_q_ui( &thempi, &thempi, intC );
108        else {
109            mpz_fdiv_q_ui( &thempi, &thempi, -intC );
110            mpz_neg( &thempi, &thempi );
111        }
112        return normalizeMyself();
113    }
114}
115//}}}
116
117//{{{ InternalCF * InternalInteger::divsame, divcoeff ( InternalCF * c )
118// docu: see CanonicalForm::div()
119InternalCF *
120InternalInteger::divsame ( InternalCF * c )
121{
122    ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
123            "type error: InternalInteger expected" );
124
125    if ( getRefCount() > 1 ) {
126        deleteObject();
127        MP_INT mpiResult;
128        mpz_init( &mpiResult );
129        mpz_divexact( &mpiResult, &thempi, &MPI( c ) );
130        return normalizeMPI( mpiResult );
131    } else {
132        mpz_divexact( &thempi, &thempi, &MPI( c ) );
133        return normalizeMyself();
134    }
135}
136
137InternalCF *
138InternalInteger::divcoeff ( InternalCF * c, bool invert )
139{
140    ASSERT( ::is_imm( c ) == INTMARK,
141            "type error: immediate integer expected" );
142    ASSERT( ! invert || imm2int( c ) == 0, "math error: c does not divide CO" );
143
144    if ( invert ) {
145        if ( deleteObject() ) delete this;
146        // this may happen iff `c' == 0
147        return int2imm( 0 );
148    } else if ( getRefCount() > 1 ) {
149        deleteObject();
150        MP_INT mpiC;
151        MP_INT mpiResult;
152        mpz_init_set_si( &mpiC, imm2int( c ) );
153        mpz_init( &mpiResult );
154        mpz_divexact( &mpiResult, &thempi, &mpiC );
155        mpz_clear( &mpiC );
156        return normalizeMPI( mpiResult );
157    } else {
158        MP_INT mpiC;
159        mpz_init_set_si( &mpiC, imm2int( c ) );
160        mpz_divexact( &thempi, &thempi, &mpiC );
161        mpz_clear( &mpiC );
162        return normalizeMyself();
163    }
164}
165//}}}
166
167// we have to divide the immediate integer `c' by CO.
168// If `c' is positive, this is quite simple: we
169// simply return `c'.  If `c' is negative we return
170// abs(CO)-abs(`c').
171// we have to divide CO by the immediate integer `c'.
172// The remainder will be less than the absolute value of
173// `c', hence it will fit again into an immediate.
174
175//{{{ InternalCF * InternalInteger::modulosame, modulocoeff ( InternalCF * c )
176// docu: see CanonicalForm::operator %()
177InternalCF *
178InternalInteger::modulosame ( InternalCF * c )
179{
180    ASSERT( ! ::is_imm( c ) && c->levelcoeff() == IntegerDomain,
181            "type error: InternalInteger expected" );
182
183    if ( cf_glob_switches.isOn( SW_RATIONAL ) || c == this ) {
184        if ( deleteObject() ) delete this;
185        return int2imm( 0 );
186    }
187
188    if ( getRefCount() > 1 ) {
189        decRefCount();
190        MP_INT mpiResult;
191        mpz_init( &mpiResult );
192        mpz_mod( &mpiResult, &thempi, &MPI( c ) );
193        return uiNormalizeMPI( mpiResult );
194    } else {
195        mpz_mod( &thempi, &thempi, &MPI( c ) );
196        return uiNormalizeMyself();
197    }
198}
199
200InternalCF *
201InternalInteger::modulocoeff ( InternalCF * c, bool invert )
202{
203    ASSERT( ::is_imm( c ) == INTMARK,
204            "type error: immediate integer expected" );
205    ASSERT( invert || imm2int( c ) != 0,
206            "math error: divide by zero" );
207
208    if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
209        if ( deleteObject() ) delete this;
210        return int2imm( 0 );
211    }
212
213    InternalCF * result;
214
215    int intC = imm2int( c );
216
217    if ( invert ) {
218        // calculate c % CO
219        if ( intC > 0 )
220            result = int2imm( intC );
221        else {
222            // no checks for refCount == 1 are done.  It is not worth ...
223            MP_INT mpiResult;
224            mpz_init_set( &mpiResult, &thempi );
225            mpz_abs( &mpiResult, &mpiResult );
226            mpz_sub_ui( &mpiResult, &mpiResult, -intC );
227            result = uiNormalizeMPI( mpiResult );
228        }
229    } else {
230        // calculate CO % c
231        MP_INT dummy;
232        mpz_init( &dummy );
233        result = int2imm( mpz_mod_ui( &dummy, &thempi, (intC > 0 ? intC : -intC) ) );
234        mpz_clear( &dummy );
235    }
236
237    // clean up
238    if ( deleteObject() ) delete this;
239    return result;
240}
241//}}}
242
243//{{{ InternalCF * InternalInteger::modsame, modcoeff ( InternalCF * c )
244// docu: see CanonicalForm::mod()
245InternalCF *
246InternalInteger::modsame ( InternalCF * c )
247{
248    return modulosame( c );
249}
250
251InternalCF *
252InternalInteger::modcoeff ( InternalCF * c, bool invert )
253{
254    return modulocoeff( c, invert );
255}
256//}}}
257
258//{{{ void InternalInteger::divremsame, divremcoeff ( InternalCF * c, InternalCF * & quot, InternalCF * & rem )
259// docu: see CanonicalForm::divrem()
260void
261InternalInteger::divremsame ( InternalCF * c, InternalCF * & quot, InternalCF * & rem )
262{
263    if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
264        quot = copyObject();
265        quot = quot->dividesame( c );
266        rem = int2imm( 0 );
267    }
268    else  if ( c == this ) {
269        quot = int2imm( 1 );
270        rem = int2imm( 0 );
271    }
272    else {
273        MP_INT q;
274        MP_INT r;
275        mpz_init( &q ); mpz_init( &r );
276        int signmpi = mpz_cmp_si( &thempi, 0 );
277        int signc = mpz_cmp_si( &MPI( c ), 0 );
278        if ( signmpi < 0 )
279            mpz_neg( &thempi, &thempi );
280        if ( signc < 0 )
281            mpz_neg( &MPI( c ), &MPI( c ) );
282        mpz_divmod( &q, &r, &thempi, &MPI( c ) );
283        if ( signmpi < 0 && mpz_cmp_si( &r, 0 ) != 0 ) {
284            mpz_sub( &r, &MPI( c ), &r );
285        }
286        if ( signmpi < 0 )
287            mpz_neg( &thempi, &thempi );
288        if ( signc < 0 )
289            mpz_neg( &MPI( c ), &MPI( c ) );
290        if ( signmpi < 0 && signc < 0 ) {
291            if ( mpz_cmp_si( &r, 0 ) != 0 )
292                mpz_add_ui( &q, &q, 1 );
293        }
294        else  if ( signc < 0 )
295            mpz_neg( &q, &q );
296        else  if ( signmpi < 0 ) {
297            mpz_neg( &q, &q );
298            if ( mpz_cmp_si( &r, 0 ) != 0 )
299                mpz_sub_ui( &q, &q, 1 );
300        }
301        if ( mpz_is_imm( &q ) )
302            quot = int2imm( mpz_get_si( &q ) );
303        else
304            quot = new InternalInteger( q );
305        if ( mpz_is_imm( &r ) )
306            rem = int2imm( mpz_get_si( &r ) );
307        else
308            rem = new InternalInteger( r );
309    }
310}
311
312void
313InternalInteger::divremcoeff ( InternalCF * c, InternalCF * & quot, InternalCF * & rem, bool invert )
314{
315    ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
316
317    if ( cf_glob_switches.isOn( SW_RATIONAL ) ) {
318        quot = copyObject();
319        quot = quot->dividecoeff( c, invert );
320        rem = int2imm( 0 );
321        return;
322    }
323    quot = copyObject();
324    quot = quot->divcoeff( c, invert );
325    rem = copyObject();
326    rem = rem->modcoeff( c, invert );
327    return;
328    int cc = imm2int( c );
329    MP_INT q, r;
330    int signmpi = mpz_cmp_si( &thempi, 0 );
331    int signc = cc;
332
333    mpz_init( &q ); mpz_init( &r );
334    if ( signmpi < 0 )
335        mpz_neg( &thempi, &thempi );
336    if ( signc < 0 )
337        cc = -cc;
338    if ( invert ) {
339        MP_INT ccc;
340        mpz_init_set_si( &ccc, cc );
341        mpz_divmod( &q, &r, &ccc, &thempi );
342        mpz_clear( &ccc );
343        if ( signc < 0 && signmpi < 0 ) {
344            if ( mpz_cmp_si( &r, 0 ) != 0 ) {
345                mpz_add_ui( &q, &q, 1 );
346                mpz_sub( &r, &thempi, &r );
347            }
348        }
349        else  if ( signc < 0 ) {
350            if ( mpz_cmp_si( &r, 0 ) != 0 ) {
351                mpz_add_ui( &q, &q, 1 );
352                mpz_neg( &q, &q );
353                mpz_sub( &r, &thempi, &r );
354            }
355        }
356        else  if ( signmpi < 0 )
357            mpz_neg( &q, &q );
358    }
359    else {
360        mpz_divmod_ui( &q, &r, &thempi, cc );
361        if ( signmpi < 0 && signc < 0 ) {
362            if ( mpz_cmp_si( &r, 0 ) != 0 ) {
363                mpz_add_ui( &q, &q, 1 );
364                mpz_neg( &r, &r );
365                mpz_add_ui( &r, &r, cc );
366            }
367        }
368        else  if ( signmpi < 0 ) {
369            if ( mpz_cmp_si( &r, 0 ) != 0 ) {
370                mpz_add_ui( &q, &q, 1 );
371                mpz_neg( &q, &q );
372                mpz_neg( &r, &r );
373                mpz_add_ui( &r, &r, cc );
374            }
375        }
376        else  if ( signc < 0 )
377            mpz_neg( &q, &q );
378    }
379    if ( signmpi < 0 )
380        mpz_neg( &thempi, &thempi );
381    if ( mpz_is_imm( &r ) ) {
382        rem = int2imm( mpz_get_si( &r ) );
383        mpz_clear( &r );
384    }
385    else
386        rem = new InternalInteger( r );
387    if ( mpz_is_imm( &q ) ) {
388        quot = int2imm( mpz_get_si( &q ) );
389        mpz_clear( &q );
390    }
391    else
392        quot = new InternalInteger( q );
393}
394//}}}
395
396//{{{ bool InternalInteger::divremsamet, divremcoefft ( InternalCF * c, InternalCF * & quot, InternalCF * & rem )
397// docu: see CanonicalForm::divremt()
398bool
399InternalInteger::divremsamet ( InternalCF * c, InternalCF * & quot, InternalCF * & rem )
400{
401    divremsame( c, quot, rem );
402    return true;
403}
404
405bool
406InternalInteger::divremcoefft ( InternalCF * c, InternalCF * & quot, InternalCF * & rem, bool invert )
407{
408    ASSERT( ::is_imm( c ) == INTMARK, "incompatible base coefficients" );
409    divremcoeff( c, quot, rem, invert );
410    return true;
411}
412//}}}
Note: See TracBrowser for help on using the repository browser.