Les végétaux sous-terrains pas ronds - Page 2

Je propose même qu'on compte le nombre de cycles pour plusieurs valeurs (utiliser VTI c plus simple qu'à la main )

POUR MESURER L'EFFICACITE DE NOS ALGOS, NOUS ALLONS UTILISER CE FICHIER

J'ai encore optimisé mon algo hier soir. Il extrait désormais... 9039 racines par secondes !!!!!!

Alors Paxal ta fonction ??

Bah ellle fonctionne en Basic mais pas en Asm, et ca m'étonnerais qu'elle soit plus rapide...
En fait c'est surtout que j'ai pas que ça à fouttre, mais attends qq jours...

int sqrt(int a)
{
register int Un, Un1;
Un1 = a / 4;
do
{
Un = Un1;
Un1 = (Un + (a / Un)) / 2;
} while (Un != Un1);
return Un;
}

[edit]Edité par segaman le 03-07-2001 à 07:15:35[/edit]

>> Je pense que la vitesse sous VTI doit être la référence (pas de pb de HW, et surtt pas de différence piles faibles/piles neuves)

NON, suivant la puissance de nos ordis et le nombre de progs en tâche de fond ça peut changer (chez moi le temps change beaucoup d'une exécution à l'autre...). RETESTE sur ta calto.

>>est-ce qu'on a le droit d'optimiser pour que la plage de valeur 1..131072 soit traitée plus rapidement ?

NON, c'est un algo "universel".

Continuons de tester avec les bsr.s pour calculer le temps d'exécution de la fontction et non le temps des sauts...


Si tu obtient moins d' 1mn 25s on-calc, alors bravo

Pardon Pollux, je voulais dire 2mn 25.

Tu veux bien balancer ta source (ou comme moi, tu peux attendre la désignation du vainqueur) ?

Je pense avoir un putain d'algo pour faire ça en ASM mais j'ai pas trop le temps de le programmer. (Je suis en Math Spé et en ce moment c'est les oraux... Vacances le 22 juillet...)
Est-ce que ceux qui code pourraient dire combien d'opérations élémentaires ils font (Divisions, multiplications, additions, décalages, comparaisons...) dans leur algo!!!

Aucune division
1 multiplication
1 addition
3 comparaisons
4 décalages de bits
[edit]Edité par Thibaut le 02-07-2001 à 22:04:29[/edit]

oulà! moi 8 comparaisons, 4 décalges, plein de soustractions, et d'addition!

Dans des itérations ?

Tu balance ta source (en C ça sera plus clair si c'est possible) ?

Ma source en basic est sur la page 1

2 code source pour trouver une racine entiere:

-------- C ANSI
long long_sqrt( long v )
{
int i;
unsigned long result, tmp;
unsigned long low, high;
if (v <= 1L) return( (unsigned) v );
low = v;
high = 0L;
result = 0;
for (i = 0; i < 16; i++)
{
result += result;
high = (high << 2) | ((low >>30) & 0x3);
low <<= 2;
tmp = result + result + 1;
if (high >= tmp)
{
result++;
high -= tmp;
}
}
if (v - (result * result) >= (result - 1))
result++;
return result;
}

-------- ASM x86

sqrt PROC NEAR ; ax <=3D sqrt (eax) , explose ebx, ecx, edx
mov ebx,eax
mov ecx,40000000h ; ecx =3D 2^32 shr 2
mov edx,ecx
add edx,eax
shr eax,1
cmp edx,ebx
ja over1
sub ebx,edx
or eax,ecx
over1:
REPT 15
LOCAL @over
shr ecx,2
mov edx,ecx
add edx,eax
shr eax,1
cmp edx,ebx
ja @over
sub ebx,edx
or eax,ecx
@over:
ENDM
ret
sqrt ENDP

-----------

alors thibault on fait moin le malin hein !

et je parie que les 2 sont plus rapide que le prog de thibault.

C'est possible.

thibault regarde ce code aussi..
trouvé par hazard ici : http://www.azillionmonkeys.com/qed/sqroot.html

static unsigned fred_sqrt(unsigned long x)
{
 static const unsigned char sqq_table[] = {
 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57,
 59, 61, 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83,
 84, 86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102,
 103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118,
 119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132,
 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145,
 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, 156, 157,
 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178,
 179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188,
 189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197,
 198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205, 206, 206,
 207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213, 214, 214, 215,
 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223,
 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231,
 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246,
 246, 247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253,
 253, 254, 254, 255
 }; unsigned long xn; if (x >= 0x10000)
 if (x >= 0x1000000)
 if (x >= 0x10000000)
 if (x >= 0x40000000) {
 if (x >= 65535UL*65535UL)
 return 65535;
 xn = sqq_table[x>>24] << 8;
 } else
 xn = sqq_table[x>>22] << 7;
 else
 if (x >= 0x4000000)
 xn = sqq_table[x>>20] << 6;
 else
 xn = sqq_table[x>>18] << 5;
 else {
 if (x >= 0x100000)
 if (x >= 0x400000)
 xn = sqq_table[x>>16] << 4;
 else
 xn = sqq_table[x>>14] << 3;
 else
 if (x >= 0x40000)
 xn = sqq_table[x>>12] << 2;
 else
 xn = sqq_table[x>>10] << 1; goto nr1;
 }
 else
 if (x >= 0x100) {
 if (x >= 0x1000)
 if (x >= 0x4000)
 xn = (sqq_table[x>>8] >> 0) + 1;
 else
 xn = (sqq_table[x>>6] >> 1) + 1;
 else
 if (x >= 0x400)
 xn = (sqq_table[x>>4] >> 2) + 1;
 else
 xn = (sqq_table[x>>2] >> 3) + 1; goto adj;
 } else
 return sqq_table[x] >> 4; xn = (xn + 1 + x / xn) / 2;
nr1:
 xn = (xn + 1 + x / xn) / 2;
adj: if (xn * xn > x)
 xn--; return xn;
}

----

Ce défi de racine carré ne m'interresse pas particulièrement, je souhaitait simplement montrer a thibault qu'il ne faut jamais croire avoir réalisé le code le plus rapide pour un probleme. Car tu te trompe A TOUS LES COUPS. la preuve ici : 4 codes qui font mieux(inclus celui de pollux)..

Et oui

test !

Non ils ont raison.
Ca se "voit à l'oeil" qu'ils ont plus rapides