Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#26 27-09-2017 17:41:06
- hgaruo1951
- Membre
- Inscription : 13-09-2017
- Messages : 104
Re : congruences
Re ,
lire Ui(x) et non Ui(x) avec i qui est un indice muet.
Hors ligne
#27 27-09-2017 17:55:16
- hgaruo1951
- Membre
- Inscription : 13-09-2017
- Messages : 104
Re : congruences
Re , pour le lien j'avais un doute et pourtant celui qui a suivi marche cliquer ici
Hors ligne
#28 27-09-2017 19:09:58
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 907
Re : congruences
Bonsoir,
Oui, le lien est bon.
Mais très difficile de lire ton programme avec le scrolling : il serait tellement plus simple de le lire directement0
Turbo Pascal 7 avec des goto et nos de lignes (quelle horreur) : ce turbo pascal 7 ne date pas d'aujourd"hui, ni même de l'an dernier.
J'ai beaucoup programmé en Turbo Basic (il y a plus de 20 ans) : il n'y avait déjà plus de goto et des nos de ligne mais des Labels et des procédures qu'on appelait avec gosub, des fonctions ce qui permettait après exécution de revenir immédiatement l'instruction appelante...
Mais les variables y étaient connues dans tout le programme écrit.
En Python, il y a un morceau principal d"où l'on peut appeler des fonctions toutes les variables présentes dans une fonction n'ont d'existence que dans ces fonctions, ou alors il faut les déclarer globales.
Je suis à peu près sûr de pouvoir passer de Python à, Pascal et réciproquement : oh, certes, cela ne ferait pas sans recherches, ni sans mal...
Mon programme est sans faille...
J'ai encore vérifié avec l'exemple de la video : j'obtiens bien 64. Mais ça c'est très simple à calculer à la main...
Par contre l'inverse de 10946 modulo 6765, je n'oserais même pas essayer avec crayon papier.
Et si mon programme affiche les 3 lignes, c'est pour bien te montrer qu'il est conforme :
113 83 30 23 7 2 1
0 -1 -2 -1 -3 -3
0 -49 36 -13 10 -3 1
L'inverse de 83 modulo 113 est : 64
@+
Arx Tarpeia Capitoli proxima...
En ligne
#29 28-09-2017 10:44:01
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 907
Re : congruences
Bonjour,
J'ai retravaillé mon programme, pour corriger des imperfections et le rendre plus "Pythonique" :
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
from fractions import gcd
def affiche_schema(lg,f,Liste):
for nb in Liste:
print(f.format(nb),end="")
print()
def calcul_inverse(x,modulo):
a,b,r = max(x,modulo),min(x,modulo),0
Dividendes_diviseurs_restes,Opp_Quotients,Fin=[a,b],[0],[0]
while r!=1:
a,(q,r)=b,divmod(a,b)
b = r
Dividendes_diviseurs_restes.append(r)
Opp_Quotients.append(-q)
c,n=0,len(Dividendes_diviseurs_restes)
Fin=[0 for ii in range(n)]
Fin[-1]=1
for ii in range(n-1,1,-1):
Fin[ii-1]=Fin[i]*(Opp_Quotients[i-1])+c
c=Fin[ii]
if x < modulo:
inv_mod = Fin[1]
else:
inv_mod=Fin[2]
if inv_mod < 0:
ex,inv_mod=inv_mod,inv_mod%modulo
lg=max(len(str(x)),len(str(modulo)))+1
formattage="{:"+str(lg)+"}"
affiche_schema(lg,formattage,Dividendes_diviseurs_restes)
affiche_schema(lg,formattage,Opp_Quotients)
affiche_schema(lg,formattage,Fin)
return inv_mod,ex
print(" *************************************************")
print(" * Calcul de l'inverse d'un nombre x modulo n *")
print(" * avec le schéma présenté par Youssef Ouragh *")
print(" *************************************************\n\n")
x,modulo=1595,2584
print("Recherche de l'inverse de",x,"modulo", modulo,end="\n\n")
if gcd(x,modulo) != 1:
print ("Désolé, votre nombre et le modulo ne sont pas premiers entre eux.")
print ("Sélectionner un autre couple de valeurs.")
else:
inv_mod,ex=calcul_inverse(x,modulo)
print ("\nRéponse :",end=" ")
if ex != inv_mod:
print(str(ex)+", soit modulo",str(modulo),":",inv_mod)
else:
print(inv_mod)
Sortie :
*************************************************
* Calcul de l'inverse d'un nombre x modulo n *
* avec le schéma présenté par Youssef Ouragh *
*************************************************
Recherche de l'inverse de 1595 modulo 2584
2584 1595 989 606 383 223 160 63 34 29 5 4 1
0 -1 -1 -1 -1 -1 -1 -2 -1 -1 -5 -1
0 -533 329 -204 125 -79 46 -33 13 -7 6 -1 1
Réponse : -533, soit modulo 2584 : 2051
Temps de calcul de cette version: 0,00004 s
Temps de calcul de ma vieille version de test qui fait beaucoup, beaucoup de calculs : 0,0009 s
soit un rapport de plus de 1 à 20...
Si on ne veut que le résultat brut (et non l'affichage des 3 lignes), la liste Dividendes_diviseurs_restes ne sert à rien : il est inutile de stocker les valeurs.
Il suffit de ne conserver qu'un Dividende un diviseur et le reste pour servir de niveau diviseur et sortir de la boucle si r=1.
Seules sont nécessaires les listes Opp_Quotients et Fin.
Reste plus qu'à justifier de A à Z le schéma, sinon, si tu t'adresses à Cédric Villani, il va t'envoyer paître...
@+
Arx Tarpeia Capitoli proxima...
En ligne
#30 28-09-2017 11:28:16
- hgaruo1951
- Membre
- Inscription : 13-09-2017
- Messages : 104
Re : congruences
Bonjour ,
Là M. yoshi vous avez parfaitement raison et je vous prie de croire à ce que je dis. Si en tant
qu'enseignant vous m'attribué un 0.5 / 20 et bien je ne dirai pas un mot car pour le programme
que je donne dans cette vidéo il est loin d'être moyen et la programmation je reconnais ce n'est pas
mon DADA. Ce que vous nous présentez est très bien et je dirai à mes étudiants qui s'intéresseraient
à la programmation de regarder ce que vous avez réalisé en ci peu de temps. Ce que surtout j'ai voulu
présenté c'est que mon programme est très simples et le programme à cet effet ne comporte
que quelques instructions. De plus ce que je démontre (même avec comme vous l'avez noté avec raison avec
des goto à la très, très ancienne!!! ) on peut résoudre le problème de l'inverse d'un nombre modulo A et aussi
résoudre facilement le problème de la recherche d'une solution particulière des équations diophantiennes
linéaires à plusieurs variables , solutions particulières très utiles à la résolution des équations pour lequel
le théorème des restes chinois est vérifié. A cette étape une question se posera tout naturellement :
Comment établir la solution générale d'une équation diophantienne linéaire à plusieurs variables.
Cette question vous admettrez qu'elle mérite qu'on lui donne une réponse. Attention les solutions présentées
dans tel ou tel site ont généralement l'inconvénient suivant: les variables s'expriment en fonction de plusieurs
paramètres sauf si l'on traite le problème par la voie matricielle et même cette dernière devient délicate si le nombre
de variables est supérieure à quatre. Par contre en appliquant mon schéma en plusieurs étapes on arrivera
à démontrer que chacune des variables s'exprimes de façon linéaires en fonction d'un seul paramètre.
Cordialement.
Hors ligne
#31 28-09-2017 11:31:50
- hgaruo1951
- Membre
- Inscription : 13-09-2017
- Messages : 104
Re : congruences
Re ,
et vous avez certainement remarqué que je ne réponds même pas à un certain p....
Cordialement.
Hors ligne
#32 28-09-2017 12:17:33
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 907
Re : congruences
Bonjour,
et vous avez certainement remarqué que je ne réponds même pas à un certain p....
Ce que j'ai remarqué tout de suite avec l'exemple 333,129 c'est que ses lignes étaient fausses.
Et que tu (dans un forum, le tutoiement est sinon "de rigueur", du moins une tradition. Si tu n'en veux plus, signale-le moi) le lui as signalé, puis reconnu que les solutions trouvées donnaient = 3 (normal : pgcd(133,129)=3) et non =1, sans réaction de sa part...
Mon programme est "long", aussi parce que je l'ai voulu didactique et modulaire...
La base est concentrée dans la fonction calcul_inverse.
Je vais voir de plus près les autre vidéos et "essayer" de les "traduire" dans un programme plus vaste..."n'importe quoi") : je me resservirai de ce que j'avais fait pour répondre à la jeune-fille à propos de son exercice sur le théorème des restes chinois...
@+
Arx Tarpeia Capitoli proxima...
En ligne
#33 28-09-2017 13:44:08
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 907
Re : congruences
Re,
J'ai cru voir dans une video, une histoire de points à distances entières des sommets traitée avec Bezout ?
Exact ou pas ?
Ça m'a rappelé quelque chose de traité via la force brute en Python ici :
http://www.bibmath.net/forums/viewtopic.php?id=6918&p=1
Donc, si je n'ai pas rêvé, il faut que je regarde ça : mon (très long) programme serait susceptible d'aller beaucoup plus vite...
@+
Arx Tarpeia Capitoli proxima...
En ligne