Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 16:02
4  
@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 at 16:22
    
please explain the requirement in simple words (sorry, I am not so good at english !) –  Mukul Kumar Mar 19 at 16:36
5  
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. –  Quincunx Mar 19 at 18:19
4  
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 at 18:50

13 Answers 13

up vote 10 down vote accepted

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.

share|improve this answer
    
This one is good! –  Mukul Kumar Mar 19 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 ints 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;
}
share|improve this answer
    
Not really long division, but I like it. :) +1 –  Martin Büttner Mar 19 at 16:57
    
-1, this is a popularity contest, not a code golf contest, so this is just simply bad code –  ASKASK Mar 19 at 17:47
6  
@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 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...

share|improve this answer
1  
Hurray (and +1) for dd! –  Kninnug Mar 19 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.

share|improve this answer

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.

share|improve this answer
3  
@ The downvoter, a reason would be appreciated! –  Runer112 Mar 19 at 19:15
1  
This a good answer, and completely within spec as far as I can see. Downvoters gonna downvote I suppose. +1 from me though. –  DigitalTrauma Mar 19 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);
share|improve this answer

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.

share|improve this answer

Python

def divide(a, b):
    q = 0
    while a >= b:
       a -= b
       q += 1
    return (q, a)
share|improve this answer
    
This is just the same as the C answer by Kninnug –  ace Mar 19 at 17:30
    
Too right you are, I don't know C so I missed that. Have given him an upvote. –  justinfay Mar 19 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
share|improve this answer
    
This looks identical to the answers by Kninnug and justinfay? (It's shorter of course) –  Martin Büttner Mar 20 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 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 Büttner Mar 20 at 19:27
    
Oh, well. It was fun to write either way. –  Kyle Macey Mar 20 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();}
share|improve this answer

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

share|improve this answer

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
share|improve this answer

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);
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.