Quelle est la pire entrée de l'algorithme de Stein?

Question

J'essaie de trouver la relation de récurrence pour l'algorithme de Stein (algorithme GCD binaire), mais ma capacité à la tracer n'est pas à la hauteur.

Je suis complètement déconcerté par les chemins multiples et les appels récursifs, ainsi que le fait que nous traitons le nombre total de bits pour représenter nos valeurs plutôt que les valeurs elles-mêmes.

est ici l'algorithme:

stein(u, v): 
    if either of u or v are 0: return their sum. 
    if either of u or v are 1: return 1. 
    if both u and v are even: return 2 * stein(u/2, v/2) 
    if u is even and v is odd: return stein(u/2, v) 
    if u is odd and v is even: return stein(u, v/2) 
    if both u and v are odd: return stein(larger-smaller/2, smaller) 

J'essaie de trouver la relation de récurrence T (n) où n est le nombre total de bits nécessaires pour représenter u et v Je pense que la première étape ici. pour moi devrait être en train de travailler quand la pire des performances se produit.

Je pense que chaque opération de division réduit le nombre de bits de 1, mais c'est à peu près le maximum que je comprends jusqu'à présent.

J'ai essayé de tracer l'algorithme mais en vain. J'ai aussi lu la section pertinente de Knuth Vol. 2 mais je pense que c'est un peu en dehors de la portée actuelle de ma compréhension parce que cela n'avait pas beaucoup de sens pour moi.

Answer 1

Vous voulez une relation de récurrence qui dénote le nombre de bits dans u et v, pas la valeur de stein (u, v) alors raisonnons-nous à travers un peu.
Étant donné u et v arbitraires, quels sont les meilleurs et les pires cas?

Meilleur cas (nous terminons rapidement): l'un des cas à temps constant.

Pire exemple: appel récursif à stein (u/2, v/2), stein (u, v/2), ou stein (Grande-inférieure/2, plus petits)

• Dans le premier scénario, nous réduisons de moitié les valeurs, ce qui supprimera simplement deux chiffres binaires. Cela nous a coûté une opération pour le faire. T (n) = T (n-2) + 1

• Dans le deuxième scénario, nous ne divisons que l'une des valeurs, donc seulement 1 chiffre de moins que nous avons commencé avec. Cela a pris une opération. T (n) = T (n-1) + 1

• Le troisième scénario devient plus laid. Une soustraction itère sur tous les chiffres de n. Cela signifie que si nous perdons m chiffres, mais utilisé n étapes (la soustraction), notre récurrence est T (n)> = T (n-m) + n. Nous devons encore trouver m, et si nous pouvons prouver que cette étape élimine beaucoup de chiffres (ex: m = n/2), la récurrence peut ne pas être trop lente.
  Malheureusement, nous pouvons facilement trouver un très mauvais scénario.
  Mettez v à 3. Cela nous assure que c'est bizarre, et ce sera toujours le plus petit des deux. Maintenant si nous mettons u tel que (u-v)/2 continue à être impair, alors la récurrence continuera à aller dans ce troisième cas. Et avec v = 3, (u-v)/2 ne sera plus qu'un chiffre plus petit que u. Cela signifie dans le pire des cas, m est 1. ==> T (n) = T (n-1) + n

exemple de ce mauvais scénario: (21,3) -> (9,3) -> (3,3) Nous pourrions continuer à construire les plus grands nombres en prenant v '= v * 2 + 3. Comme vous le voyez, la croissance de ces "mauvais" nombres est un chiffre binaire à la fois et nous conduira à toujours descendre le troisième chemin. C'est pourquoi m est 1.

Ce dernier scénario de récurrence est malheureusement O (n * n)

Answer 2

Vous êtes à la recherche d'une règle qui repose sur l'évaluation de la fonction récursive avec une aussi grande taille de sous-problème (par rapport à la taille du problème) que possible. Il existe deux règles qui nécessitent de résoudre un sous-problème avec un bit de moins: les règles qui gèrent le cas où exactement l'un de u ou v est impair. Le nombre impair ne change pas et le nombre pair doit rester même le plus longtemps possible. Cela suggère que le cas le plus défavorable est le suivant: (1) le plus petit entier impair qui n'est pas traité comme un cas de base (2) puissance croissante de 2. Autrement dit, prendre u = 3 et v=2^n pour certains n. Le temps de fonctionnement de stein est linéaire dans ce cas en nombre de bits d'entrée.