Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a procedure where I calculate gcd(a,b) many times, and it can be computationally expensive. I am trying to instead create an array containing gcd(a,b) values by using a factor sieve of some kind, but I don't know a good way to do it.

For instance if I am looking at $a=24$ then I'd be looking for a way to calculate many gcd(24,b) values in one loop or something similar.

I hope I am making sense!

share|improve this question
1  
Why is computing a gcd computationally expensive? How large are your numbers? –  lhf Dec 5 '12 at 2:18
    
@lhf 20k loop by 20k loop or so (these also represent the size of the numbers) –  user51819 Dec 5 '12 at 2:20
    
Is this quicker to just do it the way I am doing it? –  user51819 Dec 5 '12 at 2:36
1  
For a fixed $a$, $\gcd(a,b)$ is periodic of period $a$. –  lhf Dec 5 '12 at 2:46
    
@lhf Do you mean gcd(a,b)=gcd(a,kb)? –  user51819 Dec 5 '12 at 3:19

2 Answers 2

up vote 1 down vote accepted

Mathematica will vectorize this automatically for you, which be much faster than an explicit loop.

E.g. finding $gcd(a,b)$ where $a$ is a 70 digit number and $b$ ranges over a list of 10K composite numbers of the same magnitude took about 0.1 seconds. Just now, on a fairly old machine.

The Mathematica code is simply

mygcds = GCD[a,B];

where $B$ is the list containing the numbers $b$.

share|improve this answer
    
I'm not using Mathematica; I'm writing my own code for this, but thanks for the tip –  user51819 Dec 5 '12 at 2:21

In APL (NARS2000, free) :

      size ← 15

      2 2⍴(0)((1,size)⍴⍳size)((size,1)⍴⍳size)(gcd_sieve size)
  0   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

  1   1 1 1 1 1 1 1 1 1  1  1  1  1  1  1 
  2   1 2 1 2 1 2 1 2 1  2  1  2  1  2  1 
  3   1 1 3 1 1 3 1 1 3  1  1  3  1  1  3 
  4   1 2 1 4 1 2 1 4 1  2  1  4  1  2  1 
  5   1 1 1 1 5 1 1 1 1  5  1  1  1  1  5 
  6   1 2 3 2 1 6 1 2 3  2  1  6  1  2  3 
  7   1 1 1 1 1 1 7 1 1  1  1  1  1  7  1 
  8   1 2 1 4 1 2 1 8 1  2  1  4  1  2  1 
  9   1 1 3 1 1 3 1 1 9  1  1  3  1  1  3 
 10   1 2 1 2 5 2 1 2 1 10  1  2  1  2  5 
 11   1 1 1 1 1 1 1 1 1  1 11  1  1  1  1 
 12   1 2 3 4 1 6 1 4 3  2  1 12  1  2  3 
 13   1 1 1 1 1 1 1 1 1  1  1  1 13  1  1 
 14   1 2 1 2 1 2 7 2 1  2  1  2  1 14  1 
 15   1 1 3 1 5 3 1 1 3  5  1  3  1  1 15

And copy + paste this code :

      ⎕cr'gcd_sieve'
gcdmatrix ← gcd_sieve size;i;temp                              
gcdmatrix ← (size,size)⍴1                                      
:for i :in 1+⍳¯1+⌊size÷2                                       
  gcdmatrix[i×temp∘.,temp←⍳⌊size÷i] ← i                        
:endfor                                                        
gcdmatrix[⊂[2]((⌈size÷2),2)⍴2/temp] ← temp ← (⌊size÷2)+⍳⌈size÷2

Example

      gcd_array ← gcd_sieve 15

      gcd_array[8;12]
4
      gcd_array[12;6]
6
      gcd_array[7;5]
1

Have a nice day.

share|improve this answer
    
Welcome to Math.SE. Thank you for the solution; however this problem was asked 5 months ago and your hard work might not be as appreciated as had you solved a more recent problem. –  vadim123 May 13 '13 at 14:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.