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
print_factorials()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
b1(unsigned n)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
b2(unsigned n)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
main()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 */
231