Hola a todos:<br><br>Steve me has hecho recordar de un problema muy práctico:<br><br>Encontrar la solucion de: a^b mod c;<br><br>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.<br>
<br>Agradezco anticipadamente sus respuestas.<br><br>Oscar<br><br><div class="gmail_quote">El día 12 de mayo de 2008 14:19, Steven Davidson <<a href="mailto:srd4121@njit.edu">srd4121@njit.edu</a>> escribió:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">Hola Ariel,<br>
<br>
Ariel Tarifeño wrote:<br>
</div><div class="Ih2E3d">> Gracias Steven. Me ayudo mucho. Sii, del N° 13 en adelante daba<br>
> siempre error. Lo cambie y funciona aunque sigue siendo de<br>
> principiante.<br>
><br>
<br>
</div>Bueno, lo que podemos hacer es modificar tu algoritmo original para no<br>
introducir errores. Como realmente no quieres calcular el factorial de<br>
'N-1', sino que es un paso para el problema de verdad: determinar si 'N'<br>
es primo o no, entonces podemos realizar los cálculos con operaciones de<br>
módulo. De esta forma, podemos hacer el cálculo del módulo en tu fórmula<br>
por "piezas" o por términos; o sea, de una manera discreta en lugar de<br>
hacer todo de golpe.<br>
<br>
Algunas propiedades de operaciones de módulo son las siguientes:<br>
<br>
1. (x+y) mod n = (x mod n + y mod n) mod n<br>
2. (x*y) mod n = ((x mod n) * (y mod n)) mod n<br>
<br>
Por ejemplo,<br>
<br>
15 mod 4 = 3<br>
<br>
1. (10+5) mod 4 = (10 mod 4 + 5 mod 4) mod 4 = (2+1) mod 4 = 3<br>
2. (5*3) mod 4 = ((5 mod 4) * (3 mod 4)) mod 4 = (1*3) mod 4 = 3<br>
<br>
Con estas dos propiedades, podemos separar las operaciones de tu<br>
algoritmo para no tener que calcular el factorial total, sino su<br>
contribución al cálculo final de 'mod N'. Esto sería,<br>
<br>
((N-1)! + 1) mod N = 0 ?<br>
<br>
pasa a ser,<br>
<br>
((N-1)! mod N + 1) mod N = 0 ?  Ten presente que 1 mod N = 1<br>
<br>
Como el factorial es una serie de multiplicaciones, entonces podemos<br>
aplicar la propiedad #2 en un bucle 'for'. Sin embargo, podemos<br>
optimizar un poco esto, ya que los factores de '(N-1)! mod N' siempre<br>
serán menores que 'N'. Es decir,<br>
<br>
(N-1)! mod N;<br>
((N-1) mod N) * ((N-2)! mod N)) mod N;<br>
((N-1) * ((N-2)! mod N)) mod N<br>
...<br>
<br>
O sea,<br>
N-1 < N  =>  (N-1) mod N < N<br>
N-2 < N  =>  (N-2) mod N < N<br>
N-3 < N  =>  (N-3) mod N < N<br>
...<br>
<br>
Por lo tanto, no tenemos que calcular el módulo de cada factor, pero sí<br>
tenemos que hacerlo para cada pareja de factores. Con esto, podemos<br>
sacar una relación recurrente:<br>
<br>
res[2] = ((N-1) * (N-2)) mod N  (caso base o inicial)<br>
res[3] = (res[2] * (N-3)) mod N<br>
res[4] = (res[3] * (N-4)) mod N<br>
...<br>
res[n] = (res[n-1] * (N-n)) mod N, donde n=3,4,...,N-1<br>
<br>
No recomiendo implementar este algoritmo como una función recursiva,<br>
sino iterativamente; o sea, usa un bucle 'for'.<br>
<br>
Al final, agregaríamos 1 al valor final de 'res', por lo que tendríamos<br>
aplicar nuevamente el cálculo del módulo:<br>
<br>
res_final = (res+1) mod N<br>
<br>
Lo último  que queda por hacer es comprobar si 'res_final' es 0 (cero) o<br>
no, para determinar si 'N' es primo o no.<br>
<br>
<br>
Huelga decir que las limitaciones de 'int' siguen siendo las mismas que<br>
en el algoritmo anterior, pero al no tener que hacer multiplicaciones<br>
con números grandes, podemos alcanzar un valor de 'N' mayor al que<br>
podíamos antes. Si 'int' es de 32 bits, entonces podemos usar valores de<br>
N <= 65536; con 'int' de 64 bits, el alcance es de N <= 9223372036854775808.<br>
<br>
Espero que todo esto te sirva.<br>
<div><div></div><div class="Wj3C7c"><br>
Steven<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
Lista de correo Cconclase <a href="mailto:Cconclase@listas.conclase.net">Cconclase@listas.conclase.net</a><br>
<a href="http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net" target="_blank">http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net</a><br>
Bajas: <a href="http://listas.conclase.net/index.php?gid=2&mnu=FAQ" target="_blank">http://listas.conclase.net/index.php?gid=2&mnu=FAQ</a><br>
</div></div></blockquote></div><br>