home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 April: Mac OS SDK / Dev.CD Apr 97 SDK1.toast / Development Kits (Disc 1) / Apple Shared Library Manager / ASLM Examples / TestTools / Sources / TestRandom.cp < prev    next >
Encoding:
Text File  |  1996-11-19  |  10.3 KB  |  498 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        TestRandom.cp
  3.  
  4.     Contains:    Tester for the TSimpleRandom class
  5.  
  6.     Copyright:    © 1991-1994 by Apple Computer, Inc., all rights reserved.
  7.  
  8. */
  9.  
  10. #ifndef __TESTRANDOM__
  11. #include "TestRandom.h"
  12. #endif
  13. #ifndef __STDLIB__
  14. #include <stdlib.h>
  15. #endif
  16. #ifndef __STRING__
  17. #include <String.h>
  18. #endif
  19.  
  20. #define kTestArraySize    513
  21. #define kIterations    100
  22.  
  23. /**********************************************************************
  24. ** PUBLIC Constructor/Destructor
  25. ***********************************************************************/
  26.  
  27. Constructor(Random)
  28. Destructor(Random)
  29.  
  30. //
  31. // Returns the square root, or the lower of the 2 numbers which straddle
  32. // the square root.
  33. //
  34. unsigned short FigSquareRoot(unsigned long num)
  35. {
  36.     unsigned short    ret = 46340;    // square root of 0x7fffffff
  37.     while (1)
  38.     {
  39.         long    func = ret*ret - num;
  40.         long    derv = ret << 1;
  41.         long    dx   = func/derv;
  42.         ret -=  (short)dx;
  43.         if (dx == 0)
  44.         {
  45.             if (func > 0)
  46.                 ret -= 1;
  47.             return ret;
  48.         }
  49.     }
  50. }
  51.  
  52. #if USES68KINLINES
  53.     extern "C" 
  54.     {
  55.         #pragma parameter __D0 DoMod(__D0, __D1)
  56.         unsigned short DoMod(unsigned long, unsigned short) =
  57.         {
  58.             0x80c1, 0x4240, 0x4840
  59.             //    DIVU D1,D0; MOVE.W #0,D0; SWAP D0;
  60.         };
  61.     }
  62. #else
  63.     inline unsigned short DoMod(unsigned long dividend, unsigned short divisor)
  64.     {
  65.         return dividend % divisor;
  66.     }
  67. #endif
  68.  
  69. //
  70. // Returns true if "num" is prime. WARNING: This routine CANNOT HANDLE EVEN NUMBERS!
  71. //
  72. Boolean IsPrime(unsigned long num)
  73. {
  74.     unsigned short    root = FigSquareRoot(num);
  75.     unsigned short    temp = (unsigned short)(num >> 16);
  76.     unsigned short    idx = temp;
  77.     ldiv_t            res;
  78.     //
  79.     // Set up idx to be the smallest odd number which will divide into "num"
  80.     // without overflowing 65535
  81.     //
  82.     if (idx < 3)
  83.         idx = 3;
  84.     else
  85.         if ((idx & 1) == 0)
  86.             idx += 1;
  87.     //
  88.     // Try and disqualify the number using the fast divide stuff first!
  89.     //
  90.     while (idx <= root)
  91.     {
  92.         if (DoMod(num, idx) == 0)            // If there is no remainder
  93.             return false;
  94.         idx += 2;
  95.     }
  96.     //
  97.     // Then do it the hard way if it passed!
  98.     //
  99.     idx =1;
  100.     if (root < temp)
  101.         temp = root;
  102.     while ((idx += 2) < temp)
  103.     {
  104.         res = ldiv(num, idx);
  105.         if (res.rem == 0)
  106.             return false;
  107.     }
  108.     return true;
  109. }
  110.  
  111. double ExpectedRuns(double total, short inParm)
  112. {
  113.     short    foo = inParm + 1;
  114.     double expect = total - total/double(foo);
  115.     while (--foo > 1)
  116.     {
  117.         expect = expect/double(foo);
  118.     }
  119.     return expect;
  120. }
  121.  
  122. /**********************************************************************
  123. ** PUBLIC InitTest
  124. ***********************************************************************/
  125.  
  126. void TTestRandom::InitTest(BooleanParm, BooleanParm, int, char**)
  127. {
  128.     TStandardPool* pool = GetPool();
  129.  
  130.     if (pool == NULL)
  131.     {
  132.         Printf("### ERROR: There is no global pool\n");
  133.         return;
  134.     }
  135.     
  136.     fTest = NULL;
  137.     
  138.     TRY
  139.         fTest = new (pool) TFastRandom;
  140.     CATCH_ALL
  141.     ENDTRY
  142.     
  143.     if (fTest == NULL)
  144.     {
  145.         Printf("### ERROR: Could not create a TSimpleRandom object\n");
  146.         return;
  147.     }
  148. }
  149.  
  150. /**********************************************************************
  151. ** PUBLIC RunTestIteration
  152. ***********************************************************************/
  153.  
  154. void TTestRandom::RunTestIteration(BooleanParm, BooleanParm)
  155. {    
  156.     unsigned long    idx;
  157.     size_t            jdx, kdx;
  158.     size_t            runs[kTestArraySize];
  159.     size_t            rawRuns[kTestArraySize];
  160.     size_t            counts[kTestArraySize];
  161.     size_t            rawCounts[kTestArraySize];
  162.     unsigned long    runPrev;
  163.     unsigned long    rawRunPrev;
  164.     unsigned long    rawPrev;
  165.     unsigned long    val;
  166.     unsigned long    rawVal;
  167.     
  168.     TStandardPool* pool = (TStandardPool*)TMemoryPool::RecoverPool(fTest);
  169.     
  170.     for (kdx = 0; kdx < 4; ++kdx)
  171.     {
  172.         char*            className;
  173.         unsigned long    small = 0x7fffffff;
  174.         unsigned long    large = 0;
  175.         unsigned long    range;
  176.         unsigned long    clos = 0x7fffffff;
  177.         size_t            count = 0;
  178.         size_t            rawCount = 0;
  179.         
  180.         memset(runs, 0, sizeof(runs));
  181.         memset(rawRuns, 0, sizeof(rawRuns));
  182.         memset(counts, 0, sizeof(counts));
  183.         memset(rawCounts, 0, sizeof(rawCounts));
  184.         
  185.         switch (kdx)
  186.         {
  187.             case 0:
  188.                 range = kMaxFastRandom;
  189.                 className = "TFastRandom";
  190.                 break;
  191.                 
  192.             case 1:
  193.                 range = kMaxSimpleRandom;
  194.                 className = "TSimpleRandom";
  195.                 delete fTest;
  196.                 fTest = new TSimpleRandom;
  197.                 break;
  198.                 
  199.             case 2:
  200.                 range = 0xffffffff;
  201.                 className = "TSimpleRandom";
  202.                 delete fTest;
  203.                 fTest = new TSimpleRandom(0, 314159261, 453448043);
  204.                 break;
  205.  
  206.             case 3:
  207.                 range = 0x7fff;
  208.                 className = "MPW Random";
  209.                 delete fTest;
  210.                 fTest = new TSimpleRandom(0x8000, 0x41c64e6d, 0x3039);
  211.                 break;
  212.         }
  213.  
  214.         size_t            divisor        = size_t(range/kTestArraySize) + 1;
  215.         unsigned long    each        = kIterations;
  216.         unsigned long    max            = kTestArraySize*each;
  217.         short            runState    = 0;
  218.         short            rawRunState    = 0;
  219.         
  220.         Printf("\nINFO: Testing class %s\n", className);
  221.             
  222.         runPrev = fTest->GetRandomNumber(1, kTestArraySize);
  223.         rawRunPrev = fTest->GetSeed();
  224.         rawPrev = fTest->GetSeed();
  225.         
  226.         for (idx = 0; idx < max; ++idx)
  227.         {
  228.             unsigned short    slot;
  229.             
  230.             val = fTest->GetRandomNumber(1, kTestArraySize);
  231.             rawVal = fTest->GetSeed();
  232.             if (val == 0 || val > kTestArraySize)
  233.             {
  234.                 Printf("### ERROR: Value returned was %u\n", val);
  235.                 continue;
  236.             }
  237.             counts[val - 1] += 1;
  238.             slot = (unsigned short)(rawVal/divisor);
  239.             if (slot >= kTestArraySize)
  240.             {
  241.                 Printf("### ERROR: Slot value was %u for %u/%u\n",
  242.                        slot, val, divisor);
  243.                 continue;
  244.             }
  245.             rawCounts[slot] += 1;
  246.  
  247.             //
  248.             // Get the largest and smallest raw values seen
  249.             //
  250.             if (rawVal > large)
  251.                 large = rawVal;
  252.             if (rawVal < small)
  253.                 small = rawVal;
  254.             //
  255.             // Get the smallest distance between 2 raw random numbers
  256.             //
  257.             unsigned long temp;
  258.             if (rawVal != rawPrev)
  259.             {
  260.                 if (rawVal > rawPrev)
  261.                     temp = rawVal - rawPrev;
  262.                 else
  263.                     temp = rawPrev - rawVal;
  264.                 if (temp < clos)
  265.                     clos = temp;
  266.             }
  267.             //
  268.             // Save the previous number
  269.             //
  270.             rawPrev = rawVal;
  271.             //
  272.             // Update Run statistics
  273.             //
  274.             switch (runState)
  275.             {
  276.                 // Just starting out, so see if we're an up or down run
  277.                 case 0:
  278.                     if (val >= runPrev)
  279.                     {
  280.                         runState = 1;
  281.                         count = 2;
  282.                     }
  283.                     else
  284.                     {
  285.                         runState = 2;
  286.                         count = 2;
  287.                     }
  288.                     break;
  289.                     
  290.                 // Handle Up Run
  291.                 case 1:
  292.                     if (val >= runPrev)
  293.                     {
  294.                         runPrev = val;
  295.                         count += 1;
  296.                     }
  297.                     else
  298.                     {
  299.                         if (count > kTestArraySize)
  300.                             runs[kTestArraySize - 1] += 1;
  301.                         else
  302.                             runs[count - 1] += 1;
  303.                         runState = 3;
  304.                     }
  305.                     break;
  306.                     
  307.                 // Handle Down Run
  308.                 case 2:
  309.                     if (val <= runPrev)
  310.                     {
  311.                         runPrev = val;
  312.                         count += 1;
  313.                     }
  314.                     else
  315.                     {
  316.                         if (count > kTestArraySize)
  317.                             runs[kTestArraySize - 1] += 1;
  318.                         else
  319.                             runs[count - 1] += 1;
  320.                         runState = 4;
  321.                     }
  322.                     break;
  323.                     
  324.                 // After Up Run
  325.                 case 3:
  326.                     runPrev = val;
  327.                     count = 1;
  328.                     runState = 2;
  329.                     break;
  330.                     
  331.                 // After Down Run
  332.                 case 4:
  333.                     runPrev = val;
  334.                     count = 1;
  335.                     runState = 1;
  336.                     break;
  337.                     
  338.             }
  339.             //
  340.             // Update Run statistics
  341.             //
  342.             switch (rawRunState)
  343.             {
  344.                 // Just starting out, so see if we're an up or down run
  345.                 case 0:
  346.                     if (rawVal >= rawRunPrev)
  347.                     {
  348.                         rawRunState = 1;
  349.                         rawCount = 2;
  350.                     }
  351.                     else
  352.                     {
  353.                         rawRunState = 2;
  354.                         rawCount = 2;
  355.                     }
  356.                     break;
  357.                     
  358.                 // Handle Up Run
  359.                 case 1:
  360.                     if (rawVal >= rawRunPrev)
  361.                     {
  362.                         rawRunPrev = rawVal;
  363.                         rawCount += 1;
  364.                     }
  365.                     else
  366.                     {
  367.                         if (rawCount > kTestArraySize)
  368.                             rawRuns[kTestArraySize - 1] += 1;
  369.                         else
  370.                             rawRuns[rawCount - 1] += 1;
  371.                         rawRunState = 3;
  372.                     }
  373.                     break;
  374.                     
  375.                 // Handle Down Run
  376.                 case 2:
  377.                     if (rawVal <= rawRunPrev)
  378.                     {
  379.                         rawRunPrev = rawVal;
  380.                         rawCount += 1;
  381.                     }
  382.                     else
  383.                     {
  384.                         if (rawCount > kTestArraySize)
  385.                             rawRuns[kTestArraySize - 1] += 1;
  386.                         else
  387.                             rawRuns[rawCount - 1] += 1;
  388.                         rawRunState = 4;
  389.                     }
  390.                     break;
  391.                     
  392.                 // After Up Run
  393.                 case 3:
  394.                     rawRunPrev = rawVal;
  395.                     rawCount = 1;
  396.                     rawRunState = 2;
  397.                     break;
  398.                     
  399.                 // After Down Run
  400.                 case 4:
  401.                     rawRunPrev = rawVal;
  402.                     rawCount = 1;
  403.                     rawRunState = 1;
  404.                     break;
  405.                     
  406.             }
  407.         }
  408.         if (count > kTestArraySize)
  409.             runs[kTestArraySize - 1] += 1;
  410.         else
  411.             runs[count - 1] += 1;
  412.         if (rawCount > kTestArraySize)
  413.             rawRuns[kTestArraySize - 1] += 1;
  414.         else
  415.             rawRuns[rawCount - 1] += 1;
  416.         //
  417.         // Output Chi-Squared statistic
  418.         //
  419.         {
  420.             double    a = 0.0;
  421.             double    b = double(each);
  422.             for (jdx = 0; jdx < kTestArraySize; ++jdx)
  423.             {
  424.                 double    y = double(counts[jdx]) - b;
  425.                 a = a + (y*y);
  426.             }
  427.             a = a/b;
  428.             unsigned long val = (unsigned long)(a*100);
  429.             Printf("INFO: Chi-Squared value for Process Data was %u.%02u\n",
  430.                    val/100, val % 100);
  431.             
  432.             a = 0.0;
  433.             for (jdx = 0; jdx < kTestArraySize; ++jdx)
  434.             {
  435.                 double    y = double(rawCounts[jdx]) - b;
  436.                 a = a + (y*y);
  437.             }
  438.             a = a/b;
  439.             val = (unsigned long)(a*100);
  440.             Printf("INFO: Chi-Squared value for Raw Data was %u.%02u\n",
  441.                    val/100, val % 100);
  442.         }
  443.         //
  444.         // Output Run statistic statistic
  445.         //
  446.         {
  447.             size_t    total = 0;
  448.             for (jdx = 0; jdx < kTestArraySize; ++jdx)
  449.                 total += runs[jdx];
  450.             double y = 0.0;
  451.             double b = double(total);
  452.             for (jdx = 0; jdx < 9; ++jdx)
  453.             {
  454.                 double c = ExpectedRuns(b, (short)jdx + 1);
  455.                 double d = double(runs[jdx]) - c;
  456.                 y = y + (d*d)/c;
  457.             }
  458.             unsigned long val = (unsigned long)(y*100);
  459.             Printf("INFO: Chi-Squared value for Processed Data Runs was %u.%02u\n",
  460.                   val/100, val % 100);
  461.             for (jdx = 9; jdx < kTestArraySize; ++jdx)
  462.                 if (runs[jdx] > 1)
  463.                     Printf("WARNING: Runs for #%u was %u\n", jdx + 1, runs[jdx]);
  464.             total = 0;
  465.             for (jdx = 0; jdx < kTestArraySize; ++jdx)
  466.                 total += rawRuns[jdx];
  467.             y = 0.0;
  468.             b = double(total);
  469.             for (jdx = 0; jdx < 9; ++jdx)
  470.             {
  471.                 double c = ExpectedRuns(b, (short)jdx + 1);
  472.                 double d = double(rawRuns[jdx]) - c;
  473.                 y = y + (d*d)/c;
  474.             }
  475.             val = (unsigned long)(y*100);
  476.             Printf("INFO: Chi-Squared value for Raw Data Runs was %u.%02u\n",
  477.                   val/100, val % 100);
  478.             for (jdx = 9; jdx < kTestArraySize; ++jdx)
  479.                 if (rawRuns[jdx] > 1)
  480.                     Printf("WARNING: Runs for #%u was %u\n", jdx + 1, rawRuns[jdx]);
  481.         }
  482.         Printf("INFO: smallest was %lu, largest was %lu, out of %lu\n",
  483.                small, large, range);
  484.         Printf("INFO: Closest numbers were separated by %lu\n",
  485.                clos);
  486.     }
  487. }
  488.  
  489. /**********************************************************************
  490. ** PUBLIC EndTest
  491. ***********************************************************************/
  492.  
  493. void TTestRandom::EndTest(BooleanParm verbose, BooleanParm)
  494. {
  495.     if (verbose)
  496.         Printf("INFO: End of Random test\n");
  497. }
  498.