Long Division (#180)

Ruby
1

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

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

    http://splatbang.com/rubyquiz/.

  3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby T. follow the discussion. Please reply to
the original quiz message, if you can.

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

Long Division (#180)

Your task this week is to perform and display long division.

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

Your program’s output should be:

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

2

Long Division (#180)

Your task this week is to perform and display long division.

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[0] - u[0] % divisor.to_i
r << u[0] % divisor.to_i
bringdown << ((u[0] % divisor.to_i).to_s + u[1].to_s).to_i
quotient << u[0] / 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

3

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

Long Division (#180)

Your program’s output should be:
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_digitmagnitude
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

4

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
we can’t see your ingenious solutions or your questions.

#!/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

5

Matthew M. wrote:

Long Division (#180)

Your task this week is to perform and display long division.

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

10
9

1
=> nil

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

10
0

100
11

 1

=> nil

divide(10,7)

 ______

1.428571
±-
7|10
7

30
28

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

=> nil

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

10
6

40
36

4

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

1
=> nil

6

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

7

Long Division (#180)

Your task this week is to perform and display long division.

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

divisor,dvd = ARGV[0].to_i,ARGV[1]
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