Convertir nombre en fraction .

Venez à la rencontre des autres membres: discussions en tous genres (sauf politiques), anniversaires, faits divers
AlainRatomahenina
Membre Naturel
Messages: 22
Enregistré le: 09 Sep 2017, 09:15

Convertir nombre en fraction .

par AlainRatomahenina » 22 Oct 2017, 20:11

Bonjour .
Là conversion nombre/fraction comme par exemple 6,25 = 25/4 est largement utilisée , mais son algorithme n'est pas connu . Il est pourtant simple :

A=0
B=1
ENTRER N
Label m
Si (A/B)<n alors A = A + 1
Si (A/B)>n alors B = B + 1
Si (A/B)=n alors imprimer A , B ; stop
Goto m

Ce petit programme que j'ai mis au point en 2000 à permis pas mal de choses dont notamment les compressions de mémoire . On le retrouve couramment dans les calculatrices casio notamment .



aviateur
Habitué(e)
Messages: 1206
Enregistré le: 19 Fév 2017, 10:59

Re: Convertir nombre en fraction .

par aviateur » 22 Oct 2017, 23:05

Bonjour
Je ne voudrais pas te décevoir mais c'est une blague ou quoi?
Donne lui n = 15421.17 à manger à ton algorithme, il lui faut 1542216 itérations pour trouver
n=1542117/100. Calcule le temps CPU ....
Et Casio n'a pas fait faillite?

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 5799
Enregistré le: 22 Nov 2007, 13:00

Re: Convertir nombre en fraction .

par fatal_error » 23 Oct 2017, 08:06

une petite variation de "l'énoncé" car inintéressant en tant que tel.
Supposons que notre machine n'affiche jamais la virgule. Mais elle nous dit s'il reste des poussières derrière. Le but étant d'arriver à ce qu'elle nous dise qu'il n'y a plus de poussières.

On se donne deux fonctions up & down
Chaque appel à ces fonctions coute 1 inst.

encas:
supposons up == down == (x)=>x+1 (idem la fonction ajoute 1 à l'argument et retourne cette nouvelle valeur
quel algo peut on construire?
------------
entrée:
même chose, mais maintenant nous avons le prototype
up(A, nbTimes)
où cette fois si up va appliquer +1 nbTimes fois
(mais l'appel à up coute seulement 1 instruction)
------------
maindish-1
remplacons désormais up & down par (x)=>exp(x)
peut on converger?
on suppose qu'on a pas de buffer overflow...
------------
maindish-2
si on suppose désormais que nous avons buffer overflow MAIS
que nous avons up==exp, down==(x)=>ln(x+1)

PS: je n'y ai pas réfléchis outre mesure, pe les questions sont liées, stupides où non réalisables
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 18521
Enregistré le: 11 Nov 2009, 22:53

Re: Convertir nombre en fraction .

par Ben314 » 23 Oct 2017, 10:16

Salut,
AlainRatomahenina a écrit:Là conversion nombre/fraction comme par exemple 6,25 = 25/4 est largement utilisée , mais son algorithme n'est pas connu.

Si y'en a que ça intéresse, "le" bon algorithme (donc clairement pas celui proposé dans le premier post...) ça fait très longtemps (*) qu'il est connu : ça s'appelle des fractions continues et ça permet aussi d'avoir de très bonnes approximation de nombre non rationnels, par exemple pour Pi, ça donne les fameuses fraction 22/7 et 355/113 connues de longue date comme extrêmement précises au vu de la faible taille de leur dénominateur.
Ça a aussi été utilisé très souvent dans des automates pour trouver le nombre de dents à mettre à des engrenages de façon à ce que le rapport entre les vitesses de rotations de deux axes soit le plus proche possible d'un nombre fixé : voir par exemple l'automate planétaire de Christian Huygens.

En plus, le principe est on ne peut plus simple :
Partant d'un réel , on l'écrit est la partie entière de (donc ).
Si , c'est fini, sinon, on écrit est la partie entière de .
Si , c'est fini, sinon, on écrit est la partie entière de .
Etc, etc.
Et si au départ est une fraction alors on montre que l'algo. s'arrête en un temps (donc extrêmement rapidement) et on peut très facilement retrouver les valeurs de et de à l'aide des (via deux récurrences doubles et avec et qu'on peut directement injecter dans l'unique boucle du programme)

(*) Dixit Wiki, c'était déjà utilisé en Inde au moyen-age et ça a été étudié en Europe au XVIIem siècle.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

AlainRatomahenina
Membre Naturel
Messages: 22
Enregistré le: 09 Sep 2017, 09:15

Re: Convertir nombre en fraction .

par AlainRatomahenina » 23 Oct 2017, 14:25

Non , tu est mal renseigné où on t'as menti . Je suis bien l'auteur de cet algorithme que j'ai mis au point en 1998 et qui m'a été volé par des industriels de l'informatique . J'avais baptisé ce programme " compress " comme compression de mémoire , car les voleurs savaient que l'on pouvait l'utiliser pour ce faire : au lieu de mémoriser deux nombres , on les divise et on ne mémorisé que le résultat . A la sortie , grâce à l'algorithme , on retrouve les deux nombres du départ : la capacité mémoire est doublée .

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 18521
Enregistré le: 11 Nov 2009, 22:53

Re: Convertir nombre en fraction .

par Ben314 » 23 Oct 2017, 17:52

AlainRatomahenina a écrit:... Je suis bien l'auteur de cet algorithme que j'ai mis au point en 1998 et qui m'a été volé par des industriels de l'informatique.
Je voudrais bien savoir qui pourrait être suffisamment c... pour "voler" un algorithme infiniment moins performant que celui archi connu qui date d'il y a environ un millénaire (dont on ne connait pas l'inventeur, mais de toute façon c'était une époque bénie où on avait pas encore inventé la notion de brevet...)

Sans parler du fait que ça :
AlainRatomahenina a écrit:au lieu de mémoriser deux nombres , on les divise et on ne mémorisé que le résultat . A la sortie , grâce à l'algorithme , on retrouve les deux nombres du départ : la capacité mémoire est doublée .
tout ce que ça prouve, ben c'est que tu as jamais fait d'informatique : Si tu veut être sûr de retrouver les valeurs de p et q en ne connaissant que la valeur du nombre p/q, ça signifie qu'il te faut une certaine précision concernant nombre flottant x=p/q.
Et si tu fait un minimum de calculs, ben tu constatera que, si les entiers p et q sont stockés sur (par exemple) 4 octets chacun, alors il faut que le flottant x=p/q soit stocké (au moins) sur 8 octets pour avoir assez de précision pour retrouver p et q. En résumé, on est passé de 4 + 4 octets pour stocker p et q à... 8 octets pour stocker x=p/q soit une sacrée économie de mémoire !!!!

Évidement, tout cela sans parler du "léger" problème lié au fait que si on veut "compacter" p=6 ; q=4, on va stocker dans x la valeur 6/4 et que quand on va vouloir retrouver les valeurs de p et q, ça va donner p=3 et q=2 vu que 6/4=3/2...

P.S. (humour...)
Moi, je te propose un nouvel algorithme de "méga compression mémoire" : partant d'un tableau entier de nombre entiers T[1], T[2], T[3], T[4], . . ., T[N], on forme un unique nombre entier, à savoir (où désigne le n-ième nombre premier).
Tu vérifiera aisément que la connaissance de cet unique nombre entier C permet de retrouver toutes les données contenues dans le tableau.
Bilan : Un tableau complet d'entiers entièrement résumé en un simple entier : économie CONSIDÉRABLE de mémoire, non ?

Tiens, en fait j'en ait un autre algo. de compression super pas con : tu as deux entier A et B entre 0 et 255 et au lieu de bêtement les stocker sous la forme de DEUX entiers, tu stocke l'UNIQUE entier qui permet clairement de retrouver les valeurs de A et B vu que c'est le quotient et le reste de la division de C par 256 : belle économie de mémoire de nouveau, tu pense pas ?
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

AlainRatomahenina
Membre Naturel
Messages: 22
Enregistré le: 09 Sep 2017, 09:15

Re: Convertir nombre en fraction .

par AlainRatomahenina » 23 Oct 2017, 19:42

Ce petit programme n'est que l'étincelle de ce qui a mis le feu à la poudrière . Ça a surtout rendu probable le fait que l'on pouvait compresser mathématiquement des données dans une mémoire . Après cet incident j'ai quand même eu droit à l'espionnage industriel et donc passer pour un fou si je racontait tout ça ( surtout à un docteur )
De tout est né WinZip et par la suite le MP3 pour lesquels on m'aurait deproprie de mon travail .

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 18521
Enregistré le: 11 Nov 2009, 22:53

Re: Convertir nombre en fraction .

par Ben314 » 23 Oct 2017, 20:50

Bis et répéta (mais visiblement tu ne sait pas même lire) :
Ton truc ne comprime absolument rien du tout !!!!
Donc heureusement que c'est pas avec des truc pareil qu'on été créé les différents formats de compression.

Sans parler qu'en 1998, il y avait déjà un sacret paquet d'algo. de compressions extrêmement performant (et des vrais qui compriment effectivement, pas comme le tient) par exemple, le format PNG encore utilisé aujourd'hui, il date de 1996 et je peut te garantir que lui, il comprime réellement.

Bref, le seul truc que je peut te dire, c'est que la paranoïa, c'est une maladie qui se soigne...

Tient, cadeau : regarde ce lien LZ77 et LZ78, en particulier les dates et la méthode employé déjà à l'époque pour réellement compacter des données (méthode qui continue à être utilisée aujourd'hui pour pas mal de formats de compression exacte)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

aviateur
Habitué(e)
Messages: 1206
Enregistré le: 19 Fév 2017, 10:59

Re: Convertir nombre en fraction .

par aviateur » 23 Oct 2017, 21:08

Bonjour @AlainRatomahenina , vu que tu es finalement le père de Winzip, tu devrais t'en servir pour te décompresser le cerveau.

AlainRatomahenina
Membre Naturel
Messages: 22
Enregistré le: 09 Sep 2017, 09:15

Re: Convertir nombre en fraction .

par AlainRatomahenina » 23 Oct 2017, 21:22

Je répète que je n'ais fait qu'évoquer la possibilité de pouvoir compresser les données dans un fichier . C'est de là , le début des années 2000 qu'est apparu WinZip et ensuite 5 ans plus tard le mp3 . Oui je passes pour un fou quand je raconte tout ça mais c'est la vérité . Ma propre mère travaillait dans la prestigieuse société d'informatique américaine et il n'avaient aucun mal à récupérer mes travaux , car ce n'est pas le seul .
Quoiqu'il en soit , mon petit programme est très efficace mathématiquement .

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 18521
Enregistré le: 11 Nov 2009, 22:53

Re: Convertir nombre en fraction .

par Ben314 » 23 Oct 2017, 21:34

AlainRatomahenina a écrit:Quoiqu'il en soit , mon petit programme est très efficace mathématiquement .
Là, tu es mal barré : autant mon curriculum ne me permet pas forcément d'être catégorique concernant l'informatique, autant il me permet de l'être en ce qui concerne les math et donc je n'ai pas le moindre doute concernant le fait que, mathématiquement parlant, ton "petit programme" est d'une inefficacité affligeante comparé aux fractions continues.

Essaye juste pour voir combien de calculs il te faut pour retrouver la fraction correspondant au nombre çi dessous avec ta méthode puis compare avec celle datant du moyen age présenté çi dessus
x=0,6158781074578989574979951884522854851643945469125902165196471531676022453889334402566158781074578990...

(pour ceux qui ont la flemme, il faut plus de 2000 opérations dans un cas et moins de 10 dans l'autre...)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 5799
Enregistré le: 22 Nov 2007, 13:00

Re: Convertir nombre en fraction .

par fatal_error » 23 Oct 2017, 21:53

Code: Tout sélectionner
ça s'appelle des fractions continues

connaissait pas. Vu par ci par là les ... (sous le trait de fraction) puis des inversions de la dite fraction pour résoudre des équations... mais connaissait pas le terme... thx
je suis loin de comprendre pourquoi la convergence logarithmique mais qui sait, à mes heures perdues...
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 18521
Enregistré le: 11 Nov 2009, 22:53

Re: Convertir nombre en fraction .

par Ben314 » 23 Oct 2017, 22:00

fatal_error a écrit:connaissait pas. Vu par ci par là les ... (sous le trait de fraction) puis des inversions de la dite fraction pour résoudre des équations... mais connaissait pas le terme... thx
je suis loin de comprendre pourquoi la convergence logarithmique mais qui sait, à mes heures perdues...
Les fractions continues, ça fait parti (à mon sens) des truc super marrant des maths : la définition semble complètement concon, sauf que plus tu approfondi le sujet, plus tu te rend compte qu'en fait il y a des tonnes de truc à dire...
Sinon, concernant la complexité, si tu part d'un alpha qui est lui même une fraction p/q, alors ce que tu fait à travers l'algorithme des fractions continues, ben c'est très exactement l'algorithme d'Euclide pour trouver le pgcd de deux nombres p et q (quand tu écrit alpha=f0+theta0, ben f0, c'est le quotient de la division de p par q et si le reste est r, alors theta0, c'est r/q donc 1/theta0, c'est q/r, dont tu va de nouveau prendre la partie entière qui est le reste de la division de q par r, etc, etc...)
Donc la complexité, c'est la même que celle de l'algo d'Euclide et je pense que tu as déjà vu que pour l'algo d'Euclide, le "pire des cas", c'est lorsque les deux nombres de départ sont deux nombres successifs de la suite de Fibonnacci et c'est le fait que le n-ième nombre de la suite de Fibonnacci soit environ égal à Phi^n [où Phi est le nombre d'or] qui fait que la complexité est logarithmique.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 5799
Enregistré le: 22 Nov 2007, 13:00

Re: Convertir nombre en fraction .

par fatal_error » 23 Oct 2017, 22:09

Code: Tout sélectionner
je pense que tu as déjà vu que]

nan j'avais juste établi le terme général, mais de toute façon ca vaut pas le coup que tu te fatigues (en tout cas pour moi) à établir pourquoi, parce qu'en lisant bêtement je retiendrai pas de toute façon...(comprendre que si jamais je veux comprendre alors je prendrai le temps et me sortirai les doigts)
la vie est une fête :)

aviateur
Habitué(e)
Messages: 1206
Enregistré le: 19 Fév 2017, 10:59

Re: Convertir nombre en fraction .

par aviateur » 24 Oct 2017, 00:36

Bonjour
Le développement en fraction continue est assez bien connu pour la démonstration de l' irrationalité de e (par Euler) et de même pour (par Lambert ou Brouncker qui a établi de dév. en frac cont. ?).
Voici un lien où Claude Brezinski fait un petit historique concernant sur les fractions continues.
http://irem.univ-reunion.fr/IMG/pdf/Brezinski_fractions_continues.pdf

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 5799
Enregistré le: 22 Nov 2007, 13:00

Re: Convertir nombre en fraction .

par fatal_error » 24 Oct 2017, 19:52

Code: Tout sélectionner
c'est lorsque les deux nombres de départ sont deux nombres successifs de la suite de Fibonnacci

bon, finalement j'ai été curieux, pour ceux qui sont comme moi incultes... j'ai un peu mieux cerné ici :
http://gjmaths.pagesperso-orange.fr/contenu/lamenon.pdf
j'ai évidemment pas tout fait, (...) mais on y comprend au moins pourquoi la complexité est de type logarithmique et pk liée à Fibonnaci
la vie est une fête :)

aviateur
Habitué(e)
Messages: 1206
Enregistré le: 19 Fév 2017, 10:59

Re: Convertir nombre en fraction .

par aviateur » 24 Oct 2017, 20:12

Je n'ai jamais entendu parler du théorème de Lamé!! C'est le même bonhomme qui s'est intéressé aux coefficients des matériaux élastiques?

AlainRatomahenina
Membre Naturel
Messages: 22
Enregistré le: 09 Sep 2017, 09:15

Re: Convertir nombre en fraction .

par AlainRatomahenina » 24 Oct 2017, 20:57

Par la suite , vers 2003-4 , j'ai perfectionné mon travail . Je partais de la forme ( X - A ) ( X - B ) = 0 . Vous remarquerez que A et B sont solutions exactes de l'équation . Je considérais que A et B étaient les données à compresser . Il suffisait de mémoriser les valeurs résultant de la transformation de cette équation ( dont je ne me souviens plus ) et de résoudre cette forme pour retrouver les deux nombres . On pouvait , par arborescence , à partir d'un seul nombre mémorisé en déduire 2 puis 4 puis 8 jusqu'à donc 16 , le pouvoir actuel de compression du mp3 .

aviateur
Habitué(e)
Messages: 1206
Enregistré le: 19 Fév 2017, 10:59

Re: Convertir nombre en fraction .

par aviateur » 24 Oct 2017, 21:03

Bonjour
Au mieux c'est une blague, au pire c'est grave.

pascal16
Membre Complexe
Messages: 3326
Enregistré le: 01 Mar 2017, 13:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Convertir nombre en fraction .

par pascal16 » 24 Oct 2017, 21:58

Pour l'instant, les ordinateurs raisonnent en base 2
6,25 = 110,01 en base 2
25 = 11001 en base 2, c'est un décalage de virgule

 

Retourner vers ☕ Coin café

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite