Integer long division: Difference between revisions
Content added Content deleted
(Added C++ solution) |
|||
Line 15: | Line 15: | ||
*[[Long primes]] |
*[[Long primes]] |
||
<br><br> |
<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}}== |
=={{header|Common Lisp}}== |
||
<lang lisp> |
<lang lisp> |