Generated on Fri Oct 19 11:25:01 2018 for Gecode by doxygen 1.6.3

pow-ops.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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      * We look for l such that: l^n <= x < (l+1)^n
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      * We look for u such that: (u-1)^n < x <= u^n
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      * We look for l such that: l^2 <= x < (l+1)^2
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      * We look for u such that: (u-1)^n < x <= u^n
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 // STATISTICS: int-other
00239