TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
BigNumber.hpp
1 /*
2  * TdZdd: a Top-down/Breadth-first Decision Diagram Manipulation Framework
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2014 ERATO MINATO Project
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the "Software"),
8  * to deal in the Software without restriction, including without limitation
9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  * and/or sell copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  * DEALINGS IN THE SOFTWARE.
23  */
24 
25 #pragma once
26 
27 #include <cassert>
28 #include <stdint.h>
29 #include <cstdlib>
30 #include <iostream>
31 #include <sstream>
32 #include <stdexcept>
33 #include <string>
34 
35 namespace tdzdd {
36 
37 class BigNumber {
38 protected:
39  static uint64_t const MSB = uint64_t(1) << 63;
40 
41  uint64_t* array;
42 
43 public:
44  BigNumber()
45  : array(0) {
46  }
47 
48  explicit BigNumber(uint64_t* array)
49  : array(array) {
50  }
51 
52  void setArray(uint64_t* array) {
53  this->array = array;
54  }
55 
56  int size() const {
57  uint64_t const* p = array;
58  if (p == 0) return 1;
59  while (*p++ & MSB)
60  ;
61  return p - array;
62  }
63 
64  size_t store(BigNumber const& o) {
65  if (o.array == 0) return store(0);
66 
67  uint64_t* p = array;
68  uint64_t const* q = o.array;
69 
70  if (p == 0) {
71  if (*q != 0) throw std::runtime_error(
72  "Non-zero assignment to null BigNumber");
73  return 1;
74  }
75 
76  do {
77  *p++ = *q;
78  } while (*q++ & MSB);
79 
80  return p - array;
81  }
82 
83  size_t store(uint64_t n) {
84  size_t w = 1;
85 
86  if (array == 0) {
87  if (n != 0) throw std::runtime_error(
88  "Non-zero assignment to null BigNumber");
89  }
90  else {
91  array[0] = n;
92  if (n & MSB) {
93  w = 2;
94  array[1] = 1;
95  }
96  }
97 
98  return w;
99  }
100 
101  bool operator==(BigNumber const& o) const {
102  if (array == 0) return o.operator==(0);
103  if (o.array == 0) return operator==(0);
104 
105  uint64_t* p = array;
106  uint64_t const* q = o.array;
107  do {
108  if (*p++ != *q) return false;
109  } while (*q++ & MSB);
110  return true;
111  }
112 
113  bool operator!=(BigNumber const& o) const {
114  return !operator==(o);
115  }
116 
117  bool operator==(uint64_t n) const {
118  return (array == 0) ? n == 0 :
119  array[0] == n && ((n & MSB) == 0 || array[1] == 1);
120  }
121 
122  bool operator!=(uint64_t const& o) const {
123  return !operator==(o);
124  }
125 
126  size_t add(BigNumber const& o) {
127  uint64_t* p = array;
128  uint64_t const* q = o.array;
129  uint64_t x = 0;
130 
131  while (true) {
132  x += *p & ~MSB;
133  x += *q & ~MSB;
134 
135  if ((*p & MSB) == 0) {
136  while ((*q & MSB) != 0) {
137  *p++ = x | MSB;
138  ++q;
139  x >>= 63;
140  x += *q & ~MSB;
141  }
142 
143  break;
144  }
145 
146  if ((*q & MSB) == 0) {
147  while ((*p & MSB) != 0) {
148  *p++ = x | MSB;
149  x >>= 63;
150  x += *p & ~MSB;
151  }
152 
153  break;
154  }
155 
156  *p++ = x | MSB;
157  ++q;
158  x >>= 63;
159  }
160 
161  *p++ = x;
162  if (x & MSB) *p++ = 1;
163 
164  return p - array;
165  }
166 
167  uint32_t divide(uint32_t n) {
168  uint64_t* p = array;
169  if (p == 0) return 0;
170 
171  while (*p++ & MSB)
172  ;
173  uint64_t r = 0;
174  bool cont = false;
175 
176  do {
177  --p;
178  uint64_t q = cont ? MSB : 0;
179  r = (r << 31) | ((*p & ~MSB) >> 32);
180  lldiv_t d = lldiv(r, 10LL);
181  q += d.quot << 32;
182  r = (d.rem << 32) | (*p & ((uint64_t(1) << 32) - 1));
183  d = lldiv(r, 10LL);
184  q += d.quot;
185  r = d.rem;
186  *p = q;
187  if (q != 0) cont = true;
188  } while (p != array);
189 
190  return r;
191  }
192 
193  size_t shiftLeft(int k) {
194  assert(k >= 0);
195  if (k >= 63) {
196  int w = k / 63;
197  for (uint64_t* q = array + size() - 1; q >= array; --q) {
198  *(q + w) = *q;
199  }
200  for (uint64_t* q = array; q < array + w; ++q) {
201  *q = MSB;
202  }
203  }
204  k %= 63;
205 
206  uint64_t* p = array;
207  uint64_t x = 0;
208 
209  while (true) {
210  uint64_t tmp = x | (*p << k);
211  x = (*p & ~MSB) >> (63 - k);
212  if (x == 0 && (*p & MSB) == 0) {
213  *p++ = tmp & ~MSB;
214  break;
215  }
216  else if ((*p & MSB) == 0) {
217  *p++ = tmp | MSB;
218  *p++ = x;
219  break;
220  }
221  *p++ = tmp | MSB;
222  }
223 
224  return p - array;
225  }
226 
227  template<typename T>
228  T translate() const {
229  uint64_t const* p = array;
230  while (*p & MSB) {
231  ++p;
232  }
233  T v = *p;
234  while (p != array) {
235  v <<= 63;
236  v += *--p & ~MSB;
237  }
238  return v;
239  }
240 
241 private:
242  void printHelper(std::ostream& os) {
243  uint32_t r = divide(10);
244  if (*this != 0) printHelper(os);
245  os << r;
246  }
247 
248 public:
249  friend std::ostream& operator<<(std::ostream& os, BigNumber const& o) {
250  uint64_t* storage = new uint64_t[o.size()];
251  BigNumber n(storage);
252  n.store(o);
253  n.printHelper(os);
254  delete[] storage;
255  return os;
256  }
257 
258  operator std::string() const {
259  std::ostringstream ss;
260  ss << *this;
261  return ss.str();
262  }
263 };
264 
265 template<int size>
266 class FixedBigNumber {
267  uint32_t val[size];
268 
269 public:
270  FixedBigNumber() {
271  for (int i = 0; i < size; ++i) {
272  val[i] = 0;
273  }
274  }
275 
276  FixedBigNumber(uint32_t i) {
277  val[0] = i;
278  for (int i = 1; i < size; ++i) {
279  val[i] = 0;
280  }
281  }
282 
283  FixedBigNumber& operator=(uint32_t n) {
284  val[0] = n;
285  for (int i = 1; i < size; ++i) {
286  val[i] = 0;
287  }
288  return *this;
289  }
290 
291  bool operator==(FixedBigNumber const& o) const {
292  for (int i = 0; i < size; ++i) {
293  if (val[i] != o.val[i]) return false;
294  }
295  return true;
296  }
297 
298  bool operator!=(FixedBigNumber const& o) const {
299  return !operator==(o);
300  }
301 
302  bool operator==(uint32_t n) const {
303  if (val[0] != n) return false;
304  for (int i = 1; i < size; ++i) {
305  if (val[i] != 0) return false;
306  }
307  return true;
308  }
309 
310  bool operator!=(uint32_t n) const {
311  return !operator==(n);
312  }
313 
314  void operator+=(FixedBigNumber const& o) {
315  uint64_t x = 0;
316  for (int i = 0; i < size; ++i) {
317  x += val[i];
318  x += o.val[i];
319  val[i] = x;
320  x >>= 32;
321  }
322  if (x != 0) throw std::runtime_error("FixedBigNumber overflow!");
323  }
324 
325  FixedBigNumber operator+(FixedBigNumber const& o) const {
326  FixedBigNumber n = *this;
327  n += o;
328  return n;
329  }
330 
331  uint32_t divide(uint32_t n) {
332  uint64_t r = 0;
333  for (int i = size - 1; i >= 0; --i) {
334  r = (r << 32) + val[i];
335  lldiv_t d = lldiv(r, n);
336  val[i] = d.quot;
337  r = d.rem;
338  }
339  return r;
340  }
341 
342  template<typename T>
343  T translate() const {
344  T v = 0;
345  for (int i = size - 1; i >= 0; --i) {
346  v <<= 32;
347  v += val[i];
348  }
349  return v;
350  }
351 
352 private:
353  void printHelper(std::ostream& os) {
354  uint32_t r = divide(10);
355  if (*this != 0) printHelper(os);
356  os << r;
357  }
358 
359 public:
360  friend std::ostream& operator<<(std::ostream& os, FixedBigNumber const& o) {
361  FixedBigNumber n = o;
362  n.printHelper(os);
363  return os;
364  }
365 
366  operator std::string() const {
367  std::ostringstream ss;
368  ss << *this;
369  return ss.str();
370  }
371 };
372 
373 } // namespace tdzdd