mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2003-07-31, 18:18   #1
asdf
 
asdf's Avatar
 
Sep 2002

22·3·5 Posts
Default Relatively Prime

I need a fast function which determines whether 3 numbers are relatively prime. I'm thinking of doing 3 GCF's, but that seems slow.
asdf is offline   Reply With Quote
Old 2003-08-01, 02:27   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

160248 Posts
Default

Just 2 GCDs, right? gcd ( gcd ( A, B ), C )

I've seen library GCDs that took more than two arguments, but the question would be whether anyone's coded a really fast one.

[Edit: Oh, swiss! I just realized that I got it backward, but find that hyh1048576 has already pointed that out, so I can't save face by sneaking in a silent edit.

Ya know, as ya get older yer subconscious gets wiser but also gets slower.]
cheesehead is offline   Reply With Quote
Old 2003-08-01, 05:46   #3
hyh1048576
 
Jun 2003

26 Posts
Default

Quote:
Originally Posted by cheesehead
Just 2 GCDs, right? gcd ( gcd ( A, B ), C )

I've seen library GCDs that took more than two arguments, but the question would be whether anyone's coded a really fast one.
:? I don't think it is right. ;)

If gcd(A,B)>1, they are not relatively primes. So when A,B,C are relatively primes, gcd(A,B)=1, so gcd ( gcd ( A, B ), C )=gcd(1,C) must be equal to 1 ......That means it's useless in the determination :( And for example, A=p1p2, B=p3p4, C=p2p3, p1,p2,p3,p4 are primes.The two gcd are both equal to 1, but they are not relatively primes.

My method is A,B,C are relatively primes iff gcd(A,B) and gcd(AB,C) are both equal to 1 :)
hyh1048576 is offline   Reply With Quote
Old 2003-08-01, 15:37   #4
asdf
 
asdf's Avatar
 
Sep 2002

22·3·5 Posts
Default

Thanks for your help, I'll see how it goes.
asdf is offline   Reply With Quote
Old 2003-08-01, 16:35   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2×3×11×149 Posts
Default

There is no reason one needs to restrict the GCD to 2 inputs, i.e. N numbers x_1, ..., x_N are relatively prime iff GCD(x_1, ..., x_N) = 1. Of course if the GCD implementation one is using only allows for 2 inputs, one would have to do N-1 pairwise GCDs, but that has the advantage that if any one of these gives a result > 1, one can stop right there.
ewmayer is offline   Reply With Quote
Old 2003-08-01, 17:33   #6
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default

it seems to me that there should be some way to short circuit this to just look for relatively prime or not, instead of finding out the greatest common divisor.

doing GCD's seems like factoring a number to see if it is prime ..

Any thoughts?
Orgasmic Troll is offline   Reply With Quote
Old 2003-08-01, 18:13   #7
apocalypse
 
Feb 2003

2518 Posts
Default

Ernst -

Why don't we need N choose 2 gcd's. Or are we not talking about pairwise relatively prime numbers?
apocalypse is offline   Reply With Quote
Old 2003-08-01, 23:53   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·3·11·149 Posts
Default

Quote:
Originally Posted by TravisT
it seems to me that there should be some way to short circuit this to just look for relatively prime or not, instead of finding out the greatest common divisor.
The definition of relative primality of x and y is GCD(x,y) = 1. The only remaining issues are how fast one can do a GCD, and how best to test RP among more than 2 integer inputs.

Quote:
doing GCD's seems like factoring a number to see if it is prime ..
While a GCD may superficially look like a kind of factorization, it is in fact algorithmically completely different, and can be done much faster. To factor an N-digit integer takes exponential time, i.e. the amount of work needed grows faster than any finite power of the number of digits N. The fastest GCD algorithms, on the other hand, need just algebraic time, in fact they need only order of N*(log N)^2 work. That is only slightly larger than (say) a fast FFT-based multiply needs. (In fact a fast GCD involves O(log N) FFT-based muls, each of which needs O(N*log N) work, and multiplying these two together gives the overall cost.) Even a naive GCD needs just O(N^2) work.

Quote:
Originally Posted by apocalypse
Why don't we need N choose 2 gcd's. Or are we not talking about pairwise relatively prime numbers?
I believe there are some optimizations to be gained by processing all N vectors in parallel - for one, we don't need to save a copy of any of the inputs. But I wouldn't expect a huge speedup from this, perhaps at most a factor of ~2.

The Gnu MP package has fast GCD algorithms of various kinds (and both regular and "extended" GCDs - the latter are handy for finding modular inverses).
ewmayer is offline   Reply With Quote
Old 2003-08-02, 02:00   #9
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

10100000012 Posts
Default

Forest. Trees.

I'm not talking about the algorithmic details, I know that finding the GCD and factoring are very different, I meant that finding the GCD in the context of testing integers to be RP is akin to factoring a number to prove primality. The definition of a prime number is a number that has only itself and 1 as factors, but that doesn't mean you have to check every number between 1 and p and see if it is a factor, or even factor p to find out it is prime ..

what I'm saying is that if you find GCD(36,45) you get 9, but if you just wanted to know if 36 and 45 are relatively prime, getting 9 is extraneous information .. all you need is one bit of information,where RP(36,45) = false

Perhaps the algorithms for GCD are so fast that this isn't a practical issue, but it still might provide some interest. (Finding a polynomial-time primality proving algorithm is of interest, despite the fact that there are more optimized algorithms out there, again, I'm speaking conceptually)
Orgasmic Troll is offline   Reply With Quote
Old 2003-08-02, 02:57   #10
apocalypse
 
Feb 2003

132 Posts
Default

IIRC the Euclidean Algorithm for computing GCD is O(n*lg n) in the size of the input, so you are not likely to get much faster than that.
apocalypse is offline   Reply With Quote
Old 2003-08-02, 04:41   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

Quote:
Originally Posted by TravisT
The definition of a prime number is a number that has only itself and 1 as factors, but that doesn't mean you have to check every number between 1 and p and see if it is a factor, or even factor p to find out it is prime ..
That's only because it is possible to distinguish primes from composites by methods which do not involve factoring.

The situation for relatively prime numbers is not analogous. For a given number, the property of being relatively prime to another number is a less fundamental property than the property of being prime itself. So AFAIK no one has found any method of distinguishing relatively prime numbers from relatively nonprime numbers that is simpler than calculating the GCD and comparing that to 1.

Quote:
Originally Posted by TravisT
what I'm saying is that if you find GCD(36,45) you get 9, but if you just wanted to know if 36 and 45 are relatively prime, getting 9 is extraneous information .. all you need is one bit of information,where RP(36,45) = false
... and you get that one bit of information by comparing the 9 to 1, so the 9 is not completely extraneous.
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
Twin Prime Days, Prime Day Clusters cuBerBruce Puzzles 3 2014-12-01 18:15
disk died, prime work lost forever? where to put prime? on SSD or HDD? emily PrimeNet 3 2013-03-01 05:49
Prime Cullen Prime, Rest in Peace hhh Prime Cullen Prime 4 2007-09-21 16:34
The 40th known Mersenne prime, 220996011-1 is not PRIME! illman-q Miscellaneous Math 33 2004-09-19 05:02

All times are UTC. The time now is 20:21.

Sat Nov 28 20:21:00 UTC 2020 up 79 days, 17:31, 3 users, load averages: 1.04, 1.43, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.