The Wikipedia article about the Collatz Conjecture has these quotes:
If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence that does not contain 1. Such a sequence might enter a repeating cycle that excludes 1, or increase without bound. No such sequence has been found.
... sometimes a conjecture's only counterexamples are found when using very large numbers.
The bit about using very large numbers motivated me to write the following Collatz calculator that uses Googol-sized numbers.
The program is very extensible. Just change the equates on top.
The faster the calculation, the more numbers can be verified for compliance, silently hoping for non-compliance of course...
I'm most interested in speeding up the CollatzEngine.
I wrote this code on an Intel® Pentium® dual-core processor T2080 and that's Core™ microarchitecture. The instruction set goes up to SSE3 (not including SSSE3). Ideally improvement suggestions don't exceed these specs.
I display a running counter on screen just to prove that the program is still alive.
; Never ending program to verify successive numbers
; whether they comply or not with the Collatz conjecture.
; The starting number is 10 ^ PowerOfTen.
PowerOfTen = 100 ;1 Googol == 10^100
MaxDWords = 12 ;1 Googol occupies 11 dwords
MaxSteps = 100000
Width = (1+MaxDWords)*4
STD_OUTPUT_HANDLE = 0FFFFFFF5h
format PE console
Start: mov esi, Title
call PrintString
mov eax, PowerOfTen
call PrintNumber
mov esi, Title_
call PrintString
mov ebx, Slots ;Pointing at SlotA
call BuildGoogol ; -> (EAX ECX..EBP)
Next: mov esi, [Screen] ;Update the counter on screen
call PrintString
call CollatzEngine ; -> ECX (EAX EDX..EDI)
call GoToNextNumber ; -> (EAX ESI)
jmp Next
; --------------------------------------
Fatal3: call Fatal ;From inside CollatzEngine
db "needs too many steps - Possible repetition!", 0
Fatal2: call Fatal ;From inside CollatzEngine
db "grows too big - Possible divergence!", 0
Fatal1: call Fatal ;From outside CollatzEngine
db "needs more space.", 0
Fatal: mov esi, Error
call PrintString
pop esi
call PrintString
mov al, 0
jmp TerminateProgram
; --------------------------------------
; IN (ebx) OUT () MOD (eax,ecx..ebp)
BuildGoogol:
mov ecx, 1
mov [ebx], ecx ;SignificantDWords = 1
mov [ebx+4], ecx ;SlotA = 1
mov ebp, PowerOfTen
jmp .c
.a: lea edi, [ebx+4] ;Current value * 10
xor esi, esi
mov ecx, [ebx] ;SignificantDWords
.b: mov eax, 10
mul dword [edi]
add eax, esi
adc edx, 0
stosd
mov esi, edx
dec ecx
jnz .b
test esi, esi
jz .c
cmp dword [ebx], MaxDWords ;Upscale
jnb Fatal1 ;"needs more space"
mov [edi], esi
inc dword [ebx]
.c: dec ebp
jns .a
ret ;SlotA = 10 ^ #PowerOfTen
; --------------------------------------
; IN (ebx) OUT (ecx) MOD (eax,edx..edi)
CollatzEngine:
mov ecx, [ebx] ;SignificantDWords [1,MaxDWords]
inc ecx
mov esi, ebx
add ebx, Width ;(*) Within Collatz EBX points at SlotB
mov edi, ebx
rep movs dword [edi], [esi] ;Copy SlotA into SlotB
;;xor ecx, ecx ;StepCount
mov esi, [ebx] ;Cache SignificantDWords [1,MaxDWords]
jmp .Start
.Cont: mov eax, [ebx+4] ;Lowest dword of current number
bt eax, 0
adc ecx, 1 ;StepCount + [1,2]
cmp ecx, MaxSteps
ja Fatal3 ;"needs too many steps"
bt eax, 0
jnc @f
call .Odd ; -> ESI CF=0 (EAX EDX EDI)
@@: call .Even ; -> ESI (EAX EDX EDI)
.Start: cmp esi, 1
jne .Cont
cmp [ebx+4], esi
jne .Cont
.Done: mov [ebx], esi ;Un-cache SignificantDWords
sub ebx, Width ;(*) Restore EBX to point at SlotA
ret ;ECX is steps taken to reach 1
; - - - - - - - - - - - - - - - - - - -
; IN (ebx,esi,CF=1) OUT (esi,CF=0) MOD (eax,edx,edi)
.Odd: lea edi, [ebx+Width+4] ;CF=1 This produces the +1
mov edx, esi
@@: mov eax, [edi-Width] ;n --> 2n+1
rcl eax, 1
stosd ;DST is intermediate storage (SlotC)
dec edx
jnz @b
jnc @f
cmp esi, MaxDWords ;Upscale
jnb Fatal2 ;"grows too big"
mov [edi-Width], edx ;EDX=0
inc edx ; 0 -> 1
mov [edi], edx
add esi, edx ; -> CF=0
@@: lea edi, [ebx+4] ;CF=0
mov edx, esi
@@: mov eax, [edi] ;2n+1 --> 3n+1
adc eax, [edi+Width]
stosd ;DST is intermediate storage (SlotB)
dec edx
jnz @b
jnc @f
cmp esi, MaxDWords ;Upscale
jnb Fatal2 ;"grows too big"
inc edx ; 0 -> 1
mov [edi], edx
add esi, edx ; -> CF=0
@@: ret
; - - - - - - - - - - - - - - - - - - -
; IN (ebx,esi,CF=0) OUT (esi) MOD (eax,edx,edi)
.Even: lea edi, [ebx+esi*4] ;CF=0
mov edx, esi
std
@@: mov eax, [edi] ;n --> n/2
rcr eax, 1
stosd ;DST is intermediate storage (SlotB)
dec edx
jnz @b
cld
cmp [ebx+esi*4], edx ;EDX=0
sete dl ; -> EDX=[0,1]
sub esi, edx ;This is Downscale if EDX=1
ret
; --------------------------------------
; IN (ebx) OUT () MOD (eax,esi)
GoToNextNumber:
mov esi, ebx ;Increment number in SlotA
mov eax, [esi] ;SignificantDWords
.a: add esi, 4
add dword [esi], 1
jnc .b
dec eax
jnz .a
cmp dword [ebx], MaxDWords ;Upscale
jnb Fatal1 ;"needs more space"
inc eax ; 0 -> 1
add [ebx], eax
mov [esi+4], eax
.b: lea esi, [Mirror+38] ;Increment counter in mirror
jmp .d
.c: sub al, 10
mov [esi], al
dec esi
cmp esi, [Screen]
jnb .d
mov [Screen], esi
.d: mov al, [esi]
add al, 1
cmp al, "9"
ja .c
mov [esi], al
ret
; --------------------------------------
; IN (al)
TerminateProgram:
movzx eax, al
push eax
call [ExitProcess]
; IN (esi)
PrintString:
push ebx
push esi ;(1)
push STD_OUTPUT_HANDLE
call [GetStdHandle]
mov ebx, eax
pop esi ;(1)
mov edi, esi
or ecx, -1
xor al, al
repne scasb
neg ecx
sub ecx, 2
push 0
push Bytes
push ecx
push esi
push ebx
call [WriteFile]
pop ebx
ret
; IN (dl)
PrintCharacter:
mov [OneChar], dl
push STD_OUTPUT_HANDLE
call [GetStdHandle]
push 0
push Bytes
push 1
push OneChar
push eax
call [WriteFile]
ret
; IN (eax)
PrintNumber:
push ebx
mov ebx, 10 ;CONST 10
push ebx ;Sentinel
.a: xor edx,edx
div ebx
push edx
test eax, eax
jnz .a
pop edx
.b: add dl, "0"
call PrintCharacter
pop edx
cmp edx, 10
jb .b
pop ebx
ret
; ---------------------------------------------------------------------------
Title db 'Collatz Conjecture Disprover Unit - Googol Edition', 13, 10
db 10, 'Now verifying the number: 10 ^ ', 0
Title_ db ' + ...', 13, 10, 0
Error db 10, 10, 'Error: This number ', 0
Mirror db 39 dup '0', 13, 0
OneChar db 0
ALIGN 4
Screen dd Mirror+38
Bytes rd 1
Slots rd 3*(1+MaxDWords)
; -----------------------------------------------------------------------------
stack 4096
; ---------------------------------------------------------------------------
section '.idata' import data readable writeable
dd 0, 0, 0, rva kernel_name, rva kernel_table
dd 0, 0, 0, 0, 0
kernel_table:
ExitProcess dd rva _ExitProcess
WriteFile dd rva _WriteFile
GetStdHandle dd rva _GetStdHandle
dd 0
kernel_name db 'KERNEL32.DLL', 0
_ExitProcess dw 0
db 'ExitProcess', 0
_WriteFile dw 0
db 'WriteFile', 0
_GetStdHandle dw 0
db 'GetStdHandle', 0
; ---------------------------------------------------------------------------
section '.reloc' fixups data readable discardable
most interested in speeding up [a piece of machine code]Specify a micro-architecture/implementation to target. Invest months of time in manufacturers instrumentation toolset. \$\endgroup\$