[Question]
  [
We will be implementing division for arbitrarily large integers.
This is [code-golf](/questions/tagged/code-golf "show questions tagged '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](https://codegolf.stackexchange.com/questions/55807/golf-cpu-implement-arbitrary-precision-integer-division)
[Sounds related, but really isn't](https://codegolf.stackexchange.com/questions/22146/implement-arbitrary-precision-division)
  
[Answer]
# 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](https://codegolf.stackexchange.com/revisions/71764/3).
I guess this will not be the shortest solution, but maybe it gives a good start.
[Answer]
# 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]
# [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-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!](https://tio.run/##lZPNalxHEIX38xSzGw3WoPrpru4KcTbJIgZDIMoLCCR5Y@IIskgQWSU4sqwRCcGQrR0La@eVCRiCQY9yX0T5emQZb32Hufd2V3WdU6fO3fvh4Wr/572Hjx6sDn768eD7/YP96@n82b1vpsd/yPV09u908jfrr6b1SzneZfN4Wr@ZHv81rS@3ptMLHqvp5NXOcjr7T@4S@mV6@tt90j6f1hfTkxfTyeXd27dXx1/sTOun4/z67cjjcZ/VZ8ILy6P5Hge3RvzkdwpfvdYN0Nvl9tWlbE@nL3ZuEnevLo@29o5vj99swuZXSBwt71BEx8bu1p3p7J3OZXCbq0ynL6mxnNb/TE@ec2i16eTPTQvwA2eDSwvrN0tuF1A5v7pcXh9SkVcArl77OHH@bPfbL7l/9/W93euF2uJw4aUuZqvVara1vZDF8qMN4k4CWR8vP0Rdi9a0qF57tiRkTbv18X@fYuLZejfpqtlKcVKjCDnNM3lm8xpd3l@jRFSr1mt2NU0V8j1cerlN@gAuXqW6WdYSmhk1OChu2azVdLYqN/EwyVIjolmalLES15vGaDVaB0YVuE1DGkoXSuptDywLfEvWBiuRRg0QW2QpUZSddInsDqgbqU2yVkmhX7ECKc3o1jgj0ulHGplw7K1176RaBZ9iHXSLjjbWIN41pLu5VJCoJGY0Sbg6pYlW9M@iUmrJIUQzNbPuDljTm59HadnoobMltTboI5OD2BJc9OiGOiC2St@wDiVcexE4JDNrdXOlp3oLQSXJNDJpxZOzm77r4IUTupWITG/GtKhKE5UZhuAR9puafOo1fFHaYjZbPjo8nPFFGDeZqcx9ZnP3mSqN2ZyZI61jmFmLzgJmMgiQjMY@RjQmhEtKIq0yPyvmyJvFch50gSYyhsscYvhJekPp2ICI0GS32gqGduRjIHhlGFazNC4pzZkzdBAwkNhQoDNJx/eMycbYesmO42qiJPiKlIGtADZzTDnGARIt4BLtHkwzSoV1GM7BkA5x@Gfpg2jrpFEqBtwINCSo1gpmiSoc7tKHQC1tuM5xmUaqhQ9D82pMFErDRjW0EqutYtOC0b2JFCURAbWLd0aanfkGOY4P8RN@BYoaxUmFJyNHQJPKKwVxOR@FoieiJd9bl4xPtsFc/gc "APL (Dyalog Extended) – 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](https://chat.stackexchange.com/transcript/message/55347207#55347207) to [ngn's CMC](https://chat.stackexchange.com/transcript/message/55346903#55346903). 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`](http://dfns.dyalog.com/n_big.htm), designed to handle big integer arithmetic, but apparently [its modulo function is buggy](https://tio.run/##lZO9ql1VFIX7/RSn2wbuhfmz5l@dxlSCsbGMhBOEYAQrwU5IISRo4TvYWdrrm9wXuX7r5oe02Yezz95rjTXnmGOM8@zHl7fPf3728tWL@7u3fz756u7177KfHn97Pr/@8NN5/PfPd9@/uDkv580vPNy9@ev@Cubuzdu7337992@/e/0H6KdfP@b@zZdPnt5fj1PtvJ6@4jxub2@PL25OOR99ssC@AwD16evHXdelMZbh0VPDlpW29f6@h5j4VLdJq06t5UBzCZjyGX6nPLLl/bVLZFhYx7Sajgp4T5deH0Afm4uHhJtNrNSZjOSguE1ZxThLwU08TWZFZpaNydpv4vpuMEbNatqo0u5hIE1lCgX6YQZeF3zXRMFKpKhBx8pZK5eyMi457TR1A1oyETLCvGILUjrZVpwRaeaRAgnHrmpvoBb0p1jT3bLRxgrirSnt5hJ0opKYMSTb4ZRmN9B/lsqKNVuIMjWzdqdZ6buP56opZmiWJKKgj0xOxxr6okcb6tCxgrlhncp29BI4DJ5VPFzjo14pqCQzBpJRfDj7MHdsXiShbWXOeBluUZUhAg9TyAjrpSafe@1crDqP49Gr6/WQixo3OVQuftjF/VBlMLvgOdI6gTkqmxeYySYAGI19W7QdIiVrkFbxz5Y58s6yuSRToIlsc/Ehd56kC6XzoYkIQ7ZFLQLtyIchZGUHVmcVl6xyfIYOAiYSGwo0Tjq5xybbtvWaJnExKEl/RcokVjQ2c0K57aATI5ASbU/czBWwTiM5BNIhDv9ZvYlWA6NU7nZ7o5AgrBZhyRAOt/QWqMZ26pyUaY5a@g40j4ajUNoxitRgLyqI6SLoXiJLASKgtnhj6TT@Jhgnh@SJvNKKGsuBwhPLEdAkeKQgKedPoeiJaMP/rWXys2Nwkf8B) (returns the divisor when the remainder is zero), so it can't be used here anyway.
[Answer]
# 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`.
]