Optimizando función manual de modulo o resto.

[AlbertoBSD]

En su momento mas de alguno uso el operador modulo

r = a % n;

donde r es el resto de la división a/n donde n != 0

Ahora como estoy trabajando con numeros muy grandes de longitud variable el operador modulo como tal no me sirve, necesito crear la funcion que haga el modulo manualmente.

Si alguno de ustedes se perdio los temas, estos son algunos de ellos

Números de longitud variable en C (Numeros muy grandes)
Restas manuales en "Binario"

Ahora si hacemos la funcion modulo en forma de restas, tenemos solo le tenemos que restar al numero a el valor de n hastra que a sea menor que n

El siguiente codigo es muestra de ello de forma manual y sin ninguna optimizacion.

Código (c) [Seleccionar] Expandir

#include<stdio.h>

int main() {
int resto,a,n,contador;
a = 9999998;
n = 3;
resto = a;
contador = 0;
while(resto >= n) {
resto-= n;
contador++;
}
printf("resto: %u\nVeces en el ciclo %u\n",resto,contador);
}

Salida:

Código [Seleccionar] Expandir

resto: 2
Veces en el ciclo 3333332


Como vemos el numero de veces que entra al ciclo es el resultado de la división obtenido de forma iterativa mediante restas sucesivas.

Pero como se trata solo de la función "Modulo" o "Resto" no nos interesa el resultado de la división, para fines prácticos y rápidos realice esa función un poco mas optimizada y se podría optimizar mas, pero ya lo dejo a su consideración.

Código (c) [Seleccionar] Expandir

#include<stdio.h>

int main() {
int resto,a,n,contador,n_pivote,resto_pivote,entrar;
a = 9999998;
n = 3;
resto = a;
contador = 0;
resto_pivote = resto;
n_pivote = n;
entrar = 1;
while(entrar && resto >= n) {
resto_pivote-=n_pivote;
if(resto_pivote>=0) {
resto = resto_pivote;
n_pivote*=2;
}
else {
if(n_pivote > n) {
n_pivote/=2;
resto_pivote = resto;
}
else {
entrar = 0;
}
}
contador++;
}
printf("resto: %u\nVeces en el ciclo %u\n",resto,contador);
}

Salida:

Código [Seleccionar] Expandir


resto: 2
Veces en el ciclo 65


Como vemos el numero de veces que entra es muchísimo menor incluso si optimizamos mas la función para este ejemplo podremos llegar hasta solo 55 o 58 veces entrando al ciclo dado.

El programa utilizada una aproximación binaria ya que en cada iteracion al numero a se le resta un valor igual a n*2 veces la cantidad del ciclo anterior.

Dado que estoy trabajando con numero descomunalmente grandes... cualquier optimizan en estas funciones es mas que bien recibida.

Saludos!



Optimize aun mas el Código y ahora solo se ejecuta 42 veces para el ejemplo dado.

Ahora en lugar de incrementar el sustraendo dentro del ciclo principal lo incremento al máximo en un ciclo aparte antes del principal y posteriormente dentro del ciclo principal lo decremento hasta que sea el un multiplo de n inmediamtamente menor al valor actual de r

Código (c) [Seleccionar] Expandir

#include<stdio.h>

int main() {
int resto,a,n,contador,n_pivote,entrar;
a = 9999998;
n = 3;
resto = a;
contador = 0;
n_pivote = n;
entrar = 1;
while(n_pivote<resto) {
n_pivote+=n_pivote;
contador++;
}
while(entrar && resto >= n) {
while(n_pivote>resto && n_pivote>n) {
n_pivote/=2;
contador++;
}
resto-=n_pivote;
}
printf("resto: %u\nVeces en el ciclo %u\n",resto,contador);
}

Salida:

Código [Seleccionar] Expandir

resto: 2
Veces en el ciclo 42


Considero yo que es el mas optimizado pero no se tal vez se puede ahorrar alguno que otro ciclo, la variable contador solo es para fines didácticos.

Saludos

[HardForo]

Buen trabajo! ese tipo de cosas (complejidad de los algortimos) son de las mas importantes y pocos programadores le dan la importancia que se merecen