Discussion :

[mach1]

Bonjour,

j'aurais besoin d'un algorithme me permettant de calculer la partie entière de la valeur de la racine carré d'un nombre (n) multipliée par une constante (c puissance de 10) (ceci afin de ne pas utiliser les flottants).
Par exemple: pour n = 10 et c = 100, on a sqrt(n) = 3,16227766
sqrt(n) * c = 316,227766
Ainsi dans ce cas là l'algo devra me renvoyer 316.
Bien évidemment je cherche à effectuer ceci sans jamais utiliser de flottants.

J'ai regardé les algorithmes de calcul de racine carré, et en particulier sur ce site: http://membres.multimania.fr/ericmer...es/racines.htm.
Le seul qui me semble adaptable à mon problème est l'algo au "compte goutte" qui est je cite "de convergence est décevante". En effet, il me suffirait de calculer les chiffres du résultat et de les multiplier par leur poids respectif.

Voilà, j'aurais aimé avoir votre avis sur ça et savoir si un autre algo plus efficace ne pourrait pas être utilisé.

D'avance merci.

[Franck Dernoncourt]

http://en.wikipedia.org/wiki/Methods...g_square_roots ?

[edfed]

en assembleur et en anglais:

http://board.flatassembler.net/topic...r=asc&start=57

integer square root.

n'hesite pas à lire tout le post, il est fort instructif.

pour ce qui est de la partie multiplier par C, il vaut mieu multiplier le nombre de base par le carré de C, et ensuite extraire la racine, autrement il y a de grandes chance de perdre des chiffres.

car si sqrt(10)=3.16, en entier, ça ne fait que 3. donc 3*100 donne 300, et non 316.
tandis que isqrt(10*(100²))=316 directement

bien evidement, il faut aussi eviter de depasser la capacité avant l'extraction de la racine.
il est aussi possible de travailler en virgule fixe pour conserver un certain nombre de chiffres significatifs après la virgule, tout en ne travaillant que sur des entiers.

[pseudocode]

Comme le dit edfed, le plus simple c'est de d'abord calculer "n*C²". Puis ensuite d'utiliser un algo de racine carré entière (Fast integer square root).

[mach1]

Désolé d'avoir mis tant de temps à répondre.

pour ce qui est de la partie multiplier par C, il vaut mieu multiplier le nombre de base par le carré de C, et ensuite extraire la racine

Ça me semble être une très bonne idée à laquelle je n'avais pas du tout pensé.
J'avais bien remarqué qu'il existait la fonction isqrt mais je ne voyais pas à quoi elle pouvait me servir.

Pour ce qui est de l'implémentation de isqrt j'ai visité les liens proposés. J'ai essayé de me remettre un peu à l'assembleur, mais en ayant des connaissances très limitées je ne suis pas arrivé à comprendre quel algo était utilisé. Je me suis notamment penché sur ce code contenant à priori le moins d'instructions "exotiques" (SSE ...):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
isqrt_eax:
        xor     ebx,ebx
        xor     edx,edx
        bsr     edi,eax
        setnz   cl
        sub     cl,1
        shr     edi,cl
        and     edi,-2
        lea     ecx,[edi+2]
        ror     eax,cl
.digit: shld    ebx,eax,2
        lea     ecx,[edx*4+1]
        cmp     ebx,ecx
        cmc
        sbb     esi,esi
        adc     edx,edx
        and     ecx,esi
        sub     ebx,ecx
        shl     eax,2
        sub     edi,2
        jns     .digit
        mov     eax,edx
        ret

Sinon j'ai trouvé une version de isqrt en python dont je me suis servi pour coder isqrt en c:
http://code.activestate.com/recipes/...root-function/.

En conclusion, le problème est résolu mais par curoisité j'aimerais avoir si possible quelques infos sur le code asm ci-dessus.

[edfed]

c'est en gros la meme chose que le tiens:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def isqrt(x):
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

mais en version optimisée, avec pas mal de magie binaire (comprendre par là, shift left 1 = *2, cmc, sbb, etc...
en apparence, il y a plus de code, mais en vitesse et en occupation memoire, c'est presque un record.

l'idée est d'estimer d'abord un ordre de grandeur en testant le bit le plus haut (bsr edi,eax), ensuite, recuperer le numero de ce bit permet de connaitre la puissance de deux la plus proche de notre nombre X.
ensuite, on divise par deux cette puissance, pour connaitre la puissance de 2 la plus proche de notre racine de X.

puis on procede par estimation successives, tout en verifiant que notre racine correspond à notre nombre.