Implement arbitrary precision division

Question

Implement a function divide(int a, int b, int c) that prints the base 10 value of a/b. without using any floating point math nor BigInteger/BigDecimal or equivalent libraries whatsoever. At least c accurate characters within the set of 0123456789. must be printed, except for the (possible) exception in point 4 below.

1. a and b may be any 32 bit integers. Update: If, for golfing purposes, you would like to have input be 64 bit primitives that is okay, but you do not need to support the whole 64 bit range of data.
2. You do not need to check that c is positive (though hopefully your program does not crash) if it's not.
3. The minimum supported upper bound for c is 500. It is okay if your program does not support values of c above 500, but it is also okay if it does.
4. For numbers that divide evenly, it is your choice whether to print extra zeroes (based on the value of c) or nothing.
5. You do not need to be able to use the function to do any further tasks with the quotient, the only goal is printing.
6. For numbers between -1 and 1, it is your choice whether to print a leading 0. However, this is the only scenario where printing a leading zero is acceptable, and you may only print one such zero.
7. You may use any rounding / floor / ceil logic you prefer for the last decimal place.
8. For a negative answer, you must print a leading -. This does not count towards c. However, it is your choice if you wish to print , +, or nothing for a positive answer.
9. Integer division and integer modulus are both allowed. However, keep in mind that you are restricted to primitives, unless you choose to implement your own BigInteger/BigDecimal library which counts against your code length.
10. You do not need to handle b being 0, though you can if you want. Your program may enter an infinite loop, or crash, if b=0, and you will not be penalized.
11. Slight rule change per comment. To make sure the playing field is level, while a and b are guaranteed to be 32 bit integers, you may use 64 bit long integers. If your chosen language goes beyond 64 bit integers as a primitive, you may not at any point use that functionality (pretend it is capped at 64 bits).
12. Another point that is unclear (it shouldn't change any of the current valid answers, though): while c may be interpreted as either the number of printed characters or the number of spaces after the decimal, your program must use c somehow in a relevant way to decide how many characters to print. In other words, divide(2,3,2) should be much shorter output than divide(2,3,500); it is not okay to print 500 characters without regard to c.
13. I actually don't care about the name of the function. d is okay for golfing purposes.

Input

Both a function call and reading from stdin are accepted. If you read from stdin, any character not in the set [-0123456789] is considered an argument delimiter.

Output

Characters to stdout as described above.

Example

for divide(2,3,5), all of the following are acceptable outputs:

0.666
0.667
.6666
.6667
 0.666
 0.667
 .6666
 .6667
+0.666
+0.667
+.6666
+.6667

Another example: for divide(371,3,5) the following are all acceptable outputs:

123.6
123.7
 123.6
 123.7
+123.6
+123.7
123.66666
123.66667
 123.66666
 123.66667
+123.66666
+123.66667

And for divide(371,-3,5) the following are are all acceptable:

-123.6
-123.7
-123.66666
-123.66667

• Jonathan Van Matre: For the sake of a level playing field, it might be wise to give a specific maximum bit length that can be used (primitive or otherwise) unless you roll your own larger implementation, because a) in some languages bit length of primitives varies depending on the underlying architecture and b) in some languages big number types are primitives.
• durron597: @JonathanVanMatre Added rule 11 per your comment
• Howard: How do you count accurate digits? In your example I see three or four but never five as the last argument indicates.
• durron597: @Howard, if you did 92,3,5 the answer would be, for example, 30.67
• izabera: btw 370/3=123.333 lol

Answer 1

C, (削除) 98 (削除ここまで) (削除) 95 (削除ここまで) 89

d(a,b,c){if(a>0^b>0)a=-a,printf("-");for(printf("%d.",a/b);c--;putchar(a/b+48))a=a%b*10;}

prints c digits after the .

example output:

d(2,3,5);
0.66666
d(-2,3,5);
-0.66666
d(24352345,31412,500);
775.25611231376543995925124156373360499172290844263338851394371577740990704189481726728638736788488475741754743410161721635043932255189099707118298739335285878008404431427479943970457150133706863618999108620909206672609193938622182605373742518782630841716541449127721889723672481854068508850120972876607665860180822615560932127849229593785814338469374761237743537501591748376416656055010823888959633261174073602444925506175983700496625493441996689163377053355405577486310963962816757926906914554947153953
d(-77,12346463,500);
-0.00000623660395693892250760399962321192717298873369644407471192356871761572524859953818352673150196943043525906974329409159530142357369879940514137530724386409289850866600418273638369142644334656816288195250736992448768525852302801215214430238036593962173620088603513411087855687900251270343579371679160258286118056645048869461642577311412993340683886551152342172814999729072204727783171585254821563066280601982932277851559592411203111368818745903178910429650985873444078680671541315111866451144752954

should work for -2147483647<=a<=2147483647, same for b. handling the - was a pain.

online version: ideone

• TheConstructor: Does this work for a being -2147483648? Don't know c compilers well enough to tell which integer-type is assigned to your parameters.
• izabera: thanks for pointing it out. it works correctly for -2147483647<=a<=2147483647, same for b. there's a problem when a=-2147483648 and b is positive due to a=-a.
• Thomas: I tried but eventually got essentially the same solution as you. You can save one character by realizing that printf("-") returns 1.

Answer 2

Java, 92/128

void d(long a,int b,int c){if(a<0^b<0){a=-a;p('-');}for(p(a/b+".");c>0;c--)p((a=a%b*10)/b);}<T>void p(T x){System.out.print(x);}

I had to improvise so that a or b could be -2147483648 as positive 32-bit integers only count towards 2147483647, that's why a became a long. There could be a better way of handling negative results, but I know none (doubles would probably get this to work for abs(a) < abs(b) as they have -0 but only ones' complement would keep the precision).

Why two byte numbers? I needed 92 bytes for the calculation and 36 for the print-helper (System.out.print sucks; generally Java isn't that golfy).

public class Div {
 void d(long a, int b, int c) {
 if (a < 0 ^ b < 0) {
 a = -a;
 p('-');
 }
 for (p(a / b + "."); c > 0; c--) {
 p((a = a % b * 10) / b);
 }
 }
 <T> void p(T x) {
 System.out.print(x);
 }
 public static void main(String[] args) {
 final Div div = new Div();
 div.d(12345, 234, 20);
 div.p('\n');
 div.d(-12345, 234, 20);
 div.p('\n');
 div.d(234, 234, 20);
 div.p('\n');
 div.d(-234, 234, 20);
 div.p('\n');
 div.d(234, 12345, 20);
 div.p('\n');
 div.d(234, -12345, 20);
 div.p('\n');
 div.d(-234, 12345, 20);
 div.p('\n');
 div.d(-234, -12345, 20);
 div.p('\n');
 div.d(-2147483648, 2147483647, 20);
 div.p('\n');
 div.d(2147483647, -2147483648, 20);
 div.p('\n');
 }
}

The method basically exercises what most of us learned at school to generate the requested decimal digits.

• durron597: Official ruling: I would say that ignoring Integer.MIN_VALUE is not okay but that long as input is fine.
• durron597: That's a lot shorter. Nicely done.
• TheConstructor: @durron597 thank you. Still the strict typing and System.out make Java feel bulky ;-) Still a good feeling, that there already are longer answers posted.
• TheConstructor: @durron597 you specifically asked for a function so I tought it would not count. If I had to use imports than probably yes.
• TheConstructor: At least there is no $ to every variable ;-)

Answer 3

PHP, 108

function d($a,$b,$c){$a*$b<0&&$a*=-print'-';for($p='.';$c--;$a.=0,print$i.$p,$p='')$a-=$b*$i=($a-$a%$b)/$b;}

It works by simply outputting the quotient of a / b during a loop of c steps, a becoming the remainder multiplied by 10 at each iteration.

DEMO

• TheConstructor: Produces strange results when a or b are negative
• Razvan: I fixed the bug for negative numbers. Thanks!
• TheConstructor: Just found a 112 version of your code: function d($a,$b,$c){if($a*$b<0)$a*=-print'-';for($p='.';$c--;$a*=10,$p=''){$a-=$b*$i=($a-$a%$b)/$b;echo$i.$p;}} see return value
• Razvan: Thanks. I even updated your version and managed to win an extra 1 byte.

Answer 4

Python 111

f=lambda a,b,c:'-'[a*b>=0:]+'%s'%reduce(lambda(d,r),c:(d%c*10,r+`d/c`+'.'[r!='':],),[abs(b)]*c,(abs(a),''))[-1]

This solution does not violates any of the stated rules.

• The Fifth Marshal: You can save 2 bytes by deleting f=

Answer 5

C: 72 characters

d(a,b,c){for(printf("%d.",a/b);c--;putchar((a=abs(a)%b*10)/abs(b)+48));}

It almost entirely does what it is supposed to do. However it will as some of the other answers here give wonky values or fail for d(-2147483648,b,c) and d(a,-2147483648,c) since the absolute value of -2147483648 is out of bounds for a 32-bit word.

Answer 6

Perl, no arithmetic, 274 bytes

This is Euclidean long division, likely to consume an unusual amount of memory. The closest it gets to math on floating-point numbers is in using bit operations to parse them.

sub di{($v,$i,$d,$e)=(0,@_);($s,$c,$j)=$i=~s/-//g;$s^=$d=~s/-//g;
$i=~s/\.(\d+)/$j=1,ドル""/e;$d=~s/\.(\d+)/$c=1,ドル""/e;
$z=0.x+length($c|$j);$i.=$j|$z;$d.=$c|$z;
($e,$m,$z,$t)=(1.x$e,0.x$i,0.x$d,"-"x($s&1));
for(;$e;$t.="."x!$v,$v=chop$e){$t.=$m=~s/$z//g||0;$m="$m"x10}
print"$t\n"}

---

Examples:

di(-355,113,238);
di(1.13,355,239);
di(27942,19175,239);
di(1,-90.09,238);
di("--10.0","----9.801",239);
di(".01",".200",239);

Output:

-3.141592920353982300884955752212389380530973451327433628318
584070796460176991150442477876106194690265486725663716814159
292035398230088495575221238938053097345132743362831858407079
646017699115044247787610619469026548672566371681415929203539
0.0031830985915492957746478873239436619718309859154929577464
788732394366197183098591549295774647887323943661971830985915
492957746478873239436619718309859154929577464788732394366197
183098591549295774647887323943661971830985915492957746478873
1.4572099087353324641460234680573663624511082138200782268578
878748370273794002607561929595827900912646675358539765319426
336375488917861799217731421121251629726205997392438070404172
099087353324641460234680573663624511082138200782268578878748
-0.011100011100011100011100011100011100011100011100011100011
100011100011100011100011100011100011100011100011100011100011
100011100011100011100011100011100011100011100011100011100011
100011100011100011100011100011100011100011100011100011100011
1.0203040506070809101112131415161718192021222324252627282930
313233343536373839404142434445464748495051525354555657585960
616263646566676869707172737475767778798081828384858687888990
919293949596979900010203040506070809101112131415161718192021
0.0500000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000

Answer 7

Ruby, 178

def d(a,b,c)
 n=(a<0)^(b<0)
 a=-a if n
 m=a/b-b/a
 l=m.to_s.size-1
 g=(a*10**(10+c)/b).to_s
 f=m<0?"."+"0"*(l-1)+g[0..c-l-1] : g[0..l]+"."+g[l+1..c-2]
 p n ? "-"+f : f
end

Online version for testing.

The trick is to multiply a with a pretty high number, so the result is just an integer multiple of the floating point operation. Then the point and the zeros have to be inserted at the right place in the resulting string.

• durron597: Does this work for c bigger than 350?
• David Herrmann: I tested it with c=1000 - the code gave me an answer, maybe I should check the actual result though...
• durron597: does g get beyond 64 bits for large c? Edit: I think you are implicitly using BigInteger here
• durron597: Err, g is a string, but before you call to_s you've created a number in memory that is beyond 64 bits in size
• David Herrmann: That is understandable - and makes the task more challenging (and interesting)! Is it better to delete the answer or leave it for others to have an example of how not to implement the task?

Answer 8

python 92 bytes:

def d(a,b,c):c-=len(str(a/b))+1;e=10**c;a*=e;a/=b;a=str(a);x=len(a)-c;return a[:x]+'.'+a[x:]

i think some more golfing is possible.....

• durron597: does e get beyond 64 bits for large c? Edit: I think you are implicitly using BigInteger here.
• Maltysen: @durron597 i highly doubt that. It goes to BigInt(Long in python) but 2**45 is 48 bits. Is that enough presicion?? Also, python has NO primitives so...
• durron597: If a=5 and c=400 then after e=10**c, in hex, the number is 333 digits long. It starts 8889e7dd7f43fc2f7900bc2eac756d1c4927a5b8e56bbcfc97d39bac6936e648180f47d1396bc905a47cc481617c7... this is more than 64 bits.
• Maltysen: @durron597 400... do i need that
• durron597: Yes rule 3 says you need to support up to at least 500... I was trying to prevent this (imo trivial) solution.

Answer 9

C 83

d(a,b,c){printf("%d.",a/b);for(a=abs(a),b=abs(b);c--&&(a=a%b*10);)putchar(a/b+48);}

Same Idea that I used in my python implementation

• durron597: Very nice! However, it crashes on d(-2147483648,-1,10)