From news-rocq.inria.fr!couchey.inria.fr!doligez Fri Dec 8 19:48:48 1995 Article: 3255 of rec.games.corewar Path: news-rocq.inria.fr!couchey.inria.fr!doligez From: Planar Newsgroups: rec.games.corewar Subject: Re: Core_ Warrior_ 8 Date: 8 Dec 1995 13:57:45 GMT Organization: "Brilliance is typically the act of an individual, but incredible stupidity can usually be traced to an organization." -- Jon Bentley Lines: 91 Distribution: world Message-ID: <4a9g8p$kb7@news-rocq.inria.fr> References: <49v6fm$pko@mozo.cc.purdue.edu> <4a3tm7$r1i@agate.berkeley.edu> <4a4ot9$ks5@news-rocq.inria.fr> <4a7ngd$orp@agate.berkeley.edu> NNTP-Posting-Host: couchey.inria.fr Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit In article <4a7ngd$orp@agate.berkeley.edu>, mconst@soda.CSUA.Berkeley.EDU (Michael Constant) writes: >The DIV is at the beginning of my loop. And FWIW, I think the cycle you >save by having the assembler compute the division is offset by the extra >jump you have to put in. This is what I had in mind: ;redcode ;name Euclid's extended 2 ;author Planar ;assert MAXLENGTH >= 11 n equ 3 org start yx dat -n, n ; y = CORESIZE - n ab dat 1, 0 q dat 0, CORESIZE/n loop mov.ab yx, q ; (y) div.b yx, q ; q' = y' / x' start mul.ab ab, q ; (a*q) mov.x ab, ab ; (b); b' = a sub.ba q, ab ; a' = b - a*q mov.x yx, yx ; (y); y' = x mod.ab yx, yx ; x' = y % x jmn.b loop, yx ; We're done if x = 0 end The loop is only 8 instructions (6 the first time through), and the setup code (not included here) would be 5 instructions, including the jump to "start". Total: 3+8*loops instructions. We can go even further: unroll the loop once and suppress the MOV.X instructions (this time with the setup code): ;redcode ;name Euclid's extended 3 ;author Planar ;assert MAXLENGTH >= 21 n equ 3 ; n is assumed relatively prime with CORESIZE org begin yx dat 0, n ab dat 1, 0 ; The result will be in the A-field. q dat 0 begin mov.a #-1, yx ; (-1) mul.ba yx, yx ; y = -n = CORESIZE-n mov.ab #-1, q ; (CORESIZE-1) A div.b yx, q ; (CORESIZE-1)/n == CORESIZE/n jmp start loop mov.ab yx, q ; (y) B div.b yx, q ; q' = y' / x' start mul.ab ab, q ; (a*q) sub.b q, ab ; a' = b - a*q mod.ba yx, yx ; x' = y % x jmz.a done, yx ; We're done if x = 0 mov.b yx, q ; (y) div.ab yx, q ; q' = y' / x' mul.b ab, q ; (a*q) sub.ba q, ab ; a' = b - a*q mod.ab yx, yx ; x' = y % x jmn.b loop, yx ; We're done if x = 0 C mov.ba ab, ab ; Put the result into the A field. done end You can make it one instruction shorter by removing A and placing the "start" label at B. Total time: 3.5+6*loops (counting the same number of loops as above). The half-cycle is because C is executed once in half the computations. >Right. As you said, this is not hard -- but many people don't know it. >I had seen several imp-calculators posted before mine, none of which took >advantage of this fact. Glad to see that today's posters are more mathe- >matically inclined! When I wrote my article for Core Warrior, I thought I was first, but I hadn't read Theme carefully enough (the "euclid" label should have tipped me off). I can't wait for the next unknown-core-size tournament round (-: -- Planar