[C con Clase] Errores de aprendiz

[pppeee rrruuu]

Hola a todos:

Steve me has hecho recordar de un problema muy práctico:

Encontrar la solucion de: a^b mod c;

La solución sale  del uso del mod y sus propiedades.  Ahora, me preguntaba
este foro es el idoneo para lanzar estos tipos de problemas (que hacen uso
de matematicas con el de la programacion) o existe otro foros que conozcan.

Agradezco anticipadamente sus respuestas.

Oscar

El día 12 de mayo de 2008 14:19, Steven Davidson <srd4121 en njit.edu>
escribió:

> Hola Ariel,
>
> Ariel Tarifeño wrote:
> > Gracias Steven. Me ayudo mucho. Sii, del N° 13 en adelante daba
> > siempre error. Lo cambie y funciona aunque sigue siendo de
> > principiante.
> >
>
> Bueno, lo que podemos hacer es modificar tu algoritmo original para no
> introducir errores. Como realmente no quieres calcular el factorial de
> 'N-1', sino que es un paso para el problema de verdad: determinar si 'N'
> es primo o no, entonces podemos realizar los cálculos con operaciones de
> módulo. De esta forma, podemos hacer el cálculo del módulo en tu fórmula
> por "piezas" o por términos; o sea, de una manera discreta en lugar de
> hacer todo de golpe.
>
> Algunas propiedades de operaciones de módulo son las siguientes:
>
> 1. (x+y) mod n = (x mod n + y mod n) mod n
> 2. (x*y) mod n = ((x mod n) * (y mod n)) mod n
>
> Por ejemplo,
>
> 15 mod 4 = 3
>
> 1. (10+5) mod 4 = (10 mod 4 + 5 mod 4) mod 4 = (2+1) mod 4 = 3
> 2. (5*3) mod 4 = ((5 mod 4) * (3 mod 4)) mod 4 = (1*3) mod 4 = 3
>
> Con estas dos propiedades, podemos separar las operaciones de tu
> algoritmo para no tener que calcular el factorial total, sino su
> contribución al cálculo final de 'mod N'. Esto sería,
>
> ((N-1)! + 1) mod N = 0 ?
>
> pasa a ser,
>
> ((N-1)! mod N + 1) mod N = 0 ?  Ten presente que 1 mod N = 1
>
> Como el factorial es una serie de multiplicaciones, entonces podemos
> aplicar la propiedad #2 en un bucle 'for'. Sin embargo, podemos
> optimizar un poco esto, ya que los factores de '(N-1)! mod N' siempre
> serán menores que 'N'. Es decir,
>
> (N-1)! mod N;
> ((N-1) mod N) * ((N-2)! mod N)) mod N;
> ((N-1) * ((N-2)! mod N)) mod N
> ...
>
> O sea,
> N-1 < N  =>  (N-1) mod N < N
> N-2 < N  =>  (N-2) mod N < N
> N-3 < N  =>  (N-3) mod N < N
> ...
>
> Por lo tanto, no tenemos que calcular el módulo de cada factor, pero sí
> tenemos que hacerlo para cada pareja de factores. Con esto, podemos
> sacar una relación recurrente:
>
> res[2] = ((N-1) * (N-2)) mod N  (caso base o inicial)
> res[3] = (res[2] * (N-3)) mod N
> res[4] = (res[3] * (N-4)) mod N
> ...
> res[n] = (res[n-1] * (N-n)) mod N, donde n=3,4,...,N-1
>
> No recomiendo implementar este algoritmo como una función recursiva,
> sino iterativamente; o sea, usa un bucle 'for'.
>
> Al final, agregaríamos 1 al valor final de 'res', por lo que tendríamos
> aplicar nuevamente el cálculo del módulo:
>
> res_final = (res+1) mod N
>
> Lo último  que queda por hacer es comprobar si 'res_final' es 0 (cero) o
> no, para determinar si 'N' es primo o no.
>
>
> Huelga decir que las limitaciones de 'int' siguen siendo las mismas que
> en el algoritmo anterior, pero al no tener que hacer multiplicaciones
> con números grandes, podemos alcanzar un valor de 'N' mayor al que
> podíamos antes. Si 'int' es de 32 bits, entonces podemos usar valores de
> N <= 65536; con 'int' de 64 bits, el alcance es de N <=
> 9223372036854775808.
>
> Espero que todo esto te sirva.
>
> Steven
>
>
>
>
> _______________________________________________
> Lista de correo Cconclase Cconclase en listas.conclase.net
> http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net
> Bajas: http://listas.conclase.net/index.php?gid=2&mnu=FAQ
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.conclase.net/pipermail/cconclase_listas.conclase.net/attachments/20080514/91b25f8d/attachment-0001.html>