Algoritmo di logaritmo discreto

Question

Ho visto spesso che il logaritmo discreto è un problema difficile. Tuttavia, non vedo come questo possa essere. Mi sembra che una normale ricerca binaria farebbe bene a servire a questo scopo. Ad esempio,

binary_search(base, left, right, target) { 
    if (pow(base, left) == target) 
     return left; 
    if (pow(base, right) == target) 
     return right; 
    if (pow(base, (left + right)/2) < target) 
     return binary_search(base, (left + right)/2, right, target); 
    else 
     return binary_search(base, left, (left + right)/2, target); 
} 

log(base, number) { 
    left = 1; 
    right = 2; 
    while(pow(base, p) < number) { 
     left = right; 
     right *= 2; 
    } 
    return binary_search(base, left, right, number); 
} 

Se l'attuazione ingenuo di appena incrementare p fino pow(base, p) è O (n), allora sicuramente questa ricerca binaria è O (log (n)^2).

Oppure non capisco come viene misurato questo algoritmo?

Modifica: di solito non scrivo le ricerche binarie, quindi se c'è qualche errore di implementazione banale, gentilmente ignoralo o modifica in una correzione.

Answer 1

L'algoritmo presuppone che un < b implichi pow (base, a) < pow (base, b).

Questo è vero per i numeri naturali, ma non funzionerà in un gruppo ciclico finito (quando 'pow' è calcolato modulo un certo numero).