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.
You will be given 2 things as input:
- a string of base 10 digits, call it \$n\$.
- 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.
You will output two numbers, \$Q\$ and \$R\$ where \$m\times Q+R=n\$ and \$0 \leq R < m\$
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.
- In this case, inputs are \$39!\$ and \$30!\$
n = 20397882081197443358640281739902897356800000000 m = 265252859812191058636308480000000
Q = 76899763100160 R = 0
nis the sum of all factorials up to 50, plus 1.
mis concatenated numbers up to 20.
n = 31035053229546199656252032972759319953190362094566672920420940313 m = 1234567891011121314151617181920
q = 25138393324103249083146424239449429 r = 62459510197626865203087816633
nis 205! + 200!.
mis how many tears PeterTaylor has made me shed by tearing apart things I post in the sandbox.
n = 271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000 m = 247
q = 1100573825740813795225181252819477770473619155158611722708681386445423816849801159141424129060075102231232666057768175183676764503262931271346408394876267875141461722640873365274628650676808557279259873162169126398101692109801549256156915750794061370041981513180387019893765753438422927286098434193260562682052606153857091520795991080960000000000000000000000000000000000000000000000000 r = 0;
I'll probably add more test cases at some point.