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]
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

2

smile
Tu peut nous monter ca ?

3

ouaip st!

4

hyper precis.. ca serai mieux un arondi..
XLib v1.00 Powerrrrrrrrrrrrrrrrrrrr!

5

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

>> 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 tongue)...
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 smile Je pourrais me situer, et je promet que si la mienne gagne, je balance la source.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

6

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

je vais voir ca...
XLib v1.00 Powerrrrrrrrrrrrrrrrrrrr!

7

<< 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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

8

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]
Cours et tutos Asm: http://membres.lycos.fr/sirryl

9

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.
Cours et tutos Asm: http://membres.lycos.fr/sirryl

10

ola, moi je me mouille pas la dedans !tongue
:D

11

Ca y est j'ai passé ma soirée à optimiser, et je l'ai codé en ASM smile
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 ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

12

PS : c'est sans désactiver les interruptions.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

13

bon, je crois qu'il va gagner, alors balancegrin
In many respects the Yoshi is like a beautiful woman. A man can come so enamoured that he bestows on her all his time, his energy and his fortune.
- Fred whipple, 1960

*** Ne sous-estimez pas la puissance de la Marmotte ***
© Marmotte Team : LaMarmotte, sBibi, Vark & Sabrina

14

T'utilises quel alforithme? La soustraction de nombres impairs?
Cours et tutos Asm: http://membres.lycos.fr/sirryl

15

Absolument pas smile
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 ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

16

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]
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

17

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.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

18

smile Kevin arrive et tout s'éclaire.

Tu as des algos pour les racines ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

19

Thibault: tu crois que la division par R est plus rapide que ma méthode?
Cours et tutos Asm: http://membres.lycos.fr/sirryl

20

Je n'en sait rien, mais ce n'est pas cet algo que j'utilise...
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

21

Ah oui, pardon (je n'avait lu qu'à moitié smile)
Cours et tutos Asm: http://membres.lycos.fr/sirryl

22


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

sad sad
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

23

Je te code ça ce soir smile
Cours et tutos Asm: http://membres.lycos.fr/sirryl

24

OUEEEEééé smile

attention ATTENTION attention

Conventions (=REGLES) à respecter pour ce défit :


- 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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

25

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).

26

Bah on teste l'algo sur kels nombres?
Cours et tutos Asm: http://membres.lycos.fr/sirryl

27

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

28

Bah non, le rand va me prendre du temps...
Cours et tutos Asm: http://membres.lycos.fr/sirryl

29

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

30

Le rand de util ca va?
Cours et tutos Asm: http://membres.lycos.fr/sirryl