# Algorithm for finding many gcd(a,b) over a range of a?

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!

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

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

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

-
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