Integer long division: Difference between revisions

← Older edit

Integer long division (view source)

Revision as of 14:43, 3 January 2024

6,411 bytes added , 4 months ago

m

→‎{{header|RPL}}: Added comments for HP-49 version

Aerobar

1,150

edits

Revision as of 10:04, 7 October 2021 (view source) Peak (talk \| contribs) (→‎{{header\|jq}}) ← Older edit		Latest revision as of 14:43, 3 January 2024 (view source) Aerobar (talk \| contribs) m (→‎{{header\|RPL}}: Added comments for HP-49 version)
(7 intermediate revisions by 6 users not shown)
Line 15: [[Long primes]] <br><br> =={{header\|C++}}== {{libheader\|GMP}} <syntaxhighlight 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 (seen.count(c) == 0) { if (c == 0) { if (result.back() == '.') result.pop_back(); return {result, 0}; } seen[c] = digits++; if (c < d) { result += '0'; c = 10; } else { 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'; } }</syntaxhighlight> {{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~~syntaxhighlight lang="lisp"> (defun $/ (a b) "Divide a/b with infinite precision printing each digit as it is calculated and return the period length" Line 39 ⟶ 114: () )) </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 57 ⟶ 132: partly because the Unicode "overline" might not display properly. In case the overline style is preferred, simply use the following function in the obvious way: <~~lang~~syntaxhighlight lang="jq"># "\u0305" def overline: explode \| map(., 773) \| implode;</~~lang~~syntaxhighlight> <~~lang~~syntaxhighlight lang="jq"># To take advantage of gojq's support for accurate integer division: def idivide($j): . as $i Line 115 ⟶ 190: "Period is \($r\|length)\n" ; task</~~lang~~syntaxhighlight> {{out}} <pre> Line 164 ⟶ 239: =={{header\|Julia}}== <~~lang~~syntaxhighlight lang="julia">function f2d(numr, denr) dpart, remainders, r = "", Dict{BigInt, Int}(), BigInt(numr) % denr while (r != 0) && !haskey(remainders, r) Line 195 ⟶ 270: testrepeatingdecimals() </~~lang~~syntaxhighlight>{{out}} <pre> Line 214 ⟶ 289: {{trans\|Wren}} {{libheader\|bignum}} <~~lang~~syntaxhighlight ~~Nim~~lang="nim">import strformat, strutils, tables import bignum Line 269 ⟶ 344: echo &"{a}/{b} = {repr}" echo &"Cycle is <{cycle}>" echo &"Period is {period}\n"</~~lang~~syntaxhighlight> {{out}} Line 317 ⟶ 392: =={{header\|Perl}}== <~~lang~~syntaxhighlight lang="perl">use strict; use warnings; use utf8; Line 346 ⟶ 421: printf "%10s Period is %5d : %s\n", $_, long_division split '/' for <0/1 1/1 1/5 1/3 -1/3 1/7 -83/60 1/17 10/13 3227/555 1/149></~~lang~~syntaxhighlight> {{out}} <pre> 0/1 Period is 0 : 0 Line 363 ⟶ 438: =={{header\|Phix}}== Translation of the Python code linked to by the Wren entry, modified to cope with negatives. <!--<~~lang~~syntaxhighlight ~~Phix~~lang="phix">(phixonline)--> <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> Line 406 ⟶ 481: <span style="color: #0000FF;">{</span><span style="color: #000000;">476837158203125</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9223372036854775808</span><span style="color: #0000FF;">}}[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span><span style="color: #0000FF;">)]</span> <span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span><span style="color: #000000;">test</span><span style="color: #0000FF;">)</span> <!--</~~lang~~syntaxhighlight>--> {{out}} The results below are on 64 bit, not surprisingly the last example is inaccurate past 16 significant digits on 32 bit (ditto p2js), and hence omitted. Line 430 ⟶ 505: =={{header\|Raku}}== It's a built-in. <syntaxhighlight lang="raku" ~~perl6~~line>for 0/1, 1/1, 1/3, 1/7, -83/60, 1/17, 10/13, 3227/555, 521/263, 1/149, 1/5261 -> $rat { printf "%35s - Period is %-5s: %s%s\n", $rat.nude.join('/'), .[1].chars, .[0], (.[1].comb Z~ "\c[COMBINING OVERLINE]" xx ).join given $rat.base-repeating }</~~lang~~syntaxhighlight> {{out}} <pre style="overflow:auto;white-space:revert;"> 0/1 - Period is 0 : 0 Line 446 ⟶ 521: 1/149 - Period is 148 : 0.0̅0̅6̅7̅1̅1̅4̅0̅9̅3̅9̅5̅9̅7̅3̅1̅5̅4̅3̅6̅2̅4̅1̅6̅1̅0̅7̅3̅8̅2̅5̅5̅0̅3̅3̅5̅5̅7̅0̅4̅6̅9̅7̅9̅8̅6̅5̅7̅7̅1̅8̅1̅2̅0̅8̅0̅5̅3̅6̅9̅1̅2̅7̅5̅1̅6̅7̅7̅8̅5̅2̅3̅4̅8̅9̅9̅3̅2̅8̅8̅5̅9̅0̅6̅0̅4̅0̅2̅6̅8̅4̅5̅6̅3̅7̅5̅8̅3̅8̅9̅2̅6̅1̅7̅4̅4̅9̅6̅6̅4̅4̅2̅9̅5̅3̅0̅2̅0̅1̅3̅4̅2̅2̅8̅1̅8̅7̅9̅1̅9̅4̅6̅3̅0̅8̅7̅2̅4̅8̅3̅2̅2̅1̅4̅7̅6̅5̅1̅ 1/5261 - Period is 1052 : 0.0̅0̅0̅1̅9̅0̅0̅7̅7̅9̅3̅1̅9̅5̅2̅1̅0̅0̅3̅6̅1̅1̅4̅8̅0̅7̅0̅7̅0̅8̅9̅9̅0̅6̅8̅6̅1̅8̅1̅3̅3̅4̅3̅4̅7̅0̅8̅2̅3̅0̅3̅7̅4̅4̅5̅3̅5̅2̅5̅9̅4̅5̅6̅3̅7̅7̅1̅1̅4̅6̅1̅6̅9̅9̅2̅9̅6̅7̅1̅1̅6̅5̅1̅7̅7̅7̅2̅2̅8̅6̅6̅3̅7̅5̅2̅1̅3̅8̅3̅7̅6̅7̅3̅4̅4̅6̅1̅1̅2̅9̅0̅6̅2̅9̅1̅5̅7̅9̅5̅4̅7̅6̅1̅4̅5̅2̅1̅9̅5̅4̅0̅0̅1̅1̅4̅0̅4̅6̅7̅5̅9̅1̅7̅1̅2̅6̅0̅2̅1̅6̅6̅8̅8̅8̅4̅2̅4̅2̅5̅3̅9̅4̅4̅1̅1̅7̅0̅8̅8̅0̅0̅6̅0̅8̅2̅4̅9̅3̅8̅2̅2̅4̅6̅7̅2̅1̅1̅5̅5̅6̅7̅3̅8̅2̅6̅2̅6̅8̅7̅7̅0̅1̅9̅5̅7̅8̅0̅2̅6̅9̅9̅1̅0̅6̅6̅3̅3̅7̅1̅9̅8̅2̅5̅1̅2̅8̅3̅0̅2̅6̅0̅4̅0̅6̅7̅6̅6̅7̅7̅4̅3̅7̅7̅4̅9̅4̅7̅7̅2̅8̅5̅6̅8̅7̅1̅3̅1̅7̅2̅4̅0̅0̅6̅8̅4̅2̅8̅0̅5̅5̅5̅0̅2̅7̅5̅6̅1̅3̅0̅0̅1̅3̅3̅0̅5̅4̅5̅5̅2̅3̅6̅6̅4̅7̅0̅2̅5̅2̅8̅0̅3̅6̅4̅9̅4̅9̅6̅2̅9̅3̅4̅8̅0̅3̅2̅6̅9̅3̅4̅0̅4̅2̅9̅5̅7̅6̅1̅2̅6̅2̅1̅1̅7̅4̅6̅8̅1̅6̅1̅9̅4̅6̅3̅9̅8̅0̅2̅3̅1̅8̅9̅5̅0̅7̅6̅9̅8̅1̅5̅6̅2̅4̅4̅0̅6̅0̅0̅6̅4̅6̅2̅6̅4̅9̅6̅8̅6̅3̅7̅1̅4̅1̅2̅2̅7̅9̅0̅3̅4̅4̅0̅4̅1̅0̅5̅6̅8̅3̅3̅3̅0̅1̅6̅5̅3̅6̅7̅8̅0̅0̅7̅9̅8̅3̅2̅7̅3̅1̅4̅1̅9̅8̅8̅2̅1̅5̅1̅6̅8̅2̅1̅8̅9̅6̅9̅7̅7̅7̅6̅0̅8̅8̅1̅9̅6̅1̅6̅0̅4̅2̅5̅7̅7̅4̅5̅6̅7̅5̅7̅2̅7̅0̅4̅8̅0̅8̅9̅7̅1̅6̅7̅8̅3̅8̅8̅1̅3̅9̅1̅3̅7̅0̅4̅6̅1̅8̅8̅9̅3̅7̅4̅6̅4̅3̅6̅0̅3̅8̅7̅7̅5̅8̅9̅8̅1̅1̅8̅2̅2̅8̅4̅7̅3̅6̅7̅4̅2̅0̅6̅4̅2̅4̅6̅3̅4̅0̅9̅9̅9̅8̅0̅9̅9̅2̅2̅0̅6̅8̅0̅4̅7̅8̅9̅9̅6̅3̅8̅8̅5̅1̅9̅2̅9̅2̅9̅1̅0̅0̅9̅3̅1̅3̅8̅1̅8̅6̅6̅5̅6̅5̅2̅9̅1̅7̅6̅9̅6̅2̅5̅5̅4̅6̅4̅7̅4̅0̅5̅4̅3̅6̅2̅2̅8̅8̅5̅3̅8̅3̅0̅0̅7̅0̅3̅2̅8̅8̅3̅4̅8̅2̅2̅2̅7̅7̅1̅3̅3̅6̅2̅4̅7̅8̅6̅1̅6̅2̅3̅2̅6̅5̅5̅3̅8̅8̅7̅0̅9̅3̅7̅0̅8̅4̅2̅0̅4̅5̅2̅3̅8̅5̅4̅7̅8̅0̅4̅5̅9̅9̅8̅8̅5̅9̅5̅3̅2̅4̅0̅8̅2̅8̅7̅3̅9̅7̅8̅3̅3̅1̅1̅1̅5̅7̅5̅7̅4̅6̅0̅5̅5̅8̅8̅2̅9̅1̅1̅9̅9̅3̅9̅1̅7̅5̅0̅6̅1̅7̅7̅5̅3̅2̅7̅8̅8̅4̅4̅3̅2̅6̅1̅7̅3̅7̅3̅1̅2̅2̅9̅8̅0̅4̅2̅1̅9̅7̅3̅0̅0̅8̅9̅3̅3̅6̅6̅2̅8̅0̅1̅7̅4̅8̅7̅1̅6̅9̅7̅3̅9̅5̅9̅3̅2̅3̅3̅2̅2̅5̅6̅2̅2̅5̅0̅5̅2̅2̅7̅1̅4̅3̅1̅2̅8̅6̅8̅2̅7̅5̅9̅9̅3̅1̅5̅7̅1̅9̅4̅4̅4̅9̅7̅2̅4̅3̅8̅6̅9̅9̅8̅6̅6̅9̅4̅5̅4̅4̅7̅6̅3̅3̅5̅2̅9̅7̅4̅7̅1̅9̅6̅3̅5̅0̅5̅0̅3̅7̅0̅6̅5̅1̅9̅6̅7̅3̅0̅6̅5̅9̅5̅7̅0̅4̅2̅3̅8̅7̅3̅7̅8̅8̅2̅5̅3̅1̅8̅3̅8̅0̅5̅3̅6̅0̅1̅9̅7̅6̅8̅1̅0̅4̅9̅2̅3̅0̅1̅8̅4̅3̅7̅5̅5̅9̅3̅9̅9̅3̅5̅3̅7̅3̅5̅0̅3̅1̅3̅6̅2̅8̅5̅8̅7̅7̅2̅0̅9̅6̅5̅5̅9̅5̅8̅9̅4̅3̅1̅6̅6̅6̅9̅8̅3̅4̅6̅3̅2̅1̅9̅9̅2̅0̅1̅6̅7̅2̅6̅8̅5̅8̅0̅1̅1̅7̅8̅4̅8̅3̅1̅7̅8̅1̅0̅3̅0̅2̅2̅2̅3̅9̅1̅1̅8̅0̅3̅8̅3̅9̅5̅7̅4̅2̅2̅5̅4̅3̅2̅4̅2̅7̅2̅9̅5̅1̅9̅1̅0̅2̅8̅3̅2̅1̅6̅1̅1̅8̅6̅0̅8̅6̅2̅9̅5̅3̅8̅1̅1̅0̅6̅2̅5̅3̅5̅6̅3̅9̅6̅1̅2̅2̅4̅1̅0̅1̅8̅8̅1̅7̅7̅1̅5̅2̅6̅3̅2̅5̅7̅9̅3̅5̅7̅5̅3̅6̅5̅9̅</pre> =={{header\|RPL}}== {{works with\|HP\|48}} {{trans\|Nim}} « DUP2 / '''IF''' DUP FP '''THEN''' IP "." + ROT ROT <span style="color:grey">@ HP49+: add R→I after IP</span> ABS SWAP ABS OVER MOD 10 { } → quotient n c passed « "" '''WHILE''' c DUP n < AND '''REPEAT''' 10 'c' STO* 'quotient' "0" STO+ '''END''' '''WHILE''' passed c POS NOT '''REPEAT''' 'passed' c STO+ c n / IP + <span style="color:grey">@ HP49+: replace / IP by IQUOT</span> c n MOD 10 * 'c' STO '''END''' passed c POS DUP2 1 SWAP 1 - SUB quotient SWAP + ROT ROT OVER SIZE SUB '''IF''' DUP "0" == '''THEN''' DROP "" '''END''' » '''ELSE''' →STR ROT ROT DROP2 "" '''END''' » '<span style="color:blue">LDIV</span>' STO <span style="color:grey">@ ''( m n → "quotient.prefix" "repetend" )'' </span> « DUP2 "/" SWAP + + " = " + ROT ROT <span style="color:blue">LDIV</span> '''IF''' DUP SIZE '''THEN''' ")" + SWAP "(" + SWAP + '''ELSE''' DROP '''END''' + » '<span style="color:blue">VUDIV</span>' STO <span style="color:grey">@ ''@ ( m n → "m/n = quotient.prefix(repetend)" )'' </span> -3227 555 <span style="color:blue">VUDIV</span> 355 113 <span style="color:blue">VUDIV</span> {{out}} <pre> 2: "-3227/555 = -5.8(144)" 1: 355/113 = 3.(1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168) </pre> =={{header\|V (Vlang)}}== {{trans\|wren}} <syntaxhighlight lang="v (vlang)">import math.big const big_ten = big.integer_from_int(10) fn divide(m big.Integer, n big.Integer) ?[]string { if m < big.zero_int { return error('m must not be negative') } if n <= big.zero_int { return error('n must be positive') } mut quotient := '${(m/n)}.' mut c := (m % n) * big_ten mut zeros := 0 for c > big.zero_int && c < n { c = c * big_ten quotient = quotient + "0" zeros ++ } mut digits := "" mut passed := map[string]int{}//string:int mut i := 0 for { mut cs := c.str() if cs in passed { prefix := digits[0..passed[cs]] mut repetend := digits[passed[cs]..digits.len] mut result := '$quotient${prefix}(${repetend})' result = result.replace("(0)", "").trim_right(".") index := result.index("(") or {-1} if index == -1 { return [result, "", '0'] } result = result.replace("(", "").replace(")", "") for _ in 0..zeros { if repetend[repetend.len-1] == 0 { result = result[0..result.len-1] repetend = "0" + repetend[0..result.len-1] } else { break } } return [result + "....", repetend, repetend.len.str()] } q := c / n r := c % n passed[cs] = i digits += q.str() i++ c = r * big_ten } return ['FAIL','',''] } fn main(){ for test in [[0, 1], [1, 1], [1, 3], [1, 7], [83,60], [1, 17], [10, 13], [3227, 555], [476837158203125, 9223372036854775808], [1, 149], [1, 5261]] { a := big.integer_from_i64(test[0]) b := big.integer_from_i64(test[1]) res := divide(a,b) or {['Need positive numbers','','']} println('$a/$b = ${res[0]}') println("repetend is '${res[1]}'") println('period is ${res[2]}\n') } }</syntaxhighlight> {{out}} <pre> Similar as wren entry</pre> =={{header\|Wren}}== This is based on the Python code [http://codepad.org/hKboFPd2 here]. <~~lang~~syntaxhighlight ~~ecmascript~~lang="wren">import "./big" for BigInt var divide = Fn.new { \|m, n\| Line 503 ⟶ 689: System.print("Repetend is '%(res[1])'") System.print("Period is %(res[2])\n") }</~~lang~~syntaxhighlight> {{out}}