Bonjour
Peut-on construire un ensemble de nombres rationnels dont le cosinus et le sinus soient rationnels ?
Applications : rotations en arithmétique rationnelle, sans perte de précision numérique
Dit autrement: je cherche toutes les matrices de rotation dans l'espace 3D à coefficients rationnels
Bonjour,
Regardez du côté des triplets pythagoriciens.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Bonjour,Envoyé par WizardOfLinn
Si vous imposez des conditions aussi sévères qu'un angle également rationnel, vous ne trouverais pas beaucoup de solutions.
Pour des matrices de rotation rationnelles, il vous suffit que sin et cos soient rationnels et dans ce cas vous avez beaucoup de solutions : l'ensemble de tous les couples
S2 + C2 = 1
Comprendre c'est être capable de faire.
Merci pour ces indications.
Après réflexion, je dois pouvoir relacher la contrainte "angle rationnel". Après tout, si le sinus et cosinus sont rationnels, la valeur de l'angle est aussi bien représentée de façon exacte par 4 entiers, sans approximation dans la mémoire d'un ordinateur, même si ce quadruplet n'est pas un rationnel. Par contre, il me semble que l'addition de deux angles n'est plus une opération exacte (?).
Sinon, j'accepte aussi bien des valeurs de la forme a = PI*x, x rationnel, peu importe l'unité des angles.
Bon, je suis preneur de toute idée sur le sujet.
Je pense que l'angle rationnel ne sert à rien dan le calcul, l'angle est totalement représenté par le couple (sin,cos) et l'addition se programme comme une opération simple sur les doublets :
(s1,c1) + ( s2,c2) = (s1c2 + s2c1, c1c2 - s1s2)
C'est bien ça, je cesse de jouer et je vous laisse faire pour les autre opérations.
Comprendre c'est être capable de faire.
Bonjour,
Est-ce je peux être indiscret de vous demander le but.
Il est vrai que les formules de transformation mettent en oeuvre des lignes trigo, sin et cos, mais en réalité ce l'est vrai que sur le papier. Autrement dit, dans la pratique, il est rare de calculer un sinus ou un cosinus.
Par ailleurs, j'ai fait des tests de rapidité de calcul, en tout cas pour du C, ça ne vaut pas le coup d'essayer de chercher mieux.
Concernant le précision elle-même, le nombre de chiffres significatifs est 15, avec un quotient de 2 entiers, on ne pourrait pas avoir mieux que 9, je pense.
phys4 : j'aurais pu réfléchir 3 minutes de plus avant d'écrire. Une simple formule de trigo. Honte sur moi.
Dlzlogic : les problèmes d'arrondis en géométrie algorithmiques sont une plaie. C'est pour ça que les logiciels de CAO mécaniques continuent à planter sur certaines opérations, comme les opérations booléennes entre solides (sauf dans le cas trivial de primitives facettisées). Ce ne sont pas vraiment des bugs, plutôt un problème de maths, lié à la représentation des nombres.
Pour ne pas avoir de problème, il suffirait que les opérations arithmétiques soient exactes, en précision infinie.
Je suis en train de développer un petit modeleur exact n'utilisant que des rationnels, pour l'instant, mais les rotations me posent quelques problèmes.
On n'explicite évidemment jamais les rationnels par leur approximation en virgule flottante, le but est justement de ne jamais utiliser les nombres en virgule flottante disponibles dans les langages et processeurs usuels. Par contre, j'utilise des entiers aussi longs que nécessaire pour construire les rationnels sans perte de précision dans l'enchainement des opérations.
Dernière modification par WizardOfLinn ; 14/12/2011 à 15h46.
Bon, je me doutais bien d'un truc de ce genre.
Après avoir très longuement réfléchi au problème, voilà comment je procède.
Les valeurs X,Y (et Z si on veut) sont en long int (32 bits, 9 chiffres significatifs).
J'ai une unité de base, par exemple le millimètre.
Quoi qu'on fasse, un flottant ne sera jamais un réel. Donc, toute comparaison entre 2 flottants doit être faite avec une certaine tolérance, dans mon cas 3 unités de base.
Toute opération qui contient au moins une division est susceptible de générer un nombre décimal. Donc à un instant donné, le dernier chiffre a (en gros) une chance sur deux d'être faux. Exécutez la séquence suivante pour vous en persuader :
A = 3./7.;
si (3./7. == A) print("BON");
else print("FAUX");
Je sais bien (ou je suppose) que ce type de notion est assez peu connu.
Le bug se passe, par exemple, de la façon suivante.
1- on calcule un point A intersection de 2 droites D1 et D2
2- on calcule un point B intersection de 2 droites D1 et D3.
3- le test "AB parallèle à D1" ou A ou B "appartient à D1" est en général faux, d'où bug.
Dans cet exemple, si on fait tous les calculs en arithmétique rationnelle, l'intersection de deux droites est connue de façon exacte, sans approximation, et il n'est pas nécessaire de tolérancer les tests (avec des valeurs de tolérance souvent un peu arbitraires).
Dans ce cas, les algorithmes géométriques ne dépendent pas de particularités de représentation des nombres.
Etes-vous sûr de cela ? Avez-vous fait le petit test que je vous ai indiqué ? Si les valeurs de tolérance étaient arbitraires et/ou si cette méthode ne donnait pas les résultats voulus, croyez-vous que je vous l'aurais indiquée et ne pensez-vous pas que je m'en serais aperçu depuis que je l'utilise ?
Pour donner un exemple, imaginons que la droite D1 soit définie par 2 points C et D dont les ordonnées diffèrent de 1 (c'est à dire une unité arithmétique). si les points A et B sont proches de C, ils auront tous les deux la même ordonnée que C, donc AB est parallèle à l'axe des X et non parallèles à D1.
Vos nouvelles conceptions de la géométrie essaient de réaliser le rêve de Pythagore : représenter le monde par des nombres exacts.
Cela ira jusqu'à un certain point, les intersections de droites dont les coefficients sont des rationnels seront des coordonnées rationnelles qui seront, en effet sur la droite sans ambigüité.
Seulement, il ne sera pas possible de représenter toutes les droites possibles. Le rêve s’arrêtera lorsque vous aurez une solution contenant une racine carrée. C'est aussi ce qui arrivé à Pythagore.
Bon amusement.
Comprendre c'est être capable de faire.
dzlogic: je ne parlais pas du tolérancement de ce test particulier, mais du cas général. Vous avez une tolérance qui marche bien sur ce test là (mais l'avez vous vraiment démontré sur tous les cas possibles, rigoureusement, ou est-ce simplement une constatation empirique?), mais ce ne sera pas nécessairement la même pour d'autres problèmes géométriques (point sur cercle, appartenance d'un point à un domaine, etc.).
De toute façon, ce type de tolérancement ne résoud pas mes problèmes de précision et stabilité des algorithmes.
A ma connaissance, la méthode propre pour utiliser les tolérances est l'arithmétique d'intervalles : chaque nombre est représenté par un intervalle, et on définit addition, multiplication, etc. sur des intervalles.
phys4:
Ma conception n'a rien de nouvelle. Il s'agit de problèmes très pratiques, qui deviennent critiques pour le développement de logiciels fiables, et sont donc des sujets de recherche assez actifs.
A part ça, on sait très bien représenter les racines carrés de façon exacte dans la mémoire d'un ordinateur, sans aucune approximation : par une suite finie d'entiers ou de rationnels coefficients d'un polynôme dont le nombre est racine et un encadrement. A partir de là, on redéfinit les opérations arithmétiques élémentaires.
Bonjour,
Concernant cette méthode de tolérance, d'une part, c'est la méthode utilisée par un certain logiciel de cao-dao que je connais. Concernant mon expérience personnelle, je suppose que depuis une dizaine d'années je me serais aperçu si ce nl'était pas la bonne méthode. Vos problèmes de précisions sont le mêmes pour tout le monde, mais, comme le dit Phys, bon courage.
Pour la représentation de racine(2) dans la mémoire d'un ordinateur, si la méthode n'est pas secrète, pouvez-vous nous la donner.
Je ne dis pas que c'est une mauvaise méthode. Ca dépend de l'application et du degré de fiabilité recherché.
Pour de l'affichage, on se satisfait très bien des calculs en virgule flottante comme le fait OpenGL.
Pour de la CAO-DAO, on fait déjà un peu plus attention, mais des schémas de tolérancement assez simple peuvent être suffisants, si on accepte que certaines opérations échouent une fois sur 100.
Ce n'est pas parce que certains méthodes sont couramment utilisées dans les logiciels de CAO qu'elles sont bien comprises et mathématiquement rigoureuses.
Pour mon application, je cherche un niveau de fiabilité supérieur, quitte à sacrifier la vitesse.
Et pour revenir à mon problème initial, j'ai besoin d'implémenter les rotations dans l'espace sans perte de précision. Je cherche donc toutes les matrices de transformation à coefficients rationnels, parce que je dispose de rationnels formés d'entiers non limités
Pour répondre à votre dernière question :
Racine(2) = (1, 0, -2, 1, 2)
C'est l'unique solution de l'équation x²-2=0, comprise entre 1 et 2.
Racine(2) est donc représenté de façon exacte par 5 entiers, sans approximation dans la mémoire d'un ordinateur.
Après, il faut réapprendre à faire des additions, multiplications, etc. avec ce type de représentation.
Dernière modification par WizardOfLinn ; 15/12/2011 à 13h12.
Je vous ai donné la réponse au message #2.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
J'ai commencé à chercher de côté hier, merci. Effectivement, c'est la piste la plus naturelle.
