Cfrtjryk

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 display a running counter on screen just to prove that the program is still alive.

; Copyright (c) 2018, Sep Roland.

; All rights reserved.



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