1/* 2 * test4100 - 4100 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 * Under source code control: 1996/03/13 03:53:22 23 * File existed as early as: 1996 24 * 25 * Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/ 26 */ 27 28/* 29 * Some severe tests and timing functions for REDC functions and pmod. 30 * 31 * testall(str,n,N,M,verbose) 32 * performs n tests using arguments x, y, ... 33 * randomly selected from [-N, N) or when nonnegative values are 34 * required, [0, N), and m an odd positive integer in [1,N], 35 * and where a "small" (say less than 10000) exponent k is to be 36 * used (when computing x^k % m directly) k is random in [0,M). 37 * Default values for N and M are 1e20 and 100. 38 * 39 * times(str,N,n,verbose) 40 * gives times for n evaluations of rcin, etc. with 41 * N-word arguments; default n is ceil(K1/power(N,1.585). 42 * 43 * powtimes(str, N1,N2,n, verbose) 44 * gives times for n evaluations of pmod(x,k,m) 45 * for the three algorithms "small", "normal", "bignum" that 46 * pmod may use, and equivalent functions rcpow(xr,k,m) for 47 * "small" or "bignum" cases, where xr = rcin(x,m). The 48 * modulus m is a random positive odd N1-word number; x has 49 * random integer values in [0, m-1]; k has random N2-word values. 50 * N2 defaults to 1; n defaults to ceil(K2/power(N1,1.585)/N2). 51 * 52 * inittimes(str, N, n, verbose) 53 * displays the times and tests n evaluations of rcin(x,m) 54 * and rcout(x,m) where m is a random positive odd N-word integer, 55 * x is a random integer in [0, m-1]; n defaults to ceil(K1/N^2). 56 * 57 * rlen_4100(N) 58 * generates a random positive N-word integer. The global 59 * BASEB should be set to the word-size for the computer being 60 * used. The parameters K1, K2 which control the default n 61 * should be adjusted to give reasonable runtimes. 62 * 63 * olen(N) 64 * generates a random odd positive N-word number. 65 * 66 */ 67 68 69defaultverbose = 1; /* default verbose value */ 70 71/* 72 * test defaults 73 */ 74global test4100_K1 = 2^17; 75global test4100_K2 = 2^12; 76global test4100_BASE = 2^config("baseb"); 77 78define rlen_4100(N) = rand(test4100_BASE^(N-1), test4100_BASE^N); 79 80define olen(N) 81{ 82 local v; 83 84 v = rlen_4100(N); 85 if (iseven(v)) 86 v++; 87 return v; 88} 89 90define test4101(x,y,m,k,z1,z2,verbose) 91{ 92 local xr, yr, v, w, oneone; 93 94 if (isnull(verbose)) 95 verbose = defaultverbose; 96 xr = rcin(x,m); 97 yr = rcin(y,m); 98 oneone = rcin(rcin(1,m),m); 99 100 if (xr >= m || xr < 0) { 101 if (verbose > 1) 102 printf("Failure 1 for x = %d, m = %d\n", x, m); 103 return 1; 104 } 105 if (rcin(x * y, m) != mod(xr * y, m, 0)) { 106 if (verbose > 1) { 107 printf("Failure 2 for x = %d, y = %d, m = %d\n", 108 x, y, m); 109 } 110 return 2; 111 } 112 if (rcout(xr, m) != x % m) { 113 if (verbose > 1) 114 printf("Failure 3 for x = %d, m = %d\n", x, m); 115 return 3; 116 } 117 if (rcout(rcmul(xr,yr,m),m) != mod(x * y, m, 0)) { 118 if (verbose > 1) 119 printf("Failure 4 for x = %d, y = %d, m = %d\n", 120 x, y, m); 121 return 4; 122 } 123 if (rcmul(x,yr,m) != mod(x * y, m, 0)) { 124 if (verbose > 1) 125 printf("Failure 5 for x = %d, y = %d, m = %d\n", 126 x, y, m); 127 return 5; 128 } 129 if (rcin(rcmul(x,y,m),m) != mod(x * y, m, 0)) { 130 if (verbose > 1) 131 printf("Failure 6 for x = %d, y = %d, m = %d\n", 132 x, y, m); 133 return 6; 134 } 135 if (rcout(rcsq(xr,m),m) != mod(x^2, m, 0)) { 136 if (verbose > 1) 137 printf("Failure 7 for x = %d, m = %d\n", x, m); 138 return 7; 139 } 140 if (rcin(rcsq(x,m),m) != mod(x^2, m, 0)) { 141 if (verbose > 1) 142 printf("Failure 8 for x = %d, m = %d\n", 143 x, y, m); 144 return 8; 145 } 146 if (rcout(rcpow(xr,k,m),m) != mod(x^k, m, 0)) { 147 if (verbose > 1) 148 printf("Failure 9 for x = %d, m = %d, k = %d\n", 149 x, m, k); 150 return 9; 151 } 152 if (rcpow(x,k,m) != rcin(rcout(x,m)^k, m)) { 153 if (verbose > 1) 154 printf("Failure 10: x = %d, k = %d, m = %d\n", 155 x, k, m); 156 return 10; 157 } 158 if (rcpow(x, z1 * z2, m) != rcpow(rcpow(x,z1,m), z2, m)) { 159 if (verbose > 1) 160 printf("Failure 11: x = %d, z1 = %d, z2 = %d, m = %d\n", 161 x, z1, z2, m); 162 return 11; 163 } 164 if (xr != rcmul(oneone, x, m)) { 165 if (verbose > 1) 166 printf("Failure 12: x = %d, m = %d\n", x, m); 167 return 12; 168 } 169 170 return 0; 171} 172 173define testall(str,n,N,M,verbose) 174{ 175 local i, p, x, y, z1, z2, c, k, m; 176 177 if (isnull(verbose)) 178 verbose = defaultverbose; 179 if (verbose > 0) { 180 print str:":",:; 181 } 182 m = 0; 183 if (isnull(N)) 184 N = 1e20; 185 if (isnull(M)) 186 M = 100; 187 c = 0; 188 for (i = 0; i < n; i++) { 189 x = rand(-N, N); 190 y = rand(-N, N); 191 z1 = rand(N); 192 z2 = rand(N); 193 c = rand(N); 194 if (iseven(c)) 195 c++; 196 k = rand(M); 197 if (verbose > 1) 198 printf("x = %d, y = %d, c = %d, k = %d\n", x, y, c, k); 199 p = test4101(x,y,c,k,z1,z2); 200 if (p) { 201 m++; 202 if (verbose > 0) { 203 printf("*** Failure %d in test %d\n", p, i); 204 } 205 } 206 } 207 if (verbose > 0) { 208 if (m) { 209 printf("*** %d error(s)\n", m); 210 } else { 211 printf("passed %d tests\n", n); 212 } 213 } 214 return m; 215} 216 217define times(str,N,n,verbose) 218{ 219 local m, m2, A, B, C, x, y, t, i, z; 220 local trcin, trcout, trcmul, trcsq; 221 local tmul, tsq, tmod, tquomod; 222 223 if (isnull(verbose)) 224 verbose = defaultverbose; 225 if (verbose > 0) { 226 print str:":",:; 227 } 228 m = olen(N); 229 m2 = m^2; 230 if (isnull(n)) { 231 n = ceil(test4100_K1/power(N,1.585)); 232 if (verbose > 1) 233 printf("n = %d\n", n); 234 } 235 mat A[n]; 236 mat B[n]; 237 mat C[n]; 238 for (i = 0; i < n; i++) { 239 A[i] = rand(m); 240 B[i] = rand(m); 241 C[i] = rand(m2); 242 } 243 z = rcin(0,m); /* to initialize redc and maybe lastmod information */ 244 t = usertime(); 245 for (i = 0; i < n; i++) 246 z = rcin(A[i],m); 247 trcin = round(usertime() - t, 3); 248 t = usertime(); 249 for (i = 0; i < n; i++) 250 z = rcout(A[i],m); 251 trcout = round(usertime() - t, 3); 252 t = usertime(); 253 for (i = 0; i < n; i++) 254 z = rcmul(A[i],B[i],m); 255 trcmul = round(usertime() - t, 3); 256 t = usertime(); 257 for (i = 0; i < n; i++) 258 z = rcsq(A[i],m); 259 trcsq = round(usertime() - t, 3); 260 t = usertime(); 261 for (i = 0; i < n; i++) 262 z = A[i] * B[i]; 263 tmul = round(usertime() - t, 3); 264 t = usertime(); 265 for (i = 0; i < n; i++) 266 z = A[i]^2; 267 tsq = round(usertime() - t, 3); 268 t = usertime(); 269 for (i = 0; i < n; i++) 270 z = C[i] % A[i]; 271 tmod = round(usertime() - t, 3); 272 t = usertime(); 273 for (i = 0; i < n; i++) 274 quomod(C[i], A[i], x, y); 275 tquomod = round(usertime() - t,3); 276 277 if (verbose > 1) { 278 printf("rcin: %d, rcout: %d, rcmul: %d, rcsq: %d\n", 279 trcin, trcout, trcmul, trcsq); 280 printf("%s: mul: %d, sq: %d, mod: %d, quomod: %d\n", 281 str, tmul, tsq, tmod, tquomod); 282 } else if (verbose > 0) { 283 printf("no error(s)\n"); 284 } 285 return 0; 286} 287 288 289define powtimes(str, N1, N2, n, verbose) 290{ 291 local A, Ar, B, v, i, t, z1, z2, z3, z4, z5, cp, crc; 292 local tsmall, tnormal, tbignum, trcsmall, trcbig, m; 293 294 if (isnull(verbose)) 295 verbose = defaultverbose; 296 if (verbose > 0) { 297 print str:":",:; 298 } 299 m = 0; 300 301 if (isnull(N2)) 302 N2 = 1; 303 304 if (isnull(n)) { 305 n = ceil(test4100_K2/power(N1, 1.585)/N2); 306 printf ("n = %d\n", n); 307 } 308 mat A[n]; 309 mat Ar[n]; 310 mat B[n]; 311 v = olen(N1); 312 313 cp = config("pow2", 2); 314 crc = config("redc2", 2); 315 316 /* initialize redc and lastmod info */ 317 318 z1 = z2 = z3 = z4 = z5 = rcin(0,v); 319 320 for (i = 0; i < n; i++) { 321 A[i] = rand(v); 322 Ar[i] = rcin(A[i], v); 323 B[i] = rlen_4100(N2); 324 } 325 t = usertime(); 326 for (i = 0; i < n; i++) 327 z1 += pmod(A[i], B[i], v); 328 tbignum = round(usertime() - t, 4); 329 config("pow2", 1e6); 330 t = usertime(); 331 for (i = 0; i < n; i++) 332 z2 += pmod(A[i], B[i], v); 333 tnormal = round(usertime() - t, 4); 334 config("redc2",1e6); 335 t = usertime(); 336 for (i = 0; i < n; i++) 337 z3 += pmod(A[i], B[i], v); 338 tsmall = round(usertime() - t, 4); 339 t = usertime(); 340 for (i = 0; i < n; i++) 341 z4 += rcpow(Ar[i], B[i], v); 342 trcsmall = round(usertime() - t, 4); 343 config("redc2", 2); 344 t = usertime(); 345 for (i = 0; i < n; i++) 346 z5 += rcpow(Ar[i], B[i], v); 347 trcbig = round(usertime() - t, 4); 348 349 if (z1 != z2) { 350 ++m; 351 if (verbose > 0) { 352 print "*** z1 != z2"; 353 } 354 } else if (z1 != z3) { 355 ++m; 356 if (verbose > 0) { 357 print "*** z1 != z3"; 358 } 359 } else if (z2 != z3) { 360 ++m; 361 if (verbose > 0) { 362 print "*** z2 != z3"; 363 } 364 } else if (rcout(z4, v) != z1 % v) { 365 ++m; 366 if (verbose > 0) { 367 print "*** z4 != z1"; 368 } 369 } else if (z4 != z5) { 370 ++m; 371 if (verbose > 0) { 372 print "*** z4 != z5"; 373 } 374 } 375 config("pow2", cp); 376 config("redc2", crc); 377 if (verbose > 1) { 378 } 379 if (verbose > 1) { 380 printf("Small: %d, normal: %d, bignum: %d\n", 381 tsmall, tnormal, tbignum); 382 printf("%s: rcsmall: %d, rcbig: %d\n", 383 str, trcsmall, trcbig); 384 } else if (verbose > 0) { 385 if (m) { 386 printf("*** %d error(s)\n", m); 387 } else { 388 printf("passed\n"); 389 } 390 } 391 return 0; 392} 393 394define inittimes(str,N,n,verbose) 395{ 396 local A, M, B, R, i, t, trcin, trcout, m; 397 398 if (isnull(verbose)) 399 verbose = defaultverbose; 400 if (verbose > 0) { 401 print str:":",:; 402 } 403 m = 0; 404 if (isnull(n)) { 405 n = ceil(test4100_K1/N^2); 406 if (verbose > 1) { 407 printf ("n = %d\n", n); 408 } 409 } 410 mat A[n]; 411 mat M[n]; 412 mat B[n]; 413 mat R[n]; 414 for (i = 0; i < n; i++) { 415 M[i] = olen(N); 416 A[i] = rand(M[i]); 417 } 418 t = usertime(); 419 for (i = 0; i < n; i++) 420 R[i] = rcin(A[i], M[i]); 421 trcin = round(usertime() - t, 4); 422 for (i = 0; i < n; i++) 423 B[i] = rcout(R[i], M[i]); 424 trcout = round(usertime() - t, 4); 425 for (i = 0; i < n; i++) { 426 if (B[i] != A[i]) { 427 ++m; 428 if (verbose > 0) { 429 print "*** Error!!!"; 430 } 431 break; 432 } 433 } 434 if (verbose > 0) { 435 if (m) { 436 printf("*** %d error(s)?\n", m); 437 } else { 438 if (verbose > 1) { 439 printf("%d successful tests: rcin: %d, rcout: %d\n", 440 n, trcin, trcout); 441 } else { 442 printf("%d successful tests: passed\n", n); 443 } 444 } 445 } 446 return m; 447} 448 449/* 450 * test4100 - perform all of the above tests a bunch of times 451 */ 452define test4100(v, tnum) 453{ 454 local n; /* test parameter */ 455 456 /* 457 * set test parameters 458 */ 459 srand(4100e4100); 460 461 /* 462 * test a lot of stuff 463 */ 464 err += testall(strcat(str(tnum++),": testall(10,,500)"), 10,, 500, v); 465 err += testall(strcat(str(tnum++),": testall(200)"), 200,,, v); 466 467 err += times(strcat(str(tnum++),": times(3,3000)"), 3, 3000, v); 468 err += times(strcat(str(tnum++),": times(30,300)"), 30, 300, v); 469 err += times(strcat(str(tnum++),": times(300,30)"), 300, 30, v); 470 err += times(strcat(str(tnum++),": times(1000,3)"), 1000, 3, v); 471 472 err += powtimes(strcat(str(tnum++),": powtimes(100)"),100,,v); 473 err += powtimes(strcat(str(tnum++),": powtimes(250)"),250,,v); 474 475 err += inittimes(strcat(str(tnum++),": inittimes(10)"),10,,v); 476 err += inittimes(strcat(str(tnum++),": inittimes(100,70)"),100,70,v); 477 err += inittimes(strcat(str(tnum++),": inittimes(1000,4)"),1000,4,v); 478 479 /* 480 * report results 481 */ 482 if (v > 1) { 483 if (err) { 484 print "***", err, "error(s) found in testall"; 485 } else { 486 print "no errors in testall"; 487 } 488 } 489 return tnum; 490} 491