Sections
Home
Hills
Infinite Hills
Tournaments
Software
Evolving
Optimizer
Community
Newsletter
Discussion
History
Sections
 
For Beginners
First Steps
FAQ
Guides
Lexicon
Benchmarks
For Beginners
> Home > The Corewar Lexicon > Imp Steps

Imp Steps


1.1 Imp Steps for Coresize 8000

There are 802 imp-pairs.
  point  step
=================================  
    3 *  2667 =     1 *  8000 + 1
    7 *  1143 =     1 *  8000 + 1
    9 *   889 =     1 *  8000 + 1
   11 *  5091 =     7 *  8000 + 1
   13 *  3077 =     5 *  8000 + 1
   17 *  2353 =     5 *  8000 + 1
   19 *  7579 =    18 *  8000 + 1
   21 *   381 =     1 *  8000 + 1
   23 *  2087 =     6 *  8000 + 1
   27 *  2963 =    10 *  8000 + 1
   29 *  6069 =    22 *  8000 + 1
   31 *  3871 =    15 *  8000 + 1
   33 *  1697 =     7 *  8000 + 1
   37 *  4973 =    23 *  8000 + 1
   39 *  6359 =    31 *  8000 + 1
   41 *  1561 =     8 *  8000 + 1
   43 *  3907 =    21 *  8000 + 1
   47 *  2383 =    14 *  8000 + 1
   49 *  2449 =    15 *  8000 + 1 <--- Biggest binary launch in 98 lines
   51 *  3451 =    22 *  8000 + 1
   53 *  2717 =    18 *  8000 + 1
   57 *  5193 =    37 *  8000 + 1
   59 *  4339 =    32 *  8000 + 1
   61 *  3541 =    27 *  8000 + 1
   63 *   127 =     1 *  8000 + 1
   67 *  7403 =    62 *  8000 + 1
   69 *  6029 =    52 *  8000 + 1
   71 *  3831 =    34 *  8000 + 1
   73 *  6137 =    56 *  8000 + 1
   77 *  3013 =    29 *  8000 + 1
   79 *  1519 =    15 *  8000 + 1
   81 *  6321 =    64 *  8000 + 1
   83 *  6747 =    70 *  8000 + 1
   87 *  2023 =    22 *  8000 + 1
   89 *   809 =     9 *  8000 + 1
   91 *  5011 =    57 *  8000 + 1
   93 *  3957 =    46 *  8000 + 1
   97 *  6433 =    78 *  8000 + 1
   99 *  5899 =    73 *  8000 + 1
  101 *  1901 =    24 *  8000 + 1
  103 *  7767 =   100 *  8000 + 1
  107 *  2243 =    30 *  8000 + 1
  109 *  2789 =    38 *  8000 + 1
  111 *  6991 =    97 *  8000 + 1
  113 *  4177 =    59 *  8000 + 1
  117 *  7453 =   109 *  8000 + 1
  119 *  1479 =    22 *  8000 + 1
  121 *  6281 =    95 *  8000 + 1
  123 *  3187 =    49 *  8000 + 1

1.2 Imp Steps for Coresize 8192

There are 1025 imp-pairs. That's a lot more than for core size 8000, because 8192 is a power of 2, so it has more relative primes.
  point  step
=================================  
    3 *  2731 =     1 *  8192 + 1
    5 *  3277 =     2 *  8192 + 1
    7 *  3511 =     3 *  8192 + 1
    9 *  3641 =     4 *  8192 + 1
   11 *  2979 =     4 *  8192 + 1
   13 *  3781 =     6 *  8192 + 1
   15 *  3823 =     7 *  8192 + 1
   17 *  4337 =     9 *  8192 + 1
   19 *  2587 =     6 *  8192 + 1
   21 *  3901 =    10 *  8192 + 1
   23 *  6055 =    17 *  8192 + 1
   25 *  7209 =    22 *  8192 + 1
   27 *  6675 =    22 *  8192 + 1
   29 *   565 =     2 *  8192 + 1
   31 *  7135 =    27 *  8192 + 1
   33 *   993 =     4 *  8192 + 1
   35 *  3979 =    17 *  8192 + 1
   37 *  7085 =    32 *  8192 + 1
   39 *  3991 =    19 *  8192 + 1
   41 *  7193 =    36 *  8192 + 1
   43 *  7811 =    41 *  8192 + 1
   45 *  4005 =    22 *  8192 + 1
   47 *  1743 =    10 *  8192 + 1
   49 *  6353 =    38 *  8192 + 1
   51 *  6907 =    43 *  8192 + 1
   53 *  4637 =    30 *  8192 + 1
   55 *  5511 =    37 *  8192 + 1
   57 *  3593 =    25 *  8192 + 1
   59 *  6387 =    46 *  8192 + 1
   61 *  5909 =    44 *  8192 + 1
   63 *  4031 =    31 *  8192 + 1
   65 *  4033 =    32 *  8192 + 1
   67 *  3179 =    26 *  8192 + 1
   69 *  4749 =    40 *  8192 + 1
   71 *  2423 =    21 *  8192 + 1
   73 *  4601 =    41 *  8192 + 1
   75 *  2403 =    22 *  8192 + 1
   77 *  6277 =    59 *  8192 + 1
   79 *  5807 =    56 *  8192 + 1
   81 *  2225 =    22 *  8192 + 1
   83 *   987 =    10 *  8192 + 1
   85 *  7421 =    77 *  8192 + 1
   87 *  2919 =    31 *  8192 + 1
   89 *  2025 =    22 *  8192 + 1
   91 *  4051 =    45 *  8192 + 1
   93 *  5109 =    58 *  8192 + 1
   95 *  7071 =    82 *  8192 + 1
   97 *   929 =    11 *  8192 + 1
   99 *   331 =     4 *  8192 + 1
  101 *  4461 =    55 *  8192 + 1
  103 *  6999 =    88 *  8192 + 1
  105 *  4057 =    52 *  8192 + 1
  107 *  3139 =    41 *  8192 + 1
  109 *  2405 =    32 *  8192 + 1
  111 *  7823 =   106 *  8192 + 1
  113 *   145 =     2 *  8192 + 1
  115 *  1211 =    17 *  8192 + 1
  117 *  4061 =    58 *  8192 + 1
  119 *  6471 =    94 *  8192 + 1
  121 *  2505 =    37 *  8192 + 1
  123 *  7859 =   118 *  8192 + 1
  125 *  6357 =    97 *  8192 + 1
  127 *  8063 =   125 *  8192 + 1

1.3 Imp Steps for Coresize 55440

There are 2896 imp-pairs, many of which are too large to be useful.
  point  step
=================================  
   13 * 34117 =     8 * 55440 + 1
   17 * 35873 =    11 * 55440 + 1
   19 * 29179 =    10 * 55440 + 1
   23 * 38567 =    16 * 55440 + 1
   29 * 21029 =    11 * 55440 + 1
   31 * 32191 =    18 * 55440 + 1
   37 * 43453 =    29 * 55440 + 1
   41 *  6761 =     5 * 55440 + 1
   43 * 42547 =    33 * 55440 + 1
   47 * 47183 =    40 * 55440 + 1
   53 * 27197 =    26 * 55440 + 1
   59 *  2819 =     3 * 55440 + 1
   61 * 30901 =    34 * 55440 + 1
   67 * 44683 =    54 * 55440 + 1
   71 * 10151 =    13 * 55440 + 1
   73 * 31897 =    42 * 55440 + 1
   79 * 15439 =    22 * 55440 + 1
   83 * 14027 =    21 * 55440 + 1
   89 * 31769 =    51 * 55440 + 1
   97 * 49153 =    86 * 55440 + 1 <--- Biggest binary launch in 198 lines
  101 * 24701 =    45 * 55440 + 1
  103 * 53287 =    99 * 55440 + 1
  107 * 43523 =    84 * 55440 + 1
  109 *  4069 =     8 * 55440 + 1
  113 * 45137 =    92 * 55440 + 1
  127 * 12223 =    28 * 55440 + 1
  131 * 41051 =    97 * 55440 + 1
  137 * 27113 =    67 * 55440 + 1
  139 * 21139 =    53 * 55440 + 1
  149 * 23069 =    62 * 55440 + 1
  151 * 38551 =   105 * 55440 + 1
  157 * 11653 =    33 * 55440 + 1
  163 * 19387 =    57 * 55440 + 1
  167 * 13943 =    42 * 55440 + 1
  169 *  6889 =    21 * 55440 + 1
  173 * 25637 =    80 * 55440 + 1
  179 * 34379 =   111 * 55440 + 1
  181 * 37981 =   124 * 55440 + 1
  191 * 12191 =    42 * 55440 + 1
  193 * 18097 =    63 * 55440 + 1
  197 * 50093 =   178 * 55440 + 1
  199 * 23959 =    86 * 55440 + 1
  211 *  1051 =     4 * 55440 + 1
  221 * 41141 =   164 * 55440 + 1
  223 * 45247 =   182 * 55440 + 1
  227 * 11723 =    48 * 55440 + 1
  229 * 12589 =    52 * 55440 + 1
  233 * 11897 =    50 * 55440 + 1
  239 *  6959 =    30 * 55440 + 1
  241 *  5521 =    24 * 55440 + 1
  247 * 19303 =    86 * 55440 + 1
  251 * 17891 =    81 * 55440 + 1

1.4 The Mathematics of Imp Steps

If you find this too mathematical, there is some redcode and cdb macros in section 4.

0. Notations

We'll talk about an imp number N and its corresponding imp step S in a core of size C. This will give us an N-point ring or spiral with this instruction:
    MOV     0, S
N, S, and C must be such that, for some integer k,
        N*S = k*C + 1        (1)
Given C and N, the game is to find an S that satisfies equation (1). We're not really interested in the value of k. We'll call (N,S) an imp pair in C. When C is implicit from the context, we'll simply say that (N,S) is an imp pair.

We can see that equation (1) is unchanged when we exchange N and S: if (N,S) is an imp pair, then (S,N) is also an imp pair.

1. Existence

Let me state here the most important theorem of mathematics (as far as imp rings are concerned, anyway), Bezout's theorem:

For any integers x, y, and g, there exists integers u and v such that
        u*x + v*y = g        (2)
if and only if g is a multiple of the Greatest Common Divisor of x and y.

I won't explicitely prove Bezout's theorem here. One of the implications is easy, and the programs below are proof of the other. Trust me, Bezout's theorem is true.

Let us take x = N, y = C, and g = 1, and equation (2) is almost the same as equation (1):
        u*N + v*C = 1
If we can find u and v that satisfy this relation, then (u,N) is an imp pair. Conversely, if (N,S) is an imp pair, then S*N + (-k)*C = 1, so 1 must be a multiple of GCD(N,C). This means that 1 = GCD(N,C), so N and C have no common factors.

Our first result is: In a core of size C, there is an imp step for N if and only if N and C have no common factor.

Examples:
In a core of size 8192 all odd numbers are imp numbers.
In a core of size 8000 all numbers ending in 1, 3, 7, or 9 are imp numbers.
In any core size, (1,1) is an imp pair.
In any core size C, (C-1,C-1) is  an imp pair.
In any odd core size C, ((C-1)/2,C-2) is an imp pair.

2. Unicity

Assume that (N,S) and (N,T) are both imp pairs. We have:
(a)      N*S = k*C + 1
(b)      N*T = i*C + 1
Subtracting (b) from (a), we get:
(c)      N*(S-T) = (k-i)*C
But N and C have no common factors, so S-T must be a multiple of C. Thus, S = T + j*C: S and T are congruent modulo C. In a redcode program they are equal, since all redcode arithmetic is done modulo C.

Our second result is:

In a core of size C, if both (N,S) and (N,T) are imp pairs, then S and T must be congruent modulo C, and thus equal, as far as redcode programs are concerned.

3. Computation with recursion

Computing the u and v parameters of equation (1) can be done with Euclid's extended algorithm. This is a simple extension of Euclid's algorithm for computing the GCD. Given x and y, Euclid's extended algorithm will compute g = GCD(x,y) and values for u and v that make equation (1) hold.

The algorithm is extremely simple. You want to solve
       u*x + v*y = g

if x > y, solve u'*y + v'*x = g and take u = v', v = u'.
if x = 0, take g = y, u = 0, and v = 1.
else compute q and r such that y = q*x + r   and   0 <= r < x;
     solve  u'*r + v'*x = g;
     take u = v'-q*u' and v = u'.
This is the same as Euclid's algorithm except that you keep track of the quotients of the divisions and use them to compute u and v.

4. Computation without recursion

There is a version of Euclid's extended algorithm that uses a loop instead of the recursion. Instead of boring you with a description of how it works, I'll simply give the code:
;redcode
;name Euclid's extended
;author Planar
;assert MAXLENGTH >= 15 && CORESIZE >= 16

; To compute the imp step for a given imp number,
; enter the imp number in the following line:

n       equ     3

; The program terminates with gcd (n,CORESIZE) in the a-value at
; address 0.  If this is 1, there is a spiral of size n, and the
; b-value at address 1 is the corresponding step.

; This program works in any core size, and it computes imp steps
; for that core size.

; Use the following cdb macro to display all the (N,S) imp pairs
; with N <= 100 in the current core size.
; imps=@ca z=0~!!~@ca z=z+1~@ed 0~dat z~@g~@0~if a==1~!!~@1~ca z,b~!1~@s~!100
; (and launch pMARS with -r 100)

        org     start

yx      dat     0, n          ; y = CORESIZE = 0
ab      dat     1, 0

done    equ     ab
start   sub.b   yx, q         ; (CORESIZE-n)
        div.b   yx, q         ; ((CORESIZE-n)/n)
        add.ab  #1, q         ; q = (CORESIZE-n)/n+1 = CORESIZE/n
loop    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
        sub.ab  yx, yx        ; (y - x)
        mod.ab  yx, yx        ; x' = (y-x) % x = y % x
        jmz.b   done, yx      ; We're done if x = 0
        mov.ab  yx, q         ; (y)
        div.b   yx, q         ; q' = y' / x'
        jmp     loop

q       end
This program is quite fast for every imp number N and core size C: the number of loop iterations is bounded by 2*ceil(log N/log 2).

And this is a version entirely written in cdb macros:
euclid=@ca c=1,d=0~m eucloop
eucloop=!!~@ca t=d-y/x*c,d=c~@ca c=t,t=y%x~@ca y=x,x=t~if x!=0~!
imp-pairs=@ca s=$~@ca z=0~!!~@ca x=z=z+1,y=$+1~m euclid~if y==1~ca z,d~!s
This macro is much faster than Stefan's "imp-numbers", and it really finds all imp pairs, whereas Stefan's misses a few.

To use it, save it in a file named "planar.mac", launch pMARS with the core size you're interested in and type "m imp-pairs,planar.mac". pMARS will list all (N,S) imp pairs. When N = S, for some reason pMARS will only display one of them. (Bug or feature ?)

If you dislike negative numbers, just add CORESIZE to them. This is an easy exercise in cdb programming.

If you only want the reasonable imp numbers, change the "s" at the end of the last line into 100, and it will display only the imp numbers up to 100.

© 2002-2005 corewar.info. Logo © C. Schmidt
Main Articles

Paper

QScan

Scanner

Main Articles