111secondes pour multiplier 2^21701-1 par lui m=EAme...
Ce qui me fait deux nombres de 4094 chiffres en entr=E9e et un nombre de
8188 chiffres en sortie...
Seulement voila, le script que j'ai =E9cris (en perl, baaaaa) pour
bidouiller de mani=E8re p=E9dagogique sur les multiplications de grands
nombres me bouffe + de 500 Mo de ram pour faire l'op=E9ration.
Quand bien m=EAme j'aurais un peu fait ca a l'arrache (n'en doutez pas),
ca me parait tout de m=EAme beaucoup.
Du coup, les questions que je me/vous pose sont les suivantes :
1. Ca devrait se limiter =E0 quel ordre de grandeur normalement ?
2. Est-il possible de construire un algo qui travailler dans un espace
m=E9moire de taille finie ?
> 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 ?
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/Multiplication-Algorithms.html
2. Est-il possible de construire un algo qui travaille dans un espace mémoire de taille finie ?
Là dessus je ne sais pas répondre de tête, il faudrait consulter quelques références style Knuth...
-- DW
> 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 ?
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/Multiplication-Algorithms.html
2. Est-il possible de construire un algo qui travaille dans un espace
mémoire de taille finie ?
Là dessus je ne sais pas répondre de tête, il faudrait consulter
quelques références style Knuth...
> 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 ?
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/Multiplication-Algorithms.html
2. Est-il possible de construire un algo qui travaille dans un espace mémoire de taille finie ?
Là dessus je ne sais pas répondre de tête, il faudrait consulter quelques références style Knuth...
-- DW
Paul Gaborit
À (at) Thu, 9 Oct 2008 07:06:30 -0700 (PDT), Julien Vehent écrivait (wrote):
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.
Ê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";
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 ?
À des valeurs similaires à celles données ci-dessus.
2. Est-il possible de construire un algo qui travailler dans un espace mémoire de taille finie ?
Ç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 - <http://perso.enstimac.fr/~gaborit/>
À (at) Thu, 9 Oct 2008 07:06:30 -0700 (PDT),
Julien Vehent <julien.vehent@gmail.com> écrivait (wrote):
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.
Ê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";
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 ?
À des valeurs similaires à celles données ci-dessus.
2. Est-il possible de construire un algo qui travailler dans un espace
mémoire de taille finie ?
Ç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 - <http://perso.enstimac.fr/~gaborit/>
À (at) Thu, 9 Oct 2008 07:06:30 -0700 (PDT), Julien Vehent écrivait (wrote):
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.
Ê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";
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 ?
À des valeurs similaires à celles données ci-dessus.
2. Est-il possible de construire un algo qui travailler dans un espace mémoire de taille finie ?
Ç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 - <http://perso.enstimac.fr/~gaborit/>
remy
Julien Vehent a écrit :
bonjour
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,
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
Julien Vehent a écrit :
bonjour
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,
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
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,
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
Julien Vehent
On 9 oct, 17:21, remy ;> wrote:
Julien Vehent a écrit :
bonjour
> 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 d e > 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,
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 p ge 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.
On 9 oct, 17:21, remy <r...@fctpas.fr;> wrote:
Julien Vehent a écrit :
bonjour
> 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 d e
> 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,
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 p ge 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.
> 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 d e > 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,
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 p ge 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.
mpg
Le (on) jeudi 09 octobre 2008 16:44, Damien Wyart a écrit (wrote) :
pari se base sur gmp pour les calculs sur les entiers, voir par exemple http://gmplib.org/manual/Multiplication-Algorithms.html
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.
Le (on) jeudi 09 octobre 2008 16:44, Damien Wyart a écrit (wrote) :
pari se base sur gmp pour les calculs sur les entiers, voir par exemple
http://gmplib.org/manual/Multiplication-Algorithms.html
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.
Le (on) jeudi 09 octobre 2008 16:44, Damien Wyart a écrit (wrote) :
pari se base sur gmp pour les calculs sur les entiers, voir par exemple http://gmplib.org/manual/Multiplication-Algorithms.html
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.
Damien Wyart
> > pari se base sur gmp pour les calculs sur les entiers, voir par exemple > http://gmplib.org/manual/Multiplication-Algorithms.html
* mpg in fr.misc.cryptologie:
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.
En effet, comme la question n'était pas sur pari je ne suis pas trop entré dans les détails et n'ai pas revérifié mais tu as raison et même dans la branche de dev (que j'utilise et que je compile donc régulièrement avec --with-gmp), ça n'est pas le moteur par défaut.
Merci pour la précision !
-- DW
> > pari se base sur gmp pour les calculs sur les entiers, voir par exemple
> http://gmplib.org/manual/Multiplication-Algorithms.html
* mpg <mpg@elzevir.fr> in fr.misc.cryptologie:
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.
En effet, comme la question n'était pas sur pari je ne suis pas trop
entré dans les détails et n'ai pas revérifié mais tu as raison et même
dans la branche de dev (que j'utilise et que je compile donc
régulièrement avec --with-gmp), ça n'est pas le moteur par défaut.
> > pari se base sur gmp pour les calculs sur les entiers, voir par exemple > http://gmplib.org/manual/Multiplication-Algorithms.html
* mpg in fr.misc.cryptologie:
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.
En effet, comme la question n'était pas sur pari je ne suis pas trop entré dans les détails et n'ai pas revérifié mais tu as raison et même dans la branche de dev (que j'utilise et que je compile donc régulièrement avec --with-gmp), ça n'est pas le moteur par défaut.
Merci pour la précision !
-- DW
Julien Vehent
Me rendant bien compte que ma précédente version était pourrie, j'ai repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8 secondes et moi de 4Mo de mémoire.
Du coup, comme je me suis bien creusé la tête, je poste le script ci- dessous. Ca reste quand même du quick and dirty, et j'imagine (j'espere) que j'ai réinventé la roue, mais si ca apporte matière à discussion/optimisation pour le plaisir, c'est cool !
Note d'importance, ca ne marche pas si A est plus petit que B. Question d'implémentation quick n dirty ;)
Julien
------------------------------ #! /usr/bin/perl
#use strict; use Time::HiRes;
if (($ARGV[0] eq "-h") || ($ARGV[0] eq "--help")) { print "plmul2 : multiplicate two numbers whatever their respective sizes are.n", "use -v for verbose modenn", "j.vehent - oct 2008nn"; exit 0; }
my $verbose = 0; if ($ARGV[0] eq -v) { $verbose = 1; }
print "A = "; my $tA = <STDIN>; chomp $tA; print "B = "; my $tB = <STDIN>; chomp $tB;
my @tA = split(//,$tA); my @tB = split(//,$tB); my @A = reverse(@tA); my @B = reverse(@tB);
if ($verbose==1){ print "@tBnn";} if ($verbose==1){ print "table A = @Antable B = @Bn";}
my @RES;
my $initTime = [Time::HiRes::gettimeofday()];
my $colkeep=0; my $keep=0; for (my $i=0; $i<=$#A; $i++) { my $x=$i; my $j=0; my $acc=0; while ($x>=0) { $acc += ($B[$j]*$A[$x]); if ($verbose==1){ print "($B[$j]*$A[$x]) = $accn";}
$j++; $x--; }
my $add = $acc + $keep;
if ($verbose==1){ print "tacc $acc; add $add ($acc+$keep); ";}
$keep = int($add/10);
push(@RES,$add%10);
if ($verbose==1){ print "keep $keep; push $RES[$#RES]n";} } for (my $j=1;$j<=$#B;$j++) { my $x=$j; my $i=$#A; my $acc=0; while ($x<=$#B) { $acc += ($B[$x]*$A[$i]); if ($verbose==1){ print "($B[$x]*$A[$i]) = $accn";}
$i--; $x++; }
my $add = $acc + $keep;
if ($verbose==1){ print "tacc $acc; add $add ($acc+$keep); ";}
$keep = int($add/10);
push(@RES,$add%10);
if ($verbose==1){ print "keep $keep; push $RES[$#RES]n";}
if($j == $#B) { while ($keep>0) { push(@RES,$keep%10); $keep = int($keep/10); if ($verbose==1){ print "tt-->store $RES[$#RES] and keep $keep; n";} } } }
my $elapsed = Time::HiRes::tv_interval($initTime);
my @FINALRES = reverse(@RES); foreach my $i (@FINALRES) { print "$i"; } print "nncomputed in $elapsed secondsnn";
Me rendant bien compte que ma précédente version était pourrie, j'ai
repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8
secondes et moi de 4Mo de mémoire.
Du coup, comme je me suis bien creusé la tête, je poste le script ci-
dessous. Ca reste quand même du quick and dirty, et j'imagine
(j'espere) que j'ai réinventé la roue, mais si ca apporte matière à
discussion/optimisation pour le plaisir, c'est cool !
Note d'importance, ca ne marche pas si A est plus petit que B.
Question d'implémentation quick n dirty ;)
Julien
------------------------------
#! /usr/bin/perl
#use strict;
use Time::HiRes;
if (($ARGV[0] eq "-h") || ($ARGV[0] eq "--help"))
{
print "plmul2 : multiplicate two numbers whatever their respective
sizes are.n",
"use -v for verbose modenn",
"j.vehent - oct 2008nn";
exit 0;
}
my $verbose = 0;
if ($ARGV[0] eq -v)
{
$verbose = 1;
}
print "A = ";
my $tA = <STDIN>;
chomp $tA;
print "B = ";
my $tB = <STDIN>;
chomp $tB;
my @tA = split(//,$tA);
my @tB = split(//,$tB);
my @A = reverse(@tA);
my @B = reverse(@tB);
if ($verbose==1){ print "ncomputingn@tAnxn@tBnn";}
if ($verbose==1){ print "table A = @Antable B = @Bn";}
my @RES;
my $initTime = [Time::HiRes::gettimeofday()];
my $colkeep=0;
my $keep=0;
for (my $i=0; $i<=$#A; $i++)
{
my $x=$i;
my $j=0;
my $acc=0;
while ($x>=0)
{
$acc += ($B[$j]*$A[$x]);
if ($verbose==1){ print "($B[$j]*$A[$x]) = $accn";}
$j++;
$x--;
}
my $add = $acc + $keep;
if ($verbose==1){ print "tacc $acc; add $add ($acc+$keep); ";}
$keep = int($add/10);
push(@RES,$add%10);
if ($verbose==1){ print "keep $keep; push $RES[$#RES]n";}
}
for (my $j=1;$j<=$#B;$j++)
{
my $x=$j;
my $i=$#A;
my $acc=0;
while ($x<=$#B)
{
$acc += ($B[$x]*$A[$i]);
if ($verbose==1){ print "($B[$x]*$A[$i]) = $accn";}
$i--;
$x++;
}
my $add = $acc + $keep;
if ($verbose==1){ print "tacc $acc; add $add ($acc+$keep); ";}
$keep = int($add/10);
push(@RES,$add%10);
if ($verbose==1){ print "keep $keep; push $RES[$#RES]n";}
if($j == $#B)
{
while ($keep>0)
{
push(@RES,$keep%10);
$keep = int($keep/10);
if ($verbose==1){ print "tt-->store $RES[$#RES] and keep $keep;
n";}
}
}
}
my $elapsed = Time::HiRes::tv_interval($initTime);
my @FINALRES = reverse(@RES);
foreach my $i (@FINALRES)
{
print "$i";
}
print "nncomputed in $elapsed secondsnn";
Me rendant bien compte que ma précédente version était pourrie, j'ai repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8 secondes et moi de 4Mo de mémoire.
Du coup, comme je me suis bien creusé la tête, je poste le script ci- dessous. Ca reste quand même du quick and dirty, et j'imagine (j'espere) que j'ai réinventé la roue, mais si ca apporte matière à discussion/optimisation pour le plaisir, c'est cool !
Note d'importance, ca ne marche pas si A est plus petit que B. Question d'implémentation quick n dirty ;)
Julien
------------------------------ #! /usr/bin/perl
#use strict; use Time::HiRes;
if (($ARGV[0] eq "-h") || ($ARGV[0] eq "--help")) { print "plmul2 : multiplicate two numbers whatever their respective sizes are.n", "use -v for verbose modenn", "j.vehent - oct 2008nn"; exit 0; }
my $verbose = 0; if ($ARGV[0] eq -v) { $verbose = 1; }
print "A = "; my $tA = <STDIN>; chomp $tA; print "B = "; my $tB = <STDIN>; chomp $tB;
my @tA = split(//,$tA); my @tB = split(//,$tB); my @A = reverse(@tA); my @B = reverse(@tB);
if ($verbose==1){ print "@tBnn";} if ($verbose==1){ print "table A = @Antable B = @Bn";}
my @RES;
my $initTime = [Time::HiRes::gettimeofday()];
my $colkeep=0; my $keep=0; for (my $i=0; $i<=$#A; $i++) { my $x=$i; my $j=0; my $acc=0; while ($x>=0) { $acc += ($B[$j]*$A[$x]); if ($verbose==1){ print "($B[$j]*$A[$x]) = $accn";}
$j++; $x--; }
my $add = $acc + $keep;
if ($verbose==1){ print "tacc $acc; add $add ($acc+$keep); ";}
$keep = int($add/10);
push(@RES,$add%10);
if ($verbose==1){ print "keep $keep; push $RES[$#RES]n";} } for (my $j=1;$j<=$#B;$j++) { my $x=$j; my $i=$#A; my $acc=0; while ($x<=$#B) { $acc += ($B[$x]*$A[$i]); if ($verbose==1){ print "($B[$x]*$A[$i]) = $accn";}
$i--; $x++; }
my $add = $acc + $keep;
if ($verbose==1){ print "tacc $acc; add $add ($acc+$keep); ";}
$keep = int($add/10);
push(@RES,$add%10);
if ($verbose==1){ print "keep $keep; push $RES[$#RES]n";}
if($j == $#B) { while ($keep>0) { push(@RES,$keep%10); $keep = int($keep/10); if ($verbose==1){ print "tt-->store $RES[$#RES] and keep $keep; n";} } } }
my $elapsed = Time::HiRes::tv_interval($initTime);
my @FINALRES = reverse(@RES); foreach my $i (@FINALRES) { print "$i"; } print "nncomputed in $elapsed secondsnn";
Julien Vehent
On 10 oct, 13:27, Julien Vehent wrote:
Me rendant bien compte que ma précédente version était pourrie, j'a i repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8 secondes et moi de 4Mo de mémoire.
bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en 0.034s...... meme si on compare du perl a de l'assembleur, j'imagine que les algos implemetes par bc doivent etre beaucoup plus performant et tirer partie des capacites 32bits des machines.. (genre karatsuba)
On 10 oct, 13:27, Julien Vehent <julien.veh...@gmail.com> wrote:
Me rendant bien compte que ma précédente version était pourrie, j'a i
repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8
secondes et moi de 4Mo de mémoire.
bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en
0.034s......
meme si on compare du perl a de l'assembleur, j'imagine que les algos
implemetes par bc doivent etre beaucoup plus performant et tirer
partie des capacites 32bits des machines.. (genre karatsuba)
Me rendant bien compte que ma précédente version était pourrie, j'a i repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8 secondes et moi de 4Mo de mémoire.
bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en 0.034s...... meme si on compare du perl a de l'assembleur, j'imagine que les algos implemetes par bc doivent etre beaucoup plus performant et tirer partie des capacites 32bits des machines.. (genre karatsuba)
remy
Julien Vehent a écrit :
On 10 oct, 13:27, Julien Vehent wrote:
Me rendant bien compte que ma précédente version était pourrie, j'ai repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8 secondes et moi de 4Mo de mémoire.
bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en 0.034s...... meme si on compare du perl a de l'assembleur, j'imagine que les algos implemetes par bc doivent etre beaucoup plus performant et tirer partie des capacites 32bits des machines.. (genre karatsuba)
c'est dans les vieux pots que l'on fait la bonne confiture
en gros fais un décalage à gauche de la représentation en base 2 ce qui revient à multiplier par deux
a+ remy
Julien Vehent a écrit :
On 10 oct, 13:27, Julien Vehent <julien.veh...@gmail.com> wrote:
Me rendant bien compte que ma précédente version était pourrie, j'ai
repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8
secondes et moi de 4Mo de mémoire.
bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en
0.034s......
meme si on compare du perl a de l'assembleur, j'imagine que les algos
implemetes par bc doivent etre beaucoup plus performant et tirer
partie des capacites 32bits des machines.. (genre karatsuba)
c'est dans les vieux pots que l'on fait la bonne confiture
Me rendant bien compte que ma précédente version était pourrie, j'ai repris ca aujourd'hui.... et ca va beaucoup mieux !
Multiplication de deux nombres de 1774 chiffres (du random) en 2.8 secondes et moi de 4Mo de mémoire.
bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en 0.034s...... meme si on compare du perl a de l'assembleur, j'imagine que les algos implemetes par bc doivent etre beaucoup plus performant et tirer partie des capacites 32bits des machines.. (genre karatsuba)
c'est dans les vieux pots que l'on fait la bonne confiture
en gros fais un décalage à gauche de la représentation en base 2 ce qui revient à multiplier par deux
a+ remy
Julien Vehent
On 13 oct, 09:17, remy ;> wrote:
Julien Vehent a écrit :
> On 10 oct, 13:27, Julien Vehent wrote: >> Me rendant bien compte que ma précédente version était pourrie, j'ai >> repris ca aujourd'hui.... et ca va beaucoup mieux !
>> Multiplication de deux nombres de 1774 chiffres (du random) en 2.8 >> secondes et moi de 4Mo de mémoire.
> bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en > 0.034s...... > meme si on compare du perl a de l'assembleur, j'imagine que les algos > implemetes par bc doivent etre beaucoup plus performant et tirer > partie des capacites 32bits des machines.. (genre karatsuba)
c'est dans les vieux pots que l'on fait la bonne confiture
en gros fais un décalage à gauche de la représentation en base 2 ce qui revient à multiplier par deux
a+ remy
et quand A ou B est sup. a 2^32, tu fais comment pour les faire rentrer dans la mémoire ?
On 13 oct, 09:17, remy <r...@fctpas.fr;> wrote:
Julien Vehent a écrit :
> On 10 oct, 13:27, Julien Vehent <julien.veh...@gmail.com> wrote:
>> Me rendant bien compte que ma précédente version était pourrie, j'ai
>> repris ca aujourd'hui.... et ca va beaucoup mieux !
>> Multiplication de deux nombres de 1774 chiffres (du random) en 2.8
>> secondes et moi de 4Mo de mémoire.
> bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en
> 0.034s......
> meme si on compare du perl a de l'assembleur, j'imagine que les algos
> implemetes par bc doivent etre beaucoup plus performant et tirer
> partie des capacites 32bits des machines.. (genre karatsuba)
c'est dans les vieux pots que l'on fait la bonne confiture
> On 10 oct, 13:27, Julien Vehent wrote: >> Me rendant bien compte que ma précédente version était pourrie, j'ai >> repris ca aujourd'hui.... et ca va beaucoup mieux !
>> Multiplication de deux nombres de 1774 chiffres (du random) en 2.8 >> secondes et moi de 4Mo de mémoire.
> bon, c'est pas encore ca... je fais en 27 secondes ce que bc fait en > 0.034s...... > meme si on compare du perl a de l'assembleur, j'imagine que les algos > implemetes par bc doivent etre beaucoup plus performant et tirer > partie des capacites 32bits des machines.. (genre karatsuba)
c'est dans les vieux pots que l'on fait la bonne confiture
