Répondre à la discussion
Affichage des résultats 1 à 19 sur 19

Calculer rapidement




  1. #1
    SPH

    Red face Calculer rapidement

    Bonjour,
    PARI, c'est une calculatrice en ligne de commande free. Je sais que certains d'entre vous l'utilise.
    J'aimerais savoir si on peux la programmer pour avoir une serie de resultat ?
    PARI utilise quelle methode de stockage de grand nombre ??
    Dans le meme registre, je cherche la technique pour savoir si X est divisible par Y.
    Par exemple, est-ce que 4451244116848421 est divisible par 231 ?
    Quel est le premier indice indiquant une division entiere ou non ?
    Est-ce que cela est plus flagrand quand on regarde la representation binaire des 2 nombres du dessus ?

    Je pose serieusement la question car sur ordi, l'overflow au dela de 2.1 milliard force a utiliser une banque memoire mais la, le grand chiffre deviens abstrait (il est réparti dans une serie d'octets...)

    Merci

    -----


  2. Publicité
  3. #2
    invité576543
    Invité

    Re : Calculer rapidement

    pour 231 c'est facile! Tu additionnes par tranche de 6, et tu divises, je fais ça avec une machine de poche!

    (4451 + 244116 + 848421) modulo 231 = 200

    Cordialement,

  4. #3
    SPH

    Re : Calculer rapidement

    Citation Envoyé par mmy
    pour 231 c'est facile! Tu additionnes par tranche de 6, et tu divises, je fais ça avec une machine de poche!

    (4451 + 244116 + 848421) modulo 231 = 200

    Cordialement,
    Heu........ voyons voyons... j'ai beau regarder, je ne comprend pas...
    Cependant, je vois que tu as decoupé le grand chiffre comme je pourrais le faire.
    En dehors de ca, si tu pouvais expliquer plus concretement les etapes...
    PS : ce calcul rapide fonctionne quelque soit les chiffres ??


  5. #4
    matthias

    Re : Calculer rapidement

    Cela vient du fait que 1 000 000 est congru à 1 modulo 231.

  6. #5
    SPH

    Re : Calculer rapidement

    Citation Envoyé par matthias
    Cela vient du fait que 1 000 000 est congru à 1 modulo 231.
    Donc, cela veux dire que si j'avais choisi 579 au lieu de 231, on perd l'automatisme d'un calcul rapide ?

  7. A voir en vidéo sur Futura
  8. #6
    invité576543
    Invité

    Re : Calculer rapidement

    Citation Envoyé par SPH
    Donc, cela veux dire que si j'avais choisi 579 au lieu de 231, on perd l'automatisme d'un calcul rapide ?
    Il y a toujours une longueur qui marche. Il se trouve que pour 231 elle était vraiment courte! Dans le cas général, elle peut aller jusqu'à n-1, 6 par exemple si on cherche à diviser par 7.

    Pour 579, c'est un diviseur de 192, mais j'ai la flemme de trouver lequel... Ca pourrait être 192, ce qui aide pas des masses!

    En fait ça ne répond pas à ton problème, mais je n'ai pas résisté à sortir le résultat quand j'ai vu que le diviseur était 231=3.7.11

    Cordialement,

  9. #7
    SPH

    Re : Calculer rapidement

    Bon, je pense que je vais travailler en base 1 milliard.

    Mais pour simplifier, si on est en base 1000 (donc, des chiffres de 000 a 999), quelles procedures s'enchaineraient pour donner le resultat de :
    123456789001/93 (un exemple)
    Soit en bout de base 1000 :
    123 456 789 001 / 093

    Mais je me suis tjr demandé si c'etait cette technique qui etait utilisé dans des logiciels comme mathematica !! mais personne ne sait apparement

  10. Publicité
  11. #8
    matthias

    Re : Calculer rapidement

    Je ne pense pas que les logiciels come mathematica travaillent en décimal. Quitte à faire un découpage, autant le faire à partir du binaire.

  12. #9
    SPH

    Re : Calculer rapidement

    Citation Envoyé par matthias
    Je ne pense pas que les logiciels come mathematica travaillent en décimal. Quitte à faire un découpage, autant le faire à partir du binaire.
    Interessant...

    A ton avis (et je lance un appel a ceux qui savent !!!), comment cela se passe techniquement ??

  13. #10
    matthias

    Re : Calculer rapidement

    Déjà un des intérêts du découpage à partir du binaire, c'est que tu ne perds pas de place au niveau de la mémoire. Cela s'adapte parfaitement a un découpage en tranche de 8 bits et au fonctionnement des ordinateurs. Tu verras d'ailleurs souvent un nombre de 8 bits transcrit en un nombre à deux chiffres en héxadécimal pour cette raison.
    Maintenant, pour la manière d'effectuer les calculs sur les grands nombres, je pense que tu trouveras beaucoup d'algorithmes rivalisant d'astuce sur le net. Pour les additions c'est assez simple, pour les multiplications il y a pas mal d'optimisations possibles.

  14. #11
    SPH

    Re : Calculer rapidement

    j'ai cherché des "astuces", mais rien de concret

  15. #12
    Pole

    Re : Calculer rapidement

    Pour les divisions d'un grand nombre par un petit, c'est très rapide.
    A chaque fois, on prend le dernier résultat, on le multiplie par la base, on ajoute le prochain "chiffre", et on met modulo le nombre.
    Un exemple en base 10:
    53564 mod 14.
    5
    (5*10)+3 mod 14 quotient 3
    (11*10)+5 mod 14 quotient 8
    (3*10)+6 mod 14 quotient 2
    (8*10)+4 mod 14 quotient 6
    0. Donc 53564 mod 14=0.
    On peut aussi avoir le quotient en stockant le petit quotient (celui dans les modulo) pour chaque chiffre.
    Résultat : 53564=3826*14.
    Pour les grandes divisions (cad le grand nombre sur grand nombre), il y a plusieurs méthodes :
    (On doit calculer à chaque fois a/b)
    - tu peux évaluer 10^x/b (10^x pour les "décimales") par la méthode de Newton en calculant 1/b. Après, on multiplie par a, on décale pour que cela fasse un nb entier. Tu as ton quotient, tu peux calculer le reste.
    La méthode a un gros avantage si on utilise toujours le même diviseur parce que l'on calcule 1 fois l'inverse.
    -tu peux aussi faire à chaque fois une approximation du "chiffre" du quotient, qui est toujours plus grand que le vrai chiffre.
    Pour faire l'approximation, on calcule l'arrondi de nombre formé par les 3 premiers chiffres du quotient divisé par le nombre formé par les 2 premiers chiffres du diviseur.
    Si le nombre est plus grand que la base, prends le nombre formé par les 2 premiers chiffre du quotient divisé par le nombre formé par les 2 premiers chiffres du diviseur.

    Un exemple (pour la 2ème méthode) en base 10:
    2147538/23446
    3 premiers chiffre : 214
    2 premiers chiffre : 23
    214/23~=9,3
    l'arrondi est 9.
    9*23446=211014
    On doit le décaler pour qu'ils aient la même taille.
    2110140<2147538 : le premier chiffre du quotient est 9.
    On recommence avec le nouveau dividende :
    2147533-2110140=37393

    3 premiers chiffre : 373
    2 premiers chiffre : 23
    373/23~=16,2.
    l'arrondi est 16.
    16>10 donc :
    2 premiers chiffre : 37
    2 premiers chiffre : 23
    37/23~=1,608
    l'arrondi est 2.
    2*23446=46892
    46892 à la même taille : pas de décalage.
    46892>37393
    On enlève 1 au chiffre et on soustrait 23446 à 46892 : 23446.
    37393-23446=13947

    Résultat : 2147538=23446*91+13947

    Voilà.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  16. #13
    matthias

    Re : Calculer rapidement

    Citation Envoyé par Pole
    Pour les divisions d'un grand nombre par un petit, c'est très rapide.
    A chaque fois, on prend le dernier résultat, on le multiplie par la base, on ajoute le prochain "chiffre", et on met modulo le nombre.
    Un exemple en base 10:
    53564 mod 14.
    5
    (5*10)+3 mod 14 quotient 3
    (11*10)+5 mod 14 quotient 8
    (3*10)+6 mod 14 quotient 2
    (8*10)+4 mod 14 quotient 6
    0. Donc 53564 mod 14=0.
    On peut aussi avoir le quotient en stockant le petit quotient (celui dans les modulo) pour chaque chiffre.
    Résultat : 53564=3826*14.
    Cet algorithme est d'ailleurs celui que l'on apprend à l'école primaire

  17. #14
    matthias

    Re : Calculer rapidement

    Citation Envoyé par SPH
    j'ai cherché des "astuces", mais rien de concret
    Sur les algos de multiplication on trouve pourtant pas mal de choses comme l'utilisation de la FFT, l'algorithme de Karatsuba et autres ...

  18. #15
    Pole

    Re : Calculer rapidement

    Pour la deuxième partie, si le chiffre est plus grand que la base, il y a un bug. C'est un bug qui n'arrive vraiment pas souvent. Pensez à augmenter le chiffre dans ce cas.Testez aussi si le reste est plus grand que le diviseur.
    Si quelqu'un trouve le bug, ça serait très sympa.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  19. #16
    SPH

    Re : Calculer rapidement

    J'ai trouvé ca :
    http://fr.wikipedia.org/wiki/Transfo...Fourier_rapide
    Mais pour moi, c'est du chinois car je ne connais pas les maths poussées.
    Qui peux exposer rapidement comment se passe la transformé de fournier pour diviser par exemple :
    451254111414141 / 4551

  20. #17
    Pole

    Re : Calculer rapidement

    Tu ne peux pas. La FFT sert pour la multiplication. Elle ne peut pas servir pour la division.
    Regarde d'autres pages que sur wikipédia.
    La FFT peut utiliser des nb complexes, ou des nombres entiers. Seulement, pour les nb entiers, il faut changer de base,... Bref, je préfère avec des complexes.

    Bonne programmation.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  21. #18
    Bleyblue

    Re : Calculer rapidement

    Pour vérifier qu'un grand nombre est divisible par un autre j'avais vu une méthode il y a quelque temps au cours, j'ai exposé ça ici :

    http://forums.futura-sciences.com/thread54593.html

    Mais je ne me souviens plus si c'est valable pour nimporte quel nombre (faudrait que j'aille revoir )

  22. #19
    Pole

    Re : Calculer rapidement

    Citation Envoyé par Bleyblue
    Mais je ne me souviens plus si c'est valable pour nimporte quel nombre (faudrait que j'aille revoir )
    Eh non.

    En lisant le pdf de GMP, j'ai vu une méthode pour faire une division exacte (sans reste).

    234/13.
    On calcule 1/3(dernier chiffre du diviseur) mod 10
    (la base) 7.
    Dernier chiffre du dividende 4 : 4*7=28
    Le dernier chiffre du quotient est 8.
    8*13=104
    234-104=130
    On décale
    13
    Dernier chiffre du dividende 3 : 3*7=21
    Le 2ème chiffre du quotient est 1.
    1*13=13
    13-13=0
    Fini!
    234=13*18.

    Si le diviseur n'est pas premier avec la base, on divise le dividende et le diviseur par le pgcd. (Le pgcd étant plus petit ou égal à la base, la division à une complexité en
    O(l) pour un dividende de taille l)

    Le problème, c'est que c'est uniquement pour un reste de 0.

    @+.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

Sur le même thème :

Discussions similaires

  1. comment atteindre mon but rapidement?
    Par eli971 dans le forum Orientation après le BAC
    Réponses: 0
    Dernier message: 10/03/2007, 12h48
  2. besoin d'informations assez rapidement
    Par Lisbeth dans le forum Chimie
    Réponses: 1
    Dernier message: 22/02/2007, 20h54
  3. rapidement svp
    Par maxime16 dans le forum Physique
    Réponses: 1
    Dernier message: 06/02/2007, 09h24
  4. decharger rapidement un condensateur
    Par shinigami40 dans le forum Électronique
    Réponses: 1
    Dernier message: 25/05/2006, 13h37