Article 2357 of rec.games.corewar: Path: hellgate.utah.edu!dog.ee.lbl.gov!agate!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!olivea!sgigate.sgi.com!sgiblab!cs.uoregon.edu!news.uoregon.edu!gaia.ucs.orst.edu!news.csos.orst.edu!CSOS.ORST.EDU!wangsawm From: wangsawm@CSOS.ORST.EDU (Mintardjo W.) Newsgroups: rec.games.corewar Subject: PNF 3 Date: 12 Dec 1993 06:02:49 GMT Organization: CS Outreach Services, Oregon State University, Corvallis, OR, USA Lines: 144 Message-ID: <2eec69\$alc@jadzia.CSOS.ORST.EDU> NNTP-Posting-Host: csos.orst.edu Here is the way I did with prime number factorization: PNF 3. Worst cycle around 9970 (prime #7793). The algorithm description can be found at the end of the code. Enjoy, Mintardjo W. ============================================================================== ;redcode ;name PNF 3 ;author Mintardjo W. s1 equ 16 s2 equ s1 copy equ (input - 1) out equ (copy - 1) posn equ (out - s1 - 1) ; this holds the current prime number i equ (input - 25) j equ (i + 4000) prime equ (i - 1) ; this holds the first prime number dst equ (last + s1) src equ (dst + 1) sdst equ (src + s1) input dat #-3 ; please put input here nprime dat #prime ;start jmz last, input ;trace start mov #2, prime ; the first prime starts with 2 ;trace off mov #1, posn ; the next starts with 3 - 2. -2 for adjustment ; mov #0, out mark0 mov #s1, src mov @nprime, input) loop1 add @src, @dst slt @dst, @src djn loop1, copy slt @dst, @src ; check for overflow djn fill, src ; and src should be decremented as well mov #0, @dst ; mark the max number at the end mov input, copy ; do not alter the input value at input variable mov #s1+(sdst-dst), dst loop2 mov #0, sdst loop3 slt copy, 0 then reiterate loop4 sub @dst, 0 ; negate the negative exp number add @nprime, 0, then the number is not divisible by current base prime number, jump to step 4. 3. Get the quotient. The representation of I should be: I = a'^i + a'^j + ... + a'^k Find in this exponents, the smallest exponent. Then for every term, subtract it with the smallest exponent. Let's say a'^k is the smallest term, then. I / a'^k = a'^(i-k) + a'^(j-k) + ... + 1 The right hand equation is the quotient of the input divided by the prime number. If the sum in right hand equation = 1, then I = a'^k and we are done. Record a' as many as k in the output. 4. This step is to find the next prime number. I used a modified version of sieve of Erasthosenes. Once a prime number is found and if it is less than 90, then repeat step 1. Otherwise, record the prime in output and stop. In PNF 2, I didn't limit the number of base prime number to be searched and the result was pretty amazing a large number of average cycle.