]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /////////////////////////////////////////////////////////////// |
2 | // Copyright 2012 John Maddock. Distributed under the Boost | |
3 | // Software License, Version 1.0. (See accompanying file | |
92f5a8d4 | 4 | // LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt |
7c673cae FG |
5 | |
6 | #include <boost/multiprecision/cpp_int.hpp> | |
7 | #include <iostream> | |
8 | #include <iomanip> | |
9 | #include <vector> | |
10 | ||
92f5a8d4 TL |
11 | // Includes Quickbook code snippets as comments. |
12 | ||
7c673cae FG |
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 | // | |
92f5a8d4 | 33 | // Begin by building a big table of factorials, once we know just how |
7c673cae FG |
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; | |
92f5a8d4 | 39 | // |
7c673cae FG |
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: | |
92f5a8d4 | 61 | cpp_int limits[] = { |
7c673cae FG |
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 | |
92f5a8d4 | 120 | 295232799039604140847618609643520000000 |
7c673cae FG |
121 | ] |
122 | */ | |
123 | ||
124 | //] | |
125 | ||
126 | //[BITOPS | |
127 | ||
92f5a8d4 TL |
128 | /*` |
129 | In this example we'll show how individual bits within an integer may be manipulated, | |
7c673cae FG |
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 | ||
1e59de90 TL |
167 | BOOST_MP_ASSERT(!bit_test(b1(200), 200)); // OK |
168 | BOOST_MP_ASSERT(bit_test(++b1(200), 200)); // OK | |
7c673cae FG |
169 | |
170 | And of course if we flip the n'th bit after increment, then we should get back to zero: | |
171 | ||
1e59de90 | 172 | BOOST_MP_ASSERT(!bit_flip(++b1(200), 200)); // OK |
7c673cae FG |
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; | |
1e59de90 TL |
183 | BOOST_MP_ASSERT(!bit_test(b1(200), 200)); // OK |
184 | BOOST_MP_ASSERT(bit_test(++b1(200), 200)); // OK | |
185 | BOOST_MP_ASSERT(!bit_flip(++b1(200), 200)); // OK | |
7c673cae FG |
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 | |
92f5a8d4 | 229 | 295232799039604140847618609643520000000 |
7c673cae FG |
230 | 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF |
231 | 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF | |
232 | */ |