c_cpp/etc/calc/cal/test4000.cal

   1 /*
   2  * test4000 - 4000 series of the regress.cal test suite
   3  *
   4  * Copyright (C) 1999  Ernest Bowen and Landon Curt Noll
   5  *
   6  * Primary author:  Ernest Bowen
   7  *
   8  * Calc is open software; you can redistribute it and/or modify it under
   9  * the terms of the version 2.1 of the GNU Lesser General Public License
  10  * as published by the Free Software Foundation.
  11  *
  12  * Calc is distributed in the hope that it will be useful, but WITHOUT
  13  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  15  * Public License for more details.
  16  *
  17  * A copy of version 2.1 of the GNU Lesser General Public License is
  18  * distributed with calc under the filename COPYING-LGPL.  You should have
  19  * received a copy with calc; if not, write to Free Software Foundation, Inc.
  20  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  21  *
  22  * @(#) $Revision: 30.2 $
  23  * @(#) $Id: test4000.cal,v 30.2 2013/08/11 08:41:38 chongo Exp $
  24  * @(#) $Source: /usr/local/src/bin/calc/cal/RCS/test4000.cal,v $
  25  *
  26  * Under source code control:   1996/03/13 02:38:45
  27  * File existed as early as:    1996
  28  *
  29  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  30  */
  31
  32 /*
  33  * Functions for testing and timing ptest, nextcand, prevcand.
  34  *
  35  * rlen(N) for N > 0 generates a random N-word positive integer.
  36  *
  37  * plen(N) for N > 0 generates an almost certainly prime positive
  38  *      integer whose word-count is about N.
  39  *
  40  * clen(N) for N > 0 generates a composite odd N-word integer.
  41  *
  42  * ptimes(str, N [, n [, count [, skip, [, verbose]]]])
  43  *      tests, and finds the runtime, for
  44  *      ptest(x, count, skip) for n random almost certainly prime integers x
  45  *      with word-count about N; n defaults to ceil(K1/abs(count)/(H1 + N^3)),
  46  *      count to COUNT, skip to SKIP.
  47  *
  48  * ctimes(str, N [, n [, count [, skip, [, verbose]]]])
  49  *      tests, and finds the runtime, for
  50  *      ptest(x, count, skip) for n random composite integers x with word-count
  51  *      about N; n defaults to ceil(K2/(H2 + N^3)), count to COUNT, skip
  52  *      to SKIP.
  53  *
  54  * crtimes(str,a,b,n, [,count [, skip, [, verbose]]])
  55  *      tests, and finds the runtime,
  56  *      for ptest(x, count, skip) for n random integers x between a and b;
  57  *      count defaults to COUNT, skip to SKIP.
  58  *
  59  * ntimes (str, N [,n, [, count [, skip [, residue [, modulus[,verb]]]]]]) tests
  60  *      and finds the runtime for nextcand(...) and prevcand (...) for
  61  *      n integers x with word-count about N, etc. n defaults to
  62  *      ceil(K3/(H3 + N^3));
  63  *
  64  * testnextcand(str, N [, n [, count [, skip [, residue [, modulus [, verb]]]]])
  65  *      performs tests of nextcand(x, count, skip, residue, modulus)
  66  *      for n values of x with word-count N; n defaults to
  67  *      ceil(K3/(H3 + N^3)), count to COUNT, skip to SKIP, residue to 0,
  68  *      modulus to 1.
  69  *
  70  * testprevcand(str, N [, n [, count [, skip [, residue [, modulus [, verb]]]]])
  71  *      performs tests of prevcand(x, count, skip, residue, modulus)
  72  *      for n values of x with word-count N; n defaults to
  73  *      ceil(K3/(H3 + N^3)), count to COUNT, skip to SKIP, residue to 0,
  74  *      modulus to 1.
  75  */
  76
  77
  78 defaultverbose = 1;     /* default verbose value */
  79
  80 /*
  81  * test defaults
  82  */
  83 global BASEB = 32;
  84 global BASE = 2^BASEB;
  85 global COUNT = 5;
  86 global SKIP = 0;
  87 global RESIDUE = 0;
  88 global MODULUS = 1;
  89
  90 /*
  91  * internal test constants
  92  */
  93 global K1 = 2^15;
  94 global H1 = 40;
  95 global K2 = 2^17;
  96 global H2 = 40;
  97 global K3 = 2^10;
  98 global H3 = 10;
  99
 100
 101 define rlen(N)
 102 {
 103
 104         if (!isint(N) || N <= 0)
 105                 quit "Bad argument for rlen";
 106         return rand(BASE^(N-1), BASE^N);
 107 }
 108
 109 define plen(N) = nextcand(rlen(N), 10, 0);
 110
 111 define clen(N)
 112 {
 113         local n, v;
 114
 115         do {
 116                 v = rlen(N);
 117                 if (iseven(v))
 118                         v++;
 119         }
 120         while
 121                 (ptest(v, 10, 0));
 122         return v;
 123 }
 124
 125 define ptimes(str, N, n, count, skip, verbose)
 126 {
 127         local A, i, t, p, m;
 128
 129         if (isnull(verbose))
 130                 verbose = defaultverbose;
 131         if (verbose > 0) {
 132                 print str:":",:;
 133         }
 134         m = 0;
 135         if (isnull(count))
 136                 count = COUNT;
 137         if (isnull(n)) {
 138                 n = ceil(K1/abs(count)/(H1 + N^3));
 139                 if (verbose > 1) {
 140                         print "n =",n;
 141                 }
 142         }
 143         if (isnull(skip))
 144                 skip = SKIP;
 145         mat A[n];
 146         for (i = 0; i < n; i++)
 147                 A[i] = plen(N);
 148         t = usertime();
 149         for (i = 0; i < n; i++) {
 150                 p = ptest(A[i], count, skip);
 151                 if (!p) {
 152                         if (verbose > 0) {
 153                                 printf("*** Error for x = %d\n", A[i]);
 154                                 m++;
 155                         }
 156                 }
 157         }
 158         if (verbose > 0) {
 159                 if (m) {
 160                         printf("*** %d error(s)\n", m);
 161                 } else {
 162                         t = round(usertime() - t, 4);
 163                         if (verbose > 1) {
 164                                 printf("%d probable primes: time = %d\n", n, t);
 165                         } else {
 166                                 printf("%d probable primes: passed\n", n);
 167                         }
 168                 }
 169         }
 170         return m;
 171 }
 172
 173 define ctimes(str, N, n, count, skip, verbose)
 174 {
 175         local A, i, r, t, p, m;
 176
 177
 178         if (isnull(verbose))
 179                 verbose = defaultverbose;
 180         if (verbose > 0) {
 181                 print str:":",:;
 182         }
 183         m = 0;
 184         if (isnull(count))
 185                 count = COUNT;
 186         if (isnull(n)) {
 187                 n = ceil(K2/(H2 + N^3));
 188                 if (verbose > 1) {
 189                         print "n =",n;
 190                 }
 191         }
 192         if (isnull(skip))
 193                 skip = SKIP;
 194         mat A[n];
 195         for (i = 0; i < n; i++)
 196                 A[i] = clen(N);
 197         t = usertime();
 198         for (i = 0; i < n; i++) {
 199                 p = ptest(A[i], count, skip);
 200                 if (p) {
 201                         if (verbose > 0) {
 202                                 printf("*** Error, what should be rare "
 203                                        "has occurred for x = %d \n", A[i]);
 204                                 m++;
 205                         }
 206                 }
 207         }
 208         if (verbose > 0) {
 209                 if (m) {
 210                         printf("*** %d error(s)\n", m);
 211                 } else {
 212                         t = round(usertime() - t, 4);
 213                         if (verbose > 1) {
 214                                 printf("%d probable primes: time = %d\n", n, t);
 215                         } else {
 216                                 printf("%d probable primes: passed\n", n);
 217                         }
 218                 }
 219         }
 220         return m;
 221 }
 222
 223 define crtimes(str, a, b, n, count, skip, verbose)
 224 {
 225         local A, P, i, t, p, m;
 226
 227         if (isnull(verbose))
 228                 verbose = defaultverbose;
 229         if (verbose > 0) {
 230                 print str:":",:;
 231         }
 232         m = 0;
 233         if (b < a)
 234                 swap(a,b);
 235         b++;
 236         if (isnull(count))
 237                 count = COUNT;
 238         if (isnull(skip))
 239                 skip = SKIP;
 240         mat A[n];
 241         mat P[n];
 242         for (i = 0; i < n; i++) {
 243                 A[i] = rand(a,b);
 244                 P[i] = ptest(A[i], 20, 0);
 245         }
 246         t = usertime();
 247         for (i = 0; i < n; i++) {
 248                 p = ptest(A[i], count, skip);
 249                 if (p != P[i]) {
 250                         if (verbose > 0) {
 251                                 printf("*** Apparent error for %s x = %d\n",
 252                                         P[i] ? "prime" : "composite", A[i]);
 253                                 ++m;
 254                         }
 255                 }
 256         }
 257         if (verbose > 0) {
 258                 if (m) {
 259                         printf("*** %d error(s)?\n", m);
 260                 } else {
 261                         t = round(usertime() - t, 4);
 262                         if (verbose > 1) {
 263                                 printf("%d probable primes: time = %d\n", n, t);
 264                         } else {
 265                                 printf("%d probable primes: passed\n", n);
 266                         }
 267                 }
 268         }
 269         return m;
 270 }
 271
 272 define ntimes(str, N, n, count, skip, residue, modulus, verbose)
 273 {
 274         local A, i, t, p, tnext, tprev;
 275
 276         if (isnull(verbose))
 277                 verbose = defaultverbose;
 278         if (verbose > 0) {
 279                 print str:":",:;
 280         }
 281         if (isnull(count))
 282                 count = COUNT;
 283         if (isnull(n)) {
 284                 n = ceil(K3/(H3 + N^3));
 285                 if (verbose > 1) {
 286                         print "n =",n;
 287                 }
 288         }
 289         if (isnull(skip))
 290                 skip = SKIP;
 291         if (isnull(residue))
 292                 residue = RESIDUE;
 293         if (isnull(modulus))
 294                 modulus = MODULUS;
 295
 296         mat A[n];
 297         for (i = 0; i < n; i++)
 298                 A[i] = rlen(N);
 299         t = usertime();
 300         for (i = 0; i < n; i++) {
 301                 p = nextcand(A[i], count, skip, residue, modulus);
 302         }
 303         tnext = round(usertime() - t, 4);
 304         t = usertime();
 305         for (i = 0; i < n; i++) {
 306                 p = prevcand(A[i], count, skip, residue, modulus);
 307         }
 308         tprev = round(usertime() - t, 4);
 309         if (verbose > 0) {
 310                 printf("%d evaluations, nextcand: %d, "
 311                        "prevcand: %d\n", n, tnext, tprev);
 312         }
 313 }
 314
 315 define testnextcand(str, N, n, count, skip, residue, modulus, verbose)
 316 {
 317         local p, x, y, i, m;
 318
 319         if (isnull(verbose))
 320                 verbose = defaultverbose;
 321         if (verbose > 0) {
 322                 print str:":",:;
 323         }
 324         m = 0;
 325         if (isnull(count))
 326                 count = COUNT;
 327         if (isnull(n)) {
 328                 n = ceil(K3/(H3 + N^3));
 329                 print "n =",n;
 330         }
 331         if (isnull(skip))
 332                 skip = SKIP;
 333         if (isnull(residue))
 334                 residue = RESIDUE;
 335         if (isnull(modulus))
 336                 modulus = MODULUS;
 337         for (i = 0; i < n; i++) {
 338                 x = rlen(N);
 339                 y = nextcand(x, count, skip, residue, modulus);
 340                 p = testnext1(x, y, count, skip, residue, modulus);
 341                 if (p) {
 342                         m++;
 343                         if (verbose > 1) {
 344                                 printf("*** Failure %d for x = %d\n", p, x);
 345                         }
 346                 }
 347         }
 348         if (verbose > 0) {
 349                 if (m) {
 350                         printf("*** %d error(s)?\n", m);
 351                 } else {
 352                         printf("%d successful tests\n", n);
 353                 }
 354         }
 355         return m;
 356 }
 357
 358 define testnext1(x, y, count, skip, residue, modulus)
 359 {
 360         if (y <= x)
 361                 return 1;
 362         if (!ptest(y, count, skip))
 363                 return 2;
 364         if (mne(y, residue, modulus))
 365                 return 3;
 366         return 0;
 367 }
 368
 369 define testprevcand(str, N, n, count, skip, residue, modulus, verbose)
 370 {
 371         local p, x, y, i, m;
 372
 373         if (isnull(verbose))
 374                 verbose = defaultverbose;
 375         if (verbose > 0) {
 376                 print str:":",:;
 377         }
 378         m = 0;
 379         if (isnull(count))
 380                 count = COUNT;
 381         if (isnull(n)) {
 382                 n = ceil(K3/(H3 + N^3));
 383                 print "n =",n;
 384         }
 385         if (isnull(skip))
 386                 skip = SKIP;
 387         if (isnull(residue))
 388                 residue = RESIDUE;
 389         if (isnull(modulus))
 390                 modulus = MODULUS;
 391         for (i = 0; i < n; i++) {
 392                 x = rlen(N);
 393                 y = prevcand(x, count, skip, residue, modulus);
 394                 p = testprev1(x, y, count, skip, residue, modulus);
 395                 if (p) {
 396                         m++;
 397                         if (verbose > 1) {
 398                                 printf("*** Failure %d for x = %d\n", p, x);
 399                         }
 400                 }
 401         }
 402         if (verbose > 0) {
 403                 if (m) {
 404                         printf("*** %d error(s)?\n", m);
 405                 } else {
 406                         printf("%d successful tests\n", n);
 407                 }
 408         }
 409         return m;
 410 }
 411
 412
 413 define testprev1(x, y, count, skip, residue, modulus)
 414 {
 415         if (y >= x)
 416                 return 1;
 417         if (!ptest(y, count, skip))
 418                 return 2;
 419         if (mne(y, residue, modulus))
 420                 return 3;
 421         return 0;
 422 }
 423
 424 /*
 425  * test4000 - perform all of the above tests a bunch of times
 426  */
 427 define test4000(v, tnum)
 428 {
 429         local n;        /* test parameter */
 430
 431         /*
 432          * set test parameters
 433          */
 434         srand(4000e4000);
 435
 436         /*
 437          * test a lot of stuff
 438          */
 439         err += ptimes(strcat(str(tnum++),": ptimes(1,250)"), 1, 250,,,v);
 440         err += ptimes(strcat(str(tnum++),": ptimes(3,50)"), 3, 50,,,v);
 441         err += ptimes(strcat(str(tnum++),": ptimes(5,20)"), 5, 20,,,v);
 442
 443         err += ctimes(strcat(str(tnum++),": ctimes(1,7500)"), 1, 7500,,,v);
 444         err += ctimes(strcat(str(tnum++),": ctimes(3,500)"), 3, 500,,,v);
 445         err += ctimes(strcat(str(tnum++),": ctimes(5,200)"), 5, 200,,,v);
 446
 447         err += crtimes(strcat(str(tnum++),": crtimes(2^30,2^31,2500)"),
 448                 2^30, 2^31, 2500,,,v);
 449         err += crtimes(strcat(str(tnum++),": crtimes(2^300,2^301,75)"),
 450                 2^300, 2^301, 75,,,v);
 451
 452         err += testprevcand(strcat(str(tnum++),": testprevcand(1,250)"),
 453                 1, 250, ,,,,v);
 454         err += testprevcand(strcat(str(tnum++),": testprevcand(3,25)"),
 455                 3, 25, ,,,,v);
 456         err += testprevcand(strcat(str(tnum++),": testprevcand(5,10)"),
 457                 5, 10, ,,,,v);
 458
 459         err += testnextcand(strcat(str(tnum++),": testnextcand(1,250)"),
 460                 1, 250, ,,,,v);
 461         err += testnextcand(strcat(str(tnum++),": testnextcand(3,25)"),
 462                 3, 25, ,,,,v);
 463         err += testnextcand(strcat(str(tnum++),": testnextcand(5,10)"),
 464                 5, 10, ,,,,v);
 465
 466         /*
 467          * report results
 468          */
 469         if (v > 1) {
 470                 if (err) {
 471                         print "***", err, "error(s) found in testall";
 472                 } else {
 473                         print "no errors in testall";
 474                 }
 475         }
 476         return tnum;
 477 }