pow-ops.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 namespace Gecode { namespace Int { namespace Arithmetic {
00035
00036 forceinline
00037 PowOps::PowOps(int n0) : n(n0) {}
00038
00039 forceinline bool
00040 PowOps::even(int m) {
00041 return (m & 1) == 0;
00042 }
00043
00044 forceinline bool
00045 PowOps::even(void) const {
00046 return even(n);
00047 }
00048
00049 forceinline int
00050 PowOps::exp(void) const {
00051 return n;
00052 }
00053
00054 forceinline void
00055 PowOps::exp(int m) {
00056 n=m;
00057 }
00058
00059 template<class IntType>
00060 inline IntType
00061 PowOps::pow(IntType x) const {
00062 int m = n;
00063 IntType p = 1;
00064 do {
00065 if (even(m)) {
00066 x *= x; m >>= 1;
00067 } else {
00068 p *= x; m--;
00069 }
00070 } while (m > 0);
00071 return p;
00072 }
00073
00074 inline int
00075 PowOps::tpow(int _x) const {
00076 int m = n;
00077 long long int p = 1;
00078 long long int x = _x;
00079 do {
00080 if (even(m)) {
00081 x *= x; m >>= 1;
00082 } else {
00083 p *= x; m--;
00084 }
00085 if (p > Limits::max)
00086 return Limits::max+1;
00087 if (p < Limits::min)
00088 return Limits::min-1;
00089 } while (m > 0);
00090 return static_cast<int>(p);
00091 }
00092
00093 forceinline bool
00094 PowOps::powgr(long long int r, int x) const {
00095 assert(r >= 0);
00096 int m = n;
00097 long long int y = r;
00098 long long int p = 1;
00099 do {
00100 if (even(m)) {
00101 y *= y; m >>= 1;
00102 if (y > x)
00103 return true;
00104 } else {
00105 p *= y; m--;
00106 if (p > x)
00107 return true;
00108 }
00109 } while (m > 0);
00110 assert(y <= x);
00111 return false;
00112 }
00113
00114 inline int
00115 PowOps::fnroot(int x) const {
00116 if (x < 2)
00117 return x;
00118
00119
00120
00121 long long int l = 1;
00122 long long int u = x;
00123 do {
00124 long long int m = (l + u) >> 1;
00125 if (powgr(m,x)) u=m; else l=m;
00126 } while (l+1 < u);
00127 assert((pow(l) <= x) && (x < pow(l+1)));
00128 return static_cast<int>(l);
00129 }
00130
00131 forceinline bool
00132 PowOps::powle(long long int r, int x) const {
00133 assert(r >= 0);
00134 int m = n;
00135 long long int y = r;
00136 long long int p = 1;
00137 do {
00138 if (even(m)) {
00139 y *= y; m >>= 1;
00140 if (y >= x)
00141 return false;
00142 } else {
00143 p *= y; m--;
00144 if (p >= x)
00145 return false;
00146 }
00147 } while (m > 0);
00148 assert(y < x);
00149 return true;
00150 }
00151
00152 inline int
00153 PowOps::cnroot(int x) const {
00154 if (x < 2)
00155 return x;
00156
00157
00158
00159 long long int l = 1;
00160 long long int u = x;
00161 do {
00162 long long int m = (l + u) >> 1;
00163 if (powle(m,x)) l=m; else u=m;
00164 } while (l+1 < u);
00165 assert((pow(u-1) < x) && (x <= pow(u)));
00166 return static_cast<int>(u);
00167 }
00168
00169
00170
00171 forceinline bool
00172 SqrOps::even(void) const {
00173 return true;
00174 }
00175
00176 forceinline int
00177 SqrOps::exp(void) const {
00178 return 2;
00179 }
00180
00181 forceinline void
00182 SqrOps::exp(int) {
00183 GECODE_NEVER;
00184 }
00185
00186 template<class IntType>
00187 inline IntType
00188 SqrOps::pow(IntType x) const {
00189 return x * x;
00190 }
00191
00192 inline int
00193 SqrOps::tpow(int _x) const {
00194 long long int x = _x;
00195 if (x*x > Limits::max)
00196 return Limits::max+1;
00197 if (x*x < Limits::min)
00198 return Limits::min-1;
00199 return static_cast<int>(x*x);
00200 }
00201
00202 inline int
00203 SqrOps::fnroot(int x) const {
00204 if (x < 2)
00205 return x;
00206
00207
00208
00209 long long int l = 1;
00210 long long int u = x;
00211 do {
00212 long long int m = (l + u) >> 1;
00213 if (m*m > x) u=m; else l=m;
00214 } while (l+1 < u);
00215 assert((pow(l) <= x) && (x < pow(l+1)));
00216 return static_cast<int>(l);
00217 }
00218
00219 inline int
00220 SqrOps::cnroot(int x) const {
00221 if (x < 2)
00222 return x;
00223
00224
00225
00226 long long int l = 1;
00227 long long int u = x;
00228 do {
00229 long long int m = (l + u) >> 1;
00230 if (m*m < x) l=m; else u=m;
00231 } while (l+1 < u);
00232 assert((pow(u-1) < x) && (x <= pow(u)));
00233 return static_cast<int>(u);
00234 }
00235
00236 }}}
00237
00238
00239