Changeset 174 for trunk/src/helpers/math.c

Timestamp:

Jun 14, 2002, 2:20:11 PM (23 years ago)

Author:

umoeller

Message:

Misc updates.

File:

• trunk/src/helpers/math.c (modified) (2 diffs)

trunk/src/helpers/math.c

@@ -67 +67 @@
 
 }
-
-/* binary GCD alg. Based on following facts.
-   If N and M are even, then gcd(N,M) = 2 * gcd (N/2, M/2)
-   If N even and M odd, then gcd(N,M) = gcd(N/2, M)
-   If N,M odd, then |N-M|<max(N,M) thus guaranteeing that
-             we can use gcd(N,M) = gcd(N-M,M) to reduce.
-   fact: a&1 is 1 iff a is odd. Mult. and Div. by 2 more efficiently
-   implemented as shift-left 1 and shift-right 1 resp.
-
-    Found at http://remus.rutgers.edu/~rhoads/Code/int_gcd.c
-*/
-
-/* long gcd( long a, long b)
-{
-  int t;
-
-  if (a < 0) a = -a;
-  if (!b) return a;
-  if (b < 0) b = -b;
-  if (!a) return b;
-  t = 0;
-  while (! ((a|b) & 1)) {a >>= 1; b >>= 1; ++t;}
-  while (! (a&1)) a >>= 1;
-  while (! (b&1)) b >>= 1;
-  while (a != b)
-     {
-     if (a > b)
-         {
-         a -= b;
-         do {a >>= 1;} while (! (a&1));
-         }
-     else {
-         b -= a;
-         do {b >>= 1;} while (! (b&1));
-         }
-     }
-  return(a<<t); */
 
 /*
@@ -393 +356 @@
 }
 
-/* typedef struct _PRIMEDATA
-{
-    LINKLIST    llPrimes;
-    int         iCurrentInt;
-} PRIMEDATA, *PPRIMEDATA;
-
-
-typedef struct _PRIMEENTRY
-{
-    int         iPrime;
-    int         iLowestPowerFound;
-                // lowest power that was found for this prime number;
-                // if 0, a prime was previously present and then not
-                // for a later prime
-    int         iLastInt;
-} PRIMEENTRY, *PPRIMEENTRY; */
-
-/*
- *@@ GCDMultiCallbackCreate:
- *      first callback for mathGCDMulti.
- */
-
-/* int XWPENTRY GCDMultiCallbackCreate(int n,             // in: prime
-                                    int p,             // in: power
-                                    void *pUser)       // in: user param, here root of tree
-{
-    // see if we had this
-    PPRIMEDATA pData = (PPRIMEDATA)pUser;
-    PLISTNODE pNode;
-    PPRIMEENTRY pEntry;
-    for (pNode = lstQueryFirstNode(&pData->llPrimes);
-         pNode;
-         pNode = pNode->pNext)
-    {
-        pEntry = (PPRIMEENTRY)pNode->pItemData;
-        if (pEntry->iPrime == n)
-        {
-            // mark this as processed so we can later see
-            // if the current integer had this prime factor
-            // at all
-            pEntry->iLastInt = pData->iCurrentInt;
-
-            // printf(" %d^%d", n, p);
-
-            // and stop
-            return 0;
-        }
-    }
-
-    // no entry for this yet:
-    // printf(" %d^%d", n, p);
-    pEntry = NEW(PRIMEENTRY);
-    pEntry->iPrime = n;
-    pEntry->iLowestPowerFound = p;
-    pEntry->iLastInt = pData->iCurrentInt;
-    lstAppendItem(&pData->llPrimes, pEntry);
-
-    return (0);
-} */
-
-/*
- *@@ GCDMultiCallbackLowest:
- *      second callback for mathGCDMulti.
- */
-
-/* int XWPENTRY GCDMultiCallbackLowest(int n,             // in: prime
-                                    int p,             // in: power
-                                    void *pUser)       // in: user param, here root of tree
-{
-    // see if we had this
-    PPRIMEDATA pData = (PPRIMEDATA)pUser;
-    PLISTNODE pNode;
-    PPRIMEENTRY pEntry;
-    for (pNode = lstQueryFirstNode(&pData->llPrimes);
-         pNode;
-         pNode = pNode->pNext)
-    {
-        pEntry = (PPRIMEENTRY)pNode->pItemData;
-        if (pEntry->iPrime == n)
-        {
-            if (p < pEntry->iLowestPowerFound)
-            {
-                pEntry->iLowestPowerFound = p;
-                // printf(" %d^%d", n, p);
-            }
-            pEntry->iLastInt = pData->iCurrentInt;
-
-            // and stop
-            return 0;
-        }
-    }
-
-    exit(1);
-
-    return (0);
-} */
-
-/* int mathGCDMulti(int *paNs,             // in: array of integers
-                 int cNs)               // in: array item count (NOT array size)
-{
-    int i;
-    double dGCD;
-
-    PLISTNODE pNode;
-    PPRIMEENTRY pEntry;
-
-    PRIMEDATA Data;
-    lstInit(&Data.llPrimes, TRUE);
-
-    // this is done by prime-factoring each frequency
-    // and then multiplying all primes with the lowest
-    // common power that we found:
-
-    // Example 1: If we have two timers with freq.
-    // 1000 and 1500, obviously, the master timer
-    // should run at 500 ms.
-
-    // With prime factorization, we end up like this:
-
-    // 1000 = 2^3 *       5^3
-    // 1500 = 2^2 * 3^1 * 5^3
-
-    // so the highest power for factor 2 is 2;
-    //    the highest power for factor 3 is 0;
-    //    the highest power for factor 5 is 3;
-
-    // freq = 2^2 *       5^3 = 500
-
-    // Example 2: If we have three timers with freq.
-    // 1000 and 1500 and 1800:
-
-    // 1000 = 2^3 *       5^3
-    // 1500 = 2^2 * 3^1 * 5^3
-    // 1800 = 2^3 * 3^2 * 5^2
-
-    // so the highest power for factor 2 is 2;
-    //    the highest power for factor 3 is 0;
-    //    the highest power for factor 5 is 2;
-
-    // freq = 2^2 *     * 5^2 = 100
-
-    // Example 3: If we have four timers with freq.
-    // 1200 and 1500 and 1800 and 60:
-
-    // 1200 = 2^4 * 3^1 * 5^2
-    // 1500 = 2^2 * 3^1 * 5^3
-    // 1800 = 2^3 * 3^2 * 5^2
-    //   60 = 2^2 * 3^1 * 5^1
-
-    // so the highest power for factor 2 is 2;
-    //    the highest power for factor 3 is 1;
-    //    the highest power for factor 5 is 1;
-
-    // freq = 2^2 * 3^1 * 5^1 = 60
-
-    // go thru the ints array to create
-    // an entry for each prime there is
-    for (i = 0;
-         i < cNs;
-         i++)
-    {
-        // printf("\nFactoring %d\n", paNs[i]);
-        Data.iCurrentInt = paNs[i];
-        mathFactorPrime(paNs[i],
-                        GCDMultiCallbackCreate,
-                        &Data);
-    }
-
-    // now run this a second time to find the
-    // lowest prime for each
-    for (i = 0;
-         i < cNs;
-         i++)
-    {
-        // printf("\nTouching %d\n", paNs[i]);
-        Data.iCurrentInt = paNs[i];
-        mathFactorPrime(paNs[i],
-                        GCDMultiCallbackLowest,
-                        &Data);
-
-        // all list items that were just touched
-        // now have iLastInt set to the current
-        // integer; so go thru the list and set
-        // all items which do NOT have that set
-        // to power 0 because we must not use them
-        // in factoring
-        for (pNode = lstQueryFirstNode(&Data.llPrimes);
-             pNode;
-             pNode = pNode->pNext)
-        {
-            pEntry = (PPRIMEENTRY)pNode->pItemData;
-            if (pEntry->iLastInt != paNs[i])
-            {
-                pEntry->iLowestPowerFound = 0;
-                // printf(" ###%d^%d", pEntry->iPrime, 0);
-            }
-        }
-    }
-
-    // printf("\nNew:\n");
-
-    // now compose the GCD
-    dGCD = 1;
-    for (pNode = lstQueryFirstNode(&Data.llPrimes);
-         pNode;
-         pNode = pNode->pNext)
-    {
-        pEntry = (PPRIMEENTRY)pNode->pItemData;
-
-        // printf(" %d^%d", pEntry->iPrime, pEntry->iLowestPowerFound);
-
-        if (pEntry->iLowestPowerFound)
-            dGCD *= pow(pEntry->iPrime, pEntry->iLowestPowerFound);
-    }
-
-    lstClear(&Data.llPrimes);
-
-    return dGCD;
-} */
-
-// testcase
-
-#ifdef BUILD_MAIN
-
-#define INCL_DOSMISC
-#include <os2.h>
-
-int callback(int n,
-             int p,
-             void *pUser)
-{
-    if (p > 1)
-        printf("%d^%d ", n, p);
-    else
-        printf("%d ", n);
-    fflush(stdout);
-
-    return (0);
-}
-
-int main (int argc, char *argv[])
-{
-    if (argc > 1)
-    {
-        int i,
-            c,
-            cInts = argc - 1;
-        ULONG ulms, ulms2;
-        int *aInts = malloc(sizeof(int) * cInts);
-
-        for (c = 0;
-             c < cInts;
-             c++)
-        {
-            aInts[c] = atoi(argv[c + 1]);
-        }
-
-        DosQuerySysInfo(QSV_MS_COUNT,
-                        QSV_MS_COUNT,
-                        &ulms,
-                        sizeof(ulms));
-
-        c = mathGCDMulti(aInts,
-                         cInts);
-
-        DosQuerySysInfo(QSV_MS_COUNT,
-                        QSV_MS_COUNT,
-                        &ulms2,
-                        sizeof(ulms2));
-
-        printf("\nGCD is %d, %d ms time.\n",
-               c,
-               ulms2 - ulms);
-
-        for (i = 0;
-             i < cInts;
-             i++)
-        {
-            printf("  %d / %d = %d rem. %d\n",
-                   aInts[i], c, aInts[i] / c, aInts[i] % c);
-        }
-
-        /* c = mathFactorBrute(atoi(argv[1]),
-                            callback,
-                            0);
-        printf("\n%d factors found.\n", c); */
-    }
-
-    return (0);
-}
-
-#endif
+