2
$\begingroup$

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!

  • 0
    Haven't you tried the Euclidean Algorithm?2016-02-29

2 Answers 2

1

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

  • 0
    I'm not using Mathematica; I'm writing my own code for this, but thanks for the tip2012-12-05
0

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.

  • 0
    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.2013-05-13