1 // large_lcm.cpp: calculating a least common multiple of a very large set
2 //
3 // Copyright (C) 2017-2021 Stillwater Supercomputing, Inc.
4 //
5 // This file is part of the universal numbers project, which is released under an MIT Open Source license.
6 #include <iostream>
7 #include <fstream>
8 #include <vector>
9 #include <random>
10 #include <typeinfo>
11 #include <chrono>
12 // include the number system we want to use, and configure overflow exceptions so we can capture failures
13 #define INTEGER_THROW_ARITHMETIC_EXCEPTION 1
14 #include <universal/number/integer/integer.hpp>
15
16 template<size_t nbits, typename BlockType>
MeasureLCM(const std::vector<sw::universal::integer<nbits,BlockType>> & v)17 void MeasureLCM(const std::vector<sw::universal::integer<nbits, BlockType>>& v) {
18 std::chrono::steady_clock::time_point begin, end;
19 begin = std::chrono::steady_clock::now();
20 using Integer = sw::universal::integer<nbits, BlockType>;
21 Integer least_common_multple = lcm(v);
22 end = std::chrono::steady_clock::now();
23 using TimeReal = float;
24 std::chrono::duration<TimeReal> time_span = std::chrono::duration_cast<std::chrono::duration<TimeReal >> (end - begin);
25 TimeReal elapsed = time_span.count();
26
27 std::cout << "In " << elapsed << " seconds calculated LCM of " << v.size() << " elements of type " << typeid(Integer).name()
28 << " to be\n" << least_common_multple << '\n';
29 }
30
31 #define STRESS_TESTING 0
32
33 // Warning C6262 Function uses '16448' bytes of stack : exceeds / analyze : stacksize '16384'.Consider moving some data to heap.crypto_large_lcm C : \Users\tomtz\Documents\dev\clones\universal\applications\cryptography\large_lcm.cpp 31
34 // TODO: what gets allocated on the stack? Integer factor, but that is max 256bytes
main()35 int main()
36 try {
37 using namespace sw::universal;
38
39 int nrOfFailedTestCases = 0;
40
41 {
42 constexpr size_t nbits = 512;
43 using Integer = integer<nbits, uint32_t>;
44 Integer factor;
45
46 // use random_device to generate a seed for Mersenne twister engine
47 std::random_device rd{};
48 std::mt19937 engine{ rd() };
49 std::uniform_real_distribution<double> dist{0.0, 1000000000000.0 };
50
51 std::vector<Integer> v;
52 for (int i = 0; i < 10; ++i) {
53 factor = dist(engine);
54 if (factor.iseven()) ++factor;
55 // cout << factor << endl;
56 v.push_back(factor);
57 }
58 try {
59 MeasureLCM(v);
60 }
61 catch (const integer_overflow& e) {
62 std::cerr << e.what() << '\n';
63 std::cerr << typeid(Integer).name() << " has insufficient dynamic range to capture the least common multiple\n";
64 std::ofstream out;
65 out.open("lcm_dataset_1.txt");
66 for (size_t i = 0; i < v.size(); ++i) {
67 out << v[i] << '\n';
68 }
69 out.close();
70 }
71 }
72
73 // this triggers the integer_overflow exception
74 {
75 constexpr size_t nbits = 1024;
76 using Integer = integer<nbits, uint32_t>;
77 Integer factor;
78
79 std::random_device rd{};
80 std::mt19937 engine{ rd() };
81 std::uniform_real_distribution<double> dist{0.0, 100000.0 };
82
83 std::vector<Integer> v;
84 for (int i = 0; i < 100; ++i) {
85 factor = dist(engine);
86 if (factor.iseven()) ++factor;
87 v.push_back(factor);
88 }
89 try {
90 MeasureLCM(v);
91 }
92 catch (const integer_overflow& e) {
93 std::cerr << e.what() << '\n';
94 std::cerr << typeid(Integer).name() << " has insufficient dynamic range to capture the least common multiple\n";
95 std::ofstream out;
96 out.open("lcm_dataset_2.txt");
97 for (size_t i = 0; i < v.size(); ++i) {
98 out << v[i] << '\n';
99 }
100 out.close();
101 }
102 }
103
104 #if STRESS_TESTING
105 {
106 constexpr size_t nbits = 2048;
107 using Integer = integer<nbits, uint32_t>;
108 Integer factor;
109
110 std::random_device rd{};
111 std::mt19937 engine{ rd() };
112 std::uniform_real_distribution<double> dist{0.0, 1000.0 };
113
114 std::vector<Integer> v;
115 for (int i = 0; i < 1000; ++i) {
116 factor = dist(engine);
117 if (factor.iseven()) ++factor;
118 v.push_back(factor);
119 }
120 try {
121 MeasureLCM(v);
122 }
123 catch (const integer_overflow& e) {
124 std::cerr << e.what() << '\n';
125 std::cerr << typeid(Integer).name() << " has insufficient dynamic range to capture the least common multiple\n";
126 std::ofstream out;
127 out.open("lcm_dataset_3.txt");
128 for (size_t i = 0; i < v.size(); ++i) {
129 out << v[i] << '\n';
130 }
131 out.close();
132 }
133 }
134 #endif
135
136 return (nrOfFailedTestCases > 0 ? EXIT_FAILURE : EXIT_SUCCESS);
137 }
138 catch (char const* msg) {
139 std::cerr << "Caught exception: " << msg << std::endl;
140 return EXIT_FAILURE;
141 }
142 catch (const std::runtime_error& err) {
143 std::cerr << "Uncaught runtime exception: " << err.what() << std::endl;
144 return EXIT_FAILURE;
145 }
146 catch (...) {
147 std::cerr << "Caught unknown exception" << std::endl;
148 return EXIT_FAILURE;
149 }
150