ScaLAPACK 2.1  2.1
ScaLAPACK: Scalable Linear Algebra PACKage
PB_Clcm.c
Go to the documentation of this file.
1 /* ---------------------------------------------------------------------
2 *
3 * -- PBLAS auxiliary routine (version 2.0) --
4 * University of Tennessee, Knoxville, Oak Ridge National Laboratory,
5 * and University of California, Berkeley.
6 * April 1, 1998
7 *
8 * ---------------------------------------------------------------------
9 */
10 /*
11 * Include files
12 */
13 #include "../pblas.h"
14 #include "../PBpblas.h"
15 #include "../PBtools.h"
16 #include "../PBblacs.h"
17 #include "../PBblas.h"
18 
19 #ifdef __STDC__
20 int PB_Clcm( int M, int N )
21 #else
22 int PB_Clcm( M, N )
23 /*
24 * .. Scalar Arguments ..
25 */
26  int M, N;
27 #endif
28 {
29 /*
30 * Purpose
31 * =======
32 *
33 * PB_Clcm computes and returns the Least Common Multiple (LCM) of two
34 * positive integers M and N. In fact, the routine computes the Greatest
35 * Common Divisor (GCD) and use the property that M*N = GCD*LCM.
36 *
37 * Arguments
38 * =========
39 *
40 * M (input) INTEGER
41 * On entry, M must be at least zero.
42 *
43 * N (input) INTEGER
44 * On entry, N must be at least zero.
45 *
46 * -- Written on April 1, 1998 by
47 * Antoine Petitet, University of Tennessee, Knoxville 37996, USA.
48 *
49 * ---------------------------------------------------------------------
50 */
51 /*
52 * .. Local Scalars ..
53 */
54  int gcd=1, m_val, n_val, t;
55 /* ..
56 * .. Executable Statements ..
57 *
58 */
59  if( M > N ) { m_val = N; n_val = M; }
60  else { m_val = M; n_val = N; }
61 
62  while( m_val > 0 )
63  {
64  while( !( m_val & 1 ) )
65  {
66 /*
67 * m is even
68 */
69  m_val >>= 1;
70 /*
71 * if n is odd, gcd( m, n ) = gcd( m / 2, n )
72 */
73  if( !( n_val & 1 ) )
74  {
75 /*
76 * otherwise gcd( m, n ) = 2 * gcd( m / 2, n / 2 )
77 */
78  n_val >>= 1;
79  gcd <<= 1;
80  }
81  }
82 /*
83 * m is odd now. If n is odd, gcd( m, n ) = gcd( m, ( m - n ) / 2 ).
84 * Otherwise, gcd( m, n ) = gcd ( m, n / 2 ).
85 */
86  n_val -= ( n_val & 1 ) ? m_val : 0;
87  n_val >>= 1;
88  while( n_val >= m_val )
89  {
90 /*
91 * If n is odd, gcd( m, n ) = gcd( m, ( m - n ) / 2 ).
92 * Otherwise, gcd( m, n ) = gcd ( m, n / 2 )
93 */
94  n_val -= ( n_val & 1 ) ? m_val : 0;
95  n_val >>= 1;
96  }
97 /*
98 * n < m, gcd( m, n ) = gcd( n, m )
99 */
100  t = n_val;
101  n_val = m_val;
102  m_val = t;
103  }
104  return ( ( M * N ) / ( n_val * gcd ) );
105 /*
106 * End of PB_Clcm
107 */
108 }
PB_Clcm
int PB_Clcm(int M, int N)
Definition: PB_Clcm.c:22