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

J'ai inventé hier soir un algorithme de calcul de racines carrées très rapide.
Il ne travaille que sur des entiers, à aucun moment il ne fait appel aux floats.
Le résultat est donc la valeur tronquée de la racine. Par exemple R(2562) = 50.616 -> 50.
Il n'utilise que de l'algorithmie pure : pas de fonction du TIOS ou autre...

En TI-Basic :
- racine de 320, 0.25 seconde !
- racine de 1466234, 0.5 seconde !!!
... en TI-Basic !

J'insiste sur le fait que le résuiltat est hyper précis : il est juste tronqué à l'unité.
Voilà, je voudrais savoir si y'a plus rapide ou pas.
[edit]Edité par Thibaut le 28-06-2001 à 15:46:10[/edit]

Tu peut nous monter ca ?

ouaip st!

hyper precis.. ca serai mieux un arondi..

Je peux arrondir, c'est pas ça qui va ralentir, no problem

>> Tu peux nous monter ca ?
Ben il est plus rapide que l'algo de Newton, c'est flagrant surtout sur les grands nombres... et je préfère garder secret cette merveille (je vais breveter mon algo )...
Je l'ai conçu de façon à travailler au maximum avec des puissances de 2, voilà pourquoi il est ultra-rapide : la plupart des calculs de l'algo se résument à des décalages.

En fait je vais l'implémenter dans un prog ASM, mais avant j'ai quelques trucs à optimiser. On verra ce que ça donne.

Un petit défi ?
Allez : écrivez la routine d'extraction la plus rapide possible Je pourrais me situer, et je promet que si la mienne gagne, je balance la source.

lol.. en ti basic... avec aucune fonction tios...

je vais voir ca...

<< En fait je vais l'implémenter dans un prog ASM, mais avant j'ai quelques trucs à optimiser. On verra ce que ça donne >>

Je décode : je vais faire quelques optimisations, puis je le traduit en ASM. Le défi consiste donc à programmer une routine d'extraction de racines carrées en ASM.

C'est pas si facile que ça...
je dois avoir mon prog basic quelque part sur internet...
Ah voilà!
http://sirryl.multimania.com/beta/sqrt.zip
[edit]Edité par Paxal le 28-06-2001 à 19:55:22[/edit]

Sur des Words, ca devrait suffir.
Moi mon algo il est en sqrt(n).
On pourrait l'améliorer en ln(n)/ln(100)*sqrt(100) si mes souvenirs sont exacts.

ola, moi je me mouille pas la dedans !

Ca y est j'ai passé ma soirée à optimiser, et je l'ai codé en ASM
Il travaille sur des double-mots.

Je l'ai employé comme MACRO dans une boucle de test, et j'obtient... 5958 extractions / seconde !
Qui dit mieux ?

PS : c'est sans désactiver les interruptions.

bon, je crois qu'il va gagner, alors balance

T'utilises quel alforithme? La soustraction de nombres impairs?

Absolument pas
Technique maison plus rapide que l'algo de Newton (l'algo de N. c'est R= (R+N/R)/2 récursivement)

Ils signifient quoi vos "1+ln(n)" ??? C'est le nombre d'itérations maximum effectuées par la fonction pour trouver la racine ?

Un algorithme O(1+ln(n)) (ou "en 1+ln(n)") signifie que le temps pris pour le calcul de la racine carrée de n est proportionnel à 1+ln(n). Cela ne veut pas dire forcément qu'il sera plus rapide qu'un algorithme O(n) (tout dépend du facteur de proportionnalité), mais on peut dire à 100% qu'il le sera pour des nombres suffisament grands (en les supposant représentables par la machine) à cause des propriétés mathématiques des fonctions logarithmes.

On peut aussi calculer le facteur de proportionnalité en cycles par unité ou le mesurer en secondes par unité pour ainsi définir de manière plus précise la vitesse de l'algorithme.
[edit]Edité par Kevin Kofler le 29-06-2001 à 18:34:47[/edit]

Pour des algorithmes rapides, je sais qu'un algorithme rapide en virgule flottante est de ramener le nombre à un nombre compris entre 0,5 et 1 (en divisant et multipliant par des puissances de 2) et d'utiliser une approximation polynomiale (par exemple un développement limité ou une régression), suivie de l'algorithme de Newton. Le problème est ici le fait que TI utilise des nombres à virgule flottante BCD, moins adaptés à la multiplication et à la division par 2 que les nombres à virgule flottante IEEE.

Kevin arrive et tout s'éclaire.

Tu as des algos pour les racines ?

Thibault: tu crois que la division par R est plus rapide que ma méthode?

Je n'en sait rien, mais ce n'est pas cet algo que j'utilise...

Ah oui, pardon (je n'avait lu qu'à moitié )

Alors, personne ne veut coder un algo en ASM pour se mesurer au maître-des-végétaux-sous-terrains-pas-ronds ?

Je te code ça ce soir

OUEEEEééé

ATTENTION



- Le nombre entré est entier et le résultat doit être entier,
- L'arrondit (le seul possible est logiquement à l'unité) est autorisé, mais pas obligatoire,
- L'entrée est donnée dans d0 sur 32 bits,
- Le résultat est récupéré dans d1 sur 16 bits,
- Aucun registre à part d1 ne doit être modifié au retour de la fonction (donc faites péter les movem),
- C'est à coder comme fonction, donc on commence par un label et on finit par un rts,
- Vous devez mesurer le temps d'exécution toutes interruptions activées, mais sans appuyer sur les touches (je ne suis pas trop méchant).

Je vais de mon côté transformer ma macro en fonction, encore optimiser un peu, et remesurer sa vitesse avec ces règles.

Vous devez mesurer le temps d'exécution toutes interruptions activées. Ca serait quand même beaucoup plus precis si le bench se faisez sans ints (surtout qu'elles changent parfois d'une version d'AMS à un autre).

Bah on teste l'algo sur kels nombres?

for (a=0; a<1500; a++) square_root (rand (0xFFFFFFFF)); ?

Bah non, le rand va me prendre du temps...

bah si on prend tous le même prog qui test l'algo (donc le même rand), c bon.

Le rand de util ca va?