Arbitrary Precision Integer Division

Question

We will be implementing division for arbitrarily large integers.

This is code-golf.

The task is to write a program or function that implements arbitrary precision integers and Division on them.

Note that many things that might make this very easy are disallowed, please make sure to read through the spec.

Input

You will be given 2 things as input:

1. a string of base 10 digits, call it \$n\$.
2. another string of base 10 digits, call it \$m\$

Assume that \$n>m>0\$ meaning that you will never be asked to divide by zero.

Output

You will output two numbers, \$Q\$ and \$R\$ where \$m\times Q+R=n\$ and \$0 \leq R < m\$

Specifications

• Your submission should work for arbitrarily large integers (limited by available memory).

• You may not use external libraries. If you need an external library for i/o, you may treat it as a built-in. (looking at things like iostream, etc).

• If your language has a built-in that trivializes this, you may not use it. This includes (but may not be limited to) built-in types that can handle arbitrary precision integers.

• If a language for some reason uses arbitrary precision integers by default, this functionality cannot be used to represent integers that could not be typically stored in a 64 bits.

• Input and output MUST be in base 10. It does not matter how you store the numbers in memory or how you perform arithmetic on them, but i/o will be base 10.

• You have 15 Seconds to output a result. This is to prohibit iterated subtraction.

• The goal here is to actually implement arbitrary precision integers. If for some reason you are able to adhere to the challenge specs and successfully do this without implementing them, well I guess good for you, sounds valid.

Test Cases

1. In this case, inputs are \$39!\$ and \$30!\$

Input

n = 20397882081197443358640281739902897356800000000 
m = 265252859812191058636308480000000

Output

Q = 76899763100160
R = 0

2. n is the sum of all factorials up to 50, plus 1. m is concatenated numbers up to 20.

input

n = 31035053229546199656252032972759319953190362094566672920420940313
m = 1234567891011121314151617181920

output

q = 25138393324103249083146424239449429
r = 62459510197626865203087816633

3. n is 205! + 200!. m is how many tears PeterTaylor has made me shed by tearing apart things I post in the sandbox.

Input

n = 271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000
m = 247

Output

q = 1100573825740813795225181252819477770473619155158611722708681386445423816849801159141424129060075102231232666057768175183676764503262931271346408394876267875141461722640873365274628650676808557279259873162169126398101692109801549256156915750794061370041981513180387019893765753438422927286098434193260562682052606153857091520795991080960000000000000000000000000000000000000000000000000
r = 0;

I'll probably add more test cases at some point.

Related

Sounds related, but really isn't

Answer 1

Java 8, 485 bytes

Could reduce by another 5 bytes naming the function d instead of divide or another 16 bytes if not counting class-definition.

public class G{int l(String a){return a.length();}String s(String n,String m){while(l(n)>l(m))m=0+m;String a="";for(int c=1,i=l(n);i>0;c=c/10){c=n.charAt(--i)+c-m.charAt(i)+9;a=c%10+a;}return e(a);}String e(String a){return a.replaceAll("^0+(?=[0-9])","");}String divide(String n,String m){String q="",p=q,y;for(int b=0,i=0;b<=l(n);i--){y=n.substring(0,b);if(l(y)==l(p)&&p.compareTo(y)<=0||l(y)>l(p)){y=s(y,p);n=y+n.substring(b);q+=i;b=l(y)+1;i=10;p=m+0;}p=s(p,m);}return e(q)+","+n;}}

Can be used like this:

public static void main(String[] args) {
    G devision = new G();
    System.out.println(devision.divide("20397882081197443358640281739902897356800000000",
            "265252859812191058636308480000000"));
    System.out.println(devision.divide("31035053229546199656252032972759319953190362094566672920420940313",
            "1234567891011121314151617181920"));
    System.out.println(devision.divide(
            "271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000",
            "247"));
}

yielding

76899763100160,0
25138393324103249083146424239449429,62459510197626865203087816633
1100573825740813795225181252819477770473619155158611722708681386445423816849801159141424129060075102231232666057768175183676764503262931271346408394876267875141461722640873365274628650676808557279259873162169126398101692109801549256156915750794061370041981513180387019893765753438422927286098434193260562682052606153857091520795991080960000000000000000000000000000000000000000000000000,0

Ungolfed:

public class ArbitraryPrecisionDivision {

    /**
     * Length of String
     */
    int l(String a) {
        return a.length();
    }

    /**
     * substract m of n; n >= m
     */
    String s(String n, String m) {
        while (l(n) > l(m))
            m = 0 + m;
        String a = "";
        for (int c = 1, i = l(n); i > 0; c = c / 10) {
            c = n.charAt(--i) + c - m.charAt(i) + 9;
            a = c % 10 + a;
        }
        return e(a);
    }

    /**
     * trim all leading 0s
     */
    String e(String a) {
        return a.replaceAll("^0+(?=[0-9])", "");
    }

    /**
     * divide n by m returning n/m,n%m; m may not start with a 0!
     */
    String divide(String n, String m) {
        // q stores the quotient, p stores m*i, y are the b leading digits of n
        String q = "", p = q, y;
        for (int b = 0, i = 0; b <= l(n); i--) {
            y = n.substring(0, b);
            if (l(y) == l(p) && p.compareTo(y) <= 0 || l(y) > l(p)) {
                y = s(y, p);
                n = y + n.substring(b);
                q += i;
                b = l(y) + 1;
                i = 10;
                p = m + 0;
            }
            p = s(p, m);
        }
        return e(q) + "," + n;
    }

    public static void main(String[] args) {
        ArbitraryPrecisionDivision division = new ArbitraryPrecisionDivision();
        System.out.println(division.divide("20397882081197443358640281739902897356800000000",
                "265252859812191058636308480000000"));
        System.out.println(division.divide("31035053229546199656252032972759319953190362094566672920420940313",
                "1234567891011121314151617181920"));
        System.out.println(division.divide(
                "271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000",
                "247"));
    }
}

I sacrificed a bit of speed by not precalculating an array with m times 1 through 9 and starting with b=0 instead of b=l(m), but saved lots of bytes doing so. If you are interested in arbitrary precision addition see a previous version.

I guess this will not be the shortest solution, but maybe it gives a good start.

Answer 2

Python 2, 427 bytes

b=S=lambda l:sorted(l)[::-1]
A=lambda a,b,o=0:A(a^b,{n+1for n in[b&a,b-a][o]},o)if b else a
M=lambda a,*b:reduce(A,({n+m for n in a}for m in b))
def D(a,b):
 q=a-a
 while b<=S(a):n=max(a)-b[0];n-=S(M(b,n))>S(a);q|={n};a=A(a,M(b,n),1)
 return q,a
exec"a=b;b=[]\nfor d in raw_input():b=A(M(b,3,1),{i for i in range(4)if int(d)>>i&1})\n"*2
for n in D(a,S(b)):
 s=''
 while n:n,d=D(n,[3,1]);s=`sum(2**i for i in d)`+s
 print s or 0

Reads the input through STDIN, each number on a separate line, and prints the result to STDOUT.

Explanation

Instead of representing integers as arrays of digits, we represent each integer as the set of "on" bits in its binary representation. That is, an integer n is represented as the set of indices of the bits that equal 1 in the binary representation of n. For example, the number 10, 1010 in binary, is represented as the set {1, 3}. This representation allows us to express some of the arithmetic operations rather succinctly, using Python's set operations.

To add two sets, we (recursively) take the sum of their symmetric difference, and the set of succeeding integers to their intersection (which corresponds to the collective carry, and hence eventually becomes the empty set, at which point we have the final sum.) Similarly, to subtract two sets, we (recursively) take the difference of their symmetric difference, and the set of succeeding integers to their (set) difference (which corresponds to the collective borrow, and hence eventually becomes the empty set, at which point we have the final difference.) The similarity of these two operations allows us to implement them as a single function (A).

Multiplication (M) is simply distributed addition: given two sets A and B, we take the sum, as described above, of all the sets {A+b | b∈B} (where A+b is the set {a+b | a∈A}).

Integer comparison becomes lexicographical comparison of the two sets, sorted in descending order.

To divide (D) two sets, A and B, we start with the empty set as the quotient, and repeatedly find the largest integer n, such that B+n is less than or equal to A (which is simply the difference between the maxima of A and B, possibly minus-1), add n as an element to the quotient, and subtract B+n from A, as described above, until A becomes less than B, i.e., until it becomes the remainder.

There is no free lunch, of course. We pay the tax by having to convert from-, and to-, decimal. In fact, the conversion to decimal is what takes most of the run time. We do the conversion "the usual way", only using the above operations, instead of ordinary arithmetic.

Answer 3

APL (Dyalog Extended), 131 bytes

⌷∘⎕D⍤0{S←{⍵↓⍨(⊥⍨-∧/)⌽0=⍵}⋄L←<⍥≢∨=⍥≢∧{>/⍋⍵⍺}⋄⍺L⍵:0⍺⋄q a←(⍵∇⍨¯1↓⍺),¨0,⊢/⍺⋄S¨q(a{⍺L⍵:⍺⋄(⊃⌽q)+←1⋄(S(+⌿1 0⌽0 10⊤⊢)⍣≡⍺-⍵↑⍨-≢⍺)∇⍵}⍵)}⍥(⍎¨)

Try it online!

An anonymous function that takes n (dividend) on the left and m (divisor) on the right, and returns a 2-row char matrix of digits where the first row is the quotient and the second is the remainder.

This is an expansion of my "shitty" solution to ngn's CMC. It was really hard to get this right and short at the same time.

Ungolfed with comments

⍝ Post-processing: Map each digit (numeric 0-9) to respective chars
f←⌷∘⎕D⍤0{
  ⍝ Inner function, m f n → (n/m)(n%m), I/O as numeric digit vectors
  ⍝ S x → trim leading zeros of x, leaving a single zero if x is entirely 0
  S←{⍵↓⍨(⊥⍨-∧/)⌽0=⍵}
  ⍝ x L y → given two numbers as digit vectors, is x less than y?
  L←<⍥≢∨=⍥≢∧{>/⍋⍵⍺}

  ⍝ if ⍺<⍵, return quotient 0 and remainder ⍺
  ⍺L⍵:0⍺
  ⍝ get recursive result for (⍺/10) f ⍵,
  ⍝ multiply quotient by 10 (by appending 0),
  ⍝ and multiply remainder by 10 and add the last digit of ⍺ (by appending ⊢/⍺)
  q a←(⍵∇⍨¯1↓⍺),¨0,⊢/⍺
  ⍝ fix the quotient and remainder by repeatedly subtracting the remainder
  ⍝ and adding 1 to the quotient until it is right,
  ⍝ then trim leading zeros from both
  S¨q(a{
    ⍝ inner function with ⍺←remainder to fix, ⍵←divisor
    ⍝ done if ⍺ is less than ⍵
    ⍺L⍵:⍺
    ⍝ increment the last digit of q
    (⊃⌽q)+←1
    ⍝ subtract and fix negative digits by borrowing
    (S(+⌿1 0⌽0 10⊤⊢)⍣≡⍺-⍵↑⍨-≢⍺)∇⍵
  }⍵)
⍝ Pre-processing: convert the char vectors on both sides to numeric digit vectors
}⍥(⍎¨)

A fun fact: Dyalog APL has a library operator, dfns.big, designed to handle big integer arithmetic, but apparently its modulo function is buggy (returns the divisor when the remainder is zero), so it can't be used here anyway.

Answer 4

Mathematica, 251 bytes

r=Reverse;f=FoldPairList;s={0}~Join~#&;
p[a_,b_]:={First@#,#[[2,1,-1,2]]}/.{Longest[0..],x__}:>{x}&@Reap@f[Sow@{Length@#-1,Last@#}&@NestWhileList[r@f[{#~Mod~10,⌊#/10⌋}&[#+Subtract@@#2]&,0,r@Thread@{#,s@b}]&,Rest@#~Join~{#2},Order[#,s@b]<=0&]&,0s@b,s@a]

---

Explanation

Arithmetics on decimal numbers can easily be implemented by FoldPairList. For example,

times[lint_,m_]:=Reverse@FoldPairList[{#~Mod~10,⌊#/10⌋}&[m #2+#]&,0,Reverse@lint]

just mimics the process of doing multiplications by hand.

times[{1,2,3,4,5},8]
(* {9,8,7,6,0} *)

---

Test case

p[{1,2,3,4,5,6,7,8,9},{5,4,3,2,1}] 
(* {{2,2,7,2},{3,9,4,7,7}} *)

means 123456789 / 54321= 2272...39477.