multiplication de grands nombres
Le
Julien Vehent
111secondes pour multiplier 2^21701-1 par lui même
Ce qui me fait deux nombres de 4094 chiffres en entrée et un nombre de
8188 chiffres en sortie
Seulement voila, le script que j'ai écris (en perl, baaaaa) pour
bidouiller de manière pédagogique sur les multiplications de grands
nombres me bouffe + de 500 Mo de ram pour faire l'opération.
Quand bien même j'aurais un peu fait ca a l'arrache (n'en doutez pas),
ca me parait tout de même beaucoup.
Du coup, les questions que je me/vous pose sont les suivantes :
1. Ca devrait se limiter à quel ordre de grandeur normalement ?
2. Est-il possible de construire un algo qui travailler dans un espace
mémoire de taille finie ?
Merci,
Julien
Ce qui me fait deux nombres de 4094 chiffres en entrée et un nombre de
8188 chiffres en sortie
Seulement voila, le script que j'ai écris (en perl, baaaaa) pour
bidouiller de manière pédagogique sur les multiplications de grands
nombres me bouffe + de 500 Mo de ram pour faire l'opération.
Quand bien même j'aurais un peu fait ca a l'arrache (n'en doutez pas),
ca me parait tout de même beaucoup.
Du coup, les questions que je me/vous pose sont les suivantes :
1. Ca devrait se limiter à quel ordre de grandeur normalement ?
2. Est-il possible de construire un algo qui travailler dans un espace
mémoire de taille finie ?
Merci,
Julien
Poser une question
En faisant un test rapide avec pari/gp
(http://pari.math.u-bordeaux.fr/), j'obtiens le résultat instantanément
et la consommation mémoire semble très peu bouger.
pari se base sur gmp pour les calculs sur les entiers, voir par exemple
http://gmplib.org/manual/Multiplica...ithms.html
Là dessus je ne sais pas répondre de tête, il faudrait consulter
quelques références style Knuth...
--
DW
Julien Vehent
Êtes-vous sûr de votre implémentation ? 2^21701-1 s'écrit avec 21700
chiffres binaires, donc 5425 chiffres hexa...
Je viens d'ecrire en Perl, un script qui fait le calcul
ci-dessus. Résultats :
- 2^21701-1 s'écrit avec 6533 chiffres décimaux.
- son carré s'écrit avec 13067 chiffres décimaux.
- la calcul prend 1 seconde.
- je n'ai pas mesuré l'occupation mémoire.
Voici le script :
###########################
#!/usr/bin/perl -w
use strict;
use warnings;
use bigint;
open my $log, ">" , "bigint-res.txt"
or die "Can't write 'bigint-res.txt' : $!n";
my $a = 2 ** 21701 - 1;
my $b = $a * $a;
print $log "$an";
print $log "$bn";
###########################
À des valeurs similaires à celles données ci-dessus.
Ça dépend des données et des calculs à réaliser. C'est au moins
proportionnel à la taille des données (en supposant qu'on stocke les
données d'entrée et de sortie). ;-)
--
Paul Gaborit -
bonjour
il y a un truc qui m'échappe
time bc pow
real 0m6.985s
user 0m6.128s
sys 0m0.040s
less pow
(2^221701-1)^2
quit
cat /proc/cpuinfo
processor : 0
vendor_id : AuthenticAMD
cpu family : 6
model : 3
model name : AMD Duron(tm) Processor
stepping : 1
cpu MHz : 800.097
cache size : 64 KB
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 1
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca
cmov pat pse36 mmx fxsr syscall mmxext 3dnowext 3dnow up
bogomips : 1602.20
clflush size : 32
en gros un truc antédiluvien
a+ remy
Et oui, tout cela est bien exact, mais avant de savoir marcher, il
faut faire du quatres pattes :)
La prog et les maths ne sont pas mon domaine de prédilection, donc je
tatonne.
Effectivement les valeurs de longueurs que j'ai donnée sont fausses,
petit soucis de copié collé.
Je vais reprendre mon algo (de base) et le mettre en C pour voir déjà
comment ça tourne.
Après je regarderais la conso mémoire.
En tout cas, merci pour les pointeurs.
Je voudrais pas dire de bêtises, mais il me semble que ce n'est pas vrai
pour toutes les installations de GP, et que c'est plutôt une option de
compilation et qu'on peut utiliser du code propre à pari/gp pour ça (qui
est moins performant que gmp). Je ne sais plus quelle est l'option par
défaut.
Manuel.