Fraction continue

bonuscad · le 12 février 2015

Bonjour,

Un petit problème que je cherche à résoudre pour faciliter la constitution de fichier de forme (qui seront compilé en SHX)

En effet les formes complexes peuvent être un peu casse-tête à dessiner car les vecteurs introduit sont généralement des valeur entières. Pour obtenir des vecteurs de longueur quelconque (nombre réel) if faut jouer sur des facteurs de division/multiplication.

C'est pour cela qu'une fonction qui me convertirait un réel en fraction me serait utile pour avoir une forme le plus fidèle à ce que je veux produire.

Dans l'absolu un dénominateur <= 255 est suffisant (c'est la valeur maxi autorisée dans une forme)

J'ai fouillé un peu sur google est j'ai trouvé un exemple en common-lisp. J'ai essayé de le convertir pour Autolisp de la manière suivante pour tester.

(defun cont-frac (n_i d_i k)
 (defun recurse (n)
   (defun next (n)
     (+ n 1)
   )
   (if (= n k) (/ (n_i k) (d_i k)) 
       (/ (n_i n) (+ (d_i n) (recurse (next n))))
   )
 )
 (recurse 1)
)
(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k)

mais en retour d'execution j'ai ceci:

Une erreur matérielle s'est produite ***
limite de la pile interne atteinte (simulation)

Je ne suis toujours pas un pro de la récursive :(

Si vous avez une idée ou une autre proposition.

PS: Le besoin n'est pas indispensable, aucune urgence, je continu de chercher tranquilement de mon coté.

Bon j'ai déjà trouvé mon erreur d'execution: il faut définir k avant de lancer (cont-frac). Plus la valeur est haute plus je me rapproche de la valeur (sans la mantisse) de phi (nombre d'or).

Modifié le 12 février 2015 par bonuscad

VDH-Bruno · le 13 février 2015

Bonjour,

Pour obtenir des vecteurs de longueur quelconque (nombre réel) if faut jouer sur des facteurs de division/multiplication.
C'est pour cela qu'une fonction qui me convertirait un réel en fraction me serait utile pour avoir une forme le plus fidèle à ce que je veux produire.
Dans l'absolu un dénominateur <= 255 est suffisant (c'est la valeur maxi autorisée dans une forme).

Ci-dessous mon interprétation de ton énoncé, suis-je dans le vrai? Car personnellement je n'ai jamais créé de fichier de forme, tout au plus je me souviens en déjà utilisé à l'époque de la R11 ou R12.

;;; Conversion d'un nombre réel en fraction
;;; fraction retourné sous forme d'une liste de 2 nombres entiers
;;; (numérateur dénominateur) avec un dénominateur <= 255
;;;
;;; Ex:  (reel2frac pi)  -> (355 113)
;;;      (reel2frac 0.5) -> (1 2)
;;;      (reel2frac 3)   -> (3 1)

(defun reel2frac (r / a d p q qmax frac recurse)
 (defun recurse (d p q)
   (cond ((< qmax (car q)) (list (cadr p) (cadr q))) ; sortie
         ((zerop d) (list (car p) (car q))) ; sortie
         (T
          (setq r (/ 1.0 d)
                a (fix r)
                d (- r a)
                p (cons (+ (* a (car p)) (cadr p)) p)
                q (cons (+ (* a (car q)) (cadr q)) q)
          )
          (recurse d p q)
         )
   )
 )
 ;; Initialisation (fraction ordre 0)
 (setq qmax 255 ; condition de sortie
       a    (fix r)
       d    (- r a)
       p    (list a)
       q    (list 1)
 )
 (mapcar 'float
         (if (zerop d)
           (list (car p) (car q))
           ;; Si partie décimal (fraction ordre 1)
           (setq r    (/ 1.0 d)
                 a    (fix r)
                 d    (- r a)
                 p    (cons (1+ (* a (car p))) p)
                 q    (cons a q)
                 frac (recurse d p q)
           )
         )
 )
)

Appliqué au nombre d'or (Phi) 1,618033.., une conversion de ce nombre irrationnel en une fraction réduite par approximation de 2 nombres entier (avec un dénomination <= 255), donnerait 377/233 soit 1.618025..

_$ (setq phi (/ (1+ (sqrt 5)) 2))
1.61803
_$ (setq frac (reel2frac(/ (1+ (sqrt 5)) 2)))
(377.0 233.0)
_$ (apply '/ frac)
1.61803

A+ Bruno

Edit: modifié dmax et 1 par qmax et 1.0

Modifié le 15 février 2015 par VDH-Bruno

VDH-Bruno · le 13 février 2015

Re,

Code après factorisation...

;;; Conversion d'un nombre réel en fraction réduite par approximation
;;; fraction représenté sous la forme d'une liste de 2 nombres entiers
;;; (numérateur dénominateur) avec un dénominateur <= 255
;;;
;;; Ex:  (reel2frac pi)  -> (355.0 113.0)
;;;      (reel2frac 0.5) -> (1.0 2.0)
;;;      (reel2frac 3)   -> (3.0 1.0)

(defun reel2frac (r / a qmax recurse)
 (defun recurse (d p q)
   (cond ((< qmax (car q)) (list (cadr p) (cadr q)))
  ((zerop d) (list (car p) (car q)))
  (T
   (setq r (/ 1.0 d)
	 a (fix r)
   )
   (recurse (- r a)
	    (cons (+ (* a (car p)) (cadr p)) p)
	    (cons (+ (* a (car q)) (cadr q)) q)
   )
  )
   )
 )
 (setq	qmax 255
a    (fix r)
 )
 (mapcar 'float (recurse (- r a) (list a 1) (list 1 0)))
)

Edit: modifié dmax et 1 par qmax et 1.0

Modifié le 15 février 2015 par VDH-Bruno

bonuscad · le 15 février 2015

Bonjour Bruno,

mon interprétation de ton énoncé, suis-je dans le vrai?

Excellent! Tout à fait ce que je cherchais à obtenir.

Pour ma part j'étais encore sur la consultation de page sous internet de sujet concernant les fractions réduites.

Ca m'a permis d'apprendre que les Egyptiens utilisaient essentiellement cette notation pour représenter des nombres réel, qu'Archimède s'en est servi pour définir Pi ainsi que Al-Kashi (cité déjà par notre ami (gile)).

Plus proche de nous on avait Euler, Lagrange, Finnobaci, Lambert etc... qui ont pousser les théorèmes d'équations mathématique; ces énoncés m'ont d'ailleurs embrouillé mon esprit.

Je retrouve bien dans ton algo la démarche préconisée que j'ai pu lire à droite ou à gauche et ton premier post m'a eclairée sur la façon concise du deuxième. Mais soyons honnête, je ne crois pas que j'aurais été capable de le mettre en place de façon si réduite que toi ou du moins en si peu de temps. Plus le temps passe, plus j'ai du mal à me concentrer pour visualiser ce genre d'algo dans mon esprit.

Je vais pouvoir faire des formes en notation égyptienne qui auront une belle définition, jusqu'à présent je m'aidais de la notation (rtos x 5 7) pour avoir une approximation acceptable, mais beaucoup plus approchée que précise.

Merci à toi grand scribe égyptien.

Je te souhaite un grand avenir dans la programmation, car de toute évidence tu as les qualités requises, tu es dans les pas d'un grand Kador de ce site.

PS: En apparté sur la fonction que j'avais traduite du common-lisp (et qui faisait plutôt l'inverse de ce que je souhaitais), je ne comprends pas pourquoi l'appel à la fonction se fait avec un argument défini en lambda.

En effet si (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 14) fonctionne

(cont-frac 1.0 1.0 14) ne fonctionne pas?

Je ne saisi pas la subtilité du (lambda (i) 1.0)

Edit:

Il y a juste une erreur de frappe dans la déclaration des variables (qui ne porte aucun préjudice à ta fonction) c'est qmax au lieu de dmax.

Modifié le 15 février 2015 par bonuscad

zebulon_ · le 15 février 2015

Bonjour,

ça vaut ce que ça vaut. C'est sans doute moins précis (le 100ème), mais comme je suis une bille en récursion je vous propose ceci

(defun r2f (N / PREC PGCD)
 (setq PREC 100)
 (setq N (fix (* N PREC)))
 (setq PGCD (float (gcd N PREC)))
 (list (/ N PGCD) (/ PREC PGCD))
)

En même temps, je n'ai jamais eu l'occasion d'utiliser la fonction gcd. Voilà, c'est chose faite.

Amicalement

Vincent

(gile) · le 15 février 2015

comme je suis une bille en récursion

La même avec while :

(defun float2frac (x / i n d r)
 (setq	i (fix x)
n (list i 1)
d (list 1 0)
 )
 (while (not r)
   (cond
     ((< 255 (car d))
      (setq r (list (cadr n) (cadr d)))
     )
     ((zerop x)
      (setq r (list (car n) (car d)))
     )
     (T
      (setq x (/ 1. x)
     i (fix x)
     x (- x i)
     n (cons (+ (* i (car n)) (cadr n)) n)
     d (cons (+ (* i (car d)) (cadr d)) d)
      )
     )
   )
 )
 r
)

VDH-Bruno · le 15 février 2015

Bonsoir,

Je venais faire un petit tour, pour donner la version itérative, je vois que (gile) m’as précédé, au passage bien vu le réel 1. dans la division, c’est une bonne précaution :) .

PS: En apparté sur la fonction que j'avais traduite du common-lisp (et qui faisait plutôt l'inverse de ce que je souhaitais), je ne comprends pas pourquoi l'appel à la fonction se fait avec un argument défini en lambda.
En effet si (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 14) fonctionne
(cont-frac 1.0 1.0 14) ne fonctionne pas?
Je ne saisi pas la subtilité du (lambda (i) 1.0)

Un petit rappel http://fr.wikipedia.org/wiki/Nombre_d'or (rubrique fraction continu). L’approche de sa valeur réel se fait au moyen de rapport sur 1. Si personnellement la fonction aurait pu être écrite autrement, l’énoncé du problème obligeait l’emploie de lambda (l'esprit étant de définir une fonction polyvalente).

(cont-frac (lambda (i) 1.0) (lambda (i) 1.0) fonctionne à cause des expressions (n_i k) et (d_i k) que l'on retrouve dans le corps de la fonction, avec n_i et d_i ayant la valeur (lambda (i) 1.0)

Donc quelque soit K on à ((lambda (i) 1.0) k),soit une fonction et un argument qui retourne 1.

Maintenant si on passe le nombre 1 à la place d’une fonction, tu as l’erreur d’argument, il te faut une valeur fonctionnelle…

Pour l'exemple l'approximation de la partie décimal de phi, sans les fonctions lambda (un cont-frac allégé):

(defun phi-1 (k)
 (if (= 1 k)
   1
   (/ 1. (+ 1 (phi-1 (1- k))))
 )
)

A + Bruno

Ps : Merci pour le dmax, c’est un oubli pas une erreur de frappe :rolleyes: , j’avais au départ commencé à coder n et d (numérateur et dénominateur), pour finalement codé p et q (produit et quotient) pour être dans les notations plus proche des formules.

bonuscad · le 16 février 2015

Bonjour,

fonctionne à cause des expressions (n_i k) et (d_i k) que l'on retrouve dans le corps de la fonction

Arff!

Maintenant que tu le souligne, j'avais mal interpreté ma lecture rapide de (n_i k) (ainsi que de (n_i n) d'ailleurs)

Tout s'explique, merci.

Un problème avec la fonction itérative de (gile)!

Le numérateur (ou produit) n'est pas bon. Le plus rigolo est que si j'évalue la fraction, la mantisse est le double de celle du réel introduit mais les décimales sont bonnes.

A zebulon, c'est vrai que la fonction (gcd) serait à creuser (j'y avais songer), pour une aproximation c'est déjà mieux que le retour fractionnaire de (rtos)

Merci à tous de vos talents.

VDH-Bruno · le 16 février 2015

Slt

Un problème avec la fonction itérative de (gile)!
Le numérateur (ou produit) n'est pas bon. Le plus rigolo est que si j'évalue la fraction,

Remplace:

(setq i (fix x)
       n (list i 1)
       d (list 1 0)
 )

Par:

(setq n (list 0 1)
       d (list 1 0)
)

Merci à tous de vos talents

Merci au tien, et à tes nombreuses contributions de qualités sur ce forum.

A+

(Ps: Historiquement et légitimement sur ce forum Bruno c'est toi ;) )

VDH-Bruno · le 16 février 2015

Re,

En même temps, je n'ai jamais eu l'occasion d'utiliser la fonction gcd. Voilà, c'est chose faite.

Pour l'occasion 2 routines avec gcd, écrites par jeu il y a quelque temps, j'ai rarement eu l'occasion de m'en servir, la première est une généralisation de ce que tu as posté, la seconde est une tentative de recherche du pgcd sur une liste d'entier.

;;; FRAC-RED                                                   VDH-Bruno
;;; Arg: liste de 2 entiers (numerateur dénominateur)
;;; Retourne: les 2 entiers réduit au plus petit diviseur commun 
;;; (frac-red '(10 5))     retourne     (2 1)
(defun frac-red (l)
 ((lambda (d) (list (/ (car l) d) (/ (cadr l) d))) (gcd (car l) (cadr l)))
)

;;; L->PGCD                                                     VDH-Bruno
;;; Retourne le plus grand diviseur appliqué à une liste de nombre entier
;;; ex : (l->pgcd '(6 12 18 24 30 36)) retourne 6                        
(defun l->pgcd (l)
 (if (apply '= l) (car l) (l->pgcd (mapcar 'gcd l (cdr l))))
)

;| Optimisation possible     
(defun l->pgcd (l)
 (cond ((member 1 l) 1)
       ((apply '= l) (car l))
       ((l->pgcd (mapcar 'gcd l (cdr l))))
 )
)
;|

Sinon pour dans le cas qui nous préoccupe et comme tu l'as souligné le passage par une troncature de la partie décimal sera le plus souvent moins précis que de passer par le développement en fraction continue.

A+

Patrick_35 · le 16 février 2015

Bonjour

C'est hors sujet, mais je trouve amusant la date et heure de la réponse #7 et #10 :D

Bruno nous fait de la bilocation ;)

@+

VDH-Bruno · le 16 février 2015

Salut,

C'est hors sujet, mais je trouve amusant la date et heure de la réponse #7 et #10 :D
Bruno nous fait de la bilocation ;)

Plus simplement

réponse #7: le 12h42 vient du forum en fait c'était cette nuit à 0h42 ou 24h42 :rolleyes:

réponse #10: 12h10, fin de matinée pendant la pause déjeuné :D

Patrick_35 · le 16 février 2015

Salut,

Plus simplement
réponse #7: le 12h42 vient du forum en fait c'était cette nuit à 0h42 ou 24h42
réponse #10: 12h10, fin de matinée pendant la pause déjeuné :D

Oui, j'avais compris. C'est juste l'affichage qui pose problème.

C'est comme la réponse de _zebulon à 06:43 et quand il est cité, à 18:43

:D

@+

VDH-Bruno · le 16 février 2015

Re,

En tout cas ton intervention permet de voir regroupé sur un même fil, les contributeurs historique de ce forum que j'apprécie le plus tant sur le plan humain que intellectuel.

(Ps: 2003 pour le trio (_zebulon, bonuscad, Patrick_35) et 2005 pour (gile), c'est beau! :) )

bonuscad · le 16 février 2015

Remplace:

(setq i (fix x)
n (list i 1)
d (list 1 0)
)

Par:

(setq n (list 0 1)
d (list 1 0)
)

Effectivement, ça va mieux.

J'ai bien cherché à trouver l'erreur de (gile), mais encore une fois tu as eu l'esprit plus vif que moi.

En tout cas ton intervention permet de voir regroupé sur un même fil, les contributeurs historique de ce forum que j'apprécie le plus tant sur le plan humain que intellectuel.

(Ps: 2003 pour le trio (_zebulon, bonuscad, Patrick_35) et 2005 pour (gile), c'est beau! :) )

Bien moi j'ai plaisir à voir de nouvelle pointure, place aux jeunes (et moins jeunes)... ;)

Lire:

VDH-Bruno

Olivier Eckmann

-Olivier-

ElpanovEvgeniy (dommage que la langue soit certainement un frein à sa participation)

bryce

usegomme

et d'autres...

c'est pour moi un plaisir énorme de voir un sens du partage qui perdure.

CadXp ne vit que grâce à cela: Evoluer ensemble et ne pas prendre sans même dire merci comme cela peut se voir parfois, car ce comportement ne peut que donner la mort à un site d'échange (un appel du pied.. ) :rolleyes:

VDH-Bruno · le 16 février 2015

(et moins jeunes)... ;)

:(rires forts): :(rires forts): :(rires forts):

-Olivier- · le 16 février 2015

Bonjour bonuscad,

Bien moi j'ai plaisir à voir de nouvelle pointure, place aux jeunes (et moins jeunes)... ;)

Lire:
VDH-Bruno
Olivier Eckmann
-Olivier-
ElpanovEvgeniy (dommage que la langue soit certainement un frein à sa participation)
bryce
usegomme
et d'autres...

Même si cela fait plaisir, je pense tout de même que ma présence dans cette liste est très largement exagéré, la preuve je comprends un mot sur deux dans ce sujet.

En grand merci à vous tous pour cette mine d'information.

Olivier

Patrick_35 · le 16 février 2015

Bien moi j'ai plaisir à voir de nouvelle pointure, place aux jeunes (et moins jeunes)... ;)

Lire:
VDH-Bruno
Olivier Eckmann
-Olivier-
ElpanovEvgeniy (dommage que la langue soit certainement un frein à sa participation)
bryce
usegomme
et d'autres...

Je plussoie :D

@+

zebulon_ · le 16 février 2015

(Ps: 2003 pour le trio (_zebulon, bonuscad, Patrick_35) et 2005 pour (gile), c'est beau! :) )

Normal, chez nous,

, l'entraide est chevillée au corps.

Amicalement

Vincent

VDH-Bruno · le 17 février 2015

Bonjour,

…je ne comprends pas pourquoi l'appel à la fraction se fait avec un argument défini en lambda.
[…] Je ne saisi pas la subtilité du (lambda (i) 1.0)

Je me suis aperçu que je n'avais pas vraiment répondu à la question du pourquoi d'une fonction en guise d'argument, je vais tenter une réponse au moyen d'une application pratique simple et un peu plus parlant que l'exemple du nombre d'or (et sa multitude de 1 en quotient et période):

Pour l'exemple on va chercher avec cette fonction à approcher finement la valeur de la diagonale d'un cube unitaire (pour mémoire c'est la définition de la racine carré de 3 :rolleyes: ) au moyen de sa fraction continue.

Si je mesure cette longueur sur un cube 1m de côté, je vais trouver avec une précision de l'ordre du mm, une valeur de 1.732m pour la diagonale (difficile d'être plus précis avec mon décamètre :P ).

Cette valeur est suffisante pour que si je développe ce nombre en fraction continue, j'obtienne le résultat suivant:

[1 1 2 1 2 1 2 1 2 … ], à partir du numéro d'ordre 1, ma fraction est périodique (période=2, la séquence se répète tous les 2 chiffres).

Ce qui implique que quand mon numéro d'ordre est impaire le quotient vaut 1, quand mon numéro d'ordre est paire le quotient vaut 2.

Une fois ces éléments posés, il est facile de définir une fonction représentative en lisp au moyen de l'expession suivante:

(lambda (i) (1+ (rem (1+ i) 2)) )

Puis de l'injecter dans la fonction cont-frac pour obtenir la valeur décimale de la racine de avec une précision d'ordre k (avec k=100 pour l'exemple), et ce à partir de la fraction continue du nombre.

_$ (cont-frac (lambda (i) 1.0) (lambda (i) (1+ (rem (1+ i) 2)) ) 100)
0.732051

CQFD

bonuscad · le 18 février 2015

CQFD

C'est Quasi Facile à Démontrer (pour toi)

Plus sérieusement, merci de ce cours magistral, mais heureusement que la fonction (trace) existe pour suivre ces récursions, ça me permet au moins de comprendre ces fonctions à défaut de savoir les construire...

Bonne journée

VDH-Bruno · le 18 février 2015

C'est Quasi Facile à Démontrer (pour toi)

Merci, on pourrait le croire, la vérité est que j'ai eu le besoin/envie, il y a peu de temps d'assimiler ces notions, donc par un heureux concours de circonstance j'avais déjà bien en tête une partie du sujet avant de commencer à répondre.

Pour le reste ce n'est qu'une question d'entrainement, par habitude j'écris plus facilement mes fonctions de façon récursives, il est donc normal que je sois un peu plus à l'aise avec tous ce qui s'y rapporte (que ce soit le décryptage des fonctions récursives, ou des formules mathématiques établies sur un principe de récurrence).

Amicalement Bruno

bonuscad · le 18 février 2015

Un retour qui montre que la réponse à ma demande était fort utile B)

Le fichier forme (avec une super bonne définition) que j'ai pu produire.

Le fichier diabolo.shp contient:

*128,384,DIABOLO
2,020,1,022,048,02E,2,4,14,3,99,014,4,99,3,14,1,4,51,3,29,012,028,01E,4,29,3,51,
2,4,14,3,99,014,4,99,3,14,1,4,44,3,29,012,028,01E,4,29,3,44,2,4,14,3,99,014,4,
99,3,14,1,4,37,3,29,012,028,01E,4,29,3,37,2,4,14,3,99,014,4,99,3,14,1,4,211,3,
204,012,028,01E,4,204,3,211,2,4,14,3,99,014,4,99,3,14,1,4,134,3,169,012,028,01E,
4,169,3,134,2,4,14,3,99,014,4,99,3,14,1,4,75,3,136,012,028,01E,4,136,3,75,2,4,
14,3,99,014,4,99,3,14,1,4,71,3,229,012,028,01E,4,229,3,71,2,4,14,3,99,014,4,99,
3,14,1,4,7,3,102,012,028,01E,4,102,3,7,2,4,14,3,99,08C,4,99,3,14,1,02A,040,026,
2,4,14,3,99,01C,4,99,3,14,1,4,51,3,29,01A,020,016,4,29,3,51,2,4,14,3,99,01C,4,
99,3,14,1,4,44,3,29,01A,020,016,4,29,3,44,2,4,14,3,99,01C,4,99,3,14,1,4,37,3,29,
01A,020,016,4,29,3,37,2,4,14,3,99,01C,4,99,3,14,1,4,211,3,204,01A,020,016,4,204,
3,211,2,4,14,3,99,01C,4,99,3,14,1,4,134,3,169,01A,020,016,4,169,3,134,2,4,14,3,
99,01C,4,99,3,14,1,4,75,3,136,01A,020,016,4,136,3,75,2,4,14,3,99,01C,4,99,3,14,
1,4,71,3,229,01A,020,016,4,229,3,71,2,4,14,3,99,01C,4,99,3,14,1,4,7,3,102,01A,
020,016,4,102,3,7,2,4,14,3,99,084,4,99,3,14,028,0

Une fois compilé (avec la commande COMPILE sous Autocad) j'ai pu faire cette définition de type de ligne

Le fichier diabolo.lin contient:

*diabolo, Diabolo ---|X|----|X|----|X|----|X|----|X|--
A,.25,-.1,[DIABOLO,diabolo.shx,x=0,s=.1],-.5,1

Voila en attendant d'en faire d'autres...

Connexion

Fraction continue

Messages recommandés

bonuscad

VDH-Bruno

VDH-Bruno

bonuscad

zebulon_

(gile)

VDH-Bruno

bonuscad

VDH-Bruno

VDH-Bruno

Patrick_35

VDH-Bruno

Patrick_35

VDH-Bruno

bonuscad

VDH-Bruno

-Olivier-

Patrick_35

zebulon_

VDH-Bruno

bonuscad

VDH-Bruno

bonuscad

Créer un compte ou se connecter pour commenter

Créer un compte

Se connecter

Forums

Naviguer

Activité

Information importante