Esiste un modo efficace per convertire un numero unario in un numero binario?

Question

lasciare che quei tipi di dati rappresentano numeri naturali unarie e binari rispettivamente:

data UNat = Succ UNat | Zero 
data BNat = One BNat | Zero BNat | End 

u0 = Zero 
u1 = Succ Zero 
u2 = Succ (Succ Zero) 
u3 = Succ (Succ (Succ Zero)) 
u4 = Succ (Succ (Succ (Succ Zero))) 

b0 = End     // 0 
b1 = One End    // 1 
b2 = One (Zero End)  // 10 
b3 = One (One End)   // 11 
b4 = One (Zero (Zero End)) // 100 

(Alternatively, one could use `Zero End` as b1, `One End` as b2, `Zero (Zero End)` as b3...) 

La mia domanda è: esiste un modo per implementare la funzione:

toBNat :: UNat -> BNat 

che opera nel O(N), facendo una sola passata attraverso UNat?

Answer 1

Per incrementare una cifra binaria, è necessario capovolgere il primo zero alla fine del proprio numero e tutti quelli precedenti. Il costo di questa operazione è proporzionale al numero di 1 alla fine del tuo input (per questo il tuo dovrebbe rappresentare il numero come elenco da destra a sinistra, ad esempio i codici lista [1; 0; 1; 1] per 13) .

Diamo una (n) il numero di 1 alla fine del n:

a(n) = 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ... 

e lasciatevi

s(k) = a(2^k) + a(2^k+1) + ... + a(2^(k+1)-1) 

essere la somma di elementi tra due potenze di 2. Si dovrebbe essere grado di convincersi che s (k + 1) = 2 * s (k) + 1 (con s (0) = 1) osservando che

a(2^(k+1)) ..., a(2^(k+2) - 1) 

è ottenuta concatenando

a(2^k) + 1, ..., a(2^(k+1) - 1) and a(2^k), ..., a(2^(k+1) - 1) 

E quindi, come una serie geometrica, s (k) = 2^k - 1.

Ora il costo di incrementare N volte un numero deve essere proporzionale alla

a(0) + a(1) + ... + a(N) 
    = s(0) + s(1) + s(2) + ... + s(log(N)) 
    = 2^0 - 1 + 2^1 -1 + 2^2-1 + ... + 2^log(N) - 1 
    = 2^0 + 2^1 + 2^2 + ... + 2^log(N) - log(N) - 1 
    = 2^(log(N) + 1) - 1 - log(N) - 1 = 2N - log(N) - 2 

Quindi, se ti occupi di rappresentare i tuoi numeri da destra a sinistra, allora l'algoritmo ingenuo è lineare (nota che puoi eseguire l'inversione dell'elenco e rimanere lineare se hai davvero bisogno dei tuoi numeri al contrario).

Answer 2

Se abbiamo una funzione per incrementare un BNat, possiamo farlo abbastanza facilmente eseguendo lungo la UNat, incrementare un BNat ad ogni passo:

toBNat :: UNat -> BNat 
toBNat = toBNat' End 
    where 
    toBNat' :: BNat -> UNat -> BNat 
    toBNat' c Zero  = c 
    toBNat' c (Succ n) = toBNat' (increment c) n 

Ora, questo è O(NM) dove M è il peggiore custodia per increment. Quindi se possiamo fare increment in O (1), allora la risposta è sì.

Ecco il mio tentativo di attuare increment:

increment :: BNat -> BNat 
increment = (reverse End) . inc' . (reverse End) 
    where 
    inc' :: BNat -> BNat 
    inc' End  = One End 
    inc' (Zero n) = One n 
    inc' (One n) = Zero (inc' n) 

    reverse :: BNat -> BNat -> BNat 
    reverse c End = c 
    reverse c (One n) = reverse (One c) n 

Questa implementazione è O(N) perché si deve reverse la BNat a guardare i bit meno significativi, che vi dà O(N) complessiva. Se consideriamo il tipo BNat per rappresentare numeri binari invertiti, non è necessario invertire lo BNat e, come dice @augustss, abbiamo O (1), che fornisce O (N) nel complesso.

Answer 3

Mi piacciono le altre risposte, ma trovo le loro analisi asintotiche complicate.Propongo quindi un'altra risposta che abbia un'analisi asintotica molto semplice. L'idea di base è di implementare divMod 2 per i numeri unari. Così:

data UNat = Succ UNat | Zero 
data Bit = I | O 

divMod2 :: UNat -> (UNat, Bit) 
divMod2 Zero = (Zero, O) 
divMod2 (Succ Zero) = (Zero, I) 
divMod2 (Succ (Succ n)) = case divMod2 n of 
    ~(div, mod) -> (Succ div, mod) 

Ora possiamo convertire in binario da iterazione divMod.

toBinary :: UNat -> [Bit] 
toBinary Zero = [] 
toBinary n = case divMod2 n of 
    ~(div, mod) -> mod : toBinary div 

L'analisi asintotica è ora piuttosto semplice. Dato un numero n in notazione unaria, divMod2 impiega O (n) il tempo necessario per produrre un numero pari alla metà di un valore - ad esempio, ci vuole al massimo c*n tempo per un numero sufficiente di n. Iterando questa procedura richiede quindi questo molto tempo:

c*(n + n/2 + n/4 + n/8 + ...) 

Come tutti sappiamo, questa serie converge c*(2*n), così toBinary è anche in O (n) con la testimonianza costante 2*c.