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