Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [QUIZ] Long Division (#180)

Reply
Thread Tools

[QUIZ] Long Division (#180)

 
 
Matthew Moss
Guest
Posts: n/a
 
      10-17-2008
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

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



 
Reply With Quote
 
 
 
 
Harry Kakueki
Guest
Posts: n/a
 
      10-19-2008
>
> ## 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

 
Reply With Quote
 
 
 
 
Sebastian Hungerecker
Guest
Posts: n/a
 
      10-19-2008
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: http://www.velocityreviews.com/forums/(E-Mail Removed)
ICQ: 205544826

 
Reply With Quote
 
Ken Bloom
Guest
Posts: n/a
 
      10-19-2008
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/
 
Reply With Quote
 
Harry Kakueki
Guest
Posts: n/a
 
      10-21-2008
>
> ## 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

 
Reply With Quote
 
Sarcar, Shourya C (GE Healthcare)
Guest
Posts: n/a
 
      10-21-2008
=20

-----Original Message-----
From: Matthew Moss [(E-Mail Removed)]=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[i]*(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=3 D=3D=3D=3D=3D=3D=3D=3D=3D=

Shourya Sarcar
http://blog.shouryalive.com





 
Reply With Quote
 
Matthew Moss
Guest
Posts: n/a
 
      10-24-2008
Apologies for lack of summary... mid-terms and stuff. Will try to have
it and new quiz done before the weekend.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Having compilation error: no match for call to (const __gnu_cxx::hash<long long int>) (const long long int&) veryhotsausage C++ 1 07-04-2008 05:41 PM
long long and long Mathieu Dutour C Programming 4 07-24-2007 11:15 AM
division by 7 without using division operator krypto.wizard@gmail.com C Programming 94 02-09-2007 06:57 AM
unsigned long long int to long double Daniel Rudy C Programming 5 09-20-2005 02:37 AM
Assigning unsigned long to unsigned long long George Marsaglia C Programming 1 07-08-2003 05:16 PM



Advertisments