Forum: Ruby Long Division (#180)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
A61ecce13ed142622f24a5ca3a123922?d=identicon&s=25 Matthew Moss (Guest)
on 2008-10-17 15:58
(Received via mailing list)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz 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 Quiz 2 by submitting ideas as often as you can! (A
permanent, new website is in the works for Ruby Quiz 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 Talk 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).
2f4d4f9c35ea851bffb9a9cc2e086365?d=identicon&s=25 Harry Kakueki (Guest)
on 2008-10-19 16:09
(Received via mailing list)
>
> ## 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
7a561ec0875fcbbe3066ea8fe288ec77?d=identicon&s=25 Sebastian Hungerecker (Guest)
on 2008-10-19 17:08
(Received via mailing list)
Matthew Moss 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
851acbab08553d1f7aa3eecad17f6aa9?d=identicon&s=25 Ken Bloom (Guest)
on 2008-10-19 17:15
(Received via mailing list)
On Fri, 17 Oct 2008 08:57:01 -0500, Matthew Moss 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_digit*divisor
            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
851acbab08553d1f7aa3eecad17f6aa9?d=identicon&s=25 Ken Bloom (Guest)
on 2008-10-19 17:43
(Received via mailing list)
On Sun, 19 Oct 2008 10:07:34 -0500, Sebastian Hungerecker 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
2f4d4f9c35ea851bffb9a9cc2e086365?d=identicon&s=25 Harry Kakueki (Guest)
on 2008-10-21 10:15
(Received via mailing list)
>
> ## 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
A61ecce13ed142622f24a5ca3a123922?d=identicon&s=25 Matthew Moss (Guest)
on 2008-10-24 02:33
(Received via mailing list)
Apologies for lack of summary... mid-terms and stuff. Will try to have
it and new quiz done before the weekend.
This topic is locked and can not be replied to.