5
\$\begingroup\$

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
\$\endgroup\$
6
  • 1
    \$\begingroup\$ 0th suggestion: add a head comment what the code is about and where "the Collatz branch and steps" are coded. (Yes, for me, who can spot them as well as for yourself who knows what is what. In 2018…) 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\$
    – greybeard
    Dec 30, 2018 at 21:05
  • \$\begingroup\$ (Eye-balling this table in Computational verification of the 3x+1 conjecture, you'd need more than twice the length of the starting value to hold the "maximum excursion".) \$\endgroup\$
    – greybeard
    Dec 30, 2018 at 21:50
  • 3
    \$\begingroup\$ (See also: C++ code for testing the Collatz conjecture faster than hand-written assembly.) \$\endgroup\$
    – greybeard
    Dec 30, 2018 at 22:02
  • 1
    \$\begingroup\$ Regarding your license comment, note that all user contributions on this site are licensed under the cc by-sa 3.0. \$\endgroup\$
    – Graham
    Dec 30, 2018 at 23:01
  • 1
    \$\begingroup\$ @Graham That does not invalidate that Sep Roland holds the copyright on the material. He still does; CC by-SA just means that others are allowed to use and remix it, as long as they give him proper attribution. No one else can claim it as their own. The real reason you don't need to include a copyright header is that it is always implied. At least in all countries that are parties to the Berne Convention. An explicit copyright notice like this is only useful to prevent people from claiming ignorance in court, which is never a good defense. \$\endgroup\$ Feb 16, 2019 at 7:23

1 Answer 1

1
\$\begingroup\$

I don't speak x86 good :). That means, no style tips. I couldn't figure out how you're terminating in the known cycle at all...

But, I know some things about how to improve your algorithm. If you write this in C, I'd be happy to give better feedback.

A couple speed hints:

  • You're only working with Googol sized words? That fits in 6 64-bit registers. Forget memory until you prove you need it!
  • You can detect cycles using only two numbers worth of storage (look up cycle-finding algorithms). This is probably something you would want to run only AFTER you suspect a cycle. Then again, you may not ever hit this case, but just so you know.
  • You can do more than one step at a time. Definitely do this for evens at least--get rid of all the zeros on the right, not just one. To do this for odds is fairly complicated, but would make it faster.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.