Calculer rapidement

[SPH]

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
-----

[invité576543]

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,

[SPH]

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 ??

[invitec314d025]

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

[A voir en vidéo sur Futura]

[SPH]

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 ?

[invité576543]

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,

[SPH]

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

[invitec314d025]

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

[SPH]

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 ??

[invitec314d025]

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.

[SPH]

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

[invite3d7be5ae]

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à.

[invitec314d025]

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

[invitec314d025]

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 ...

[invite3d7be5ae]

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.

[SPH]

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

[invite3d7be5ae]

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.

[Bleyblue]

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 )

[invite3d7be5ae]

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.

@+.