Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Common Divisor’s computing -> Non-Linear Programming task
Replies: 2   Last Post: Jun 22, 2009 6:52 PM

 Messages: [ Previous | Next ]
 Yuly Shipilevsky Posts: 17 Registered: 1/25/05
Re: Common Divisor’s computing -> Non-Linear Programming task
Posted: Jun 6, 2009 7:47 AM

Author: Yuly Shipilevsky

Algorithms for finding the Common Divisors and Greatest Common Divisor .
(Reducing of the Common Divisor?s computing to the solution of a Quadratic and
Non-Linear Programming/Optimization problem).

First algorithm.

Let N be a set of positive integers, N = {1, 2, . . . }
Let D be a Common Divisor of X1, . . . , XM.
There exists an unique M-tucle m0=(m01 , . . . , m0M) that corresponds to the
M-tucle X=( X1, . . . , XM) so that:

(1) Xi = Dm0i ,

(2) 1 <= m0i <= Xi , 1<= i <= M

Let gcd(X1, . . . , XM) denotes the Greatest Common Divisor of X1, . . . , XM.

Let N^M denotes a Cartesian product of M sets N,
Let m denotes an arbitrary M-tucle (m1 , . . . , mM) contained in N^M.

Let S_ N^M = {m : 1 <= mi <= Xi , 1<= i <= M }

Let's define the following function:

(3) S1(m,X) = SUM_i,j=1...M,i>j [Xi/mi - Xj/mj]^2 ,

where m=(m1 , . . . , mM) is contained in S_N^M

Proposition 1 (Minimum Principle).

for any
M-tucle m contained in S_N^M the following is true:

min_m { S1(m,X) | S_N^M } = S1(m0,X) = 0,

(the minimum is being searched amongst all the ?m?s
contained in S_N^M),

S1(m,X) > = S1(m0,X) = 0,

If and only if m0 contained in S_N^M corresponds to the
M-tucle X=( X1, . . . , XM) and satisfies

(1) and (2)

Proof.

It follows from X ' s Common Divisors ' existence (1 is considered as a Common Divisor as well) and (1) , (2) , (3) .

On the base of Proposition 1 we can suggest a

Theorem 1 (Reducing of Common Divisor?s computing to the solution of a Quadratic Integer Programming/Optimization problem).

To compute the Greatest Common Divisor of X1, . . . , XM do the following steps:

(a) Find M-tucles m contained in S_N^M and minimizing S1
(S1 -> min | S_N^M)
(b) For each and every M-tucle, determined at step (a) find the
corresponding Common Divisor of X using (1) and then
(c) Find the Greatest amongst Common Divisors determined at the step (b)

(the minimum is being searched amongst all the " m " s
contained in S_N^M).

Proof.

It follows from the Proposition 1.

Lemma 1.

If S_R_ N^M = {m: 1<= mi <= Xi, mi - real numbers,
1<= i <=M } ,

then

min_m { S1(m,X) | S_N^M } = min_m { S1(m,X) | S_R_ N^M} = 0

Proof.

It follows from the Proposition 1 and (1) , (2), (3).

On the base of Lemma 1 and Theorem 1 we can suggest a

Theorem 2 (Reducing of Common Divisor?s computing to the solution of a Quadratic Programming
/Optimization problem).

To compute the Greatest Common Divisor of X1, . . . , XM do the following steps:

(a) Find M-tucles m contained in S_R_N^M and minimizing S1
(S1 -> min | S_R_N^M)
(b) For each and every M-tucle, determined at step (a) find the
corresponding Common Divisor of X using (1) and then
(c) Find the Greatest amongst Common Divisors determined at the step (b)

(the minimum is being searched amongst all the " m " s
contained in S_R_N^M).

Second algorithm.

Let?s define the following function:

(4) S2(m,X) = SUM_i,j=1...M,i>j [Xi/mi - Xj/mj]^2 -
- Xk/mk ,

where m=(m1 , . . . , mM) is contained in S_N^M,
1 <= k <= M.

Proposition 2 (Minimum Principle).

The following is true:

gcd(X1, . . . , XM) = - min_m { S2(m,X) | S_N^M } =
= - S2(m0,X)

(the minimum is being searched amongst all the ?m?s
contained in S_N^M).

If and only if m0 corresponds to the
M-tucle X=( X1, . . . , XM) , satisfies

(1) and (2) and corresponds to the Greatest Common Devisor
gcd(X1, . . . , XM).

Proof.

It follows from X?s Common Divisors? existence (1 is considered as a Common Divisor as well) and (1) , (2) , (4) .

On the base of Proposition 2 we can suggest a

Theorem 3. (Reducing of gcd?s computing to the solution of a Integer Programming
/Optimization problem).

To compute the Greatest Common Divisor of X1, . . . , XM do:

(a) Find an M-tucle m0 contained in S_N^M and minimizing S2
(S2 -> min | S_N^M)
(b) Find the Greatest Common Divisor corresponding to the M-tucle m0 determined at step (b)
as follows:

gcd(X1, . . . , XM) = - min_m { S2(m,X) | S_N^M }
= - S2(m0,X).

(the minimum is being searched amongst all the " m " s
contained in S_N^M).

Lemma 2.

If S_R_ N^M = {m: 1<= mi <= Xi, mi - real numbers,
1<= i <=M } ,

then

min_m { S2(m,X) | S_N^M } = min_m { S2(m,X) | S_R_ N^M}

Proof.

It follows from Proposition 2, the fact that

SUM_i,j=1...M,i>j [Xi/mi - Xj/mj]^2 >= 0 and

continuosity and monotonicity of S21(mk) = Xk/mk function.

On the base of Lemma 2 and Theorem 3 we can suggest a

Theorem 4. (Reducing of gcd?s computing to the solution of a Non-Linear Programming
/Optimization problem).

To compute the Greatest Common Divisor of X1, . . . , XM do:

(a) Find an M-tucle m0 contained in S_R_N^M and minimizing S2
(S2 -> min | S_R_N^M)
(b) Find the Greatest Common Divisor corresponding to the M-tucle m0 determined at step (b)
as follows:

gcd(X1, . . . , XM) = - min_m { S2(m,X) | S_R_N^M }
= - S2(m0,X).

(the minimum is being searched amongst all the ?m?s
contained in S_R_N^M).

Example.

Finding the Greatest Common Divisor of 9636, 1456 and 2098 is being reduced to the

S2(m , X) = ( 9636 / m1 - 1456 / m2 )^2 + ( 1456 / m2 - 2098/ m3 )^2 - 9636 / m1 -> min

m =(m1, m2, m3) ,

X=(9636, 1456, 2098),

m1, m2, m3 - real numbers,

satisfying the following constraints:

1 <= m1 <= 9636 ,

1 <= m2 <= 1456,

1 <= m3 <= 2098

gcd(9636, 1456, 2098) = - min_m { S2(m , X) |
1 <= m1 <= 9636 , 1 <= m2 <= 1456,
1 <= m3 <= 2098 }.

Date Subject Author
6/5/09 Yuly Shipilevsky
6/6/09 Yuly Shipilevsky
6/22/09 Yuly Shipilevsky