Article 2358 of rec.games.corewar: Newsgroups: rec.games.corewar Path: hellgate.utah.edu!caen!usenet.cis.ufl.edu!eng.ufl.edu!spool.mu.edu!howland.reston.ans.net!pipex!sunic!liuida!curofix!d91andiv From: d91andiv@IDA.LiU.SE (Anders Ivner) Subject: Fast Factors 5 Message-ID: Sender: news@ida.liu.se Organization: CIS Dept, University of Linkoping, Sweden Distribution: rec Date: Tue, 14 Dec 1993 19:06:41 GMT Lines: 78 Here's my solution to the factorization problem. Worst time: ~8200 cycles (89*89) Average time: ~7500 cycles Best time: ~6700 cycles (2) The program is based on a faster division algorithm than the simple loop most people seem to have used (?). My first version included a table of all primes < 90, and several checks to speed up the execution, which resulted in a worst case time of ~2000 cycles. After that, I optimized only for size, at the cost of speed. I removed the primetable and as many checks as possible (Hence the long best-case time). Some explanations: np is a list of multiples of the current factor (2^n * f < 4000). q is a pointer to the quotient. I can save one instruction by using an unused b-field to change the pointer, rather than MOVing #0. x is the number to be divided, a copy of input. The code can be divided into four 'parts': lines foo - yes+3 : Initialize division algorithm. Create 2^n * f. lines shift - prev+2 : Division algorithm lines found - found+1 : Last division succeded, store results. lines next - next+3 : Division failed, try next number. /Anders Ivner BTW: Stefan, how did you manage to get it down to 14 instructions?? I tried writing one a short as possible (totally ignoring speed), but never got it below 16 instructions. ;redcode ;name Fast Factors 5 ;author Anders Ivner np equ yes+4000 q equ yes+7500 x equ yes+1000 input dat #2 ;dividable found mov factor,