15
\$\begingroup\$

Implement a division algorithm in your favourite language which handles integer division. It need only handle positive numbers - but bonus points if it handles negative and mixed-sign division, too. Results are rounded down for fractional results.

The program may not contain the /, \, div or similar operators. It must be a routine which does not use native division capabilities of the language.

You only need to handle up to 32-bit division. Using repeated subtraction is not allowed.

Input

Take two inputs on stdin separated by new lines or spaces (your choice)

740 
2

Output

In this case, the output would be 370.

The solution which is the shortest wins.

\$\endgroup\$
  • \$\begingroup\$ is 740,2 also permitted for the input? ie comma separated? \$\endgroup\$ – gnibbler Feb 4 '11 at 10:44
  • \$\begingroup\$ "Results are rounded down for fractional results" - ok, so apparently the input can also result in a non-integer number... But what about the divisor being larger than the divided (say, 5 and 10) - is that permitted or not? \$\endgroup\$ – Aurel Bílý Feb 4 '11 at 12:13
  • \$\begingroup\$ @gnibber That would be fine, but make it clear in the program description. \$\endgroup\$ – Thomas O Feb 4 '11 at 12:23
  • 2
    \$\begingroup\$ is using exponentials and other math functions really allowed? they use division behind the scenes, because many solutions are doing ab⁻¹ \$\endgroup\$ – Ming-Tang Feb 5 '11 at 7:12
  • 2
    \$\begingroup\$ this is shortest-time but I haven't seen anyone time the code \$\endgroup\$ – phuclv Jun 9 '14 at 13:45

31 Answers 31

27
\$\begingroup\$

Python - 73 chars

Takes comma separated input, eg 740,2

from math import*
x,y=input()
z=int(exp(log(x)-log(y)))
print(z*y+y<=x)+z
\$\endgroup\$
  • 5
    \$\begingroup\$ This, my friend, is CLEVER \$\endgroup\$ – Aamir Feb 4 '11 at 11:25
  • \$\begingroup\$ Output for "740,2" is 369. Is this correct? \$\endgroup\$ – Eelvex Feb 17 '11 at 23:23
  • \$\begingroup\$ @Eelvex, should have been <=, fixed it and made it shorter :) \$\endgroup\$ – gnibbler Feb 17 '11 at 23:43
14
\$\begingroup\$

JavaScript, 61

A=Array,P=prompt,P((','+A(+P())).split(','+A(+P())).length-1)

This makes a string the length of the dividend ,,,,,, (6) and splits on the divisor ,,, (3), resulting in an array of length 3: ['', '', ''], whose length I then subtract one from. Definitely not the fastest, but hopefully interesting nonetheless!

\$\endgroup\$
  • 2
    \$\begingroup\$ My favorite implementation here so far. Congrats for the cool code! \$\endgroup\$ – Thomas Eding Aug 12 '11 at 23:14
  • \$\begingroup\$ I tried to make it a little shorter. A=Array,P=prompt,P((''+A(+P())).split(','+A(+P())).length) \$\endgroup\$ – pimvdb Aug 30 '11 at 19:54
10
\$\begingroup\$

JavaScript - 36 characters

p=prompt;alert(p()*Math.pow(p(),-1))
\$\endgroup\$
  • 5
    \$\begingroup\$ Replacing alert with p will net you some extra characters. :) \$\endgroup\$ – Casey Chu Aug 9 '11 at 3:00
9
\$\begingroup\$

Mathematica: 34 chars

Solves symbolically the equation (x a == b)

Solve[x#[[1]]==#[[2]],x]&@Input[]
\$\endgroup\$
  • 2
    \$\begingroup\$ 23 chars, Solve[x#==#2]&@@Input[] \$\endgroup\$ – chyanog Jul 21 '13 at 10:42
8
\$\begingroup\$

Python - 72 chars

Takes comma separated input, eg 740,2

x,y=input();z=0
for i in range(32)[::-1]:z+=(1<<i)*(y<<i<=x-z*y)
print z
\$\endgroup\$
8
\$\begingroup\$

Python, 37

Step 1. Convert to unary.

Step 2. Unary division algorithm.

print('1'*input()).count('1'*input())
\$\endgroup\$
7
\$\begingroup\$

Python - 41 chars

Takes comma separated input, eg 740,2

x,y=input();z=x
while y*z>x:z-=1 
print z
\$\endgroup\$
  • 1
    \$\begingroup\$ This, in some cases, is worse than continuously subtracting. e.g., input is 5,4. while loop will run 4 times while in case of subtraction, we will only have to subtract once. \$\endgroup\$ – Aamir Feb 4 '11 at 11:20
6
\$\begingroup\$

Python, 70

Something crazy I just thought (using comma separated input):

from cmath import*
x,y=input()
print round(tan(polar(y+x*1j)[1]).real)

If you accept small float precision errors, the round function can be dropped.

\$\endgroup\$
4
\$\begingroup\$

Yabasic - 17 characters

input a,b:?a*b^-1
\$\endgroup\$
3
\$\begingroup\$

PHP - 82 characters (buggy)

$i=fgets(STDIN);$j=fgets(STDIN);$k=1;while(($a=$j*$k)<$i)$k++;echo($a>$i?--$k:$k);

This is a very simple solution, however - it doesn't handle fractions or different signs (would jump into an infinite loop). I won't go into detail in this one, it is fairly simple.

Input is in stdin, separated by a new line.

PHP - 141 characters (full)

$i*=$r=($i=fgets(STDIN))<0?-1:1;$j*=$s=($j=fgets(STDIN))<0?-1:1;$k=0;$l=1;while(($a=$j*$k)!=$i){if($a>$i)$k-=($l>>=2)*2;$k+=$l;}echo$k*$r*$s;

Input and output same as the previous one.

Yes, this is almost twice the size of the previous one, but it:

  • handles fractions correctly
  • handles signs correctly
  • won't ever go into an infinite loop, UNLESS the second parameter is 0 - but that is division by zero - invalid input

Re-format and explanation:

$i *= $r = ($i = fgets(STDIN)) < 0 ? -1 : 1;
$j *= $s = ($j = fgets(STDIN)) < 0 ? -1 : 1;
                                    // First, in the parentheses, $i is set to
                                    // GET variable i, then $r is set to -1 or
                                    // 1, depending whether $i is negative or
                                    // not - finally, $i multiplied by $r ef-
                                    // fectively resulting in $i being the ab-
                                    // solute value of itself, but keeping the
                                    // sign in $r.
                                    // The same is then done to $j, the sign
                                    // is kept in $s.

$k = 0;                             // $k will be the result in the end.

$l = 1;                             // $l is used in the loop - it is added to
                                    // $k as long as $j*$k (the divisor times
                                    // the result so far) is less than $i (the
                                    // divided number).

while(($a = $j * $k) != $i){        // Main loop - it is executed until $j*$k
                                    // equals $i - that is, until a result is
                                    // found. Because a/b=c, c*b=a.
                                    // At the same time, $a is set to $j*$k,
                                    // to conserve space and time.

    if($a > $i)                     // If $a is greater than $i, last step
        $k -= ($l >>= 2) * 2;       // (add $l) is undone by subtracting $l
                                    // from $k, and then dividing $l by two
                                    // (by a bitwise right shift by 1) for
                                    // handling fractional results.
                                    // It might seem that using ($l>>=2)*2 here
                                    // is unnecessary - but by compressing the
                                    // two commands ($k-=$l and $l>>=2) into 1
                                    // means that curly braces are not needed:
                                    //
                                    // if($a>$i)$k-=($l>>=2)*2;
                                    //
                                    // vs.
                                    //
                                    // if($a>$i){$k-=$l;$l>>=2;}

    $k += $l;                       // Finally, $k is incremented by $l and
                                    // the while loop loops again.
}

echo $k * $r * $s;                  // To get the correct result, $k has to be
                                    // multiplied by $r and $s, keeping signs
                                    // that were removed in the beginning.
\$\endgroup\$
  • \$\begingroup\$ You used a division operator in this one, you might get away with a bit shift though. ;) \$\endgroup\$ – Thomas O Feb 4 '11 at 18:12
  • \$\begingroup\$ @Thomas O yeah... I noticed it now... I was actually thinking about a bit shift (when I changed it to /=2 instead of /=10) - but it was one more char... Guess I'll have to use it anyway... Btw that is not division at all :D. \$\endgroup\$ – Aurel Bílý Feb 4 '11 at 18:52
  • \$\begingroup\$ The question says you need to use stdin, which PHP does have support for. \$\endgroup\$ – Kevin Brown Feb 5 '11 at 2:08
  • \$\begingroup\$ @Bass5098 Aaahhh... Oh well, gained 4 chars... Fixed. \$\endgroup\$ – Aurel Bílý Feb 5 '11 at 17:07
3
\$\begingroup\$

Ruby 1.9, 28 characters

(?a*a+?b).split(?a*b).size-1

Rest of division, 21 characters

?a*a=~/(#{?a*b})\1*$/  

Sample:

a = 756
b = 20
print (?a*a+?b).split(?a*b).size-1  # => 37
print ?a*a=~/(#{?a*b})\1*$/         # => 16

For Ruby 1.8:

a = 756
b = 20
print ('a'*a+'b').split('a'*b).size-1  # => 37
print 'a'*a=~/(#{'a'*b})\1*$/          # => 16
\$\endgroup\$
  • \$\begingroup\$ NoMethodError: private method `split' called for 69938:Fixnum \$\endgroup\$ – rkj Aug 26 '11 at 8:27
  • \$\begingroup\$ @rkj, Sorry, Ruby 1.9 only. To run on Ruby 1.8 you must do ('a'*a+'b').split('a'*b).size-1, 3 characters bigger. \$\endgroup\$ – LBg Aug 29 '11 at 0:30
3
\$\begingroup\$

APL (6)

⌊*-/⍟⎕

/ is not division here, but foldr. i.e, F/a b c is a F (b F c). If I can't use foldr because it's called /, it can be done in 9 characters:

⌊*(⍟⎕)-⍟⎕

Explanation:

  • : input()
  • ⍟⎕: map(log, input())
  • -/⍟⎕: foldr1(sub, map(log, input()))
  • *-/⍟⎕: exp(foldr1(sub, map(log, input())))
  • ⌊*-/⍟⎕: floor(exp(foldr1(sub, map(log, input()))))
\$\endgroup\$
2
\$\begingroup\$

PHP, 55 characters

<?$a=explode(" ",fgets(STDIN));echo$a[0]*pow($a[1],-1);

Output (740/2): http://codepad.viper-7.com/ucTlcq

\$\endgroup\$
  • \$\begingroup\$ 44 chars: <?$a=fgetcsv(STDIN);echo$a[0]*pow($a[1],-1); Just use a comma instead of a space to separate numbers. \$\endgroup\$ – jdstankosky May 10 '13 at 17:28
2
\$\begingroup\$

Scala 77

def d(a:Int,b:Int,c:Int=0):Int=if(b<=a)d(a-b,b,c+1)else c
d(readInt,readInt)
\$\endgroup\$
2
\$\begingroup\$

Haskell, 96 characters

main=getLine>>=print.d.map read.words
d[x,y]=pred.snd.head.filter((>x).fst)$map(\n->(n*y,n))[0..]

Input is on a single line.

The code just searches for the answer by taking the divisor d and multiplying it against all integers n >= 0. Let m be the dividend. The largest n such that n * d <= m is picked to be the answer. The code actually picks the least n such that n * d > m and subtracts 1 from it because I can take the first element from such a list. In the other case, I would have to take the last, but it's hard work to take the last element from an infinite list. Well, the list can be proven to be finite, but Haskell does not know better when performing the filter, so it continues to filter indefinitately.

\$\endgroup\$
2
\$\begingroup\$

Common Lisp, 42 charaacters

(1-(loop as x to(read)by(read)counting t))

Accepts space or line-separated input

\$\endgroup\$
2
\$\begingroup\$

Bash, 72 64 characters

read x y;yes ''|head -n$x>f;ls -l --block-size=$y f|cut -d\  -f5

Output an infinite number of newlines, take the first x, put them all into a file called f, then get the size of f in blocks the size of y. Took manatwork's advice to shave off eight characters.

\$\endgroup\$
  • \$\begingroup\$ As “Take two inputs on stdin separated by new lines or spaces (your choice)”, better choose the later, the space separated values. In which case you can write read x y. With a few more spaces removed can be reduced to 64 characters: pastebin.com/Y3SfSXWk \$\endgroup\$ – manatwork Sep 20 '13 at 8:20
1
\$\begingroup\$

Python - 45 chars

Takes comma separated input, eg 740,2

x,y=input()
print-1+len((x*'.').split('.'*y))
\$\endgroup\$
1
\$\begingroup\$

Python, 94 characters

A recursive binary search:

a,b=input()
def r(m,n):return r(m,m+n>>1)if n*b>a else n if n*b+b>a else r(n,2*n)
print r(0,1)
\$\endgroup\$
1
\$\begingroup\$

Python, 148

Other solutions may be short, but are they web scale?

Here's an elegant, constant-time solution that leverages the power of the CLOUD.

from urllib import*
print eval(urlopen('http://tryhaskell.org/haskell.json?method=eval&expr=div%20'+raw_input()+'%20'+raw_input()).read())['result']

Did I mention it also uses Haskell?

\$\endgroup\$
0
\$\begingroup\$

Python, 46 bytes

Nobody had posted the boring subtraction solution, so I could not resist doing it.

a,b=input()
i=0
while a>=b:a-=b;i+=1
print i
\$\endgroup\$
0
\$\begingroup\$

Smalltalk, Squeak 4.x flavour

define this binary message in Integer:

% d 
    | i |
    d <= self or: [^0].
    i := self highBit - d highBit.
    d << i <= self or: [i := i - 1].
    ^1 << i + (self - (d << i) % d)

Once golfed, this quotient is still long (88 chars):

%d|i n|d<=(n:=self)or:[^0].i:=n highBit-d highBit.d<<i<=n or:[i:=i-1].^1<<i+(n-(d<<i)%d)

But it's reasonnably fast:

[0 to: 1000 do: [:n |
    1 to: 1000 do: [:d |
        self assert: (n//d) = (n%d)]].
] timeToRun.

-> 127 ms on my modest mac mini (8 MOp/s)

Compared to regular division:

[0 to: 1000 do: [:n |
    1 to: 1000 do: [:d |
        self assert: (n//d) = (n//d)]].
] timeToRun.

-> 31 ms, it's just 4 times slower

I don't count the chars to read stdin or write stdout, Squeak was not designed for scripting.

FileStream stdout nextPutAll:
    FileStream stdin nextLine asNumber%FileStream stdin nextLine asNumber;
    cr

Of course, more stupid repeated subtraction

%d self>d and:[^0].^self-d%d+1

or plain stupid enumeration

%d^(0to:self)findLast:[:q|q*d<=self]

could work too, but are not really interesting

\$\endgroup\$
0
\$\begingroup\$
#include <stdio.h>
#include <string.h>
#include <math.h>


main()
{
   int i,j,ans;
   i=740;
   j=2;

   ans = pow(10,log10(i) - log10(j));
   printf("\nThe answer is %d",ans);
}
\$\endgroup\$
0
\$\begingroup\$

DC: 26 characters

?so?se0[1+dle*lo>i]dsix1-p

I do admit that it is not the fastest solution around.

\$\endgroup\$
0
\$\begingroup\$

Python 54

Takes comma delimited input.

  1. Makes a string of dots of length x
  2. Replaces segments of dots of length y with a single comma
  3. Counts commas.

Words because markdown dies with a list followed by code?:

x,y=input()
print("."*x).replace("."*y,',').count(',')
\$\endgroup\$
0
\$\begingroup\$

Q, 46

{-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}

.

q){-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}[740;2]
370
q){-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}[740;3]
246
\$\endgroup\$
0
\$\begingroup\$
int divide (int num, int divideBy)
{
    int sum = 0;
    int shift = divideBy -1;
    while (num > divideBy) {
        sum += num >> shift ;
        num = (num >> shift ) + (num & divideBy);
    }
    if (num == divideBy) ++sum;
    return sum; 
}

Reference: http://www.forums.hscripts.com/viewtopic.php?f=13&t=1358

\$\endgroup\$
0
\$\begingroup\$

Python, 40 characters

print(float(input())*float(input())**-1)
\$\endgroup\$
0
\$\begingroup\$

Python, 37

x,y=input()
print len(('0'*x)[y-1::y])

Constructs a string of length x ('0'*x) and uses extended slicing to pick every yth character, starting from the index y-1. Prints the length of the resulting string.

Like Gnibbler, this takes comma separated input. Removing it costs 9 chars:

i=input
x,y=i(),i()
print len(('0'*x)[y-1::y])
\$\endgroup\$
0
\$\begingroup\$

Retina 0.7.3, 33 bytes (not competing)

The language is newer than the challenge. Takes space-separated input with the divisor first. Dividing by zero is undefined.

\d+
$*
^(.+) (\1)+.*$
$#+
.+ .*
0

Try it online

\$\endgroup\$
  • \$\begingroup\$ How do you count this as 25 bytes? If you expect unary I/O you should say so (and I think then it's 24 bytes). Not sure why you treat the 0 case separately though: retina.tryitonline.net/… \$\endgroup\$ – Martin Ender Dec 7 '16 at 22:24
  • \$\begingroup\$ It was mis-copied \$\endgroup\$ – mbomb007 Dec 7 '16 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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