Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#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

Pied de page des forums