Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-14 Thread David Van Horn 

On 12/14/11 5:11 AM, Marijn wrote:

(gcd-rational 2/3 2/3 2/3)

2/3

(lcm-rational 2/3 2/3 2/3)

4/9

is that 4/9 the intended result?


No, I must've messed up the definition.  Fortunately, Matthew did the 
right thing when he implemented lcm:


Welcome to Racket v5.2.0.6.
> (lcm 2/3 2/3 2/3)
2/3

David

_
 For list-related administrative tasks:
 http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-14 Thread Marijn 
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On 09-12-11 20:04, Jens Axel Søgaard wrote:
> One definition of greatest common divisor in a ring R is: d is a
> greatest common divisor of x and y when: i)  d divides both x and
> y ii)  If e is a divisor of both x and y, then d divides e

I think you mixed up ii) here since to get the _greatest_ common
divisor it makes more sense if any other common divisor divides the
greatest instead of the other way around.

> Now let's consider the ring Q. Since Q is a field, 1 divides all
> elements.

Since Q is a field any non-zero element a divides any element b: a *
b/a = b. And all such non-zero divisors divide each other by the same
token.

> It is therefore not obvious that gcd should be extendend as you
> suggest.

Indeed. The definition seems plausible at a first glance:

> (gcd-rational 2/3 2/3)
2/3
> (lcm-rational 2/3 2/3)
2/3

but what about:

> (gcd-rational 2/3 2/3 2/3)
2/3
> (lcm-rational 2/3 2/3 2/3)
4/9

is that 4/9 the intended result?

Marijn
-BEGIN PGP SIGNATURE-
Version: GnuPG v2.0.18 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk7odlMACgkQp/VmCx0OL2xJXgCfRhnUR/GXHs4PoMhVWGGkqdC2
95UAoKGN3/SigQDq5mPX+NO9dzj5Ox+S
=n0HH
-END PGP SIGNATURE-
_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-10 Thread David Van Horn 

On 12/10/11 9:25 AM, David Van Horn wrote:

On 12/9/11 3:31 PM, Daniel King wrote:

On Fri, Dec 9, 2011 at 15:27, Carl Eastlund wrote:

What does "divides" even mean in Q? I think we need David to explain
what his extension of GCD and LCM means here, in that "divisors" and
"multiples" are fairly trivial things in Q.


I took "x divides y" to mean x/y is an integer.


I meant: y/x is an integer.

David

_
 For list-related administrative tasks:
 http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-10 Thread David Van Horn 

On 12/9/11 3:31 PM, Daniel King wrote:

On Fri, Dec 9, 2011 at 15:27, Carl Eastlund  wrote:

What does "divides" even mean in Q?  I think we need David to explain
what his extension of GCD and LCM means here, in that "divisors" and
"multiples" are fairly trivial things in Q.


I took "x divides y" to mean x/y is an integer.


I don't suppose to understand all the math on this page, but I think
it uses the same definition that dvh is using.

http://mathworld.wolfram.com/GreatestCommonDivisor.html


Yes, that's where I got the definition I suggested.

As a concrete example of why I wanted gcd extended to rationals: I wrote 
a big-bang program that runs a set of big-bang programs, so it needs a 
tick-rate that is the gcd of all the tick-rates of the programs it runs, 
which may be rational.


David
_
 For list-related administrative tasks:
 http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-10 Thread Jens Axel Søgaard 
2011/12/10 Stephen Bloch 

>
> On Dec 9, 2011, at 3:31 PM, Daniel King wrote:
>
> > On Fri, Dec 9, 2011 at 15:27, Carl Eastlund  wrote:
> >> What does "divides" even mean in Q?  I think we need David to explain
> >> what his extension of GCD and LCM means here, in that "divisors" and
> >> "multiples" are fairly trivial things in Q.
> >
> > I don't suppose to understand all the math on this page, but I think
> > it uses the same definition that dvh is using.
> >
> > http://mathworld.wolfram.com/GreatestCommonDivisor.html
>
> Interesting: the Mathematica people have extended the gcd function from
> the integers to the rationals, not by applying the usual definition of gcd
> to Q (which would indeed be silly, as everything except 0 divides
> everything else), but by coming up with a different definition which, when
> restricted to integers, happens to coincide with the usual definition of
> gcd.
>

If we for rational numbers x and y define "x divides y" to mean "y/x is an
integer",
then I believe the definition
  d is a gcd of x and y
 <=> i) d divides a and y
ii) e divides x and y => d divides e
coincides with the MathWorld definition.


> I would wonder: is this the ONLY "reasonable" function on rationals which,
> when restricted to integers, coincides with the usual definition of gcd?
>

Not sure, but this seems relevant.

http://trac.sagemath.org/sage_trac/ticket/10771

-- 
Jens Axel Søgaard
_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-09 Thread Stephen Bloch 

On Dec 9, 2011, at 3:31 PM, Daniel King wrote:

> On Fri, Dec 9, 2011 at 15:27, Carl Eastlund  wrote:
>> What does "divides" even mean in Q?  I think we need David to explain
>> what his extension of GCD and LCM means here, in that "divisors" and
>> "multiples" are fairly trivial things in Q.
> 
> I don't suppose to understand all the math on this page, but I think
> it uses the same definition that dvh is using.
> 
> http://mathworld.wolfram.com/GreatestCommonDivisor.html

Interesting: the Mathematica people have extended the gcd function from the 
integers to the rationals, not by applying the usual definition of gcd to Q 
(which would indeed be silly, as everything except 0 divides everything else), 
but by coming up with a different definition which, when restricted to 
integers, happens to coincide with the usual definition of gcd.

I would wonder: is this the ONLY "reasonable" function on rationals which, when 
restricted to integers, coincides with the usual definition of gcd?


Stephen Bloch
sbl...@adelphi.edu


_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-09 Thread Daniel King 
On Fri, Dec 9, 2011 at 15:27, Carl Eastlund  wrote:
> What does "divides" even mean in Q?  I think we need David to explain
> what his extension of GCD and LCM means here, in that "divisors" and
> "multiples" are fairly trivial things in Q.

I don't suppose to understand all the math on this page, but I think
it uses the same definition that dvh is using.

http://mathworld.wolfram.com/GreatestCommonDivisor.html

-- 
Dan King
College of Computer and Information Science
Northeastern University

_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-09 Thread Carl Eastlund 
What does "divides" even mean in Q?  I think we need David to explain
what his extension of GCD and LCM means here, in that "divisors" and
"multiples" are fairly trivial things in Q.

Carl Eastlund

On Fri, Dec 9, 2011 at 3:08 PM, J. Ian Johnson  wrote:
> What? The greatest common divisor would definitely not divide 1, unless it 
> truly were 1.
> -Ian
> - Original Message -
> From: "Jens Axel Søgaard" 
> To: "David Van Horn" 
> Cc: "Racket Dev List" 
> Sent: Friday, December 9, 2011 2:04:46 PM GMT -05:00 US/Canada Eastern
> Subject: Re: [racket-dev] feature request: gcd, lcm for rationals
>
>
>
>
> One definition of greatest common divisor in a ring R is:
> d is a greatest common divisor of x and y when:
> i) d divides both x and y
> ii) If e is a divisor of both x and y, then d divides e
>
>
> Now let's consider the ring Q. Since Q is a field, 1 divides all elements.
>
>
> This implies that 1 is a greatest common divisor of any non-zero x and y.
> ( ad i) 1 is a divisor of both x and y
> ad ii) 1 is a divisor of e )
>
>
> It is therefore not obvious that gcd should be extendend as you suggest.
> But maybe we can finde another name for the operation?
>
>
> /Jens Axel
>
>
>
> 2011/12/7 David Van Horn < dvanh...@ccs.neu.edu >
>
>
> It would be nice if gcd and lcm were extended to rational numbers, which 
> seems in-line with Scheme's philosophy (but not standards) on numbers.
>
> (define (gcd-rational . rs)
> (/ (apply gcd (map numerator rs))
> (apply lcm (map denominator rs
>
> (define (lcm-rational . rs)
> (/ (abs (apply * rs))
> (apply gcd-rational rs)))
>
> David

_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-09 Thread J. Ian Johnson 
What? The greatest common divisor would definitely not divide 1, unless it 
truly were 1.
-Ian
- Original Message -
From: "Jens Axel Søgaard" 
To: "David Van Horn" 
Cc: "Racket Dev List" 
Sent: Friday, December 9, 2011 2:04:46 PM GMT -05:00 US/Canada Eastern
Subject: Re: [racket-dev] feature request: gcd, lcm for rationals




One definition of greatest common divisor in a ring R is: 
d is a greatest common divisor of x and y when: 
i) d divides both x and y 
ii) If e is a divisor of both x and y, then d divides e 


Now let's consider the ring Q. Since Q is a field, 1 divides all elements. 


This implies that 1 is a greatest common divisor of any non-zero x and y. 
( ad i) 1 is a divisor of both x and y 
ad ii) 1 is a divisor of e ) 


It is therefore not obvious that gcd should be extendend as you suggest. 
But maybe we can finde another name for the operation? 


/Jens Axel 



2011/12/7 David Van Horn < dvanh...@ccs.neu.edu > 


It would be nice if gcd and lcm were extended to rational numbers, which seems 
in-line with Scheme's philosophy (but not standards) on numbers. 

(define (gcd-rational . rs) 
(/ (apply gcd (map numerator rs)) 
(apply lcm (map denominator rs 

(define (lcm-rational . rs) 
(/ (abs (apply * rs)) 
(apply gcd-rational rs))) 

David 
__ ___ 
For list-related administrative tasks: 
http://lists.racket-lang.org/ listinfo/dev 




-- 
-- 
Jens Axel Søgaard 



_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-09 Thread Jens Axel Søgaard 
One definition of greatest common divisor in a ring R is:
  d is a greatest common divisor of x and y when:
   i)  d divides both x and y
  ii)  If e is a divisor of both x and y, then d divides e

Now let's consider the ring Q. Since Q is a field, 1 divides all elements.

This implies that 1 is a greatest common divisor of any non-zero x and y.
( ad i) 1 is a divisor of both x and y
  ad ii) 1 is a divisor of e )

It is therefore not obvious that gcd should be extendend as you suggest.
But maybe we can finde another name for the operation?

/Jens Axel


2011/12/7 David Van Horn 

> It would be nice if gcd and lcm were extended to rational numbers, which
> seems in-line with Scheme's philosophy (but not standards) on numbers.
>
> (define (gcd-rational . rs)
>  (/ (apply gcd (map numerator rs))
> (apply lcm (map denominator rs
>
> (define (lcm-rational . rs)
>  (/ (abs (apply * rs))
> (apply gcd-rational rs)))
>
> David
> __**___
>  For list-related administrative tasks:
>  
> http://lists.racket-lang.org/**listinfo/dev
>



-- 
-- 
Jens Axel Søgaard
_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

Re: [racket-dev] feature request: gcd, lcm for rationals

2011-12-08 Thread Matthew Flatt 
I'll make this change.

At Wed, 07 Dec 2011 12:25:34 -0500, David Van Horn wrote:
> It would be nice if gcd and lcm were extended to rational numbers, which 
> seems in-line with Scheme's philosophy (but not standards) on numbers.
> 
> (define (gcd-rational . rs)
>(/ (apply gcd (map numerator rs))
>   (apply lcm (map denominator rs
> 
> (define (lcm-rational . rs)
>(/ (abs (apply * rs))
>   (apply gcd-rational rs)))
> 
> David

_
  For list-related administrative tasks:
  http://lists.racket-lang.org/listinfo/dev

[racket-dev] feature request: gcd, lcm for rationals

2011-12-07 Thread David Van Horn 
It would be nice if gcd and lcm were extended to rational numbers, which 
seems in-line with Scheme's philosophy (but not standards) on numbers.


(define (gcd-rational . rs)
  (/ (apply gcd (map numerator rs))
 (apply lcm (map denominator rs

(define (lcm-rational . rs)
  (/ (abs (apply * rs))
 (apply gcd-rational rs)))

David
_
 For list-related administrative tasks:
 http://lists.racket-lang.org/listinfo/dev