Re: [QUIZ] Long Division (#180)

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

> 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

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




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