Saturday, December 15, 2007

Collatz Conjecture

For me the most fasinating thing about the Collatz Conjecture is how it so blantantly points to a deficiency in mathematics. It seems incredibly obvious that it is true. The problem lies in a way to say that no loops are created excluding one - a limited understanding of process dynamics.

Recently, I've changed the problem to eliminate the split condition - there is no reason to divide even numbers by two. Without the split we have a simplified algorithm, but it must work with larger numbers. This doesn't seem like an intuitive step.


1. y <= 1+Shr[Xor[x,x-1],1]

2. if x=y then step 5

3. x <= 3x + y

4. goto step 1

5. number is a power of two



The first step calculates the value of least set bit. Instead of dividing by two, one is scaled up to match the bit which would make (x) odd if it were down scaled. Only when a single bit is set does the algorithm end (step 2). (y) can be tracked progressively instead of looking at the complete representation of (x) as step 3 always clears the least set bit (or more). Of course, I've coded this in x86:

; check Collatz Conjecture on multi-percision number
;
; carry flag set on array overflow
; carry flag clear on pass
; (otherwise it loops forever: not likely, but hasn't been proven)
;
; NOTE: array should be twice the size of number to test - too large
; is not a problem as only active bits are operated on.
CollatzArrayQ:
label .arr at esp+4+32 ; BigInt
label .len at esp+8+32 ; length (dwords)

pushad
mov ebx,[.arr]
mov eax,[.len]
mov edx,1
mov esi,ebx
lea ebp,[ebx+eax*4]
; address past number in EDI (active end marker)
; (need at least one zero dword on end!)
.z: dec eax
test dword [ebx+eax*4],-1
je .z
lea edi,[ebx+eax*4+4]
cmp edi,ebp
je .over

; advance to lowest set bit
.0: test [esi],edx
jne .1
.0a: rol edx,1
jnc .0 ; HINT: taken
add esi,4
cmp esi,ebp ; end
cmovnc esi,ebx ; reset
jmp .0
; ESI[ECX] is first set bit, multiply by three and add ESI[ECX]
; all (virtual) lower bits are zero.
.1:
; test if buffer is == ESI[ECX] then done!
cmp [esi],edx
jne .kx ; HINT: taken
; if EDI==ESI+4 or (ESI+4==EBP && EDI==EBX)
; (faster than testing all of buffer)
mov ecx,edi
lea eax,[esi+4]
cmp edi,ebx
cmove ecx,ebp
cmp eax,ecx
je .x
.kx:
push edx
push esi
.2:
mov eax,3
mov ecx,edx
mul dword [esi]
add eax,ecx
adc edx,0
mov [esi],eax

add esi,4
cmp esi,ebp ; end
cmovnc esi,ebx ; reset

cmp esi,edi
jne .2

test edx,edx
je .5

cmp edi,[esp]
je .over
mov [edi],edx
add edi,4
cmp edi,ebp ; end
cmovnc edi,ebx ; reset

.5: pop esi
pop edx
jmp .0a ; we just cleared that bit

.x: popad
clc
retn 8

.over: popad
stc
retn 8
Try a really big number - like 2^131072 + 3

TestBuffer rb 32*1024 ; zero bytes

mov dword [TestBuffer],3
mov dword [TestBuffer+16*1024],1

push 32*1024/4 ; L1 cache size (c:
push TestBuffer1
call CollatzArrayQ
; 3829ms on my machine
Why is this important? The algorithm is no longer concerned with value of (x) except for the exit condition - the same operation takes place each loop. It is sufficient to show that (y) -> (x) for all (x), and the conjecture is true. The multiplication by three is irrelavant because the addition propells the least set bit at a rate greater than the constant multiple!

(c:

Update:

Status of the 3x+1 class record progress as of: Dec 13, 2007. Intervals are
indicated in blocks of 20,000,000,000,000 (20 E+12 or 20 trillion numbers).
Calculation of a single block takes approximately 20 days of (idle) time on a
Pentium 1000 MHz.
Basically, a trillion per day, per Ghz.

Naturally, I'm currious how my routine compares:
Currently, they are working on 7 * 2^53 block of numbers. I ran a test of my algorithm for 2^24 numbers (in that block range) which took 38781ms. Which means it is roughly 25 times slower. Their algorithm is tuned for this size and uses large data structures (to avoid processing numbers). I might be able to double the speed of my algorithm, but confirming ranges of numbers is not what it's designed for.

2 comments:

bitRAKE said...

Every number (A) can be represented as: A = k * 2^m + 2^n, m > n >= 0 and k odd or zero.

A <- 3A + 2^n, as per the algorithm

We have to look at three cases:

1) m-n = 1
2) m-n = 2
3) m-n > 2

...and show a reduction in (k).

3) case three progresses to:

3^(m-n) * k * 2^m + 2^m

where (k) begins to get reduced - the other two cases are more direct.

Anonymous said...
This comment has been removed by a blog administrator.