ceph/src/boost/libs/multiprecision/example/integer_examples.cpp

   1 ///////////////////////////////////////////////////////////////
   2 //  Copyright 2012 John Maddock. Distributed under the Boost
   3 //  Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_
   5
   6 #include <boost/multiprecision/cpp_int.hpp>
   7 #include <iostream>
   8 #include <iomanip>
   9 #include <vector>
  10
  11 //[FAC1
  12
  13 /*`
  14 In this simple example, we'll write a routine to print out all of the factorials
  15 which will fit into a 128-bit integer.  At the end of the routine we do some
  16 fancy iostream formatting of the results:
  17 */
  18 /*=
  19 #include <boost/multiprecision/cpp_int.hpp>
  20 #include <iostream>
  21 #include <iomanip>
  22 #include <vector>
  23 */
  24
  25 void print_factorials()
  26 {
  27    using boost::multiprecision::cpp_int;
  28    //
  29    // Print all the factorials that will fit inside a 128-bit integer.
  30    //
  31    // Begin by building a big table of factorials, once we know just how
  32    // large the largest is, we'll be able to "pretty format" the results.
  33    //
  34    // Calculate the largest number that will fit inside 128 bits, we could
  35    // also have used numeric_limits<int128_t>::max() for this value:
  36    cpp_int limit = (cpp_int(1) << 128) - 1;
  37    //
  38    // Our table of values:
  39    std::vector<cpp_int> results;
  40    //
  41    // Initial values:
  42    unsigned i = 1;
  43    cpp_int factorial = 1;
  44    //
  45    // Cycle through the factorials till we reach the limit:
  46    while(factorial < limit)
  47    {
  48       results.push_back(factorial);
  49       ++i;
  50       factorial *= i;
  51    }
  52    //
  53    // Lets see how many digits the largest factorial was:
  54    unsigned digits = results.back().str().size();
  55    //
  56    // Now print them out, using right justification, while we're at it
  57    // we'll indicate the limit of each integer type, so begin by defining
  58    // the limits for 16, 32, 64 etc bit integers:
  59    cpp_int limits[] = {
  60       (cpp_int(1) << 16) - 1,
  61       (cpp_int(1) << 32) - 1,
  62       (cpp_int(1) << 64) - 1,
  63       (cpp_int(1) << 128) - 1,
  64    };
  65    std::string bit_counts[] = { "16", "32", "64", "128" };
  66    unsigned current_limit = 0;
  67    for(unsigned j = 0; j < results.size(); ++j)
  68    {
  69       if(limits[current_limit] < results[j])
  70       {
  71          std::string message = "Limit of " + bit_counts[current_limit] + " bit integers";
  72          std::cout << std::setfill('.') << std::setw(digits+1) << std::right << message << std::setfill(' ') << std::endl;
  73          ++current_limit;
  74       }
  75       std::cout << std::setw(digits + 1) << std::right << results[j] << std::endl;
  76    }
  77 }
  78
  79 /*`
  80 The output from this routine is:
  81 [pre
  82                                        1
  83                                        2
  84                                        6
  85                                       24
  86                                      120
  87                                      720
  88                                     5040
  89                                    40320
  90 ................Limit of 16 bit integers
  91                                   362880
  92                                  3628800
  93                                 39916800
  94                                479001600
  95 ................Limit of 32 bit integers
  96                               6227020800
  97                              87178291200
  98                            1307674368000
  99                           20922789888000
 100                          355687428096000
 101                         6402373705728000
 102                       121645100408832000
 103                      2432902008176640000
 104 ................Limit of 64 bit integers
 105                     51090942171709440000
 106                   1124000727777607680000
 107                  25852016738884976640000
 108                 620448401733239439360000
 109               15511210043330985984000000
 110              403291461126605635584000000
 111            10888869450418352160768000000
 112           304888344611713860501504000000
 113          8841761993739701954543616000000
 114        265252859812191058636308480000000
 115       8222838654177922817725562880000000
 116     263130836933693530167218012160000000
 117    8683317618811886495518194401280000000
 118  295232799039604140847618609643520000000
 119 ]
 120 */
 121
 122 //]
 123
 124 //[BITOPS
 125
 126 /*`
 127 In this example we'll show how individual bits within an integer may be manipulated,
 128 we'll start with an often needed calculation of ['2[super n] - 1], which we could obviously
 129 implement like this:
 130 */
 131
 132 using boost::multiprecision::cpp_int;
 133
 134 cpp_int b1(unsigned n)
 135 {
 136    cpp_int r(1);
 137    return (r << n) - 1;
 138 }
 139
 140 /*`
 141 Calling:
 142
 143    std::cout << std::hex << std::showbase << b1(200) << std::endl;
 144
 145 Yields as expected:
 146
 147 [pre 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF]
 148
 149 However, we could equally just set the n'th bit in the result, like this:
 150 */
 151
 152 cpp_int b2(unsigned n)
 153 {
 154    cpp_int r(0);
 155    return --bit_set(r, n);
 156 }
 157
 158 /*`
 159 Note how the `bit_set` function sets the specified bit in its argument and then returns a reference to the result -
 160 which we can then simply decrement.  The result from a call to `b2` is the same as that to `b1`.
 161
 162 We can equally test bits, so for example the n'th bit of the result returned from `b2` shouldn't be set
 163 unless we increment it first:
 164
 165    assert(!bit_test(b1(200), 200));     // OK
 166    assert(bit_test(++b1(200), 200));    // OK
 167
 168 And of course if we flip the n'th bit after increment, then we should get back to zero:
 169
 170    assert(!bit_flip(++b1(200), 200));   // OK
 171 */
 172
 173 //]
 174
 175 int main()
 176 {
 177    print_factorials();
 178
 179    std::cout << std::hex << std::showbase << b1(200) << std::endl;
 180    std::cout << std::hex << std::showbase << b2(200) << std::endl;
 181    assert(!bit_test(b1(200), 200));  // OK
 182    assert(bit_test(++b1(200), 200));    // OK
 183    assert(!bit_flip(++b1(200), 200));   // OK
 184    return 0;
 185 }
 186
 187 /*
 188
 189 Program output:
 190
 191                                        1
 192                                        2
 193                                        6
 194                                       24
 195                                      120
 196                                      720
 197                                     5040
 198                                    40320
 199 ................Limit of 16 bit integers
 200                                   362880
 201                                  3628800
 202                                 39916800
 203                                479001600
 204 ................Limit of 32 bit integers
 205                               6227020800
 206                              87178291200
 207                            1307674368000
 208                           20922789888000
 209                          355687428096000
 210                         6402373705728000
 211                       121645100408832000
 212                      2432902008176640000
 213 ................Limit of 64 bit integers
 214                     51090942171709440000
 215                   1124000727777607680000
 216                  25852016738884976640000
 217                 620448401733239439360000
 218               15511210043330985984000000
 219              403291461126605635584000000
 220            10888869450418352160768000000
 221           304888344611713860501504000000
 222          8841761993739701954543616000000
 223        265252859812191058636308480000000
 224       8222838654177922817725562880000000
 225     263130836933693530167218012160000000
 226    8683317618811886495518194401280000000
 227  295232799039604140847618609643520000000
 228  0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
 229  0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
 230  */