# Long Division (#180)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q. 2:

1. Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2. Support Ruby Q. 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Q. 2. Until then,
please visit the temporary website at

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Long Division (#180)

Your program should take two arguments: the dividend and the divisor.
Your output should display the long division needed to determine the
quotient and remainder (if it exists). For example, if I run your
program like so:

`````` \$ ruby long_division.rb 11 4096
``````

``````     372 R4
+----
11|4096
33
--
79
77
--
26
22
--
4
``````

If there is no remainder, do not display anything after the quotient;
that is, do not display R0. As an alternative to the remainder, you
may instead calculate the decimal fraction out to N digits (e.g. use
command-line option --digits=N or similar to switch to decimal
fraction output).

## Long Division (#180)

Here is my solution

divisor,dividend = ARGV
products,bringdown,f,r,quotient = [],[],[],[],[]
(1…dividend.length).each {|x|f << dividend.unpack(“a#{x}”).join}
str = “a#{f.detect{|x| x.to_i >= divisor.to_i}.length}” +
“a1”*dividend.length
u = dividend.unpack(str).select{|x| x != “”}.map{|x| x.to_i}
products << u - u % divisor.to_i
r << u % divisor.to_i
bringdown << ((u % divisor.to_i).to_s + u.to_s).to_i
quotient << u / divisor.to_i

(0…u.length-1).each do |x|
products << bringdown[x] - bringdown[x] % divisor.to_i
r << bringdown[x] % divisor.to_i
bringdown << ((bringdown[x] % divisor.to_i).to_s + u[x+2].to_s).to_i
quotient << bringdown[x] / divisor.to_i
end

fmt = dividend.length + divisor.length + 3
print “#{quotient.join.rjust(fmt)}”
print " R#{r[-1]}\n" if r[-1] != 0
print “\n” if r[-1] == 0
print “#{(”-" * (dividend.length + 1)).rjust(fmt)}\n"
print “#{divisor} | #{dividend}\n”

fmt2 = divisor.length + 3 + f.detect{|x| x.to_i >= divisor.to_i}.length
(0…u.length).each do |x|
print “#{products[x].to_s.rjust(fmt2+x)}\n”
print “#{(”-"*divisor.length).rjust(fmt2+x)}\n"
print “#{r[x].to_s.rjust(fmt2+x)}#{u[x+1]}\n”
end

Harry

On Fri, 17 Oct 2008 08:57:01 -0500, Matthew M. wrote:

## Long Division (#180)

22

4

If there is no remainder, do not display anything after the quotient;
that is, do not display R0. As an alternative to the remainder, you may
instead calculate the decimal fraction out to N digits (e.g. use
command-line option --digits=N or similar to switch to decimal fraction
output).

class Integer
def longdiv divisor
begin
# do math
products=[]
dividends=[self] #intermediate dividends – the next number we’ll
divide
exps=[]
dividend=self
quotient=0
while dividend>=divisor
Math.log10(dividend).ceil.downto(0) do |exp|
magnitude=10**exp
trydiv,rest=dividend.divmod(magnitude)
if trydiv>=divisor
exps << exp
dividends[-1]=trydiv
quotient_digit,remainder=trydiv.divmod(divisor)
products << quotient_digitdivisor
quotient+=quotient_digit
magnitude
dividend=(remainder*magnitude+rest)
dividends << remainder
break
end
end
end

``````ensure
#danger of infinite loops, so if I have
#to hit ^C to debug one, I want to be sure to print
#what I've got so I can debug

fmtwidth=self.to_s.size+divisor.to_s.size+1
exps << 0

printf "%#{fmtwidth}d",quotient
print " R#{dividends.last}" if dividends.last > 0
puts ""
puts " "*divisor.to_s.size+"+"+"-"*self.to_s.size
puts divisor.to_s+"|"+self.to_s
i=0
while i<products.size
printf "%#{fmtwidth-exps[i]}d\n",products[i]
printf "%#{fmtwidth-exps[i]}s\n","-"*products[i].to_s.size
i+=1
printf "%#{fmtwidth-exps[i]}d\n",dividends[i]
end
puts
end

[quotient,dividend]
``````

end
end

require ‘test/unit’
require ‘stringio’

class TestLongDiv < Test::Unit::TestCase
def test_division
assert_equal [372,4],4096.longdiv(11)
assert_equal [302,4],(4096-770).longdiv(11)
assert_equal [0,100],100.longdiv(1000)

``````#the following cases showed up as problematic ones when I ran
#the big loop that follows
assert_equal 2205.divmod(10),2205.longdiv(10)
assert_equal 2442.divmod(2),2442.longdiv(2)

#are there problems I didn't think of?
1000.times do
dividend=rand(10000)
divisor=rand(50)+1
printf "%d / %d\n", dividend, divisor
assert_equal dividend.divmod(divisor),dividend.longdiv(divisor)
end
``````

end

## def test_output_format oldstdout=\$stdout begin newstdout=StringIO.new \$stdout=newstdout expected=<<OUTPUT 372 R4 ±— 11|4096 33

``````79
77
--
26
22
--
4
``````

OUTPUT
4096.longdiv(11)
\$stdout=oldstdout
assert_equal expected,newstdout.string
ensure
\$stdout=oldstdout
end
end
end

On Sun, 19 Oct 2008 10:07:34 -0500, Sebastian H. wrote:

## divisor [–base=BASE] [–remainder] BASE is the base as a decimal number Some sample output from irb: 1

7
40

divide(1,6)
36

4

divide(1,6,10,false)
0 R1
±
6|1
0

1
=> nil

I’m posting Sebastian’s solution to the newsgroup, because I don’t know
long pastie will keep the code around. Please don’t use pastebins with
ruby-talk – the code may disappear while the message sticks around,
then

#!/usr/bin/ruby

module LongDivision
module_function
def divide(dividend, divisor, base=10, decimal=true)
result = “”
division = " “*divisor.to_s(base).length
division << “+”.ljust(dividend.to_s(base).length + 1,”-") << “\n”
division << “#{divisor.to_s(base)}|#{dividend.to_s(base)}”
indent = divisor.to_s(base).length + 1
digits = dividend.to_s(base).chars.map {|d| d.to_i(base) }
quotient = 0
remainder = 0
while remainder < divisor && digits.size > 0
remainder = remainder * base + digits.shift
indent += 1
end

``````digits << nil
digits.each do |digit|
quotient = remainder / divisor
result << quotient.to_s(base)
prod = (quotient * divisor).to_s(base)
division << "\n" << prod.rjust(indent) << "\n"
division << ("-" * remainder.to_s(base).length).rjust(indent) <<
``````

“\n”
remainder %= divisor
remstring = “”
if digit
remstring = “0” if remainder == 0
remainder = remainder * base + digit
indent += 1
end
remstring << remainder.to_s(base)
division << remstring.rjust(indent)
end

``````if remainder == 0
puts result.rjust(division.lines.first.length-1), division
elsif decimal
rem_positions = {}
dec_result = ""
periodicity = 0
while remainder > 0
if rem_positions[remainder]
periodicity = rem_positions.size - rem_positions[remainder]
break
end
rem_positions[remainder] = rem_positions.size
division << "0\n"
indent += 1
remainder *= base
quotient = remainder / divisor
dec_result << quotient.to_s(base)
prod = (quotient * divisor).to_s(base)
division <<  prod.rjust(indent) << "\n"
division << ("-" * remainder.to_s(base).length).rjust(indent) <<
``````

“\n”
remainder %= divisor
division << remainder.to_s(base).rjust(indent)
end
result =
“#{result.rjust(division.lines.first.length-1)}.#{dec_result}”
if periodicity > 0
puts ("_"*periodicity).rjust(result.size)
end
puts result, division
else
puts “#{result.rjust(division.lines.first.length-1)}
R#{remainder.to_s(base)}”, division
end
end
end

if \$0 == FILE
base = ARGV.find {|arg| arg =~ /^–base/}
if base
base = base.split("=",2).last.to_i(10)
else
base = 10
end

dividend = ARGV.shift.to_i(base)
divisor = ARGV.shift.to_i(base)
decimal = !ARGV.include?("–remainder")
LongDivision.divide(dividend, divisor, base, decimal)
end

Matthew M. wrote:

## Long Division (#180)

This isn’t thoroughly tested but it seems to work. It supports
specifying a
base and it can display the result either as integer+remainder or as a
decimal. There’s no option to limit the digits as I didn’t see the
point.
If the number is periodic, it draws a vinculum above the apropriate
digits.
Usage: long_divide dividend divisor [–base=BASE] [–remainder]
BASE is the base as a decimal number (both dividend and divisor are
specified
as BASE)
If --remainder is specified, it will print the integer part of the
division
and the remainder, instead of printing the result as a decimal. If the
division has no remainder, there is no difference.

The code can be used from irb (or another script, if you should want to
do
that for some reason), by requireing it and then using the divide
method.
Here’s the code:
http://pastie.org/295741

Some sample output from irb:

divide(1,3)
_
0.3
±
3|1
0

1
=> nil

divide(1,3,2)
__
0.01
±
11|1
0

## 100 11

`````` 1
``````

=> nil

divide(10,7)

`````` ______
``````

## 30 28

``````20
14
--
60
56
--
40
35
--
50
49
--
10
7
--
3
``````

=> nil

divide(1,6)
_
0.16
±
6|1
0

## 40 36

``````4
``````

divide(1,6,10,false)
0 R1
±
6|1
0

1
=> nil

Apologies for lack of summary… mid-terms and stuff. Will try to have
it and new quiz done before the weekend.

## Long Division (#180)

This is about the same as my first solution.
I just cleaned up the code a little.

divisor,dvd = ARGV.to_i,ARGV
f, quotient, r, products = [],[""],[""],[""]
(1…dvd.length).each {|x|f << dvd.unpack(“a#{x}”).join}
g = f.detect{|x| x.to_i >= divisor}.length
str = “a#{g}” + “a1”*(dvd.length-g)
dividend = dvd.unpack(str).unshift("")

(0…dividend.length-1).each do |x|
quotient << (r[x] + dividend[x+1]).to_i / divisor
r << ((r[x] + dividend[x+1]).to_i % divisor).to_s
products << (r[x] + dividend[x+1]).to_i - r[x+1].to_i
end

fmt = dvd.length + 3 + divisor.to_s.length
print “#{quotient.join.rjust(fmt)}”
print " R#{r[-1]}\n" if r[-1].to_i != 0
print “\n” if r[-1].to_i == 0
print “#{(”-" * (dvd.length + 1)).rjust(fmt)}\n"
print “#{divisor.to_s} | #{dvd}\n”

fmt2 = divisor.to_s.length + 3 + g
(1…dividend.length).each do |x|
print “#{products[x].to_s.rjust(fmt2+x-1)}\n”
print “#{(”-"*(divisor.to_s.length+1)).rjust(fmt2+x-1)}\n"
print “#{r[x].rjust(fmt2+x-1)}#{dividend[x+1]}\n”
end

Harry