NASM - The Netwide Assembler
NASM Forum => Programming with NASM => Topic started by: djasy3 on March 03, 2014, 09:38:50 PM
-
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 (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
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:
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
-
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!
%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
-
I used to be able to do math, now my eyes just glaze over...
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.
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
-
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.
-
Or "test". This was as far as I got with my implementation of it
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
-
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.)
; 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