aide pour programmer x exponentiations d'exposants n bits

cyrille <cyrille@news.net> dixit:

Bonjour,

je ne m'y connais pas en math,
et je voudrais faire un petit benchmarck informatique sur la phrase suivante :

1606 exponentiations d'exposants 160 bits

comment celà s'écrit il en Java ou en C++ ou C# ou Visual Basic ou ...

Merci beaucoup !
cyrille

Voir http://www.cacr.math.uwaterloo.ca/hac/index.html

Le chapitre 2 algorithme 2.143 fait l'exponentiation modulaire. Si tu
veux seulement l'exponentation (pas modulaire) il suffit d'ignorer
"mod n" aux lignes 4.1 et 4.2.

Voir aussi le chapitre 14.6 pour des algorithmes un peu plus
efficaces.

Sylvain Croussette wrote:

cyrille <cyrille@news.net> dixit:

Bonjour,

je ne m'y connais pas en math,
et je voudrais faire un petit benchmarck informatique sur la phrase sui vante :

1606 exponentiations d'exposants 160 bits

comment celà s'écrit il en Java ou en C++ ou C# ou Visual Basic ou ...

Merci beaucoup !
cyrille

Voir http://www.cacr.math.uwaterloo.ca/hac/index.html

Le chapitre 2 algorithme 2.143 fait l'exponentiation modulaire. Si tu
veux seulement l'exponentation (pas modulaire) il suffit d'ignorer
"mod n" aux lignes 4.1 et 4.2.

Voir aussi le chapitre 14.6 pour des algorithmes un peu plus
efficaces.

Bonjou
et merci beaucoup d'avoir pris le temps de me fournir des liens aussi d étaillés.
j'ais bien lu le doc cité, mais mes connaissances en math sont telles q ue je ne suis toujours pas sûr d'avoir compris.
Peut être que oui, peut être que non.

Alors pour m'aider il faudrait me donner un bout de code.

En fait, j'en ais juste besoin pour faire des tests de vitesses sur diffé rentes configurations de machines.

cyrille

Salut....


Le Thu, 14 Oct 2004 10:30:10 +0200, cyrille a écrit de ses petites mains
habiles :

Voir http://www.cacr.math.uwaterloo.ca/hac/index.html

Le chapitre 2 algorithme 2.143 fait l'exponentiation modulaire. Si tu
veux seulement l'exponentation (pas modulaire) il suffit d'ignorer "mod
n" aux lignes 4.1 et 4.2.

Voir aussi le chapitre 14.6 pour des algorithmes un peu plus efficaces.


Bonjou

et merci beaucoup d'avoir pris le temps de me fournir des liens aussi
détaillés. j'ais bien lu le doc cité, mais mes connaissances en math
sont telles que je ne suis toujours pas sûr d'avoir compris. Peut être
que oui, peut être que non.

Alors pour m'aider il faudrait me donner un bout de code.

Il serait possible de reprendre cet algorithme mais faire de
l'exponentiation avec un exposant de 160 bits... bonjour chez vous... En
C, pour manipuler de si grands nombres, il faut alors utiliser la libGMP,
et alors, ça devient presque ridicule dans ce cas de réécrire
l'exponentiation car la fonction est déjà prête...

http://www.swox.com/gmp/manual/Integer-Exponentiation.html#Integer%20Exponentiation


Quoi qu'il en soit, voici la tête d'une telle fonction (je n'ai pas tapé
ds la libGMP pour faire simple -> donc pas la peine de penser se servir de
cette fonction pour des exposants de 160 bits...) :

-------(snip)--------------------(snip)--------------------(snip)-------------

#define NB_OF_DIGITS_4_EXP 10

/* #define MODULAR */

#ifdef MODULAR
#define MODULO 100 /* Up to you */ #endif


int exponentiation (int base, int exposant) {
int i;
int res = 1;
int temp = base;

if (exposant == 0) return res;
if ((exposant & 0x01) == 1) temp = base;

for (i = 1; i < NB_OF_DIGITS_4_EXP; i++)
{
temp *= temp;
#ifdef MODULAR
temp %= MODULO;
#endif
if (get_bit (exposant, i) == 1)
{
res *= temp;
#ifdef MODULAR
temp %= MODULO;
#endif
}
}

return res;
}

int
main (int argc, char **argv)
{
if (argc < 3)
{
printf ("Erreur...n Syntaxe : %s base exposantnn", argv[0]);
return -1;
}
printf ("Le résultat est : %d^%d = %dnn", atoi (argv[1]), atoi
(argv[2]),
exponentiation (atoi (argv[1]), atoi (argv[2])));
return 0;
}


-------(snip)--------------------(snip)--------------------(snip)-------------

C'est fait à la va ultra vite, donc voilà... Pas vérifié mais c le
principe...
Si, malgré tout, tu as besoin d'aide, n'hésite pas...

Yanisto.