elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Tutorial básico de Quickjs


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Optimización de algoritmo de fuerza bruta
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Optimización de algoritmo de fuerza bruta  (Leído 4,148 veces)
kutcher

Desconectado Desconectado

Mensajes: 53


Ver Perfil
Optimización de algoritmo de fuerza bruta
« en: 2 Septiembre 2014, 22:30 pm »

Buenas, tengo el siguiente algoritmo:

Código
  1. void bruteforce(int inc, int fin, char *rotation)
  2. {
  3.    int i = 0, j, len = strlen(rotation);
  4.    long int r = 0, end, c;
  5.    char test[200];
  6.    for(j = inc; j < fin+1; j++)
  7.    {
  8.        r = 0;
  9.        end = (long int)pow(len, j);
  10.        while(r != end)
  11.        {
  12.            c = r;
  13.            while(i < j)
  14.            {
  15.                test[i] = rotation[c % len];
  16.                c = (long int)c / len;
  17.                i++;
  18.            }
  19.            test[i] = '\0';
  20.            puts(test);
  21.            i = 0;
  22.            r++;
  23.        }
  24.    }
  25. }

Mi intención es evitar el uso de pow porque esta consume demasiado recursos, lo que busco es la forma de representarlo con solo operaciones aritméticas .... alguna idea

Saludos kutcher   


En línea

MCKSys Argentina
Moderador Global
***
Desconectado Desconectado

Mensajes: 5.513


Diviértete crackeando, que para eso estamos!


Ver Perfil
Re: Optimización de algoritmo de fuerza bruta
« Respuesta #1 en: 2 Septiembre 2014, 22:41 pm »

Hola!

Revisa este post.

Saludos!


En línea

MCKSys Argentina

"Si piensas que algo está bien sólo porque todo el mundo lo cree, no estás pensando."

kutcher

Desconectado Desconectado

Mensajes: 53


Ver Perfil
Re: Optimización de algoritmo de fuerza bruta
« Respuesta #2 en: 3 Septiembre 2014, 02:06 am »

Revisa este post.

La verdad no entendí mucho, por otro lado hice una función pow que solo trabaja con enteros pensé que de esta manera podría ser mas rápida pero no:

Código
  1. int pow2(int x, int n)
  2. {
  3.    int p;
  4.    for ( p = 1 ; n > 0 ; --n )
  5.        p *= x;
  6.    return p;
  7. }

Saludos kutcher
En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Optimización de algoritmo de fuerza bruta
« Respuesta #3 en: 3 Septiembre 2014, 08:16 am »

La verdad no entendí mucho, por otro lado hice una función pow que solo trabaja con enteros pensé que de esta manera podría ser mas rápida pero no:

Código
  1. int pow2(int x, int n)
  2. {
  3.    int p;
  4.    for ( p = 1 ; n > 0 ; --n )
  5.        p *= x;
  6.    return p;
  7. }

Saludos kutcher

La librería estándar ha sido programada y optimizada por gente bastante ducha tanto en matemáticas como en programación... es complicado sacar una versión que sea más eficiente (no es imposible pero...)

En cualquier caso yo creo que puedes optimizar la función "arrastrando" el valor de "end", de esta forma sólo llamas a pow una vez durante la ejecución de la función.

Código
  1. void bruteforce(int inc, int fin, char *rotation)
  2. {
  3.    int i = 0, j, len = strlen(rotation);
  4.    long int r = 0, c;
  5.    char test[200];
  6.    long int end = (long int)pow( len, inc );
  7.    for(j = inc; j < fin+1; j++)
  8.    {
  9.        r = 0;
  10.        end *= len;
  11.        while(r != end)
  12.        {
  13.            c = r;
  14.            while(i < j)
  15.            {
  16.                test[i] = rotation[c % len];
  17.                c = (long int)c / len;
  18.                i++;
  19.            }
  20.            test[i] = '\0';
  21.            puts(test);
  22.            i = 0;
  23.            r++;
  24.        }
  25.    }
  26. }
En línea

kutcher

Desconectado Desconectado

Mensajes: 53


Ver Perfil
Re: Optimización de algoritmo de fuerza bruta
« Respuesta #4 en: 3 Septiembre 2014, 15:25 pm »

En cualquier caso yo creo que puedes optimizar la función "arrastrando" el valor de "end", de esta forma sólo llamas a pow una vez durante la ejecución de la función.

Hola eferion probé lo que indicaste pero no funciona y ademas provoca que entre en un ciclo infinito .. ahora tengo otra pow pero mas optimizada que creo es mas rápida según noto es este:

Código
  1. int ipow(int base, int exp)
  2. {
  3.    int result = 1;
  4.    while(exp)
  5.    {
  6.        if(exp & 1)
  7.           result *= base;
  8.        exp >>= 1;
  9.        base *= base;
  10.    }
  11.    return result;
  12. }
  13.  

Saludos kutcher
En línea

rir3760


Desconectado Desconectado

Mensajes: 1.639


Ver Perfil
Re: Optimización de algoritmo de fuerza bruta
« Respuesta #5 en: 3 Septiembre 2014, 19:29 pm »

Primero las recomendaciones:

1) Las conversiones explicitas al tipo long int no son necesarias ya que se realizan de forma automática, por ello hay que eliminarlas.

2) Los dos bucles while se pueden sustituir por bucles for para compactar el código fuente.

3) Puedes utilizar una sola vez la función pow justo antes del bucle externo, la actualización del valor de la variable "end" se debe realizar justo al final del mentado bucle.

Con los cambios:
Código
  1. void bruteforce(int inc, int fin, char *rotation)
  2. {
  3.   int i, j, len = strlen(rotation);
  4.   long int r, end, c;
  5.   char test[200];
  6.  
  7.   end = pow(len, inc);
  8.   for(j = inc; j < fin + 1; j++){
  9.      for (r = 0; r != end; r++){
  10.         c = r;
  11.         for (i = 0; i < j; i++){
  12.            test[i] = rotation[c % len];
  13.            c = c / len;
  14.         }
  15.         printf("%.*s\n", i, test);
  16.      }
  17.  
  18.      end *= len;
  19.   }
  20. }
Como no publicas el programa completo te toca a ti verificar que funcione correctamente (ya nos avisas si hubo algún resbalón).

----

Un ultimo comentario: si se trata de una solución de fuerza bruta la prioridad debe ser la claridad del código fuente, si esta fuera la eficiencia lo mejor es simplemente ... cambiar de algoritmo.

Un saludo
En línea

C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language
kutcher

Desconectado Desconectado

Mensajes: 53


Ver Perfil
Re: Optimización de algoritmo de fuerza bruta
« Respuesta #6 en: 3 Septiembre 2014, 19:56 pm »

Como no publicas el programa completo te toca a ti verificar que funcione correctamente (ya nos avisas si hubo algún resbalón).

Hola rir3760 ahora si va bien en cuanto al código completo es el siguiente:

Código
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<math.h>
  4. #include<stdlib.h>
  5. #include<time.h>
  6.  
  7. void bruteforce(int inc,int fin,char *rotation);
  8.  
  9. int main(void)
  10. {
  11.    int inc, fin;
  12.    unsigned long t_start = 0, t_end = 0;
  13.    char rotation[200] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  14.                         "abcdefghijklmnopqrstuvwxyz"
  15.                         "1234567890<>,?;.:/!&#1079;*&#9569;&#8729;%$&#1075;"
  16.                         "&#1076;&#1080;+=})]&#1088;@&#1095;^\\_`&#1096;|-[({'#\"&#1097;~&\0";
  17.  
  18.    printf("\n Comenzar de: ");
  19.    scanf("%d", &inc);
  20.    printf("\n Terminar en: ");
  21.    scanf("%d", &fin);
  22.  
  23.    t_start = clock();
  24.    bruteforce(inc, fin, rotation);
  25.    t_end = clock();
  26.  
  27.    printf("Terminado en : %ld segundos.\n", (t_end - t_start)/1000);
  28.  
  29.    return 0;
  30. }
  31.  
  32. void bruteforce(int inc, int fin, char *rotation)
  33. {
  34.    int i, j, len = strlen(rotation);
  35.    long int r, end, c;
  36.    char test[200];
  37.  
  38.    end = pow(len, inc);
  39.    for(j = inc; j < fin + 1; j++)
  40.    {
  41.        for(r = 0; r != end; r++)
  42.        {
  43.            c = r;
  44.            for(i = 0; i < j; i++)
  45.            {
  46.                test[i] = rotation[c % len];
  47.                c = c / len;
  48.            }
  49.            puts(test);
  50.        }
  51.        end *= len;
  52.    }
  53. }
  54.  

Solo le cambie lo del printf ya que considero que es mas lento que puts

Saludos kutcher
En línea

rir3760


Desconectado Desconectado

Mensajes: 1.639


Ver Perfil
Re: Optimización de algoritmo de fuerza bruta
« Respuesta #7 en: 4 Septiembre 2014, 05:27 am »

Solo le cambie lo del printf ya que considero que es mas lento que puts
En ese caso debes agregar manualmente el carácter '\0' justo antes de la llamada a función (esa es la ventaja de printf):
Código
  1. test[i] = '\0';
  2. puts(test);

Un saludo
En línea

C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Fuerza Bruta En VB
Programación Visual Basic
Cicklow 6 7,881 Último mensaje 24 Agosto 2005, 22:51 pm
por 5v5
alguien sabe algun algoritmo de fuerza bruta
Programación Visual Basic
adn 2 3,175 Último mensaje 7 Enero 2006, 19:38 pm
por adn
Algoritmo de Fuerza bruta...
Programación General
rdzlcs 4 14,146 Último mensaje 31 Diciembre 2010, 16:26 pm
por rdzlcs
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines