[QUIZ] Long Division (#180)

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

1. Matthew MossGuest

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

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
the original quiz message, if you can.

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

## Long Division (#180)

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

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

2. Harry KakuekiGuest

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

3. Sebastian HungereckerGuest

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
4. Ken BloomGuest

[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
> 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
5. Harry KakuekiGuest

>
> ## 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
6. Sarcar, Shourya C (GE Healthcare)Guest

=20

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

## Long Division (#180)

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

Run this like

\$ ruby longdiv.rb 5002101 201

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

=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
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
7. Matthew MossGuest

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