Divide Two Numbers Using Long Division

Your challenge is to divide two numbers using long division. The method we used to use in old days of school to divide two numbers.

Example here
You should NOT use `/` or any other division operator in your code.

Also, this is not an `ASCII - ART`

Example:

``````Input  : 4 2 (4 divided by 2)

Output : 2 0 (here 2 is quotient and 0 is remainder)
``````

Another example

``````Input  : 7182 15 (7182 divided by 15)

Output : 478 12 (7170 is quotient and 12 is remainder)
``````

The answer with most up-votes after 24 hours wins because this is a popularity contest.

-
Even using the hand method I still mentally divide each grouping. I guess you could subtract in a loop or multiply by the inverse, but those just seem like trivial workarounds. Also, you might want to give better examples than single-digit numbers if you want the "long-hand" method to show clearly. – Geobits Mar 19 '14 at 16:02
@Geobits is right, everyone still uses division (mostly mentally) even when performing long division. I suggest the modifying the requirement like "division operators may only be used if the result is less than 10". All that long division serves to do is break a large division problem into a bunch of smaller division problems where each quotient is guaranteed to be in the range of 0 through 9. – Rainbolt Mar 19 '14 at 16:22
please explain the requirement in simple words (sorry, I am not so good at english !) – Mukul Kumar Mar 19 '14 at 16:36
24 hours is too little time. It is recommended that you wait for a while (maybe a week), and update the winner every now and then. – Justin Mar 19 '14 at 18:19
The previous long division of integers question had a spec and required output which made clear what calculations had to be performed. The long division of polynomials question would be most easily implemented by long division even if that weren't specified. This one is so imprecise that you're praising answers which don't even pretend to follow what little instruction it gives. – Peter Taylor Mar 19 '14 at 18:50

C

Not exactly a long division - this answer uses the method used in the real old days.

``````#include <stdio.h>
#include <stdlib.h>
int main() {
int a,b;
scanf("%d %d", &a, &b);
int *p=calloc(b, sizeof(int));
int *q=p;
while(a--) {
(*p)++;
if(p-q<b-1) p++;
else p-=b-1;
}
p=q;
int r=0, i;
for(i=0; i<b; i++) r+=p[i]-p[b-1];
printf("%d %d\n", p[b-1], r);
return 0;
}
``````

Explanation:

Suppose you are given `a` number of sheep and you need to split them up into `b` number of groups. The method used here is to assign each sheep into a different group until the total number of groups reaches `b`, then start from the first group again. This repeats until there are no more sheep. Then, the quotient will be the number of sheep in the last group, and the remainder will be the sum of the differences between each group and the last group.

An illustration for `8/3`:

``````       |Group 1 | Group 2 | Group 3
-------------------------------------
| 1      | 2       | 3        // first sheep in group 1, second sheep in group 2, etc
| 4      | 5       | 6
| 7      | 8       |
-------------------------------------
total: | 3      | 3       | 2
``````

So the quotient is 2 and the remainder is (3-2)+(3-2)=2.

-
This one is good! – Mukul Kumar Mar 19 '14 at 16:51

C: 73 characters

The best way to solve long division is with short code of course!

``````j;d;main(i){scanf("%d%d",&i,&j);while(i>=j)d++,i-=j;printf("%d %d",d,i);}
``````

I never really bothered to learn long division in school anyway. Came to really bite me when we had to use it in university-level calculus...

Here's a more readable version of the code. It's not very spectacular. I changed the `int`s to `unsigned` as it doesn't handle negatives correctly. They weren't specified in the question so I'm going with the benefit of the doubt here.

``````#include <stdio.h>

int main(){
unsigned int i = 0, j = 0, d = 0;
scanf("%u%u", &i, &j);

while(i >= j){
i -= j;
d++;
}

printf("%d %d\n", d, i);
return 0;
}
``````
-
Not really long division, but I like it. :) +1 – Martin Ender Mar 19 '14 at 16:57
-1, this is a popularity contest, not a code golf contest, so this is just simply bad code – ASKASK Mar 19 '14 at 17:47
@ASKASK As this is indeed a popularity-contest it is of course your right to downvote answers that you think shouldn't win. And my answer is indeed not very creative. I don't think however, that a popularity-contest automatically invalidates a golfed answer, especially with the hugastically bad 'long division - short code'-pun. Have added more readable and correct code to my answer (the only incorrectness I can see is that it doesn't validate the result of `scanf`, but that seems beyond the scope here). – Kninnug Mar 19 '14 at 18:05

Bash + coreutils

Forget what you learned in school. Nobody uses long division. Its always important to chose the right tool for the job. `dd` is known by some as the swiss army knife of the command-line tools, so it really is the right tool for every job!:

``````#!/bin/bash

q=\$(dd if=/dev/zero of=/dev/null ibs=\$1 count=1 obs=\$2 2>&1 | grep out | cut -d+ -f1)
r=\$(( \$1 - \$(dd if=/dev/zero of=/dev/null bs=\$q count=\$2 2>&1 | grep bytes | cut -d' ' -f1) ))
echo \$q \$r
``````

Output:

```\$ ./divide.sh 4 2
2 0
\$ ./divide.sh 7182 15
478 12
\$
```

Sorry, I know this is a subversive, trolly answer, but I just couldn't resist. Cue the downvotes...

-
Hurray (and +1) for `dd`! – Kninnug Mar 19 '14 at 19:16

Julia

Here is an entry that not only is free from division but doesn't employ any multiplication either. It does the long division quite literally by using more string manipulation than arithmetic. It also prints out an ASCII version of what the long-division would look like on a sheet of paper (at least the way I learned it)

``````function divide(x,y)
if y > x
return 0, x
end

x = "\$x"
q = ""
r = ""

workings = ""

for i = 1:length(x)
r = "\$(r)0"
num = int(r) + int(x[i:i])
sum = 0
m = 0
while sum+y <= num
m += 1
sum += y
end
r = string(num-sum)
q = "\$q\$m"
ls = length(string(sum))
workings *= repeat(" ", i-ls) * "-\$sum\n"
workings *= repeat(" ", i+1-ls) * repeat("-", ls) * "\n"
workings *= repeat(" ", i+1-length(r)) * r * (i >= length(x) ? "" : x[i+1:i+1]) * "\n"
end

workings *= repeat(" ", length(x)-length(r)+1) * repeat("=", length(r)) * "\n"

print(" \$x : \$y = \$(int(q)) R \$r\n\$workings")
int(q), int(r)
end
``````

Results (the `(q,r)` line at the end is just Julia printing the result of the function call):

``````> divide(5,3)         > divide(4138,17)           > divide(7182,15)

5 : 3 = 1 R 2         4138 : 17 = 243 R 7         7182 : 15 = 478 R 12
-3                    -0                          -0
-                     -                           -
2                     41                          71
=                    -34                         -60
--                          --
(1,2)                   73                         118
-68                        -105
--                         ---
58                         132
-51                        -120
--                         ---
7                          12
=                          ==

(243,7)                     (478,12)
``````

I suppose I could get rid of the remaining arithmetic by using a unary number system, `repeat` and `length` but that feels more like multiplying than not using arithmetic.

Don't even try dividing by zero! (Seriously, who would do long division for that?) Also don't try negative numbers.

-

C

Long division! At least how a standard computer algorithm might do it, one binary digit (bit) at a time. Handles negatives, too.

``````#include <stdio.h>

#define INT_BITS (sizeof(int)*8)

typedef struct div_result div_result;
struct div_result {
int quotient;
int remainder;
};

div_result divide(int dividend, int divisor) {
int negative = (dividend < 0) ^ (divisor < 0);

if (divisor == 0) {
result.quotient = dividend < 0 ? INT_MIN : INT_MAX;
result.remainder = 0;
return result;
}

if ((dividend == INT_MIN) && (divisor == -1)) {
result.quotient = INT_MAX;
result.remainder = 0;
return result;
}

if (dividend < 0) {
dividend = -dividend;
}
if (divisor < 0) {
divisor = -divisor;
}

int quotient = 0, remainder = 0;

for (int i = 0; i < sizeof(int)*8; i++) {
quotient <<= 1;

remainder <<= 1;
remainder += (dividend >> (INT_BITS - 1)) & 1;
dividend <<= 1;

if (remainder >= divisor) {
remainder -= divisor;
quotient++;
}
}

div_result result;
if (negative) {
result.quotient = -quotient;
result.remainder = -remainder;
} else {
result.quotient = quotient;
result.remainder = remainder;
}
return result;
}

int main() {
int dividend, divisor;
scanf("%i%i", &dividend, &divisor);

div_result result = divide(dividend, divisor);
printf("%i %i\r\n", result.quotient, result.remainder);
}
``````

It can be seen in action here. I chose to handle negative results to be symmetrical to positive results, but with both the quotient and remainder negative.

Handling of edge cases is done with best effort. Division by zero returns the integer of highest magnitude with the same sign as the dividend (that's `INT_MIN` or `INT_MAX`), and `INT_MIN / -1` returns `INT_MAX`.

-
@ The downvoter, a reason would be appreciated! – Runer112 Mar 19 '14 at 19:15
This a good answer, and completely within spec as far as I can see. Downvoters gonna downvote I suppose. +1 from me though. – Digital Trauma Mar 19 '14 at 19:19

C#

Not exactly golfing, but IMO it's pretty easy to follow. It only uses the `/` operator after it has broken the dividend down into smaller sections. It performs division in the "old" way. For example, for `1907 / 12`, it takes `19` and divides it by `12`, then carries the remainder `7` over, divides `70` (from `707`) by `12`, etc.

``````string divisor = "12";
string dividend = "1907";
string output = "";
do
{
double dd = Convert.ToDouble(dividend.Substring(0, divisor.Length));
double dr = Convert.ToDouble(divisor);
if (dd >= dr)
{
string s = (dd / dr).ToString();
output += s.Substring(0, s.Contains(".") ? s.IndexOf(".") : s.Length);
dividend = dd % dr + dividend.Substring(divisor.Length);
}
else
{
double d2 = Convert.ToDouble(dividend.Substring(0, divisor.Length + 1));
string s = (d2 / dr).ToString();
output += s.Substring(0, s.Contains(".") ? s.IndexOf(".") : s.Length);
dividend = d2 % dr + dividend.Substring(divisor.Length + 1);
}
} while (Convert.ToDouble(dividend) >= Convert.ToDouble(divisor))
for (int i = 0; i < dividend.Length - 1; i++ )
if (dividend[i].ToString() == "0") output += "0";
dividend = Convert.ToInt32(dividend).ToString();
Console.WriteLine("result: " + output + " r." + dividend);
``````
-

D

Horribly roundabout method that has more steps than is probably necessary to divide a number, but there you are.

``````import std.stdio;
import std.traits : isIntegral, isUnsigned;
import std.conv   : to;

TNum divide( TNum )( TNum dividend, TNum divisor, out TNum remainder ) if( isIntegral!TNum )
{
TNum quot = 0,
rem  = dividend,
prod = divisor,
t    = 1,
max  = ( ( TNum.sizeof * 8 ) - 1 ) ^^ 2;

while( t < max  && prod < rem )
{
prod = prod * 2;
t    = t    * 2;
}

while( t >= 1 )
{
if( prod <= rem )
{
quot = quot + t;
rem  = rem - prod;
}

static if( isUnsigned!TNum )
{
prod >>>= 1;
t    >>>= 1;
}
else
{
prod >>= 1;
t    >>= 1;
}
}

remainder = rem;
return quot;
}

void main( string[] args )
{
if( args.length < 3 )
return;

long dividend  = args[1].to!long;
long divisor   = args[2].to!long;
long remainder = 0;
long result    = divide( dividend, divisor, remainder );

if( remainder == 0 )
"%s / %s = %s".writefln( dividend, divisor, result );
else
"%s / %s = %s (r %s)".writefln( dividend, divisor, result, remainder );
}
``````

Obviously `/` appears in the code, but it's in a string and is just for output. There's no string interpolation in D, so it's not diving anything.

-

Python

``````def divide(a, b):
q = 0
while a >= b:
a -= b
q += 1
return (q, a)
``````
-
This is just the same as the C answer by Kninnug – ace Mar 19 '14 at 17:30
Too right you are, I don't know C so I missed that. Have given him an upvote. – justinfay Mar 19 '14 at 17:34

64 characters in Ruby

``````def d a,b;x=0;while((x+1)*b<=a);x+=1;end;puts"#{x} #{a-x*b}";end
``````

Example:

``````pry(main)> d 31,6
5 1
=> nil
``````
-
This looks identical to the answers by Kninnug and justinfay? (It's shorter of course) – Martin Ender Mar 20 '14 at 19:23
Oh... I didn't know we had to have a unique approach. I just wanted to write a super short one. – Kyle Macey Mar 20 '14 at 19:25
No that's fair enough. I was just wondering whether I overlooked something else that sets this answer apart from the other two (except its shortness). Although neither of these three answers technically implements long division. ;) – Martin Ender Mar 20 '14 at 19:27
Oh, well. It was fun to write either way. – Kyle Macey Mar 20 '14 at 19:28

C 371 with whitespaces

Includes cases for div by zero and divisor<0. Uses subtraction loop.

``````#include <stdio.h>
int a, b, n, r;
void e(int i, int j){ printf("Output: %d %d\n", i, j); }
void g()
{
if (scanf_s("%d %d", &a, &b))
{
r = 1;
if (b < 0){ r = -1; b = r*b; }
if (!b) e(0, 0);
else{
if (b>a){
n = 0;
}
else{
n = 1;
while ((a -= b) >= b){
n++;
}

}
e(r*n, a);
}
}
}

int main(){ g();}
``````
-

Brainfuck

works only for numbers between 1 and 9

Do not fit the rules, so I don't expect to win but answers in brainfuck are always awesome.

``````++++++++>,>,<<[>------>------<<-]>[->-[>+>>]>[+[-<+>]>+>>]<<<<<]++++++++[>>++++++>++++++<<<-]>>>.<.
``````

Based on `divmod` method

Test it here (and try to change input) : http://ideone.com/9L2yYf

Some tests :

74 returns 13
82 returns 40
92 returns 41

-

Edited:170 with Excel VBA:

``````Sub Long_Div(n As Integer, d As Integer)
j = 1
If d <> 0 Then
If (n * d) < 0 Then
j = -1
End If
Do While (Abs(n) >= Abs(d))
n = Abs(n) - Abs(d)
i = i + 1
Loop

MsgBox i * j & " " & n
Else:
MsgBox "can't divide by zero"
End If
End Sub
``````
-

C

Sorry for the bulky code, I am still a noob. The idea is to grab the first piece of bits from n such that k < bits, then extract each bit of n from that point on and update remainder and quotient along the way.

``````#include <stdio.h>

unsigned int rightMostBit(unsigned int n){
int position=31;
position-=1;
}
return position;
}

unsigned int extractBits(unsigned int n, unsigned int start, unsigned int end){
for(int i=start;i<end;i++){
}
return  ((mask &  n) >> start);
}

void longDivision(unsigned int n, unsigned int k)
{
unsigned int q=0;
while(k>r && tail>=0){
tail-=1;
}

unsigned int pointMask= 0x1 << tail;

while(pointMask>0) //scan all bits of n
{
if(k<= r){ //If k less than r, we can do division
r-= k ; //subtraction
q=q << 1; //make space
q = q | 0x1;  //add a 1 to quotient
}else{
q=q << 1; //make space
q= q | 0x0; //k > r, so add 0 to quotient
}