home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / xwphescr.zip / XWPH0208.ZIP / src / helpers / math.c < prev    next >
C/C++ Source or Header  |  2002-06-14  |  8KB  |  359 lines
  1.  
  2. /*
  3.  *@@sourcefile math.c:
  4.  *      some math helpers.
  5.  *
  6.  *      This file is new with V0.9.14 (2001-07-07) [umoeller]
  7.  *      Unless marked otherwise, these things are based
  8.  *      on public domain code found at
  9.  *      "ftp://ftp.cdrom.com/pub/algorithms/c/".
  10.  *
  11.  *      Usage: All C programs.
  12.  *
  13.  *      Function prefix:
  14.  *
  15.  *      --  math*: semaphore helpers.
  16.  *
  17.  *@@added V0.9.14 (2001-07-07) [umoeller]
  18.  *@@header "helpers\math.h"
  19.  */
  20.  
  21. #define OS2EMX_PLAIN_CHAR
  22.     // this is needed for "os2emx.h"; if this is defined,
  23.     // emx will define PSZ as _signed_ char, otherwise
  24.     // as unsigned char
  25.  
  26. #include <stdlib.h>
  27. #include <stdio.h>
  28. #include <math.h>
  29.  
  30. #include "setup.h"                      // code generation and debugging options
  31.  
  32. #include "helpers\math.h"
  33. #include "helpers\linklist.h"
  34. #include "helpers\standards.h"
  35.  
  36. #pragma hdrstop
  37.  
  38. /*
  39.  *@@category: Helpers\Math helpers
  40.  *      see math.c.
  41.  */
  42.  
  43.  
  44. /*
  45.  *@@ mathGCD:
  46.  *      returns the greatest common denominator that
  47.  *      evenly divides m and n.
  48.  *
  49.  *      For example, mathGCD(10, 12) would return 2.
  50.  *
  51.  *      Modern Euclidian algorithm (The Art of Computer
  52.  *      Programming, 4.5.2).
  53.  */
  54.  
  55. int 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. /*
  71.  *@@ mathIsSquare:
  72.  *      returns 1 if x is a perfect square, that is, if
  73.  *
  74.  +      sqrt(x) ^ 2 ==x
  75.  */
  76.  
  77. int mathIsSquare(int x)
  78. {
  79.     int t;
  80.     int z = x % 4849845; // 4849845 = 3*5*7*11*13*17*19
  81.     double r;
  82.     // do some quick tests on x to see if we can quickly
  83.     // eliminate it as a square using quadratic-residues.
  84.     if (z % 3 == 2)
  85.         return 0;
  86.  
  87.     t =  z % 5;
  88.     if((t==2) || (t==3))
  89.         return 0;
  90.     t =  z % 7;
  91.     if((t==3) || (t==5) || (t==6))
  92.         return 0;
  93.     t = z % 11;
  94.     if((t==2) || (t==6) || (t==7) || (t==8) || (t==10))
  95.         return 0;
  96.     t = z % 13;
  97.     if((t==2) || (t==5) || (t==6) || (t==7) || (t==8) || (t==11))
  98.         return 0;
  99.     t = z % 17;
  100.     if((t==3) || (t==5) || (t==6) || (t==7) || (t==10) || (t==11) || (t==12) || (t==14))
  101.         return 0;
  102.     t = z % 19;
  103.     if((t==2) || (t==3) || (t==8) || (t==10) || (t==12) || (t==13) || (t==14) || (t==15) || (t==18))
  104.         return 0;
  105.  
  106.     // If we get here, we'll have to just try taking
  107.     // square-root & compare its square...
  108.     r = sqrt(abs(x));
  109.     if (r*r == abs(x))
  110.         return 1;
  111.  
  112.     return 0;
  113. }
  114.  
  115. /*
  116.  *@@ mathFindFactor:
  117.  *      returns the smallest factor > 1 of n or 1 if n is prime.
  118.  *
  119.  *      From "http://tph.tuwien.ac.at/~oemer/doc/quprog/node28.html".
  120.  */
  121.  
  122. int mathFindFactor(int n)
  123. {
  124.     int i,
  125.         max;
  126.     if (n <= 0)
  127.         return 0;
  128.  
  129.     max = floor(sqrt(n));
  130.  
  131.     for (i=2;
  132.          i <= max;
  133.          i++)
  134.     {
  135.         if (n % i == 0)
  136.             return i;
  137.     }
  138.     return 1;
  139. }
  140.  
  141. /*
  142.  *@@ testprime:
  143.  *      returns 1 if n is a prime number.
  144.  *
  145.  *      From "http://tph.tuwien.ac.at/~oemer/doc/quprog/node28.html".
  146.  */
  147.  
  148. int mathIsPrime(unsigned n)
  149. {
  150.     int i,
  151.         max = floor(sqrt(n));
  152.  
  153.     if (n <= 1)
  154.         return 0;
  155.  
  156.     for (i=2;
  157.          i <= max;
  158.          i++)
  159.     {
  160.         if (n % i == 0)
  161.             return 0;
  162.     }
  163.  
  164.     return 1;
  165. }
  166.  
  167. /*
  168.  *@@ mathFactorBrute:
  169.  *      calls pfnCallback with every integer that
  170.  *      evenly divides n ("factor").
  171.  *
  172.  *      pfnCallback must be declared as:
  173.  *
  174.  +          int pfnCallback(int iFactor,
  175.  +                          int iPower,
  176.  +                          void *pUser);
  177.  *
  178.  *      pfnCallback will receive the factor as its
  179.  *      first parameter and pUser as its third.
  180.  *      The second parameter will always be 1.
  181.  *
  182.  *      The factor will not necessarily be prime,
  183.  *      and it will never be 1 nor n.
  184.  *
  185.  *      If the callback returns something != 0,
  186.  *      computation is stopped.
  187.  *
  188.  *      Returns the no. of factors found or 0 if
  189.  *      n is prime.
  190.  *
  191.  *      Example: mathFactor(42) will call the
  192.  *      callback with
  193.  *
  194.  +          2 3 6 7 14 21
  195.  *
  196.  +      This func is terribly slow.
  197.  */
  198.  
  199. int mathFactorBrute(int n,                           // in: integer to factor
  200.                     PFNFACTORCALLBACK pfnCallback,   // in: callback func
  201.                     void *pUser)                     // in: user param for callback
  202. {
  203.     int rc = 0;
  204.  
  205.     if (n > 2)
  206.     {
  207.         int i;
  208.         int max = n / 2;
  209.  
  210.         for (i = 2;
  211.              i <= max;
  212.              i++)
  213.         {
  214.             if ((n % i) == 0)
  215.             {
  216.                 rc++;
  217.                 // call callback with i as the factor
  218.                 if (pfnCallback(i,
  219.                                 1,
  220.                                 pUser))
  221.                     // stop then
  222.                     break;
  223.             }
  224.         }
  225.     }
  226.  
  227.     return (rc);
  228. }
  229.  
  230. /*
  231.  *@@ mathFactorPrime:
  232.  *      calls pfnCallback for every prime factor that
  233.  *      evenly divides n.
  234.  *
  235.  *      pfnCallback must be declared as:
  236.  *
  237.  +          int pfnCallback(int iFactor,
  238.  +                          int iPower,
  239.  +                          void *pUser);
  240.  *
  241.  *      pfnCallback will receive the prime as its
  242.  *      first parameter, its power as its second,
  243.  *      and pUser as its third.
  244.  *
  245.  *      For example, with n = 200, pfnCallback will
  246.  *      be called twice:
  247.  *
  248.  *      1)  iFactor = 2, iPower = 3
  249.  *
  250.  *      2)  iFactor = 5, iPower = 2
  251.  *
  252.  *      because 2^3 * 5^2 is 200.
  253.  *
  254.  *      Returns the no. of times that the callback
  255.  *      was called. This will be the number of
  256.  *      prime factors found or 0 if n is prime
  257.  *      itself.
  258.  */
  259.  
  260. int mathFactorPrime(double n,
  261.                     PFNFACTORCALLBACK pfnCallback,   // in: callback func
  262.                     void *pUser)                     // in: user param for callback
  263. {
  264.     int rc = 0;
  265.  
  266.     double d;
  267.     double k;
  268.  
  269.     if (n <= 3)
  270.        // this is a prime for sure
  271.        return 0;
  272.  
  273.     d = 2;
  274.     for (k = 0;
  275.          fmod(n, d) == 0;
  276.          k++)
  277.     {
  278.         n /= d;
  279.     }
  280.  
  281.     if (k)
  282.     {
  283.         rc++;
  284.         pfnCallback(d,
  285.                     k,
  286.                     pUser);
  287.     }
  288.  
  289.     for (d = 3;
  290.          d * d <= n;
  291.          d += 2)
  292.     {
  293.         for (k = 0;
  294.              fmod(n,d) == 0.0;
  295.              k++ )
  296.         {
  297.             n /= d;
  298.         }
  299.  
  300.         if (k)
  301.         {
  302.             rc++;
  303.             pfnCallback(d,
  304.                         k,
  305.                         pUser);
  306.         }
  307.     }
  308.  
  309.     if (n > 1)
  310.     {
  311.         if (!rc)
  312.             return (0);
  313.  
  314.         rc++;
  315.         pfnCallback(n,
  316.                     1,
  317.                     pUser);
  318.     }
  319.  
  320.     return (rc);
  321. }
  322.  
  323. /*
  324.  *@@ mathGCDMulti:
  325.  *      finds the greatest common divisor for a
  326.  *      whole array of integers.
  327.  *
  328.  *      For example, if you pass in three integers
  329.  *      1000, 1500, and 1800, this would return 100.
  330.  *      If you only pass in 1000 and 1500, you'd
  331.  *      get 500.
  332.  *
  333.  *      Use the fact that:
  334.  *
  335.  *         gcd(u1, u2, ..., un) = gcd(u1, gcd(u2, ..., un))
  336.  *
  337.  *      Greatest common divisor of n integers (The
  338.  *      Art of Computer Programming, 4.5.2).
  339.  */
  340.  
  341. int mathGCDMulti(int *paNs,             // in: array of integers
  342.                  int cNs)               // in: array item count (NOT array size)
  343. {
  344.     int d = paNs[cNs-1];
  345.     int k = cNs-1;
  346.  
  347.     while (    (d != 1)
  348.             && (k > 0)
  349.           )
  350.     {
  351.         d = mathGCD(paNs[k-1], d);
  352.         k--;
  353.     }
  354.  
  355.     return (d);
  356. }
  357.  
  358.  
  359.