Divide Two Numbers Using Long Division

Question

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

Answer 1

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.

Answer 2

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...}}

Answer 3

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.

Answer 4

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.

Answer 5

Python

def divide(a, b):
    q = 0
    while a >= b:
       a -= b
       q += 1
    return (q, a)

Answer 6

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

Answer 7

Python

Advantages:

• 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]

Answer 8

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.

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

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){
   unsigned int bitmask=0x1 << 31;
   int position=31;
   while((bitmask & n)==0 && position>=0){
        position-=1;
        bitmask = bitmask>>1;
   }
   return position;
}

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

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

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

Answer 13

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

Answer 14

Python

Using recursion

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