Metodologias de Programación: Recursividad

1. Especificació de l’algorisme
Tal i com indica l’enunciat, la nostra funció s’encarrega de fer exponencials modulars (). Com a tal, vaig decidir que les entrades haurien de
tenir alguna condició. S’ha d’introduir sempre una x major que 0 per evitar el cas i, també la N per evitar fer el mòdul 0.

2. Algorisme recursiu lineal
a. Especificació de la funció
El que busquem és un algorismerecursiu. Primer vaig pensar en anar restant un a unitat a l’exponent però era poc eficient, ja
que hauria de fer y-1 crides recursives. Finalment, la manera més eficient que vaig trobar de fer, seria dividint l’exponent per 2
cada vegada que crida la funció, disminuint el cost de l’algorisme.
b. Anàlisis per casos
El cas directe: Si l’exponent és 0, f serà 1. Ja que qualsevol número elevat a 0és 1. Per tant ens quedaria 1 mod N
I el cas indirecte: Aquí hem de diferenciar dos casos. El primer, si l’exponent es divisible per 2. I el segon, que no. En el primer
cas al sortir de la funció l’únic que farem es multiplicar per sí la f i fer el mòdul. En el segon cas primer haurem de restar una unitat
a l’exponent. Amb això queda una x “
suelta” que multiplicarem a les dues f i finalmentfarem el mòdul.

c. Construcció de l’algorisme
Ara que ja tenim els tres casos que ens trobarem podem passar a la construcció de l’algorisme.
fun pot_modRL(x, y, N: nat) ret f:nat
{Pre:(x>0)}
[y=0 f:=1 mod N;
[]y 0
[y mod 2=0 f:=pot_modRL(x,(y/2), N);
f:=(f*f) mod N;
[]y mod 2
f:=pot_modRL(x,((y-1)/2),N);
f:=((f*f)modN*xmodN)mod N;
]
]
[Post: f=xy mod N}
ret f;
d. Verificacióde l’algorisme
1. Verificació cas directe:
x,h(x))

2. Verificació cas recursiu
tant si y es parell com senar
x,c(x,v))

3. Cutoa t(x) i t(y)
t(x) ha d’estar definida en el domini dels naturals.
t(y) també ha d’estar definida en el domini dels natural.
4. t(x) decreix estrictament

e. Estudi del cost de l’algorisme
Aquest algorisme te un cost logarítmic() ja que és una potencia onanem dividint l’exponent cada vegada per dos. Per exemple
si la nostra y fos 512, passaria en la primera crida a 256, la segona a 128, la tercera a 64, la cuarta a 32 , després a 16, a 8, a 4 , a 2 i
finalment arribaríem a 0. És a dir, en total tindrem nou crides que és el resultat de .

3. Algorisme recursiu final
a. Transformació recursiu lineal a final, mitjançant desplegat-plegat
En elcas parell tenim:

En el cas imparell:

Així que ajuntant les dues funcions obtenim que necessitem dues variables més a i b.
Per tant ara tenim que:
On c i d son l’element neutre de la multiplicació,1.

Passarem a fer el desplegat.
Pel cas directe:
Pel cas parell:

Pel cas imparell:

Com podem observar ens queda un . Haurem de substituir w per x mod N. Per tant haurem de sumar unavariable més, la qual s’anirà
multiplicant per si mateixa, w*w.
Així ens quedarà que:
Pel cas parell:
Pel cas imparell:

b. Codi de la funció recursiva final
fun pot_modRF(x, y, N, a, b: nat) ret f:nat
{Pre:(x>0)}
[si y=0 f:=a mod N;
[]si y 0
[si y mod 2=0 f:= pot_mod(x,y/2,N,a,2*b,(w*w)modN);
[]si y mod 2
f:= pot_mod(x,(y-1)/2,N,a*w,2*b,(w*w)modN);
]
[Post: w=xy mod N}
ret w;

]4. Algorisme iteratiu
a. Transformació de recursiu final a iteratiu
Per tal de fer una bona transformació a iteratiu el que hem de fer es fixar-nos en que canvia en la funció recursiva lineal.
{Pre:(x>0)}
*[y>0
[ y mod 2=0) =
[]y mod 2!=0)
=
]
f:=a mod N
{Post: f=a*(pot_modRF(x,y/2,N))b}
b. Estudi del cost de l’algorisme iteratiu
El cost de l’algorisme iteratiu al igual que abansés un cost logarítmic degut al mateix, que anem dividint l’exponent entre 2.
Tot i això aquest és més eficient ja que no crida a cap funció, sino que va actualitzant les variables sobre ella mateixa i no
necessita carregar res cada cop que entra en la funció.

5. Implementació en Java dels codis dissenyats en els apartats anteriors
public class PotenciaModular {
public static int...