Ignore:
Timestamp:
Jul 23, 2001, 11:46:18 PM (24 years ago)
Author:
umoeller
Message:

Misc changes.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/helpers/math.c

    r87 r88  
    4141 */
    4242
     43
    4344/*
    4445 *@@ mathGCD:
    … …  
    4748 *
    4849 *      For example, mathGCD(10, 12) would return 2.
    49  */
    50 
    51 int mathGCD(int m, int n)
    52 {
    53     int d = m;
    54     int r = n;
    55 
    56     while (r != 0)
    57     {
    58         d = r;
    59         r = m % r;
    60     }
    61 
    62     return d;
    63 }
     50 *
     51 *      Modern Euclidian algorithm (The Art of Computer
     52 *      Programming, 4.5.2).
     53 */
     54
     55int mathGCD(int a, int b)
     56{
     57    int r;
     58
     59    while (b)
     60    {
     61        r = a % b;
     62        a = b;
     63        b = r;
     64    }
     65
     66    return (a);
     67
     68}
     69
     70/* binary GCD alg. Based on following facts.
     71   If N and M are even, then gcd(N,M) = 2 * gcd (N/2, M/2)
     72   If N even and M odd, then gcd(N,M) = gcd(N/2, M)
     73   If N,M odd, then |N-M|<max(N,M) thus guaranteeing that
     74             we can use gcd(N,M) = gcd(N-M,M) to reduce.
     75   fact: a&1 is 1 iff a is odd. Mult. and Div. by 2 more efficiently
     76   implemented as shift-left 1 and shift-right 1 resp.
     77
     78    Found at http://remus.rutgers.edu/~rhoads/Code/int_gcd.c
     79*/
     80
     81/* long gcd( long a, long b)
     82{
     83  int t;
     84
     85  if (a < 0) a = -a;
     86  if (!b) return a;
     87  if (b < 0) b = -b;
     88  if (!a) return b;
     89  t = 0;
     90  while (! ((a|b) & 1)) {a >>= 1; b >>= 1; ++t;}
     91  while (! (a&1)) a >>= 1;
     92  while (! (b&1)) b >>= 1;
     93  while (a != b)
     94     {
     95     if (a > b)
     96         {
     97         a -= b;
     98         do {a >>= 1;} while (! (a&1));
     99         }
     100     else {
     101         b -= a;
     102         do {b >>= 1;} while (! (b&1));
     103         }
     104     }
     105  return(a<<t); */
    64106
    65107/*
    … …  
    316358}
    317359
    318 typedef struct _PRIMEDATA
     360/*
     361 *@@ mathGCDMulti:
     362 *      finds the greatest common divisor for a
     363 *      whole array of integers.
     364 *
     365 *      For example, if you pass in three integers
     366 *      1000, 1500, and 1800, this would return 100.
     367 *      If you only pass in 1000 and 1500, you'd
     368 *      get 500.
     369 *
     370 *      Use the fact that:
     371 *
     372 *         gcd(u1, u2, ..., un) = gcd(u1, gcd(u2, ..., un))
     373 *
     374 *      Greatest common divisor of n integers (The
     375 *      Art of Computer Programming, 4.5.2).
     376 */
     377
     378int mathGCDMulti(int *paNs,             // in: array of integers
     379                 int cNs)               // in: array item count (NOT array size)
     380{
     381    int d = paNs[cNs-1];
     382    int k = cNs-1;
     383
     384    while (    (d != 1)
     385            && (k > 0)
     386          )
     387    {
     388        d = mathGCD(paNs[k-1], d);
     389        k--;
     390    }
     391
     392    return (d);
     393}
     394
     395/* typedef struct _PRIMEDATA
    319396{
    320397    LINKLIST    llPrimes;
    … …  
    331408                // for a later prime
    332409    int         iLastInt;
    333 } PRIMEENTRY, *PPRIMEENTRY;
     410} PRIMEENTRY, *PPRIMEENTRY; */
    334411
    335412/*
    … …  
    338415 */
    339416
    340 int XWPENTRY GCDMultiCallbackCreate(int n,             // in: prime
     417/* int XWPENTRY GCDMultiCallbackCreate(int n,             // in: prime
    341418                                    int p,             // in: power
    342419                                    void *pUser)       // in: user param, here root of tree
    … …  
    374451
    375452    return (0);
    376 }
     453} */
    377454
    378455/*
    … …  
    381458 */
    382459
    383 int XWPENTRY GCDMultiCallbackLowest(int n,             // in: prime
     460/* int XWPENTRY GCDMultiCallbackLowest(int n,             // in: prime
    384461                                    int p,             // in: power
    385462                                    void *pUser)       // in: user param, here root of tree
    … …  
    411488
    412489    return (0);
    413 }
    414 
    415 /*
    416  *@@ mathGCDMulti:
    417  *      finds the greatest common divisor for a
    418  *      whole array of integers.
    419  *
    420  *      For example, if you pass in three integers
    421  *      1000, 1500, and 1800, this would return 100.
    422  *      If you only pass in 1000 and 1500, you'd
    423  *      get 500.
    424  *
    425  *      Potentially expensive since this calls
    426  *      mathFactorPrime for each integer in the
    427  *      array first.
    428  */
    429 
    430 int mathGCDMulti(int *paNs,             // in: array of integers
     490} */
     491
     492/* int mathGCDMulti(int *paNs,             // in: array of integers
    431493                 int cNs)               // in: array item count (NOT array size)
    432494{
    … …  
    549611
    550612    return dGCD;
    551 }
     613} */
    552614
    553615// testcase
Note: See TracChangeset for help on using the changeset viewer.