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,