multiplication de grands nombres

> 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

À (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";

my $a = 2 ** 21701 - 1;
my $b = $a * $a;

print $log "$an";
print $log "$bn";
###########################

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

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

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.

Après je regarderais la conso mémoire.

En tout cas, merci pour les pointeurs.

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.

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

Merci pour la précision !

--
DW

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

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)

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

http://www.recreomath.qc.ca/dict_russe_multiplication.htm


en gros fais un décalage à gauche de la représentation en base 2
ce qui revient à multiplier par deux

a+ remy

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

http://www.recreomath.qc.ca/dict_russe_multiplication.htm

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 ?