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.
|
