Divide Two Numbers Using Long Division [closed]

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

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
• Actually i would divide the Sheep into group of size b. If i have less than b sheeps left thats the remainder. – Lee Oct 18 '19 at 12:43

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 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 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#

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);


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 – user12205 Mar 19 '14 at 17:30
• Too right you are, I don't know C so I missed that. Have given him an upvote. – Justin Fay Mar 19 '14 at 17:34

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.

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
}
r=((r << 1) | 1);
}else{
r=((r << 1) | 0);
}
}
}
printf("quotient: %d, remainder: %d \n",q,r);
}


Python

• Go as Precise as you want or can handle

• Find out the repetitiveness from the quotient

• Fast

Late to the party but here you go:

def ManualDivision(Dividend, Divisor, acQPrecision, BreakOnRepetitive):

Repetitive = False
RepetitiveIndex = 0
bcQComplete = False
acQComplete = False
bcQ = ''   #before comma Quotient
acQ = ''   #after comma Quotient
history = []
a = 0
b = 0

while (not bcQComplete or not acQComplete):
if not bcQComplete:
for digit in map(int, str(Dividend)):
a = int(str(a) + str(digit))
if a in history:
if not Repetitive:
Repetitive = True
RepetitiveIndex = len(history) - len(bcQ)
if BreakOnRepetitive:
break
else:
history.append(a)
if a < Divisor:
b = 0
bcQ += '0'
else:
pQ = 0
result = a - Divisor
while result >= 1:
pQ += 1
result -= Divisor
b = pQ * Divisor
bcQ += str(pQ)
a -= b
bcQComplete = True

if not acQComplete:
acQPrecision -= 1
if acQPrecision <= 0:
acQComplete = True
a = int(str(a) + str('0'))
if a in history:
if not Repetitive:
Repetitive = True
RepetitiveIndex = len(history) - len(bcQ)
if BreakOnRepetitive:
break
else:
history.append(a)
if a < Divisor:
b = 0
acQ += '0'
else:
pQ = 0
result = a - Divisor
while result >= 1:
pQ += 1
result -= Divisor
b = pQ * Divisor
acQ += str(pQ)
a-=b
return '{0}.{1} \nRepetitive: {2} from position {3} acQ \nHistory:{4}'.format(bcQ, acQ, Repetitive, RepetitiveIndex, history)


Result

Quotient = ManualDivision(91,256,100,False) #Dividend = 91, Divisor = 256, precision= 100, breakonrepetitive=False
print(Quotient)


00.3554687499999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

Repetitive: True from position 9 acQ

History:[9, 91, 910, 1420, 1400, 1200, 1760, 2240, 1920, 1280, 2560]

Python

Using recursion

def divide(a, b, q=0):
if a < b:
return (q, a)
return divide(a - b, b, q+1)