Collatz conjecture

[djasy3]

hi, i'm trying to write a math exercice called Collatz conjecture you can find the explannation here: http://en.wikipedia.org/wiki/Collatz_conjecture, i have it right in c++, but when i try to write it in nasm it gives a wrong result. don't really find the error here is the code in c++:
i attached the file too

Code: [Select]

int main (int argc, char *argv[])
{
int l = 1, lTemp = 1, GdNbre = 0;

cout << "Conjoncture d'Ulam" << endl;

for(int i(2); i <=100; i++)
{
int N = i;
while(N != 1)
{
if(N%2 == 0)
N /= 2;
else
N = (3*N)+1;
l++;
}
//
if( lTemp < l )
{
lTemp = l;
GdNbre = i;
}

l = 1;
}

cout << "Longueur: " << lTemp << endl;
cout << "Et le nombre qui le génère est: " << GdNbre << endl;
return 0;
}
the result has to be: 119 as the length and 97 is the number that generats it. but in nasm it gives me 113 as the length and 54 as the number.
here is my assembler code:

Code: [Select]

   
    mov  ax, word [nbre]
    mov  cx, word [l]
    mov  bx, word 2

for: ;ici on fait pour nombre allant de 2 à 100, on retient le nombre ayant la plus longue conjoncture d'ulam
    cmp word[i], 100
    jg endfor
    mov ax, word[i] ;on place dans ax notre i= 2
   
;debut de la fonction d'ulam 
while:
    cmp ax, 1 ;on fait la comparaison entre le nombre et 1
    je  endwhile ;si le nombre est égale à 1 on quitte notre boucle
    xor dx, dx
    div bx ;[ax:dx]/dx et le reste est mis dans  dx
if: cmp dx, 0 ;on compare si le reste de la division[dx] est == zéro pour savoir si le nombre est paire
    jne else
    mov [nbre], ax ;on passe a la variable [nbre], sa nouvelle valeur. ceci nous permet de garder la valeur de ax, parce qu'on veut la conserver après
;chaque comparaison(à savoir si c'est un nombre paire ou pas)
    jmp endif
   
else:
    mov ax, word[nbre] ;on repasse à ax, l'ancienne valeur au cas ou après vérification, il ne serait plus paire
    mov dx, word 3 ;on place 3 dans le bx pour nous permettre de faire une multiplication non signé
    mul dx ;3*ax = 3*nbre
    inc ax ;(3*nbre)+1
    jmp endif
   
endif:
    inc cx ;on incremente cx qui est la longueur d'ulam
    jmp while
     
endwhile:
    ;mov [l], cx
    ;jmp afficher
   
grandeValeur:
    cmp word[lTemp], cx ;on compare cx donc la longueur d'ulam en cours à la valeur stockée dans la longueur temporaire
    jl echanger ;si elle est supérieure, on la place dans la longueur temporaire
;si elle est inférieure , donc on garde la même longueur
    jmp endGrandeValeur
   
echanger:
    mov [lTemp], cx ;la longueur d'ulam courante devient la plus grande longueur
    xor dx, dx
    mov dx, word[i]
    mov [longNbre], dx ;ainsi le nombre qui le génère
    ;jmp endGrandeValeur

endGrandeValeur:
    mov cx, word[l] ;on remet cx à 1
    inc word[i] ;on incrémente si qui va contenir le prochain nombre
    jmp for ;on retourne à la boucle for

endfor:
    xor bx, bx
    mov bx, word[lTemp]
    mov word[l], bx ;on a la longueur finale
    jmp afficher

erreur:
    push IErreur
    call printf
    add esp, 4
    jmp exit
   
afficher:
    popa
    ;on affiche les variables
    movsx eax, word[l] ;lextension du signe est placé dans le MSB du eax
    push  eax    ;push la valeur à afficher
    push  IShow         ;push la deuxième valeur à afficher
    call  printf        ;l'appel à printf convertira le string et l'affichera
    add   esp, 8
    ; deuxième message
    movsx edx, word[longNbre] ;
    push  edx;dword[longNbre]
    push  IShow2
    call  printf
    add   esp, 8
;;;Fin de toute notre programme



[Rob Neff]

I like little challenges like these on occasion.  I took this particular occasion to translate your C example into NASM-X.  I've obtained the expected results: length=119 and 97 is the number that generates it.

I've provided the outline and assembler logic to implement the algorithm in 32-bit mode.  It should be easy for you at this point to convert it into pure 16-bit nasm.  I've placed the C code in comments next to the assembly code which should make it easy for you to understand.  I would expect a C compiler to generate something "almost" similar if optimizations not enabled.  Take it and run with it!

Code: [Select]

%include 'nasmx.inc'

IMPORT printf

[section .text]

ENTRY my_main

PROC my_main, dword argc, ptrdiff_t cmdline ; int main(int argc, char *argv[])
                                            ; {
LOCALS                                      ; int l = 1, lTemp = 1, GdNbre = 0;
    LOCAL l, dword, 1
    LOCAL lTemp, dword, 1
    LOCAL GdNbre, dword, 1
ENDLOCALS
    mov  eax, 1
    mov  dword [var(.l)], eax
    mov  dword [var(.lTemp)], eax
    xor  eax, eax
    mov  dword [var(.GdNbre)], eax

    INVOKE printf, announce_msg          ; cout << "Conjoncture d'Ulam" << endl;

    mov  ecx, 2
    WHILE ecx,<=,100                     ; for (int i(2); i <=100; i++)
                                         ; {
push ecx                         ;

        mov  eax, ecx                    ;     int N = i;
        WHILE eax,!=,1                   ;     while (N != 1)
                                         ;     {
            mov  edx, eax
    and  eax, 1
    jnz  .isodd                  ;         if (N%2 == 0)
                 mov eax, edx
shr eax, 1              ;             N /= 2;
jmp .increment
          .isodd:                        ;          else
                 mov eax, edx            ;             N = (3*N)+1;
mov ecx, 3
         mul ecx
inc eax
          .increment:
   mov edx, dword [var(.l)]      ;          l++;
   inc edx
   mov dword [var(.l)], edx

ENDWHILE                         ;      }

pop  ecx

mov  edx,dword [var(.lTemp)]
mov  eax,dword [var(.l)]
IF edx,<,eax                      ;     if ( lTemp < l )
                                          ;     {
    mov dword [var(.lTemp)], eax  ;         lTemp = l;
    mov dword [var(.GdNbre)], ecx ;         GdNbre = i;
ENDIF                             ;     }

mov  dword [var(.l)], 1           ;     l = 1;
        inc ecx
       
    ENDWHILE                              ; }

    ; cout << "Longueur: " << lTemp << endl;
    INVOKE printf, longuer_msg, dword [var(.lTemp)]
    ; cout << "Et le nombre qui le génère est: " << GdNbre << endl;
    INVOKE printf, genere_msg, dword [var(.GdNbre)]
    ; return 0;
ENDPROC                                  ; }

[section .data]

announce_msg: db 'Conjoncture d Ulam',0xa,0
longuer_msg: db 'Longueur: %d',0xa,0
genere_msg: db 'Et le nombre qui le génère est: %d',0xa,0


[Frank Kotler]

I used to be able to do math, now my eyes just glaze over...

Code: [Select]

   
    mov  ax, word [nbre]
; okay, we start off with 2

    mov  cx, word [l]
    mov  bx, word 2

for: ;ici on fait pour nombre allant de 2 à 100, on retient le nombre ayant la plus longue conjoncture d'ulam
    cmp word[i], 100
    jg endfor
; signed?
    mov ax, word[i] ;on place dans ax notre i= 2
; okay, this is also 2 (first time through - it increments...)   
;debut de la fonction d'ulam 
while:
    cmp ax, 1 ;on fait la comparaison entre le nombre et 1
    je  endwhile ;si le nombre est égale à 1 on quitte notre boucle
    xor dx, dx
    div bx ;[ax:dx]/dx et le reste est mis dans  dx
if: cmp dx, 0 ;on compare si le reste de la division[dx] est == zéro pour savoir si le nombre est paire
    jne else
    mov [nbre], ax ;on passe a la variable [nbre], sa nouvelle valeur. ceci nous permet de garder la valeur de ax, parce qu'on veut la conserver après
;chaque comparaison(à savoir si c'est un nombre paire ou pas)
; so now [nbre] is 1 (first time through)
    jmp endif
   
else:
    mov ax, word[nbre] ;on repasse à ax, l'ancienne valeur au cas ou après vérification, il ne serait plus paire
; what are we putting in ax here?

    mov dx, word 3 ;on place 3 dans le bx pour nous permettre de faire une multiplication non signé
    mul dx ;3*ax = 3*nbre
    inc ax ;(3*nbre)+1

; at this point, if N was even, you divide by two and put it back into [nbre]
; if N was odd, you do 3N+1, but don't put it back, Should you?
; or should you have loaded ax from [nbre] (or [i]) at the "else"?

    jmp endif
; don't really need to jump here - doesn't hurt
   
endif:
    inc cx ;on incremente cx qui est la longueur d'ulam
    jmp while
     
endwhile:
    ;mov [l], cx
    ;jmp afficher
   
grandeValeur:
    cmp word[lTemp], cx ;on compare cx donc la longueur d'ulam en cours à la valeur stockée dans la longueur temporaire
    jl echanger ;si elle est supérieure, on la place dans la longueur temporaire
;si elle est inférieure , donc on garde la même longueur
;signed?

    jmp endGrandeValeur
   
echanger:
    mov [lTemp], cx ;la longueur d'ulam courante devient la plus grande longueur
    xor dx, dx
    mov dx, word[i]
    mov [longNbre], dx ;ainsi le nombre qui le génère
    ;jmp endGrandeValeur

endGrandeValeur:
    mov cx, word[l] ;on remet cx à 1
    inc word[i] ;on incrémente si qui va contenir le prochain nombre
    jmp for ;on retourne à la boucle for

endfor:
    xor bx, bx
    mov bx, word[lTemp]
    mov word[l], bx ;on a la longueur finale
    jmp afficher

erreur:
    push IErreur
    call printf
    add esp, 4
    jmp exit
   
afficher:
    popa
    ;on affiche les variables
    movsx eax, word[l] ;lextension du signe est placé dans le MSB du eax
    push  eax    ;push la valeur à afficher
    push  IShow         ;push la deuxième valeur à afficher
    call  printf        ;l'appel à printf convertira le string et l'affichera
    add   esp, 8
    ; deuxième message
    movsx edx, word[longNbre] ;
    push  edx;dword[longNbre]
    push  IShow2
    call  printf
    add   esp, 8
;;;Fin de toute notre programme

I guess I understand the "specification" here... Do you really need to use all those 16-bit registers and variables? Your C++ version doesn't. That was my first thought - that maybe the 16-bit ax was overflowing... but I don't think that's it. I'm suspicious of [ i ] vs [nbre].

Here's a thought... We can determine if a number is odd or even without dividing by 2 by testing bit 0.

Code: [Select]

test eax, 1
jnz itsodd
shr eax, 1 ; divide by two
jmp carryon
itsodd:
lea eax, [eax + eax * 2 + 1]
carryon:

I'm just thinking out loud, that probably isn't the way you want to do it - won't work with 16-bit registers anyway...

I may have to replace "printf" with something I can actually link to try i out...

Well... I see Rob has posted a better idea... more to study...

Best,
Frank

[HD1920.1]

OK, maybe a bit off-topic, but instead of using div to check if the number is even, you could move the value into another register and use shr <register>, 1. Then check the carry flag.

[Frank Kotler]

Or "test". This was as far as I got with my implementation of it

Code: [Select]

global _start

section .text
_start:
    mov esi, 2
    xor edi, edi
    xor ecx, ecx

top:
    mov eax, esi
collatz:
    inc ecx
    cmp eax, 1
    je endcollatz
    test eax, 1
    jnz odd
    shr eax, 1
    jmp collatz
odd:
    lea eax, [1 + eax + eax * 2]
    jmp collatz
endcollatz:
    cmp ecx, edi
    jbe shorter
    mov edi, ecx
    mov edx, esi
shorter:
    inc esi
    cmp esi, 100
    ja done
    xor ecx, ecx
    jmp top
done:

    mov ebx, edi ; return longest path
    ; mov ebx, edx ; return number giving longest path
    mov eax, 1
    int 80h

No provision for displaying the answer, but you can see it with "echo $?"...

Proving it's true would be more interesting. Proving it's not true would be more interesting still!

Best,
Frank

[z80a]

I noticed 'C' program incremented step counter BEFORE doing step. Based on Wikipedia (look at number 27 in their examples), 97 should be 118 steps, not 119.
Anyways, attached is a Linux x64 version. Does binary to ASCII conversion at end. (What to do when late night TV doesn't cut it.)

Code: [Select]

; Written by: z80a for x64 Linux
; Date      : Started 1 am 4-23-14 out of boredom.
; Comments  : Collatz conjecture 100 -> 1. Displays value & number of steps
;             to achieve at that value.
; Compiling : nasm -f elf64 conjecture.asm
;             ld -melf_x86_64 -o conjecture conjecture.o
; Optional  : debug: edb --run <path>/filename
;==============================================================================
; rdi, rsi, rdx, rcx, r8, r9                    ;64 bit parameter passing
; %include "/usr/include/asm-generic/fcntl.h"   ;Reference
; %include "/usr/include/asm/unistd_64.h        ;Reference
;
                BITS    64
                SECTION .data                   ;Must be writable, one dirty
                                                ; step above self modifing
                                                ; code. ;-)
;
Txt1            db      'Number : '
nValue          equ     $+2
                db      '000 required '
nSteps          equ     $+3
                db      '0000 steps.',0Ah
Txt1Len         equ     $ - Txt1
;
                SECTION .bss
;
                SECTION .text
                global  _start
;
; RAX = f(x), RBX = Value that attained peak value, RCX = (x) Note: we start
; at 100 and decrement to zero; why not., RSI = Peak steps, RDI = Temp steps
;
_start:         mov     rcx,64h                 ;100 decimal count
                xor     rsi,rsi                 ;Peak iteration
lp_for:         mov     rax,rcx                 ;
                xor     rdi,rdi                 ;Clear iteration counter
;
lp_while:       inc     rdi                     ;Increment iteration counter
                test    al,0001b                ;MOD 2 test
                jnz     is_odd                  ;Odd, do f(x)=3*N+1
                shr     rax,1h                  ; else f(x)=N/2
                jmp     chk_one                 ;Check if f(x)=1
;
is_odd:         lea     rax,[rax*3+1]           ;Is odd so f(x)=3*N+1
;
chk_one:        cmp     rax,1h                  ;Result 1 yet?
                jnz     lp_while                ; if not do another iteration
                cmp     rsi,rdi                 ;Check against previous peak
                jg      no_set                  ; if less skip
                mov     rsi,rdi                 ;  else new peak
                mov     rbx,rcx                 ;Value that set that peak
;
no_set:         loop    lp_for                  ; if not dec RCX and repeat
;
                mov     rdi,nValue              ;Point to ASCII string to Mod
                mov     rax,rbx                 ;Get Value max step required
                call    a_conv                  ;Convert to ASCII & insert
                mov     rdi,nSteps              ;Point to ASCII string to Mod
                mov     rax,rsi                 ;Get # of steps at that value
                call    a_conv                  ;Convert to ASCII & insert
;
_done:          mov     rax,1h                  ;Display our text string
                mov     rdi,rax
                mov     rsi,Txt1
                mov     rdx,Txt1Len
                syscall                         ; (Write)
;
                mov     rax,3Ch                 ; (Exit)
                xor     rdi,rdi                 ;Return code 0
                syscall                         ;Invoke system call
;------------------------------------------------------------------------------
; Binary -> ASCII conversion.
; On Entry: RAX = binary value, RDI pointer to place ASCII value              -
; On Exit : RAX, RCX, RDX, RDI modified                                       -
;------------------------------------------------------------------------------
a_conv:         mov     rcx,0Ah
a_conv_lp:      xor     rdx,rdx
                div     rcx
                or      dl,30h
                mov     [rdi],dl
                dec     rdi
                cmp     rax,0h
                jnz     a_conv_lp
                ret