Cómo saber si un número es primo en ensamblador x86

Mayo 2017

Este pequeño código en lenguaje ensamblador está escrito para las arquitecturas x86 (procesadores AMD e Intel 32 bits) y utiliza la sintaxis de Nasm, un ensamblador libre, gratuito y que puede ser utilizado en diferentes plataformas como Windows y Linux.

Las funciones externas utilizadas son tomadas de la biblioteca C estándar. De este modo, no tendrás problemas al utilizar este código en cualquier equipo, ya que no depende del sistema operativo. Únicamente depende de la arquitectura x86.

Nota: Para saber cómo utilizar Nasm a fin de testear este código, haz clic aquí.


Funciones y nociones utilizadas para escribir un código que determine si un número es primo

Para escribir este código se tiene en cuenta de las funciones con parámetro de entrada y valor de salida, las instrucciones de salto (jmp, jz/je, etc.), la aritmética que tiene en cuenta el tipo de variable (con signo, sin signo), la división.

Enunciado

El objetivo es escribir una función en ensamblador capaz de determinar si un entero sin signo es un número primo o no. Habrá un solo parámetro de entrada de tipo entero sin signo que representará el número a testear. El valor de retorno deber ser 1 si el número es primo y 0 si no lo es.

El código en C sería:
int es_primo(unsigned int n); //El modelo de esta función
//Ejemplo de uso:
unsigned int nb = 3;
if (es_primo(nb) == 1){
printf("El número %d es primo!, nb);
}


Deberás insertar este código aquí:
extern printf, scanf

seccion .data
ingresar db 'Ingrese un número!', 0xa, 0x0
sí db 'C es un número primo', 0xa, 0x0
no db 'No es un número primo', 0xa, 0x0
format_d db '%d', 0x0

seccion .text
global main

es_primo:
;Inserte el código aquí!


main:
push ebp
mov ebp, esp

;Dejamos espacio para un entero en la pila
;El que ingresaremos con scanf
sub esp, 4

;Frase de bienvenida
push ingresar
call printf
add esp, 4

;Solicitamos al usuario ingresar un número
push esp ;Dirección del entero
push format_d ; %d
call scanf
add esp, 8

;Llamamos a la función con el entero ingresado
push dword [esp]
call es_primo
;Probamos el retorno (eax == 0 ?)
test eax, eax
;Si es igual a cero => no es primo
jz noPrimo
;Si no
push sí
call printf
;Vamos al final de la función para no
;ingresar en la sección noPrimo
jmp quit

noPrimo:
push no
call printf

quit:
leave
ret

Para recordar

Qué es un número primo

Un número primo es un número que puede ser dividido únicamente por él mismo y por 1. Si es dividido por otro número, el residuo de la división no será igual a 0.

Tipos de saltos condicionales

Los saltos condicionales no son los mismos para números con signo que para números sin signo. Lo mismo para los operadores de multiplicación y división.

Dónde se coloca el valor de retorno de una función

El valor de retorno de una función se coloca en el registro eax.

Código para saber si un número es primo en lenguaje ensamblador x86

A continuación, el código:
es_primo:
;Prólogo de la función
push ebp
mov ebp, esp

;Cargamos el número n en ecx
;luego ecx será decrementado para testear todos los números
;que podrían dividir n yendo desde n hasta 2
mov ecx, [ebp + 8]
;Partimos del principio que es primo (ebx = 1)
mov ebx, 1
divisiones:
;Aquí se presentan dos casos
;O hemos entrado en la función y ecx es nuestro número
;si es menor o igual a 2, es primo
;O hemos comprobado la división por 2 y por lo tanto es inútil continuar
;ya que no es primo
cmp ecx, 2
;ecx <= 2, el número es primo
jbe finDivisiones
;Decrementamos el divisor
dec ecx
;Ponemos en eax el número a dividir (el argumento n)
mov eax, [ebp + 8]
;edx debe ser igual a cero
xor edx, edx
;La división (eax/ecx)
div ecx
;¿El residuo de la división es igual a 0?
test edx, edx
;Si no, es que el divisor no ha podido dividir
;el número n. Seguimos suponiendo que es primo y lo dividiremos
;por ecx - 1
jnz divisiones
;Si el residuo es cero significa que el número no es primo
mov ebx, 0

finDivisiones:
;Cargamos el retorno de la función con ebx
;que contiene la respuesta
;(1: número primo 0: no primo)
mov eax, ebx
leave
ret

Explicación

El algoritmo utilizado en esta solución es bastante simple, así no lo parezca, una vez traducido en ensamblador (al igual que con casi todos los algoritmos en ensamblador).

Esto es lo que hemos hecho. Partimos del principio que nuestro número n es primo. Dividimos sucesivamente n entre todos los números menores a n hasta el número 2 incluido. Si es divisible por alguno de estos números (es decir el residuo es igual a cero), entonces paramos el test y concluimos que el número no es primo. En cambio, si el número es desde un inicio menor o igual a 2, no hacemos ningún test y concluimos que es primo.

Esquemáticamente está es nuestra idea:
Funcion es_primo (n: entero sin signo) : entero
divisor = n
primo = 1
Mientras n <= 2
Hacer
divisor = divisor - 1
resto = n mod divisor
Si resto == 0
Entonces
primo = 0
salir del bucle
FinSi
FinMientras
Fin
devolver primo


Para ello utilizamos la instrucción div que divide eax entre un registro dado como parámetro, en este caso es ecx que es nuestro divisor y que es decrementado en cada test. Es una división para números sin signo (si no, utilizar idiv). El cociente se coloca en eax (el número n, recargado en cada pasada en la bucle) y el residuo es colocado en edx. Únicamente tenemos que testear el residuo. Este bucle de divisiones está situado bajo la etiqueta “divisiones”.
Este es un algoritmo que podría ser optimizado, pero no es el objetivo aquí…después de todo no son los números primos que nos interesan, sino el ensamblador.


En el código, cuando escribimos
div ecx


Da como resultado: eax = eax / ecx y edx = eax % ecx

Hemos tenido cuidado en poner edx en cero. Es una precaución que debemos tener en cuenta.

Esto es lo que pasa en realidad:
eax = edx:eax / ecx et edx = edx:eax / ecx

Poniendo edx en cero, estamos seguros de que edx no agregará bits significativos inesperados en la división.


Foto: © Bobicova_Valeria - Shutterstock.com

Consulta también

Publicado por Carlos-vialfa. Última actualización: 16 de junio de 2016 a las 07:38 por Carlos-vialfa.
El documento «Cómo saber si un número es primo en ensamblador x86» se encuentra disponible bajo una licencia Creative Commons. Puedes copiarlo o modificarlo libremente. No olvides citar a CCM (es.ccm.net) como tu fuente de información.