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