1;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 2; File: takr.sch 3; Description: TAKR benchmark 4; Author: Richard Gabriel 5; Created: 12-Apr-85 6; Modified: 12-Apr-85 10:12:43 (Bob Shaw) 7; 22-Jul-87 (Will Clinger) 8; Language: Scheme 9; Status: Public Domain 10;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 11 12;;; TAKR -- 100 function (count `em) version of TAK that tries to defeat cache 13;;; memory effects. Results should be the same as for TAK on stack machines. 14;;; Distribution of calls is not completely flat. 15 16(define (tak0 x y z) 17 (cond ((not (< y x)) z) 18 (else (tak1 (tak37 (- x 1) y z) 19 (tak11 (- y 1) z x) 20 (tak17 (- z 1) x y))))) 21(define (tak1 x y z) 22 (cond ((not (< y x)) z) 23 (else (tak2 (tak74 (- x 1) y z) 24 (tak22 (- y 1) z x) 25 (tak34 (- z 1) x y))))) 26(define (tak2 x y z) 27 (cond ((not (< y x)) z) 28 (else (tak3 (tak11 (- x 1) y z) 29 (tak33 (- y 1) z x) 30 (tak51 (- z 1) x y))))) 31(define (tak3 x y z) 32 (cond ((not (< y x)) z) 33 (else (tak4 (tak48 (- x 1) y z) 34 (tak44 (- y 1) z x) 35 (tak68 (- z 1) x y))))) 36(define (tak4 x y z) 37 (cond ((not (< y x)) z) 38 (else (tak5 (tak85 (- x 1) y z) 39 (tak55 (- y 1) z x) 40 (tak85 (- z 1) x y))))) 41(define (tak5 x y z) 42 (cond ((not (< y x)) z) 43 (else (tak6 (tak22 (- x 1) y z) 44 (tak66 (- y 1) z x) 45 (tak2 (- z 1) x y))))) 46(define (tak6 x y z) 47 (cond ((not (< y x)) z) 48 (else (tak7 (tak59 (- x 1) y z) 49 (tak77 (- y 1) z x) 50 (tak19 (- z 1) x y))))) 51(define (tak7 x y z) 52 (cond ((not (< y x)) z) 53 (else (tak8 (tak96 (- x 1) y z) 54 (tak88 (- y 1) z x) 55 (tak36 (- z 1) x y))))) 56(define (tak8 x y z) 57 (cond ((not (< y x)) z) 58 (else (tak9 (tak33 (- x 1) y z) 59 (tak99 (- y 1) z x) 60 (tak53 (- z 1) x y))))) 61(define (tak9 x y z) 62 (cond ((not (< y x)) z) 63 (else (tak10 (tak70 (- x 1) y z) 64 (tak10 (- y 1) z x) 65 (tak70 (- z 1) x y))))) 66(define (tak10 x y z) 67 (cond ((not (< y x)) z) 68 (else (tak11 (tak7 (- x 1) y z) 69 (tak21 (- y 1) z x) 70 (tak87 (- z 1) x y))))) 71(define (tak11 x y z) 72 (cond ((not (< y x)) z) 73 (else (tak12 (tak44 (- x 1) y z) 74 (tak32 (- y 1) z x) 75 (tak4 (- z 1) x y))))) 76(define (tak12 x y z) 77 (cond ((not (< y x)) z) 78 (else (tak13 (tak81 (- x 1) y z) 79 (tak43 (- y 1) z x) 80 (tak21 (- z 1) x y))))) 81 82(define (tak13 x y z) 83 (cond ((not (< y x)) z) 84 (else (tak14 (tak18 (- x 1) y z) 85 (tak54 (- y 1) z x) 86 (tak38 (- z 1) x y))))) 87(define (tak14 x y z) 88 (cond ((not (< y x)) z) 89 (else (tak15 (tak55 (- x 1) y z) 90 (tak65 (- y 1) z x) 91 (tak55 (- z 1) x y))))) 92(define (tak15 x y z) 93 (cond ((not (< y x)) z) 94 (else (tak16 (tak92 (- x 1) y z) 95 (tak76 (- y 1) z x) 96 (tak72 (- z 1) x y))))) 97(define (tak16 x y z) 98 (cond ((not (< y x)) z) 99 (else (tak17 (tak29 (- x 1) y z) 100 (tak87 (- y 1) z x) 101 (tak89 (- z 1) x y))))) 102(define (tak17 x y z) 103 (cond ((not (< y x)) z) 104 (else (tak18 (tak66 (- x 1) y z) 105 (tak98 (- y 1) z x) 106 (tak6 (- z 1) x y))))) 107(define (tak18 x y z) 108 (cond ((not (< y x)) z) 109 (else (tak19 (tak3 (- x 1) y z) 110 (tak9 (- y 1) z x) 111 (tak23 (- z 1) x y))))) 112(define (tak19 x y z) 113 (cond ((not (< y x)) z) 114 (else (tak20 (tak40 (- x 1) y z) 115 (tak20 (- y 1) z x) 116 (tak40 (- z 1) x y))))) 117(define (tak20 x y z) 118 (cond ((not (< y x)) z) 119 (else (tak21 (tak77 (- x 1) y z) 120 (tak31 (- y 1) z x) 121 (tak57 (- z 1) x y))))) 122(define (tak21 x y z) 123 (cond ((not (< y x)) z) 124 (else (tak22 (tak14 (- x 1) y z) 125 (tak42 (- y 1) z x) 126 (tak74 (- z 1) x y))))) 127(define (tak22 x y z) 128 (cond ((not (< y x)) z) 129 (else (tak23 (tak51 (- x 1) y z) 130 (tak53 (- y 1) z x) 131 (tak91 (- z 1) x y))))) 132(define (tak23 x y z) 133 (cond ((not (< y x)) z) 134 (else (tak24 (tak88 (- x 1) y z) 135 (tak64 (- y 1) z x) 136 (tak8 (- z 1) x y))))) 137(define (tak24 x y z) 138 (cond ((not (< y x)) z) 139 (else (tak25 (tak25 (- x 1) y z) 140 (tak75 (- y 1) z x) 141 (tak25 (- z 1) x y))))) 142(define (tak25 x y z) 143 (cond ((not (< y x)) z) 144 (else (tak26 (tak62 (- x 1) y z) 145 (tak86 (- y 1) z x) 146 (tak42 (- z 1) x y))))) 147(define (tak26 x y z) 148 (cond ((not (< y x)) z) 149 (else (tak27 (tak99 (- x 1) y z) 150 (tak97 (- y 1) z x) 151 (tak59 (- z 1) x y))))) 152(define (tak27 x y z) 153 (cond ((not (< y x)) z) 154 (else (tak28 (tak36 (- x 1) y z) 155 (tak8 (- y 1) z x) 156 (tak76 (- z 1) x y))))) 157(define (tak28 x y z) 158 (cond ((not (< y x)) z) 159 (else (tak29 (tak73 (- x 1) y z) 160 (tak19 (- y 1) z x) 161 (tak93 (- z 1) x y))))) 162(define (tak29 x y z) 163 (cond ((not (< y x)) z) 164 (else (tak30 (tak10 (- x 1) y z) 165 (tak30 (- y 1) z x) 166 (tak10 (- z 1) x y))))) 167(define (tak30 x y z) 168 (cond ((not (< y x)) z) 169 (else (tak31 (tak47 (- x 1) y z) 170 (tak41 (- y 1) z x) 171 (tak27 (- z 1) x y))))) 172(define (tak31 x y z) 173 (cond ((not (< y x)) z) 174 (else (tak32 (tak84 (- x 1) y z) 175 (tak52 (- y 1) z x) 176 (tak44 (- z 1) x y))))) 177(define (tak32 x y z) 178 (cond ((not (< y x)) z) 179 (else (tak33 (tak21 (- x 1) y z) 180 (tak63 (- y 1) z x) 181 (tak61 (- z 1) x y))))) 182(define (tak33 x y z) 183 (cond ((not (< y x)) z) 184 (else (tak34 (tak58 (- x 1) y z) 185 (tak74 (- y 1) z x) 186 (tak78 (- z 1) x y))))) 187(define (tak34 x y z) 188 (cond ((not (< y x)) z) 189 (else (tak35 (tak95 (- x 1) y z) 190 (tak85 (- y 1) z x) 191 (tak95 (- z 1) x y))))) 192(define (tak35 x y z) 193 (cond ((not (< y x)) z) 194 (else (tak36 (tak32 (- x 1) y z) 195 (tak96 (- y 1) z x) 196 (tak12 (- z 1) x y))))) 197(define (tak36 x y z) 198 (cond ((not (< y x)) z) 199 (else (tak37 (tak69 (- x 1) y z) 200 (tak7 (- y 1) z x) 201 (tak29 (- z 1) x y))))) 202(define (tak37 x y z) 203 (cond ((not (< y x)) z) 204 (else (tak38 (tak6 (- x 1) y z) 205 (tak18 (- y 1) z x) 206 (tak46 (- z 1) x y))))) 207(define (tak38 x y z) 208 (cond ((not (< y x)) z) 209 (else (tak39 (tak43 (- x 1) y z) 210 (tak29 (- y 1) z x) 211 (tak63 (- z 1) x y))))) 212(define (tak39 x y z) 213 (cond ((not (< y x)) z) 214 (else (tak40 (tak80 (- x 1) y z) 215 (tak40 (- y 1) z x) 216 (tak80 (- z 1) x y))))) 217(define (tak40 x y z) 218 (cond ((not (< y x)) z) 219 (else (tak41 (tak17 (- x 1) y z) 220 (tak51 (- y 1) z x) 221 (tak97 (- z 1) x y))))) 222(define (tak41 x y z) 223 (cond ((not (< y x)) z) 224 (else (tak42 (tak54 (- x 1) y z) 225 (tak62 (- y 1) z x) 226 (tak14 (- z 1) x y))))) 227(define (tak42 x y z) 228 (cond ((not (< y x)) z) 229 (else (tak43 (tak91 (- x 1) y z) 230 (tak73 (- y 1) z x) 231 (tak31 (- z 1) x y))))) 232(define (tak43 x y z) 233 (cond ((not (< y x)) z) 234 (else (tak44 (tak28 (- x 1) y z) 235 (tak84 (- y 1) z x) 236 (tak48 (- z 1) x y))))) 237(define (tak44 x y z) 238 (cond ((not (< y x)) z) 239 (else (tak45 (tak65 (- x 1) y z) 240 (tak95 (- y 1) z x) 241 (tak65 (- z 1) x y))))) 242(define (tak45 x y z) 243 (cond ((not (< y x)) z) 244 (else (tak46 (tak2 (- x 1) y z) 245 (tak6 (- y 1) z x) 246 (tak82 (- z 1) x y))))) 247(define (tak46 x y z) 248 (cond ((not (< y x)) z) 249 (else (tak47 (tak39 (- x 1) y z) 250 (tak17 (- y 1) z x) 251 (tak99 (- z 1) x y))))) 252(define (tak47 x y z) 253 (cond ((not (< y x)) z) 254 (else (tak48 (tak76 (- x 1) y z) 255 (tak28 (- y 1) z x) 256 (tak16 (- z 1) x y))))) 257(define (tak48 x y z) 258 (cond ((not (< y x)) z) 259 (else (tak49 (tak13 (- x 1) y z) 260 (tak39 (- y 1) z x) 261 (tak33 (- z 1) x y))))) 262(define (tak49 x y z) 263 (cond ((not (< y x)) z) 264 (else (tak50 (tak50 (- x 1) y z) 265 (tak50 (- y 1) z x) 266 (tak50 (- z 1) x y))))) 267(define (tak50 x y z) 268 (cond ((not (< y x)) z) 269 (else (tak51 (tak87 (- x 1) y z) 270 (tak61 (- y 1) z x) 271 (tak67 (- z 1) x y))))) 272(define (tak51 x y z) 273 (cond ((not (< y x)) z) 274 (else (tak52 (tak24 (- x 1) y z) 275 (tak72 (- y 1) z x) 276 (tak84 (- z 1) x y))))) 277(define (tak52 x y z) 278 (cond ((not (< y x)) z) 279 (else (tak53 (tak61 (- x 1) y z) 280 (tak83 (- y 1) z x) 281 (tak1 (- z 1) x y))))) 282(define (tak53 x y z) 283 (cond ((not (< y x)) z) 284 (else (tak54 (tak98 (- x 1) y z) 285 (tak94 (- y 1) z x) 286 (tak18 (- z 1) x y))))) 287(define (tak54 x y z) 288 (cond ((not (< y x)) z) 289 (else (tak55 (tak35 (- x 1) y z) 290 (tak5 (- y 1) z x) 291 (tak35 (- z 1) x y))))) 292(define (tak55 x y z) 293 (cond ((not (< y x)) z) 294 (else (tak56 (tak72 (- x 1) y z) 295 (tak16 (- y 1) z x) 296 (tak52 (- z 1) x y))))) 297(define (tak56 x y z) 298 (cond ((not (< y x)) z) 299 (else (tak57 (tak9 (- x 1) y z) 300 (tak27 (- y 1) z x) 301 (tak69 (- z 1) x y))))) 302(define (tak57 x y z) 303 (cond ((not (< y x)) z) 304 (else (tak58 (tak46 (- x 1) y z) 305 (tak38 (- y 1) z x) 306 (tak86 (- z 1) x y))))) 307(define (tak58 x y z) 308 (cond ((not (< y x)) z) 309 (else (tak59 (tak83 (- x 1) y z) 310 (tak49 (- y 1) z x) 311 (tak3 (- z 1) x y))))) 312(define (tak59 x y z) 313 (cond ((not (< y x)) z) 314 (else (tak60 (tak20 (- x 1) y z) 315 (tak60 (- y 1) z x) 316 (tak20 (- z 1) x y))))) 317(define (tak60 x y z) 318 (cond ((not (< y x)) z) 319 (else (tak61 (tak57 (- x 1) y z) 320 (tak71 (- y 1) z x) 321 (tak37 (- z 1) x y))))) 322(define (tak61 x y z) 323 (cond ((not (< y x)) z) 324 (else (tak62 (tak94 (- x 1) y z) 325 (tak82 (- y 1) z x) 326 (tak54 (- z 1) x y))))) 327(define (tak62 x y z) 328 (cond ((not (< y x)) z) 329 (else (tak63 (tak31 (- x 1) y z) 330 (tak93 (- y 1) z x) 331 (tak71 (- z 1) x y))))) 332(define (tak63 x y z) 333 (cond ((not (< y x)) z) 334 (else (tak64 (tak68 (- x 1) y z) 335 (tak4 (- y 1) z x) 336 (tak88 (- z 1) x y))))) 337(define (tak64 x y z) 338 (cond ((not (< y x)) z) 339 (else (tak65 (tak5 (- x 1) y z) 340 (tak15 (- y 1) z x) 341 (tak5 (- z 1) x y))))) 342(define (tak65 x y z) 343 (cond ((not (< y x)) z) 344 (else (tak66 (tak42 (- x 1) y z) 345 (tak26 (- y 1) z x) 346 (tak22 (- z 1) x y))))) 347(define (tak66 x y z) 348 (cond ((not (< y x)) z) 349 (else (tak67 (tak79 (- x 1) y z) 350 (tak37 (- y 1) z x) 351 (tak39 (- z 1) x y))))) 352(define (tak67 x y z) 353 (cond ((not (< y x)) z) 354 (else (tak68 (tak16 (- x 1) y z) 355 (tak48 (- y 1) z x) 356 (tak56 (- z 1) x y))))) 357(define (tak68 x y z) 358 (cond ((not (< y x)) z) 359 (else (tak69 (tak53 (- x 1) y z) 360 (tak59 (- y 1) z x) 361 (tak73 (- z 1) x y))))) 362(define (tak69 x y z) 363 (cond ((not (< y x)) z) 364 (else (tak70 (tak90 (- x 1) y z) 365 (tak70 (- y 1) z x) 366 (tak90 (- z 1) x y))))) 367(define (tak70 x y z) 368 (cond ((not (< y x)) z) 369 (else (tak71 (tak27 (- x 1) y z) 370 (tak81 (- y 1) z x) 371 (tak7 (- z 1) x y))))) 372(define (tak71 x y z) 373 (cond ((not (< y x)) z) 374 (else (tak72 (tak64 (- x 1) y z) 375 (tak92 (- y 1) z x) 376 (tak24 (- z 1) x y))))) 377(define (tak72 x y z) 378 (cond ((not (< y x)) z) 379 (else (tak73 (tak1 (- x 1) y z) 380 (tak3 (- y 1) z x) 381 (tak41 (- z 1) x y))))) 382(define (tak73 x y z) 383 (cond ((not (< y x)) z) 384 (else (tak74 (tak38 (- x 1) y z) 385 (tak14 (- y 1) z x) 386 (tak58 (- z 1) x y))))) 387(define (tak74 x y z) 388 (cond ((not (< y x)) z) 389 (else (tak75 (tak75 (- x 1) y z) 390 (tak25 (- y 1) z x) 391 (tak75 (- z 1) x y))))) 392(define (tak75 x y z) 393 (cond ((not (< y x)) z) 394 (else (tak76 (tak12 (- x 1) y z) 395 (tak36 (- y 1) z x) 396 (tak92 (- z 1) x y))))) 397(define (tak76 x y z) 398 (cond ((not (< y x)) z) 399 (else (tak77 (tak49 (- x 1) y z) 400 (tak47 (- y 1) z x) 401 (tak9 (- z 1) x y))))) 402(define (tak77 x y z) 403 (cond ((not (< y x)) z) 404 (else (tak78 (tak86 (- x 1) y z) 405 (tak58 (- y 1) z x) 406 (tak26 (- z 1) x y))))) 407(define (tak78 x y z) 408 (cond ((not (< y x)) z) 409 (else (tak79 (tak23 (- x 1) y z) 410 (tak69 (- y 1) z x) 411 (tak43 (- z 1) x y))))) 412(define (tak79 x y z) 413 (cond ((not (< y x)) z) 414 (else (tak80 (tak60 (- x 1) y z) 415 (tak80 (- y 1) z x) 416 (tak60 (- z 1) x y))))) 417(define (tak80 x y z) 418 (cond ((not (< y x)) z) 419 (else (tak81 (tak97 (- x 1) y z) 420 (tak91 (- y 1) z x) 421 (tak77 (- z 1) x y))))) 422(define (tak81 x y z) 423 (cond ((not (< y x)) z) 424 (else (tak82 (tak34 (- x 1) y z) 425 (tak2 (- y 1) z x) 426 (tak94 (- z 1) x y))))) 427(define (tak82 x y z) 428 (cond ((not (< y x)) z) 429 (else (tak83 (tak71 (- x 1) y z) 430 (tak13 (- y 1) z x) 431 (tak11 (- z 1) x y))))) 432(define (tak83 x y z) 433 (cond ((not (< y x)) z) 434 (else (tak84 (tak8 (- x 1) y z) 435 (tak24 (- y 1) z x) 436 (tak28 (- z 1) x y))))) 437(define (tak84 x y z) 438 (cond ((not (< y x)) z) 439 (else (tak85 (tak45 (- x 1) y z) 440 (tak35 (- y 1) z x) 441 (tak45 (- z 1) x y))))) 442(define (tak85 x y z) 443 (cond ((not (< y x)) z) 444 (else (tak86 (tak82 (- x 1) y z) 445 (tak46 (- y 1) z x) 446 (tak62 (- z 1) x y))))) 447(define (tak86 x y z) 448 (cond ((not (< y x)) z) 449 (else (tak87 (tak19 (- x 1) y z) 450 (tak57 (- y 1) z x) 451 (tak79 (- z 1) x y))))) 452(define (tak87 x y z) 453 (cond ((not (< y x)) z) 454 (else (tak88 (tak56 (- x 1) y z) 455 (tak68 (- y 1) z x) 456 (tak96 (- z 1) x y))))) 457(define (tak88 x y z) 458 (cond ((not (< y x)) z) 459 (else (tak89 (tak93 (- x 1) y z) 460 (tak79 (- y 1) z x) 461 (tak13 (- z 1) x y))))) 462(define (tak89 x y z) 463 (cond ((not (< y x)) z) 464 (else (tak90 (tak30 (- x 1) y z) 465 (tak90 (- y 1) z x) 466 (tak30 (- z 1) x y))))) 467(define (tak90 x y z) 468 (cond ((not (< y x)) z) 469 (else (tak91 (tak67 (- x 1) y z) 470 (tak1 (- y 1) z x) 471 (tak47 (- z 1) x y))))) 472(define (tak91 x y z) 473 (cond ((not (< y x)) z) 474 (else (tak92 (tak4 (- x 1) y z) 475 (tak12 (- y 1) z x) 476 (tak64 (- z 1) x y))))) 477(define (tak92 x y z) 478 (cond ((not (< y x)) z) 479 (else (tak93 (tak41 (- x 1) y z) 480 (tak23 (- y 1) z x) 481 (tak81 (- z 1) x y))))) 482(define (tak93 x y z) 483 (cond ((not (< y x)) z) 484 (else (tak94 (tak78 (- x 1) y z) 485 (tak34 (- y 1) z x) 486 (tak98 (- z 1) x y))))) 487(define (tak94 x y z) 488 (cond ((not (< y x)) z) 489 (else (tak95 (tak15 (- x 1) y z) 490 (tak45 (- y 1) z x) 491 (tak15 (- z 1) x y))))) 492(define (tak95 x y z) 493 (cond ((not (< y x)) z) 494 (else (tak96 (tak52 (- x 1) y z) 495 (tak56 (- y 1) z x) 496 (tak32 (- z 1) x y))))) 497(define (tak96 x y z) 498 (cond ((not (< y x)) z) 499 (else (tak97 (tak89 (- x 1) y z) 500 (tak67 (- y 1) z x) 501 (tak49 (- z 1) x y))))) 502(define (tak97 x y z) 503 (cond ((not (< y x)) z) 504 (else (tak98 (tak26 (- x 1) y z) 505 (tak78 (- y 1) z x) 506 (tak66 (- z 1) x y))))) 507(define (tak98 x y z) 508 (cond ((not (< y x)) z) 509 (else (tak99 (tak63 (- x 1) y z) 510 (tak89 (- y 1) z x) 511 (tak83 (- z 1) x y))))) 512(define (tak99 x y z) 513 (cond ((not (< y x)) z) 514 (else (tak0 (tak0 (- x 1) y z) 515 (tak0 (- y 1) z x) 516 (tak0 (- z 1) x y))))) 517 518;;; call: (tak0 18 12 6) 519 520(let ((input (with-input-from-file "input.txt" read))) 521 (time 522 (let loop ((n 500) (v 0)) 523 (if (zero? n) 524 v 525 (loop (- n 1) (tak0 18 12 (if input 6 0))))))) 526