Puoi chiamare questo algoritmo a radice quadrata su un numero intero senza segno tramite la manipolazione del numero binario?

Question

Puoi chiamare questo algoritmo a radice quadrata su un numero intero senza segno tramite la manipolazione del numero binario?

Naviga le tue risposte

#1 da (3 voti)
#2 da (0 voti)
#3 da (0 voti)

1

Apparentemente questo algoritmo è ben noto.

L'algoritmo costruisce la risposta radice quadrata bit per bit a partire dal bit più a sinistra fino all'ultimo.

Diciamo che supporteremo la quadratura di un intero senza segno a 8 bit per semplicità.

lascia res essere risultato

lascia x essere un numero intero senza segno a 8 bit

lascia che n sia l'ennesimo bit nel risultato in cui il bit 0 è l'ultimo bit.

set res to 0
for nth bit from 3 down to 0
    change the nth bit of the res to 1
    if res * res > x then: <- The Comparison
         restore the nth bit back to 0
return res

Il risultato di ritorno sarà un intero senza segno a 4 bit

Ad esempio: ricerca della radice quadrata di 4

(vedi immagine)

Questoèforseilcalcolodellacifrapercifre:sistemanumericobinario(base2)? Link Wiki qui

Grazie per il tuo tempo!

algorithms binary

posta chickenninja565 29.09.2016 - 07:42

fonte

3 risposte

Leggi altre domande sui tag algorithms binary

Sovraccarico / ereditarietà di Java Creazione di astrazione su API

score 3 · Answer 1

potrei chiamarlo approssimazione successiva o forse ricerca binaria per invertire una funzione monotonaica .

se sei in grado di eseguire una funzione f(x) , e se sai che f(x) è strettamente monotonico (strettamente crescente o strettamente decrescente) nel dominio di x che è saliente, puoi sempre invertire f(x) a qualunque grado finito di precisione desideri con questa ricerca binaria. una iterazione per ogni bit di cui hai bisogno nel tuo risultato.

score 0 · Answer 2

Sì, è essenzialmente lo stesso algoritmo descritto nell'articolo che hai collegato.

La differenza principale è l'uso della moltiplicazione del tuo pseudo-codice, che costa più di quello che può essere fatto, come sottolinea lo stesso articolo, "... le operazioni necessarie per calcolare ... e * e possono essere sostituite con operazioni di shift rapido più veloci. "

'HTH,

score 0 · Answer 3

In parole semplici, se è dato che X == Y^2 (una riformulazione di sqrt(X) == Y ), e vorresti risolvere (N*N*X + m) == (N*Y + k)^2 per k dove il valore di N è corretto per l'intero algoritmo, puoi semplicemente sostituire i valori in k da k = 0, 1, ..., N-1 e confrontare la grandezza tra il lato sinistro (che è fisso) e il lato destro (che dipende dal valore sostituito in k ).

Per N = 2 , il possibile valore di k è semplicemente 0, 1 in modo che si riduca a una ricerca binaria.