Integer long division: Difference between revisions
Added C++ solution
(Added C++ solution) |
|||
Line 15:
*[[Long primes]]
<br><br>
=={{header|C++}}==
{{libheader|GMP}}
<lang cpp>#include <gmpxx.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
using big_int = mpz_class;
std::pair<std::string, size_t> divide(const big_int& n, const big_int& d) {
assert(n >= 0);
assert(d > 0);
std::string result = big_int(n / d).get_str();
result += '.';
big_int c = 10 * (n % d);
size_t digits = 0;
std::map<big_int, size_t> seen;
while (c > 0 && c < d) {
seen[c] = digits++;
result += '0';
c *= 10;
}
while (seen.count(c) == 0) {
if (c == 0) {
if (result.back() == '.')
result.pop_back();
return {result, 0};
}
seen[c] = digits++;
result += big_int(c / d).get_str();
c = 10 * (c % d);
}
return {result, digits - seen[c]};
}
int main() {
big_int test[][2] = {
{0, 1}, {1, 1}, {1, 5},
{1, 3}, {1, 7}, {83, 60},
{1, 17}, {10, 13}, {3227, 555},
{1, 149}, {1, 5261}, {476837158203125, big_int("9223372036854775808")}};
for (auto [n, d] : test) {
auto [result, period] = divide(n, d);
std::string str = n.get_str();
str += '/';
str += d.get_str();
std::string repetend = result.substr(result.size() - period);
if (repetend.size() > 30)
repetend.replace(15, repetend.size() - 30, "...");
result.resize(result.size() - period);
std::cout << std::setw(35) << str << " = " << result;
if (period != 0)
std::cout << '{' << repetend << "} (period " << period << ')';
std::cout << '\n';
}
}</lang>
{{out}}
<pre>
0/1 = 0
1/1 = 1
1/5 = 0.2
1/3 = 0.{3} (period 1)
1/7 = 0.{142857} (period 6)
83/60 = 1.38{3} (period 1)
1/17 = 0.{0588235294117647} (period 16)
10/13 = 0.{769230} (period 6)
3227/555 = 5.8{144} (period 3)
1/149 = 0.{006711409395973...087248322147651} (period 148)
1/5261 = 0.{000190077931952...263257935753659} (period 1052)
476837158203125/9223372036854775808 = 0.000051698788284564229679463043254372678347863256931304931640625
</pre>
=={{header|Common Lisp}}==
<lang lisp>
| |||