- **Ruby**
(*http://www.velocityreviews.com/forums/f66-ruby.html*)

- - **prog for g.c.d. of 2 integers**
(*http://www.velocityreviews.com/forums/t812537-prog-for-g-c-d-of-2-integers.html*)

prog for g.c.d. of 2 integersTopics from mathematics make good practice programs, IMO.
Comments are welcome. First we need a program that will give the greatest common denominator (g.c.d.) of 2 (then of n) numbers, denoted (a,b) (or (a_1,a_2,...,a_n)) and the least common multiple (l.c.m.), denoted [a,b]. (This will verify the theorem that (a,b)[a,b] = ab). First, a program to give the g.c.d of 2 integers. This shows the steps I went through writing this. I hope they are of some use or interest to someone. Use the Euclidean algorithm. The following is not a program, but work towards a program (see the end for the program). Choose numbers a and b between 1 and 999, so the program will start with a = rand(999) + 1 b = rand(999) + 1 # make sure that a > b if b > a a,b = b,a end # The Euclidean algorithm; a = r_0 , b = r_1 # r_2 = r_0 % r1 = a % b ; r_i = r_(i-2) % r_(i-1) for i = 2,3,...,n # till r_n = 0. The g.c.d. = r_(n-1) r_2 = a % b if r_2 == 0 gcd = b end r_3 = b % r_2 if r_3 == 0 gcd = r_3 end We need to do this recursively until we get 0. We want a function or method that takes 2 integers x > y and if x % y = 0, y is the gcd and that part of the program is done. If x % y is not 0, we keep applying r_i = r_(i-2) % r_(i-1) until we get 0, in which case r_(i-1) = gcd. I think this will work: ============== def mod(x,y) z = x % y if z == 0 return y else w = mod(y,z) end end a = rand(999) + 1 b = rand(999) + 1 if b > a a,b = b,a end gcd = mod(a,b) puts a.to_s + " " + b.to_s + " g.c.d. is " + gcd.to_s ========== I tested this and it does work. So now to extend to the g.c.d. of n numbers--see my next post, unless someone else does it first. |

Re: prog for g.c.d. of 2 integers"Van Jacques" <vanjac12@yahoo.com> schrieb im Newsbeitrag news:70ae81fd.0312110524.309e73c0@posting.google.c om... > Topics from mathematics make good practice programs, IMO. > Comments are welcome. > > First we need a program that will give the greatest > common denominator (g.c.d.) of 2 (then of n) numbers, > denoted (a,b) (or (a_1,a_2,...,a_n)) and the least > common multiple (l.c.m.), denoted [a,b]. > (This will verify the theorem that (a,b)[a,b] = ab). > > First, a program to give the g.c.d of 2 integers. > This shows the steps I went through writing this. > I hope they are of some use or interest to someone. > > Use the Euclidean algorithm. > > The following is not a program, but work towards a program > (see the end for the program). > > Choose numbers a and b between 1 and 999, so > the program will start with > > a = rand(999) + 1 > b = rand(999) + 1 > > # make sure that a > b > > if b > a > a,b = b,a > end > > # The Euclidean algorithm; a = r_0 , b = r_1 > # r_2 = r_0 % r1 = a % b ; r_i = r_(i-2) % r_(i-1) for i = 2,3,...,n > # till r_n = 0. The g.c.d. = r_(n-1) > > r_2 = a % b > > if r_2 == 0 > gcd = b > end > > r_3 = b % r_2 > > if r_3 == 0 > gcd = r_3 > end > > We need to do this recursively until we get 0. > We want a function or method that takes 2 integers x > y > and if x % y = 0, y is the gcd and that part > of the program is done. If x % y is not 0, we keep applying > r_i = r_(i-2) % r_(i-1) until we get 0, > in which case r_(i-1) = gcd. > > I think this will work: > ============== > def mod(x,y) > z = x % y > if z == 0 > return y > else > w = mod(y,z) > end > end > > a = rand(999) + 1 > b = rand(999) + 1 If you put this test into the function, it is more general because then arguments can be placed in any order. > if b > a > a,b = b,a > end > > gcd = mod(a,b) > puts a.to_s + " " + b.to_s + " g.c.d. is " + gcd.to_s > ========== > > I tested this and it does work. So now to extend to the > g.c.d. of n numbers--see my next post, unless someone > else does it first. Here are two implementations that don't use recursion since this is more efficient. def gcd2(a,b) raise ArgumentError, "Value out of range" if a <= 0 || b <= 0 a,b = b,a if b > a begin a,b = b,a % b end while b != 0 a end def gcd3(*num) raise ArgumentError, "Value out of range" if num.detect{|n|n<=0} case num.size when 1 raise ArgumentError, "too few arguments" when 2 a,b = num a,b = b,a if b > a begin a,b = b,a % b end while b != 0 a else num.inject{|a,b| gcd3(a,b)} end end Kind regards robert |

Re: prog for g.c.d. of 2 integersHi!
* Van Jacques; 2003-12-11, 14:14 UTC: > Topics from mathematics make good practice programs, IMO. I don't agree with that. When starting with mathematics the most important task of programming has already taken place: The modelling of the problem in an abstract way. > Comments are welcome. My implementations are these: def Extmath.gcd(m, n) m = Integer(m) n = Integer(n) if m <= 0 || n <= 0 return nil end loop { if m < n m, n = n, m end if (l = m % n) == 0 break end m = l } n end def Extmath.lcm(m, n) m = Integer(m) n = Integer(n) if m <= 0 || n <= 0 return nil end m / gcd(m, n) * n end They are part of extmath - http://extmath.rubyforge.org/ Josef 'Jupp' SCHUGT -- http://oss.erdfunkstelle.de/ruby/ - German comp.lang.ruby-FAQ http://rubyforge.org/users/jupp/ - Ruby projects at Rubyforge |

Re: prog for g.c.d. of 2 integersOn Fri, 12 Dec 2003 07:19:18 +0900, Josef 'Jupp' SCHUGT wrote:
[snip gcd] > They are part of extmath - http://extmath.rubyforge.org/ Nice collection of math routines. BTW: Why are extmath not registered on RAA ? -- Simon Strandgaard |

Re: prog for g.c.d. of 2 integersOn Fri, Dec 12, 2003 at 12:42:10AM +0900, Robert Klemme wrote:
> def gcd2(a,b) > raise ArgumentError, "Value out of range" if a <= 0 || b <= 0 > a,b = b,a if b > a > begin > a,b = b,a % b > end while b != 0 > a > end Hi A few remarks about the above - it's late, and i am tired, so forgive me if I am wrong.. ;-= .) Since b,a % b = b,a for b > a, you don't need the a,b-swapping I believe: gdc2(4,6) -> a=4,b=6 a,b = b,a%b -> a=6,b=4%6=4 So the swapping happens automagically. .) Mathematically speaking, gdc is well-defined for negative arguments too.. So I would write it: def gcd2(a,b) a,b=b,a%b while (b != 0) a.abs end greetings, Florian Pflug |

Re: prog for g.c.d. of 2 integersHi!
* Simon Strandgaard; 2003-12-12, 00:32 UTC: > On Fri, 12 Dec 2003 07:19:18 +0900, Josef 'Jupp' SCHUGT wrote: > Nice collection of math routines. > > BTW: Why are extmath not registered on RAA ? I don't want to manually update two locations. Chances are good that information runs out of sync. I am quit confident that auto-sync of RAA and Rubyforge is only a question of time. Josef 'Jupp' SCHUGT -- http://oss.erdfunkstelle.de/ruby/ - German comp.lang.ruby-FAQ http://rubyforge.org/users/jupp/ - Ruby projects at Rubyforge |

Re: prog for g.c.d. of 2 integersOn Fri, 12 Dec 2003 22:48:39 +0900, Josef 'Jupp' SCHUGT wrote:
> Hi! > > * Simon Strandgaard; 2003-12-12, 00:32 UTC: >> On Fri, 12 Dec 2003 07:19:18 +0900, Josef 'Jupp' SCHUGT wrote: >> Nice collection of math routines. >> >> BTW: Why are extmath not registered on RAA ? > > I don't want to manually update two locations. Chances are good that > information runs out of sync. I am quit confident that auto-sync of RAA > and Rubyforge is only a question of time. I have just submitted our conversation as a feature-request: http://rubyforge.org/tracker/index.p..._id=5&atid=104 -- Simon Strandgaard |

All times are GMT. The time now is 04:52 AM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.