[QUIZ] Long Division (#180)

Discussion in 'Ruby' started by Matthew Moss, Oct 17, 2008.

  1. Matthew Moss

    Matthew Moss Guest

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

    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).
    Matthew Moss, Oct 17, 2008
    #1
    1. Advertising

  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

    --
    A Look into Japanese Ruby List in English
    http://www.kakueki.com/ruby/list.html
    Harry Kakueki, Oct 19, 2008
    #2
    1. Advertising

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

    --
    NP: In Flames - Sleepless Again
    Jabber:
    ICQ: 205544826
    Sebastian Hungerecker, Oct 19, 2008
    #3
  4. Matthew Moss

    Ken Bloom Guest

    [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}d\n",products
    printf "%#{fmtwidth-exps}s\n","-"*products.to_s.size
    i+=1
    printf "%#{fmtwidth-exps}d\n",dividends
    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/
    Ken Bloom, Oct 19, 2008
    #4
  5. >
    > ## 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

    --
    A Look into Japanese Ruby List in English
    http://www.kakueki.com/ruby/list.html
    Harry Kakueki, Oct 21, 2008
    #5
  6. =20

    -----Original Message-----
    From: Matthew Moss [mailto:]=20

    ## Long Division (#180)

    Your task this week is to perform and display long division.
    Here's a solution. I checked it with quite a few combinations, seems
    like its robust.
    A define and use an object called "Slot" which takes a number and puts
    each digit
    in a "slot".

    Comments welcome.


    Run this like

    $ ruby longdiv.rb 5002101 201

    24886 R 15
    +-------
    201|5002101
    402
    ---
    982
    804
    ---
    1781
    1608
    ----
    1730
    1608
    ----
    1221
    1206
    ----
    15

    Checked answer ! Correct



    =3D=3D=3D CODE follows =3D=3D=3D
    # An abstraction where a number is modeled
    # such that each digit sits in a "slot"
    # Eg : 345 =3D=3D> |3|4|5| (internally stored in an array)
    # Makes it easy to left shift
    class Slot
    def initialize(num)
    @x =3D []
    if (num =3D=3D 0) then
    @x << 0
    else
    while (num > 0)
    @x << num % 10
    num =3D num / 10
    end
    @x.reverse!
    end
    end

    def zero?
    (@x =3D=3D "0" * @x.length)=20
    end

    def show
    @x.each {|f| print f}
    puts
    end

    def length
    return @x.length
    end

    def int
    return 0 if self.zero?
    y =3D @x.reverse
    val =3D 0
    (0 .. (y.length - 1)).each {|i| val +=3D y*(10 ** i)}
    return val
    end

    # left shift
    def lshift(p=3D1)
    return if @x.empty?
    val =3D 0
    (p-1).downto(0) do |i|
    val +=3D @x.shift * (10 ** (i))
    end
    return Slot.new(val)
    end

    def div(a)
    return Slot.new(0) if self.zero?
    x =3D self.int
    y =3D a.int
    return Slot.new(x/y)
    end

    def mod(a)
    return Slot.new(0) if self.zero?
    x =3D self.int
    y =3D a.int
    return Slot.new(x % y)
    end

    def concat(p)
    return self if p =3D=3D nil
    s =3D p.clone
    s.length.times do |i|
    @x << s.lshift.int
    end
    return self
    end

    def clone
    return Slot.new(self.int)
    end

    def to_s
    @x.to_s
    end
    end

    def spc(x)
    " " * x.to_i
    end

    #
    # MAIN
    # Programmer: Shourya Sarcar
    # ruby log_div.rb <dividend> <divisor>
    #

    # Get the dividend followed by the divisor
    b =3D Slot.new(ARGV.shift.to_i)
    a =3D Slot.new(ARGV.shift.to_i)

    # Some initialisation
    al =3D a.length
    q =3D b.clone
    steps, anss, rems, ds =3D [], [], [], [] # Arrays to store numbers at
    various stages
    init_gaps =3D 0
    first_line =3D true
    rem =3D q.lshift

    # That magic loop of long division
    # This is where the calculation is performed
    while (q.length > 0) do
    d =3D rem
    while (d.int < a.int && (q.length > 0)) do=20
    d.concat(q.lshift)
    anss << d.div(a).int if (d.int < a.int)
    init_gaps +=3D 1 if (first_line)
    end
    first_line =3D false
    ans =3D d.div(a)
    step =3D Slot.new(a.int * ans.int)
    rem =3D d.mod(a)
    #puts "Divide " + d.to_s + " by " + a.to_s + " =3D=3D> " + ans.to_s
    + " Step " + step.to_s + " , R " + rem.to_s
    ds << d
    steps << step
    anss << ans.int if (ans.int > 0)
    end

    # Print the hard-earned results
    lm =3D spc(al + 1) # left margin
    while (anss[0] =3D=3D 0) do anss.shift end # spit leading zeroes if any
    ansline =3D lm + spc(init_gaps) + anss.to_s=20
    ansline +=3D " R " + rem.to_s if (rem.int !=3D 0)
    puts ansline
    puts spc(al) + "+" + "-" * b.length
    mainline =3D a.to_s + "|" + b.to_s
    puts mainline
    pre_line =3D lm
    d =3D ds.shift
    steps.each do |s|
    puts pre_line + spc(d.length - s.length)+ s.to_s
    puts pre_line + "-" * d.length
    pre_line +=3D spc(d.length - Slot.new(d.int - s.int).length)
    d =3D ds.shift
    if (d!=3Dnil) then
    puts pre_line + d.to_s
    else
    puts pre_line + rem.to_s
    end
    end


    # Check results
    puts
    if (a.int * anss.to_s.to_i + rem.int =3D=3D b.int) then
    puts "Checked answer ! Correct"
    else
    puts "Problem in calculation :-(. Answer is not correct"
    end



    =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=

    Shourya Sarcar
    http://blog.shouryalive.com
    Sarcar, Shourya C (GE Healthcare), Oct 21, 2008
    #6
  7. Matthew Moss

    Matthew Moss Guest

    Apologies for lack of summary... mid-terms and stuff. Will try to have
    it and new quiz done before the weekend.
    Matthew Moss, Oct 24, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. George Marsaglia

    Assigning unsigned long to unsigned long long

    George Marsaglia, Jul 8, 2003, in forum: C Programming
    Replies:
    1
    Views:
    655
    Eric Sosman
    Jul 8, 2003
  2. Daniel Rudy

    unsigned long long int to long double

    Daniel Rudy, Sep 19, 2005, in forum: C Programming
    Replies:
    5
    Views:
    1,173
    Peter Shaggy Haywood
    Sep 20, 2005
  3. Replies:
    94
    Views:
    4,380
    ┬Ča\\/b
    Feb 9, 2007
  4. Mathieu Dutour

    long long and long

    Mathieu Dutour, Jul 17, 2007, in forum: C Programming
    Replies:
    4
    Views:
    457
    santosh
    Jul 24, 2007
  5. Matthew Moss

    [SUMMARY] Long Division (#180)

    Matthew Moss, Oct 26, 2008, in forum: Ruby
    Replies:
    0
    Views:
    162
    Matthew Moss
    Oct 26, 2008
Loading...

Share This Page