racine carrée - Page 1

Je cherche une fonction racine carré sur des entiers qui soit assez rapide...y a pas une lib qui a ca?
Ou alrs une fonction asm a incorporer dans tigcc?
Merci d'avance...
(et me dites pad d'utilise sqrt....jamais vu un truc aussi lent )

Voici ma fonction, qui a déjà servit à beaucoup de gens

unsigned short SquareThib(unsigned long n)
{
  unsigned short m, p, i, s;
  unsigned long q;
  
  if (!n) return 0;
  
  q= 1;
  s= 1;
  do
  {
    s+= s;
    q<<= 2;
  }
  while (q<=n);
  
  i= s >> 1;
  m= 0;
  
  do
  {
    p= m;
    m= (i + s) >> 1;
    if (m*m > n) s= m;
            else i= m;
  }
  while (m!=p);
  
  return m;
}

[edit]Edité par Thibaut le 17-03-2002 à 12:34:31[/edit]

Merci!
Tu connais sa rapidité?
Sinon g vu que tu avais aussi fait une version asm, il vaut mieux que j' implante celle-la?

C'est long, cette routine. Que dirais-tu de:
unsigned short SquareKK(unsigned long n) {
unsigned short i;
for(i=0;(unsigned long)i*i<n;i++);
return i; }
? C'est plus lent (peut-être même beaucoup plus lent, à voir), et ça arrondit toujours par excès, mais c'est bien plus court (et donnera du code assembleur bien plus petit)!
Et (unsigned long)i*i n'est pas une erreur, il suffit de transtyper un des i en un unsigned long pour que la multiplication soit effectuée dans un unsigned long.
[edit]Edité par Kevin Kofler le 16-03-2002 à 23:55:17[/edit]

D'ailleurs, j'ai peur que Thibaut viendra encore m'insulter parce que je préfère l'optimisation en place à l'optimisation en vitesse...

arf, ça depend de ce que tu veux faire et tu le sais bien :-)
Ici visiblement il veut qq chose de très RAPIDE ;p
(parce que pour les cas std, sqroot est parfait :-))
[edit]Edité par Pen^2 le 17-03-2002 à 02:01:15[/edit]

ps : attention, tu as fait une pitite faute de temps : <<j'ai peur que Thibaut viendra >>
prefere >>j'ai peur que Thibaut [ne] vienne

Effectivement, j'ai besoin de quelque chose de rapide :-)
(au moins 5000 extractions par secondes)
J'ai teste la routine de Thibaut, et elle est plutot rapide! Je pense pas qu'on peut faire mieux en C

Ma routine est très largement plus rapide que celle de Kevin. Son algorithme est complètement bourrin, aucune élégance

La version ASM de ma fonction est un peu plus rapide, elle traîne quelque part dans deux-trois topics de la section ASM du forum.

Mon algo est une recherche par dichotomie.

(Ma fonction extrait 9039 racines par seconde si je me souviens bien)

Tu parles de la version C ou asm?
Si c'est la version C =>
Largement ce dont j'ai besoin!

ASM. Pour la version C je dirais autour de 6-7000

Au fait, "Je pense pas qu'on peut faire mieux en C" : si, il y a des implémentations plus performantes, mais faut voir la place qu'elles bouffent...

6000 c'est bon aussi!
J'ai pas besoin de plus pour ce que veux faire...

Attention je viens de m'apercevoir d'une erreur dans mon code, j'avais oublié un else !
C'est corigé.

Euh, je voudrais pas t'alarmer, mais je trouve des trucs bizzare avec ta fonction!
Enfin, c peut-etr moi qui me plante dans son utilisation!
Voila ma source :

unsigned short SquareThib(unsigned long);
// Main Function
void _main(void)
{
unsigned long lo=0;
unsigned short sh=0;
lo=289;
sh=SquareThib(lo);
clrscr();
printf("%un",sh);
ngetchx();
}

unsigned short SquareThib(unsigned long n)
{
unsigned short m, p, i, s;
unsigned long q;

if (!n) return 0;

q= 1;
s= 1;
do
{
s+= s;
q<<= 2;
}
while (q<=n);

i= s >> 1;
m= 0;

do
{
p= m;
m= (i + s) >> 1;
if (m*m > n) s= m;
i= m;
}
while (m!=p);

return m;
}

Alors... :
pour racine de 289, je trouve 24 or 24^2=576
pour racine de 90000, je trouve 511. or 511^2=261121
====>???

Oups! j'avais pu vu ton message!
Je v voir ca
----------------------------------------
Euh...Ca marche mais qu'avec des nombres <65536!!!
Y a moyen d'arranger ca?

[edit]Edité par Pegasus le 17-03-2002 à 13:51:41[/edit]

Bon le mieux c'est que tu prennes la version ASM, il doit y avoir un problème de transtypage implicite quelque part. La version ASM marche très bien normalement
post.php?id=1,1889
[edit]Edité par Thibaut le 17-03-2002 à 14:02:05[/edit]

Pk, le temps de comprendre comment mixer asm et C et je reviens

Si tu n'y arrives pas, je te ferais l'intégration en in-line

:-)
Pour l'instant ca va, G créé le fichier A68k avec au debut
section ".data"
xdef SquareThib
puis ta fonction...
Maintenant je cherche comment passer et recuperer les parametres....
pour mettre les parametre dans d0, faut pas faire un truc du style
asm("move.l pointeur_sur_variable,d0")? (ou quelque chose comme ca, j'y connais pas grand chose en asm...)

Non, déjà, tu prends la routine et tu remplaces partout d0 par d1 et d1 par d0, parce que la valeur de retour doit être dans d0. Ensuite tu déclares:
unsigned short SquareThib(unsigned long n asm("d1"));

Allez je te le fais :

SquareThib:
	move.l		4(a7),d0
	beq.s		Resultat0
	movem.l		d2-d5,-(a7)
	cmp.l		#65536,d0
	bhi.s		Else1ST
	moveq		#1,d1
	moveq		#1,d4
	bra.s		Repeat1ST
Else1ST:
	moveq		#1,d1
	swap		d1
	move.l		#256,d4
Repeat1ST:
	add.l		d4,d4
	lsl.l		#2,d1
	cmp.l		d0,d1
	bls.s		Repeat1ST
	move.l		d4,d3
	lsr.l		#1,d3
	moveq		#0,d1
Repeat2ST:
	move.l		d1,d2
	move.l		d3,d1
	add.l		d4,d1
	lsr.l		#1,d1
	move.l		d1,d5
	mulu		d5,d5
	cmp.l		d0,d5
	bls.s		Else2ST
	move.l		d1,d4
	cmp.l		d1,d2
	bne.s		Repeat2ST
	movem.l		(a7)+,d2-d5
	move.l		d1,d0
	rts
Else2ST:
	move.l		d1,d3
	cmp.l		d1,d2
	bne.s		Repeat2ST
	movem.l		(a7)+,d2-d5
	move.l		d1,d0
	rts
Resultat0:
	moveq		#0,d0
	rts

On peut très légèrement optimiser (pour ne pas avoir à faire move.l d1,d0), mais tu n'en a pas besoin je crois

Le prototype est : unsigned short SquareThib(unsigned long n);
[edit]Edité par Thibaut le 17-03-2002 à 14:46:13[/edit]

Le passage par registres, c'est pour les chiens?
Et puis, tout ce que tu aurais dû faire pour ne pas avoir à mettre move.l d1,d0 aurait été échanger d0 et d1 partout dans ton code! Et puis encore, pourquoi move.l si c'est un unsigned short?

Pareceque c'est aussi rapide. Je connais un minimum l'ASM, Kevin

Le passage par registre n'est pas nécessaire. Je préfère garder la convention C de base, c'est mon choix. Si Pegasus veux utiliser le passage par registres il le fera.

pkoi ne pas utiliser une table ?

Bon, voilà (le code est de Thibaut, j'ai juste échangé les registres d0 et d1):

	section	".data"
	xdef	SquareThib
SquareThib:
	tst.l		d1
	beq.s		Resultat0
	movem.l		d2-d5,-(a7)
	cmp.l		#65536,d1
	bhi.s		Else1ST
	moveq		#1,d0
	moveq		#1,d4
	bra.s		Repeat1ST
Else1ST:
	moveq		#1,d0
	swap		d0
	move.l		#256,d4
Repeat1ST:
	add.l		d4,d4
	lsl.l		#2,d0
	cmp.l		d1,d0
	bls.s		Repeat1ST
	move.l		d4,d3
	lsr.l		#1,d3
	moveq		#0,d0
Repeat2ST:
	move.l		d0,d2
	move.l		d3,d0
	add.l		d4,d0
	lsr.l		#1,d0
	move.l		d0,d5
	mulu		d5,d5
	cmp.l		d1,d5
	bls.s		Else2ST
	move.l		d0,d4
	cmp.l		d0,d2
	bne.s		Repeat2ST
	movem.l		(a7)+,d2-d5
	rts
Else2ST:
	move.l		d0,d3
	cmp.l		d0,d2
	bne.s		Repeat2ST
	movem.l		(a7)+,d2-d5
	rts
Resultat0:
	moveq		#0,d0
	rts

Prototype: unsigned short SquareThib(unsigned long n asm("d1"));
[edit]Edité par Kevin Kofler le 17-03-2002 à 14:54:30[/edit]

nEUrOne : il n'a pas besoin d'autant de vitesse, ça ne fera que gonfler la taille de son programme.

C'est vraiment une idée stupide d'utiliser une table! Taille de la table:
2*2^32=8589934592 octets
Il faut donc 13108 TI-92+ pour stocker cette table en mémoire archive.
Arrêtez de penser que les tables précalculées sont la solution à tout!
[edit]Edité par Kevin Kofler le 17-03-2002 à 15:01:19[/edit]

Et toi Kevin arrête de penser tout savoir. Tu vois il y a des gens aussi intelligents voir plus que toi qui ont trouvé des solutions pour calculer des racines carrées en s'aidant de tables de quelques ko seulement.
Il est évident qu'une table de 2*2^32 octets est irréalisable. Tu prend les gens pour des cons, c'est un de tes gros défauts
[edit]Edité par Thibaut le 17-03-2002 à 15:26:49[/edit]