Generated on Sat May 25 2013 18:00:35 for Gecode by doxygen 1.8.3.1
math.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2012
8  *
9  * Last modified:
10  * $Date: 2012-08-27 13:30:57 +0200 (Mon, 27 Aug 2012) $ by $Author: schulte $
11  * $Revision: 13006 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Int { namespace Arithmetic {
39 
40  template<class IntType>
42  bool even(IntType n) {
43  return (n & 1) == 0;
44  }
45 
46  template<class IntType>
47  inline
48  IntType pow(IntType x, int n) {
49  assert(n > 0);
50  IntType p = 1;
51  do {
52  if (even(n)) {
53  x *= x; n >>= 1;
54  } else {
55  p *= x; n--;
56  }
57  } while (n > 0);
58  return p;
59  }
60 
62  int tpow(int _x, int n) {
63  assert(n > 0);
64  long long int p = 1;
65  long long int x = _x;
66  do {
67  if (even(n)) {
68  x *= x; n >>= 1;
69  } else {
70  p *= x; n--;
71  }
72  if (p > Limits::max)
73  return Limits::max+1;
74  } while (n > 0);
75  return static_cast<int>(p);
76  }
77 
80  bool powgr(int r, int n, int x) {
81  assert((r >= 0) && (n > 0));
82  unsigned long long int y = static_cast<unsigned long long int>(r);
83  unsigned long long int p = static_cast<unsigned long long int>(1);
84  do {
85  if (even(n)) {
86  y *= y; n >>= 1;
87  if (y > x)
88  return true;
89  } else {
90  p *= y; n--;
91  if (p > x)
92  return true;
93  }
94  } while (n > 0);
95  assert(y <= x);
96  return false;
97  }
98 
99  inline
100  int fnroot(int x, int n) {
101  if (x < 2)
102  return x;
103  /*
104  * We look for l such that: l^n <= x < (l+1)^n
105  */
106  int l = 1;
107  int u = x;
108  do {
109  int m = (l + u) >> 1;
110  if (powgr(m,n,x)) u=m; else l=m;
111  } while (l+1 < u);
112  assert((pow(static_cast<long long int>(l),n) <= x) &&
113  (x < pow(static_cast<long long int>(l+1),n)));
114  return l;
115  }
116 
119  bool powle(int r, int n, int x) {
120  assert((r >= 0) && (n > 0));
121  unsigned long long int y = static_cast<unsigned long long int>(r);
122  unsigned long long int p = static_cast<unsigned long long int>(1);
123  do {
124  if (even(n)) {
125  y *= y; n >>= 1;
126  if (y >= x)
127  return false;
128  } else {
129  p *= y; n--;
130  if (p >= x)
131  return false;
132  }
133  } while (n > 0);
134  assert(y < x);
135  return true;
136  }
137 
139  inline
140  int cnroot(int x, int n) {
141  if (x < 2)
142  return x;
143  /*
144  * We look for u such that: (u-1)^n < x <= u^n
145  */
146  int l = 1;
147  int u = x;
148  do {
149  int m = (l + u) >> 1;
150  if (powle(m,n,x)) l=m; else u=m;
151  } while (l+1 < u);
152  assert((pow(static_cast<long long int>(u-1),n) < x) &&
153  (x <= pow(static_cast<long long int>(u),n)));
154  return u;
155  }
156 
157 }}}
158 
159 // STATISTICS: int-other
160