From: Ken Bloom <kbloom@...>
Date: 2008-10-20T00:14:01+09:00
Subject: [SOLUTION][QUIZ] Long Division (#180)

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

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



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

-- 
Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/