]> www.ginac.de Git - cln.git/blob - src/modinteger/cl_MI_rshift.cc
2004-01-01 Richard B. Kreckel <kreckel@ginac.de>
[cln.git] / src / modinteger / cl_MI_rshift.cc
1 // operator>> on cl_MI.
2
3 // General includes.
4 #include "cl_sysdep.h"
5
6 // Specification.
7 #include "cln/modinteger.h"
8
9
10 // Implementation.
11
12 #include "cln/integer.h"
13 #include "cl_N.h"
14 #include "cl_MI.h"
15
16 namespace cln {
17
18 const cl_MI operator>> (const cl_MI& x, sintL y) // assume 0 <= y < 2^31
19 {
20         if (y == 0)
21                 return x;
22         var const cl_modint_ring& R = x.ring();
23         if (!oddp(R->modulus)) {
24                 if (R->modulus == 2)
25                         cl_error_division_by_0();
26                 else
27                         return (cl_MI_x)cl_notify_composite(R,2);
28         }
29         if (y == 1) // frequent case
30                 return cl_MI(R, (evenp(x.rep) ? x.rep : x.rep + R->modulus) >> 1);
31         // Method:
32         // Algorithm 1: add a multiple of m to x.rep so that it becomes
33         //              divisible by 2^y (2-adic division), then shift right.
34         //              asymptotical cost: O(y * log m).
35         // Algorithm 2: x * expt(2 mod m,-y) using modular integer operations.
36         //              asymptotical cost: O(log y * (log m)^2).
37         // Use algorithm 1 for small y, algorithm 2 for large y.
38 #if 0
39         if (y <= 2*R->bits)
40                 cl_abort(); // not yet implemented
41         else
42 #endif
43                 return R->div(x, expt_pos(R->canonhom(2), (cl_I)(long)y));
44 }
45
46 }  // namespace cln