Calculer la racine carrée en utilisant des ajouts et des décalages (bits) comme primitives

8

Question: Étant donné un -bit nombre naturel , comment calculer en utilisant seulement ajouts et changements (bits)?nNNO(n)

L'astuce consiste à utiliser la recherche binaire. Cependant, je n'ai pas pu atteindre la complexité requise (j'ai obtenu ).O(n2)


Qu'est-ce que cela signifie par using only $O(n)$ (bit) additions and shifts:

Il s'agit d'un exercice dans un livre d'algorithmes.
À mon avis, cela signifie que l'ajout de deux nombres naturels , disons bits, coûte et le déplacement d'un nombre naturel , disons bits, coûte également . Ensuite , nous sommes seulement autorisés à utiliser ces opérations fois. Il ne mentionne pas le coût de la comparaison. Je suppose que nous pouvons l'ignorer ou supposer que la comparaison de deux nombres naturels , disons bits, coûte également .nO(1)nO(1)O(1)O(n)
nO(1)


Mon algorithmeO(n2) :

  1. Déterminez la plage du nombre de bits de : Par conséquent, tN
    2n-12N2n22n-12N2n2
    t1n-12+1tn2+1t2.
  2. Recherche binaire: recherchez entre et aide de la recherche binaire. Pour chaque nombre , pour calculer en utilisant des additions et des décalages comme primitives et le comparer avec .N2t12t2XX2N

La complexité est donc pour fois de recherche binaire et de calcul , chacun prenant à son tour additions et décalages.O(n×n)=O(n2)O(n)X2O(n)

hengxin
la source

Réponses:

7

Un algorithme itératif semble fonctionner.

Soit . Supposons que nous savons que est l'approximation entière de , c'est-à-dire , et supposons que nous connaissons la valeur de (obtenue précédemment).M=N/4XMX=MX2

Maintenant, nous voulons trouver . Quelles sont les valeurs possibles de ? Je suis presque sûr que les seules valeurs possibles sont ou . Et, il est facile de les essayer tous les deux et de voir ce qui est correct. En particulier, pour , nous avons , qui peut être obtenu à partir de par deux décalages à gauche (temps ); pour , nous avons , qui peut être obtenu à partir de et avec quatre décalages à gauche et deux ajouts (temps ). Maintenant, comparez simplement ces deux valeurs ày=Nyy=2Xy=2X+1y=2Xy2=4X2X2O(1)y=2X+1y2=4X2+4X+1X2XO(1)N pour voir lequel est correct.

De cette façon, nous obtenons un algorithme itératif où nous effectuons itérations, et où chaque itération prend fois. La durée totale de fonctionnement est , selon les besoins.n/2O(1)O(n)

Je me rends compte que cela n'a pas utilisé la recherche binaire. Tant pis.

DW
la source
Agréable! Merci. Il est acceptable de ne pas utiliser la recherche binaire. Un étourdissement: En prenant , nous avons , , et . Cependant, . Par conséquent, il peut s'agir de ou . De plus, l'idée clé de réutiliser lors du calcul de dans votre algorithme peut également s'appliquer à la deuxième étape de mon algorithme . Je vais laisser cela ouvert pendant un jour ou deux. N=9y=N=3M=N/4=2X=M=2y=2X-1y=2Xy=2X±1X2y2O(n2)
hengxin
3

Parlons-nous d'entiers ici? Où N est long de n bits?

A = 2(n/2), B = A  and C = A2
Step: B = B/2
     If C > N,  
         C = C - 2AB + B2    // too high - make smaller
         A = A - B
     Else 
         C = C + 2AB + B2   // keep this bit
         A = A + B                 
Repeat until B = 0                  // =1 on last loop

La boucle est effectuée n / 2 fois, ce qui devrait vous donner des performances O (n)

Edit: Comment ça marche, & pourquoi?
Il s'agit d'une version de Successive Approximation, également utilisée dans les algorithmes CORDIC.
En commençant par le plus petit bit possible (avec un carré inférieur à N), vous définissez un bit à la fois et calculez le nouveau carré.
Si le nouveau carré est toujours inférieur à N, conservez le bit tel qu'il est défini.
Si le nouveau carré est trop grand, effacez le bit, annulez l'effet de l'ajout et passez au bit suivant.

Exemple: N = 441 (1 1011 1001 binaire), n = 9

Start:  A = 24 = 16 (1 0000)  B = 16 C = 256 (100 0000)

1   B = 8 (1000) C = 256 + 2(16)(8) + (8)(8) = 576 (10 0100 0000) {high}
    A = 16 + 8 = 24
2   B = 4  (100) C = 576 - 2(16)(4) + (4)(4) = 400 (1 1001 0000) {low}
    A = 24 - 4 = 20
3   B = 2   (10) C = 400 + 2(20)(2) + (2)(2) = 484  (1 1110 0100) {high}
    A = 20 + 2 = 22
4   B = 1    (1) C = 484 - 2(20)(1) + (1)(1) = 441  (1 1011 1001) {keep this}
    A = 22 - 1 = 21
5   B = 1/2 or 0 in integer math; end
Alan Campbell
la source
Bienvenue en informatique ! Notez que vous pouvez utiliser LaTeX ici pour composer les mathématiques d'une manière plus lisible. Voir ici pour une courte introduction.
FrankW
Une explication, pourquoi (et comment) cet algorithme fonctionne serait bien.
FrankW
0

La principale méthode consiste à remplir les bits de de gauche à droite tout en gardant notre estimation ci - dessous, ou plutôt la place de notre estimation ci - dessous . Chaque bit est une puissance de 2, donc la mise au carré ou la multiplication d'un autre nombre par est toujours un décalage de bit. NNbb

Si l'estimation actuelle est , , et que nous connaissons déjà a , nous obtenons , et nous pouvons réécrire les deuxième et troisième termes comme et . Nous ajoutons ensuite tout et test (je suppose que vous pouvez faire ) et régler le bit si le carré est toujours inférieur .uneb=2jeune2(une+b)2=une2+2uneb+b2une<<(je+1)1<<(je<<1)<jeN

Nous commençons la boucle à et comptons jusqu'à zéro, en gardant et fur et à mesure. C'est une sorte de recherche binaire, mais où les limites correspondent à des différences sur un seul bit.je=n/2=n>>1uneune2

KWillets
la source
-3

J'aime la réponse d'Alan Campbell : avec un suivi attentif des suppositions précédentes, la nouvelle soustraction est facile à chaque fois, et la racine carrée de décalage et d'ajout binaire est à peu près aussi rapide qu'une division de décalage et d'ajout binaire.

Mais il peut être possible d'aller plus vite, au lieu de faire de votre prochaine supposition un seul chiffre binaire, au lieu d'utiliser un algorithme "Ab" x "Ab", et de faire de votre prochaine supposition la moyenne de votre supposition précédente, et le nombre d'origine divisé par la supposition précédente. Cela semble que cela prendrait plus de temps, pas plus court. Cependant, la division ne doit pas être exacte. Donc, si la division ne s'exécute qu'à la racine carrée du nombre de chiffres restant à trouver, vous pourriez en fait gagner du temps. De plus, si pour votre division vous utilisez la méthode française, de la division sténographique, alors vous pourriez réellement casser une certaine vitesse dans votre calcul pour de très grandes divisions.

Maintenant, si nous ajoutons des calculs en parallèle qui donnent des résultats préliminaires corrigibles avant que la réponse ne soit trouvée ... alors nous pourrions être sur quelque chose.

Michael Rudmin
la source
1
Tout cela semble très spéculatif. Avez-vous une réponse plus précise?
Yuval Filmus
Cela se lit comme un commentaire long.
Raphael
@Raphael Eh bien, c'est une réponse partielle. Pas bon, car c'est extrêmement spéculatif, mais c'est plus qu'une critique de la réponse d'Alan.
Gilles 'SO- arrête d'être méchant'