Je viens à nouveau vers vous pour une nouvelle problématique :-) .
Je me suis mis à coder mon propre type de grand entier en C++. Pour coder la multiplication, j'utilise de façon naïve la somme n fois du nombre en question sauf que c'est long pour de grand nombre. Je voulais savoir si je n'avais pas moyen d'utiliser l'opérateur natif * et de gérer le débordement. Je peux mettre mon code à disposition si besoin.
En bonus, la même problématique avec la division et le modulo.
Merci pour votre aide,
P'tit Ju
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
Pour multiplier de grands nombres entiers, on peut couper le nombre en 2 parties, un poids fort et un poids faible.
Par exemple, pour des grands nombre de taille 20 bits. On veut faire x * y, on utilise xh=x >> 10, xl=x & 0x3FF, yh=y >> 10, yl=y & 0x3FF.
Le produit x*y est [(xh<<10+xl].[(yh<<10+yl] = (xl.yl) + [(xh.yl+xl.yh)<<10] + [(xh.yh)<<20]. Les trois membres peuvent être calculé sans dépassement sur 20 bits. Seule leur addition peut produire un dépassement
Finalement, pour la multiplication et la division, j'ai réussi à m'en sortir avec les opérateurs << et >>. Pour le modulo, je passe par la division entière du coup.
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
Une idée est de faire comme dit Rouloude, une chaine de caractère et de calculer comme on le faisait à l'école primaire, mais tu peux aller plus loin : au lieu de mettre les chiffres décimaux, tu fais un tableau (dynamique) de int32 et ainsi tu fais tes calculs sur une base 2^32
Si tu promeus chaque calcul en int64 tu peux voir si tu débordes (et calculer tes retenus) car hélas il n'y a pas de façon native de récupérer le flag CARRY des processeurs (pas standard) qui s'active en cas de débordement.
Utiliser << et faire des additions ensuite est une méthode qui va bien aussi !
Quand tu veux multiplier par un nombre, tu regardes quels bits de ton multiplicateur sont à 1, et fais des << et tes sommes le tout.
D'ailleurs, la NES (console passionnante) ne savait pas multiplier, donc ils rusaient souvent comme ça, en s'arrangeant pour faire des multiplications en puissance de 2 ou bien décomposer et faire une somme.
Voici le code que j'ai utilisé pour la multiplication (pour a * b, *this est a et other est b):
Integer result{0};
while (other > 0)
{
if (other & 1)
result += *this;
*this <<= 1;
other >>= 1;
}
*this = result;
Integer est une classe template contenant un vector de T, donc si T est unsigned long long, ça fait une base de 2^64.
Là où ça se corse, c'est pour la division...
Le code suivant, tiré de ChatGPT, ne se comporte pas bien pour afficher en base décimale par division et modulo successif par 10 de 94882770404074832568499 (pour a / b, *this est a et other est b).
Integer q{0};
auto temp_n{*this};
auto temp_d{other};
Integer shift{0};
while (temp_d <= temp_n)
{
temp_d <<= 1;
++shift;
}
while (shift > 0)
{
temp_d >>= 1;
--shift;
if (temp_n >= temp_d)
{
temp_n -= temp_d;
q |= Integer{1} << shift;
}
}
J'ai beau chercher, je n'arrive pas à m'en dépatouiller, so help ;-) .
- Edité par P'tit Ju 30 décembre 2024 à 19:05:08
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
Le code suivant, tiré de ChatGPT, ne se comporte pas bien pour afficher en base décimale par division et modulo successif par 10 de 94882770404074832568499 (pour a / b, *this est a et other est b).
Integer q{0};
auto temp_n{*this};
auto temp_d{other};
Integer shift{0};
while (temp_d <= temp_n)
{
temp_d <<= 1;
++shift;
}
while (shift > 0)
{
temp_d >>= 1;
--shift;
if (temp_n >= temp_d)
{
temp_n -= temp_d;
q |= Integer{1} << shift;
}
}
J'ai beau cherché, je n'arrive pas à m'en dépatouiller, so help ;-) .
- Edité par P'tit Ju il y a 3 minutes
J'ai beau chercher, je ne vois pas d'affichage là dedans.
Au fait, c'est quoi le but du jeu ?
réfléchir aux algorithmes de calcul, les programmer pour vérifier que ça marche
ou regarder ce que chatgpt peut halluciner à partir de bouts de code recopiés ici ou là ?
- Edité par michelbillaud 30 décembre 2024 à 19:09:22
Pour la division, c'est nettement plus complexe que la multiplication. Il y a pleins de méthodes possibles. Une des plus 'simples' consiste à faire comme on a appris au primaire, on remplace juste 'chiffre' par une autre taille par exemple un 'octet'. Exemple, on veux diviser les 4 octets (122 17 200 43) par les 2 octets (23 117). On pose la division:
122 17 200 43 | 23 117
+----------
| ?
|
Pour trouver le 1er chiffre/octet, on doit d'abord chercher combien de chiffre/octet 0 il faut ajouter à droite de 23 117. On doit obtenir un nombre juste plus petit que (122 17 200 43). On trouve ici 2 zéros nécessaires.
122 17 200 43 | 23 117
+----------
| ?
| 23 117 x ? Combien de fois y a-t-il (23 117) dans (122 17) ?
Le 1er chiffre est: combien de fois y a-t-il (23 117) dans (122 17)? En première approximation, on calcule 122/23 pour trouver 5. Mais ça n'est qu'une approximation, le vrai chiffre/octet peut être plus ou moins! On calcule 5 * (23 117), on trouve (117 73) qui est plus petit que (122 117), si on essaie avec 6 c'est trop grand. 5 est bien le premier chiffre/octet.
122 17 200 43 | 23 117
- 117 73 +----------
--------- | 5 ? ? on soustrait 5 x (23 117) de (122 17)
= 5 200 | on obtient un reste donc un nombre entre 0 et (23 116)
Pour le chiffre/octet suivant, on recommence:
122 17 200 43 | 23 117
- 117 73 +---------- on récupère le chiffre/octet suivant du dividende
--------- | 5 ? ?
= 4 200 200 |
| 23 117 x ? combien de fois y a-t-il (23 117) dans (4 200 200) ?
En première approximation, on a le chiffre/octet 53 = (4 200) / 23. On calcule 53 * (23 117) = (4 219 53) trop grand. On essaie un plus petit 52. 52 * (23 117) = (4 195 196) qui est plus petit que (4 200 200)
Le chiffre/octet suivant est proche de (5 4) / 23 = 55. On calcule 55 * (23 117) = (5 10 23). Trop grand on calcule 54 * (23 117) = (4 242 174), qui est plus petit, c'est 54.
On pourrait aussi tout convertir en décimal et diviser une séquence de chiffres par une séquence de chiffres. Ça demande des divisions modulos supplémentaires sans simplifier le traitement de la division. On peut aussi prendre comme unité le bit plutôt que l'octet, ça va nécessiter beaucoup plus d'étapes mais la recherche de chaque chiffre/bit est plus immédiate le chiffre/bit étant 0 ou 1 et le produit à vérifier est nul ou égal au diviseur, mais chaque soustraction va nécessiter un décalage de bits au lieu d'octets.
Il ne reste plus qu'à mettre cela sous forme de code.
J'ai essayé d'implémenter l'algorithme de la page Wikipédia en anglais mais j'ai également un problème pour de très grands nombres (l'assertion abs() == q*other.abs()+r est fausse alors qu'elle devrait être vraie, à moins que l'opérateur *, + ou - présente une coquille également...).
EDIT : Pour la multiplication, j'implémente l'algorithme de Karatsuba mais je ne comprends pas pourquoi j'ai une erreur critique (Critical error detected c0000374) dans la libération de y1 (destructeur par défaut), je ne fais pourtant pas de gestion de mémoire manuelle...
- Edité par P'tit Ju 2 janvier 2025 à 9:43:56
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
Je viens de jeter un coup d'oeil (rapide) à ton code.
a- Il n'y pas trop de raison d'avoir des digits qui soient autre chose que des `std::uint64_t`, ou peut-être des `std::uint_max_t`. Si l'objectif est bien d'avoir des grands entiers uniquement.
Le mélange n'a de sens que si on veut économiser des octets. Mais sur de la taille variable, est-ce bien utile? (dans le cas des std::bitset, j'avais justement râlé car quand on sait à la compilation que le nombre de bits est <=8, <=16, ou <=32, il n'y a pas besoin d'occuper 64 bits à chaque fois)
=> il y a moyen de simplifier énormément ici.
Tout ça me fait penser que des optims à la SSO pourraient être employées.
a - C'est pas faux, j'avais hésité en me disant que le template pourrait être plus générique pour changer le type au besoin.
c - J'y ai pensé après coup :-) .
d - C'est sans doute possible mais j'avoue être moins à l'aise pour savoir comment l'ajouter à part peut-être le mettre partout et que le compilateur me le rejette. Des conseils là-dessus ?
J'ai toujours mon problème de destructeur.
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
constexpr tu peux le mettre à quasi toutes les fonctions, mais... avec des vector sous le capot, il faut au moins du C++20 (IIRC)
L'erreur critique sur la destruction est très clairement le signe d'un UB. Si tu es dans le monde Linux, je te conseille d'activer les sanitizer address et undefined. Sous windows, il parait qu'il y a moyen avec les derniers VC++, mai je n'ai encore jamais regardé. Je parie sur le dépassement de borne.
Alors j'ai activé le sanitizer sur ma machine virtuelle Linux et j'obtiens le message d'erreur suivant que je n'arrive pas à bien comprendre (problème sur le reserve me semble-t-il ?) :
=================================================================
==3257==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200045b988 at pc 0x58c4946b5059 bp 0x7ffe870ecf30 sp 0x7ffe870ecf20
READ of size 8 at 0x60200045b988 thread T0
#0 0x58c4946b5058 in std::reverse_iterator<unsigned long long*> std::__copy_move<false, false, std::random_access_iterator_tag>::__copy_m<std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*> >(std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*>) /usr/include/c++/11/bits/stl_algobase.h:385
#1 0x58c4946b3a9f in std::reverse_iterator<unsigned long long*> std::__copy_move_a2<false, std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*> >(std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*>) /usr/include/c++/11/bits/stl_algobase.h:495
#2 0x58c4946b013c in std::reverse_iterator<unsigned long long*> std::__copy_move_a1<false, std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*> >(std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*>) /usr/include/c++/11/bits/stl_algobase.h:522
#3 0x58c4946ab272 in std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > > std::__copy_move_a<false, std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > >, std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > > >(std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > >, std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > >, std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > >) /usr/include/c++/11/bits/stl_algobase.h:532
#4 0x58c4946a2de6 in std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > > std::copy<std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > >, std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > > >(std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > >, std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > >, std::reverse_iterator<__gnu_cxx::__normal_iterator<unsigned long long*, std::vector<unsigned long long, std::allocator<unsigned long long> > > >) /usr/include/c++/11/bits/stl_algobase.h:620
#5 0x58c494694e06 in Integer<unsigned long long, void>::operator*=(Integer<unsigned long long, void> const&) ../TestInteger/Integer.h:374
#6 0x58c4946901e9 in Integer<unsigned long long, void> operator*<unsigned long long, int>(int const&, Integer<unsigned long long, void> const&) ../TestInteger/Integer.h:1757
#7 0x58c49467b94d in Integer<unsigned long long, void>::Integer(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, unsigned long) ../TestInteger/Integer.h:173
#8 0x58c494659707 in Integer<unsigned long long, void>::Integer(char const*, unsigned long) ../TestInteger/Integer.h:87
#9 0x58c494635350 in TestInteger::testToString() ../TestInteger/testinteger.cpp:496
#10 0x58c494636bae in TestInteger::qt_static_metacall(QObject*, QMetaObject::Call, int, void**) testinteger.moc:147
#11 0x705a860c525a in QMetaMethod::invoke(QObject*, Qt::ConnectionType, QGenericReturnArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument) const (/usr/lib/x86_64-linux-gnu/libQt5Core.so.5+0x2c525a)
#12 0x705a8766f382 (/usr/lib/x86_64-linux-gnu/libQt5Test.so.5+0x1c382)
#13 0x705a8766fe1a (/usr/lib/x86_64-linux-gnu/libQt5Test.so.5+0x1ce1a)
#14 0x705a87670378 (/usr/lib/x86_64-linux-gnu/libQt5Test.so.5+0x1d378)
#15 0x705a87670863 in QTest::qRun() (/usr/lib/x86_64-linux-gnu/libQt5Test.so.5+0x1d863)
#16 0x705a87670c3f in QTest::qExec(QObject*, int, char**) (/usr/lib/x86_64-linux-gnu/libQt5Test.so.5+0x1dc3f)
#17 0x58c49463697f in main ../TestInteger/testinteger.cpp:517
#18 0x705a85629d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
#19 0x705a85629e3f in __libc_start_main_impl ../csu/libc-start.c:392
#20 0x58c494614384 in _start (/home/julien/Documents/programmation/cpp/build-TestInteger-Desktop-Debug/TestInteger+0xf384)
0x60200045b988 is located 8 bytes to the left of 8-byte region [0x60200045b990,0x60200045b998)
allocated by thread T0 here:
#0 0x705a86cb61e7 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:99
#1 0x58c4946ae8db in __gnu_cxx::new_allocator<unsigned long long>::allocate(unsigned long, void const*) /usr/include/c++/11/ext/new_allocator.h:127
#2 0x58c4946a6fd5 in std::allocator_traits<std::allocator<unsigned long long> >::allocate(std::allocator<unsigned long long>&, unsigned long) /usr/include/c++/11/bits/alloc_traits.h:464
#3 0x58c49469c88d in std::_Vector_base<unsigned long long, std::allocator<unsigned long long> >::_M_allocate(unsigned long) /usr/include/c++/11/bits/stl_vector.h:346
#4 0x58c49468422e in std::vector<unsigned long long, std::allocator<unsigned long long> >::reserve(unsigned long) /usr/include/c++/11/bits/vector.tcc:78
#5 0x58c494679a81 in Integer<unsigned long long, void>::Integer<int>(int) ../TestInteger/Integer.h:41
#6 0x58c4946901d3 in Integer<unsigned long long, void> operator*<unsigned long long, int>(int const&, Integer<unsigned long long, void> const&) ../TestInteger/Integer.h:1757
#7 0x58c49467b94d in Integer<unsigned long long, void>::Integer(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, unsigned long) ../TestInteger/Integer.h:173
#8 0x58c494659707 in Integer<unsigned long long, void>::Integer(char const*, unsigned long) ../TestInteger/Integer.h:87
#9 0x58c494635350 in TestInteger::testToString() ../TestInteger/testinteger.cpp:496
#10 0x58c494636bae in TestInteger::qt_static_metacall(QObject*, QMetaObject::Call, int, void**) testinteger.moc:147
#11 0x705a860c525a in QMetaMethod::invoke(QObject*, Qt::ConnectionType, QGenericReturnArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument) const (/usr/lib/x86_64-linux-gnu/libQt5Core.so.5+0x2c525a)
#12 0x705a8766f382 (/usr/lib/x86_64-linux-gnu/libQt5Test.so.5+0x1c382)
#13 0x705a8766fe1a (/usr/lib/x86_64-linux-gnu/libQt5Test.so.5+0x1ce1a)
SUMMARY: AddressSanitizer: heap-buffer-overflow /usr/include/c++/11/bits/stl_algobase.h:385 in std::reverse_iterator<unsigned long long*> std::__copy_move<false, false, std::random_access_iterator_tag>::__copy_m<std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*> >(std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*>, std::reverse_iterator<unsigned long long*>)
Shadow bytes around the buggy address:
0x0c04800836e0: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c04800836f0: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c0480083700: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c0480083710: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c0480083720: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
=>0x0c0480083730: fa[fa]00 fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c0480083740: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa fa fa
0x0c0480083750: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0480083760: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0480083770: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c0480083780: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==3257==ABORTING
- Edité par P'tit Ju 3 janvier 2025 à 9:00:13
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
Ligne 9 (de ton copier-coller), c'est l'endroit où la lecture hors bornes a lieu.
Et line 33, c'est la ligne où l'allocation qui t'a donné la mémoire à côté de laquelle tu tapes.
Normalement, les sanitizers peuvent indiquer la ligne de code C++ qui correspond à l'endroit qui est détecté. Il y a moyen de partir dans gdb aussi pour inspecter l'état du programme (avec `export UBSAN_OPTIONS=print_stacktrace=1:halt_on_error=1` ?)
J'ai pu résoudre le problème et ça venait bien du std::copy où j'avais plus d'éléments à copier qu'à recevoir.
Comme un train peut en cacher un autre, j'ai un nouveau problème (j'espère le dernier). Mon code plante en tout début de constructeur. J'essaye de mieux comprendre ce qu'il se passe pour donner des détails (sans doute un problème en rapport avec la division).
EDIT : Du coup, j'ai résolu le problème précédent. Par contre, j'ai une division euclidienne qui ne me donne pas le bon résultat (calculé avec Python) sur de très grands nombres (cf. dernier test de testUnsignedLongLong) et là, je sèche pour trouver pourquoi (ça semble venir de la multiplication apparemment)... J'ai codé une version itérative de l'algorithme récursif de https://www.geeksforgeeks.org/find-quotient-and-remainder-of-two-integer-without-using-division-operators/.
EDIT2 : J'ai résolu le problème du précédent EDIT, mon opérateur <<= avait une coquille et qui est utilisé dans la multiplication. Par contre, j'ai trouvé un autre exemple qui ne fonctionne pas (le code du GitHub est à jour), décidément ^^' .
EDIT3 : J'ai résolu mon précédent problème en rajoutant des assertions avec GMP. Je passe désormais tous les tests (sauf celui du grand nombre premier qui semble trop long, alors qu'avec GMP c'est instantané, je ne sais pas si c'est parce que l'algorithme de la division n'est pas assez efficace [le débogage m'indique que c'est la ligne 1471 "a = a % number + 1;" qui prend du temps par exemple] --') ! Je ne sais pas si l'algorithme page 4 de https://gmplib.org/~tege/divcnst-pldi94.pdf est plus rapide, en tout cas, j'ai du mal à comprendre, s'il y a preneur pour me l'expliquer. La méthode 1 de https://stackoverflow.com/questions/18788933/how-to-divide-large-numbers-and-what-algorithm-to-use a l'air intéressante mais le site n'est plus disponible...
@Dalfab, je suis en train de voir pour implémenter ta méthode. Lors de la troisième étape de calcul, c'est plutôt 4 200 que 5 200 non ? Et quid si ce sont des unsigned long long et non des unsigned char et que 4200 dépasse la capacité ? Bon, je galère à l'implémentation et j'aimerais bien avoir si possible quelques précisions supplémentaires si on utilise directement un unsigned long long plutôt qu'un unsigned char pour que je comprenne bien la méthodologie (à moins de gérer des groupes de 32 bits et gérer le débordement avec le reste dans 64 bits).
- Edité par P'tit Ju 8 janvier 2025 à 20:32:54
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
J'ai tenté de faire une classe BigInt une fois mais elle est trop lente pour générer de très grand nombres premiers et je ne sais pas comment faire pour optimiser.
#include "../../../include/odfaeg/Math/bigInt.hpp"
using namespace std;
namespace odfaeg {
BigInt::BigInt(const std::string& number, unsigned int base) {
this->base = base;
positif = (number.at(number.length()-1) != '-') ? true : false;
nbChiffres = (positif) ? number.length() : number.length() - 1;
for (unsigned int i = 0; i < nbChiffres; i++) {
unsigned int c;
if (number.at(i) >= 48 && number.at(i) <= 57){
c = number.at(i) - 48;
} else if (number.at(i) >= 65) {
c = number.at(i) - 55;
}
chiffres.push_back(c);
}
}
void BigInt::setStr(const std::string& number, unsigned int base) {
chiffres.clear();
this->base = base;
positif = (number.at(number.length()-1) != '-') ? true : false;
nbChiffres = (positif) ? number.length() : number.length() - 1;
for (unsigned int i = 0; i < nbChiffres; i++) {
unsigned int c;
if (number.at(i) >= 48 && number.at(i) <= 57){
c = number.at(i) - 48;
} else if (number.at(i) >= 65) {
c = number.at(i) - 55;
}
chiffres.push_back(c);
}
}
BigInt::BigInt(unsigned long long integer, bool positif, unsigned int b) {
this->positif = positif;
this->base = b;
nbChiffres = 0;
if (integer > 0) {
if (base < std::numeric_limits<unsigned int>::max()) {
unsigned long long int max = 1LL;
while (integer >= max)
max *= base;
max /= base;
while (max > 0) {
unsigned long long int c;
c = integer / max;
computeNbC(c);
chiffres.push_back(c);
integer %= max;
max /= b;
}
} else {
unsigned long long int c = integer / base;
computeNbC(c);
chiffres.push_back(c);
integer %= base;
computeNbC(integer);
}
}
}
BigInt BigInt::sqrt() {
BigInt z = *this;
BigInt rst;
int max = 8; // to define maximum digit
int i;
BigInt j(1, true, base);
BigInt dix(10, true, base);
BigInt bi (max, true, base);
BigInt two(2, true, base);
for(i = max ; i >= 0 ; i--){
// value must be bigger then 0
if(z - ((two * rst ) + ( j * dix.pow(i))*( j * dix.pow(i))) >= 0)
{
while( z - (( two * rst ) + ( j * dix.pow(i)))*( j * dix.pow(i)) >= 0
&& j >= 1)
{
j++;
}
j--; //correct the extra value by minus one to j
z -= (( two * rst ) + ( j * dix.pow(i)))*( j * dix.pow(i)); //find value of z25:
rst += j * dix.pow(i); // find sum of a
j = 1;
}
}
return rst;
}
void BigInt::computeNbC (unsigned long long int c) {
unsigned int nb = base;
unsigned int i = 1;
while (c >= nb) {
nb *= base;
i++;
}
nbChiffres += i;
}
unsigned int BigInt::getNbChiffres() {
return nbChiffres;
}
BigInt BigInt::genRandom (unsigned int nbBits, unsigned int base) {
math::Math::initSeed();
unsigned int nearestPowerOfTwo = math::Math::logn(base, 2);
base = math::Math::power(2, nearestPowerOfTwo);
BigInt n;
n.base = base;
n.nbChiffres = (nearestPowerOfTwo == 1) ? nbBits : nbBits / nearestPowerOfTwo;
do {
for (unsigned long long int i = 0; i < n.nbChiffres; ++i) {
unsigned int c = math::Math::random(base);
n.chiffres.push_back(c);
}
} while (n.isNull());
n.shorten();
return n;
}
BigInt BigInt::genPrime(unsigned int nbBits, unsigned int base) {
BigInt p;
do {
p = genRandom(nbBits, base);
} while(!miller(nbBits, p));
return p;
}
bool BigInt::isPrime(unsigned int nbBits, BigInt& p) {
// on effectue NB_ITER fois la boucle.
if (p <= 1) return false;
if (p % 2 == 0) return false;
BigInt i (3, true, p.base);
for (; i*i <= p; i+= 2) {
//std::cout<<"i : "<<i<<std::endl;
if (p % i == 0)
return false;
}
// le nombre est considéré comme premier
return true;
}
int BigInt::jacobien(BigInt& a, BigInt& b)
{
if(a == 0)
return 0;
int J = 1;
while(a != 1)
{
if(a % 2 == 0)
{
if( ((b * b - 1) >> 3) % 2 != 0)
J *= -1;
a >>= 1;
}
else
{
if( ((a - 1) * (b - 1) >> 2) % 2 != 0)
J *= -1;
BigInt temp = b % a;
b = a;
a = temp;
}
}
return J;
}
BigInt BigInt::pgcd(BigInt a, BigInt b)
{
return (b > 0) ? pgcd(b,a%b) : a;
}
bool BigInt::isPositif () {
return positif;
}
void BigInt::shorten () {
vector<unsigned int>::iterator it;
for (it = chiffres.begin(); it != chiffres.end(); ) {
if (*it == 0) {
it = chiffres.erase(it);
nbChiffres--;
} else
break;
}
}
void BigInt::clear()
{
chiffres.clear();
}
bool BigInt::isNull() const {
return chiffres.empty();
}
unsigned int BigInt::size() const {
return chiffres.size();
}
unsigned int BigInt::operator[] ( unsigned int i ) const {
return (i>=chiffres.size()) ? chiffres[chiffres.size() - 1] : chiffres[i];
}
BigInt BigInt::operator++ (int i) {
BigInt un(1, true, base);
*this += un;
return *this;
}
void BigInt::insert(unsigned int c, int pos) {
if (pos <= size()) {
BigInt result(0, true, base);
result.chiffres.resize(size() + 1, 0);
for (unsigned int i = 0, j = 0; i <= size(); i++, j++) {
if (i != pos) {
result.chiffres[i] = chiffres[j];
} else {
j--;
}
}
result.chiffres[pos] = c;
computeNbC(c);
*this = result;
}
}
BigInt BigInt::operator-- (int i) {
BigInt un(1, true, base);
*this -= un;
return *this;
}
int BigInt::comparaison (const BigInt &b) const {
/*std::cout<<"sizes : "<<chiffres.size()<<" "<<b.chiffres.size()<<std::endl;
std::string s;
std::cin>>s;*/
if (positif && !b.positif)
return +1;
if (!positif && b.positif)
return -1;
if ((chiffres.size() > b.chiffres.size() && positif && b.positif)
|| (chiffres.size() < b.chiffres.size() && !positif && !b.positif))
return +1;
if ((chiffres.size() < b.chiffres.size() && positif && b.positif)
|| (chiffres.size() > b.chiffres.size() && !positif && !b.positif))
return -1;
for(unsigned int i= 0; i < chiffres.size(); i++) {
if ((chiffres[i] > b.chiffres[i] && positif && b.positif)
|| (chiffres[i] < b.chiffres[i] && !positif && !b.positif))
return +1;
if ((chiffres[i] < b.chiffres[i] && positif && b.positif)
|| (chiffres[i] > b.chiffres[i] && !positif && !b.positif))
return -1;
}
return 0;
}
bool BigInt::operator== ( const BigInt& a ) const {
return ( comparaison(a) == 0 );
}
bool BigInt::operator!= ( const BigInt& a) const {
return ( comparaison(a) != 0 );
}
bool BigInt::operator< ( const BigInt& a ) const {
return ( comparaison(a) < 0 );
}
bool BigInt::operator<= ( const BigInt& a ) const {
return ( comparaison(a) <= 0 );
}
bool BigInt::operator> ( const BigInt& a) const {
return ( comparaison(a) > 0 );
}
bool BigInt::operator>= ( const BigInt& a) const {
return ( comparaison(a) >= 0 );
}
BigInt BigInt::operator-() const {
BigInt result = *this;
result.positif = !positif;
return result;
}
BigInt BigInt::add (const BigInt& bi) const {
if (isNull())
return bi;
if (bi.isNull())
return *this;
BigInt somme = *this;
unsigned int retenue= 0;
int i, j;
for(i=size() - 1, j = bi.size() - 1; j >= 0; i--, j--) {
unsigned long long int temp = (unsigned long long int) (*this)[i] + (unsigned long long int) bi[j] + (unsigned long long int) retenue;
if ( temp < base) {
somme.chiffres[i] = (unsigned int) temp;
retenue = 0;
}
else {
somme.chiffres[i]= (unsigned int) temp - base;
retenue = 1;
}
}
while (retenue != 0) {
if (i >= 0) {
unsigned long long int temp = (unsigned long long int) (*this)[i] + (unsigned long long int) retenue;
if ( temp < base) {
somme.chiffres[i] = (unsigned int) temp;
retenue = 0;
} else {
somme.chiffres[i]= (unsigned int) temp - base;
}
i--;
} else {
somme.chiffres.insert(somme.chiffres.begin(), retenue);
retenue = 0;
}
}
somme.shorten();
return somme;
}
BigInt BigInt::operator+ (const BigInt &bi) const {
BigInt a = *this;
BigInt b = bi;
BigInt result(0, true, base);
if (positif && bi.positif) {
if (b > a) {
a = bi;
b = *this;
}
result = a.add(b);
} else if (!positif && bi.positif) {
if (abs(*this) >= abs(bi)) {
result = a.sub(b);
} else {
result = b.sub(a);
result.positif = true;
}
} else if (positif && !bi.positif) {
if (abs(*this) >= abs(bi)) {
result = a.sub(b);
} else {
result = b.sub(a);
result.positif = false;
}
} else {
if (abs(b) > abs(a)) {
a = bi;
b = *this;
}
result = a.add(b);
}
return result;
}
BigInt& BigInt::operator+= (const BigInt &bi) {
*this = *this + bi;
return *this;
}
BigInt BigInt::sub (const BigInt &bi) const {
if (bi.isNull())
return *this;
BigInt diff = *this;
// Calculer la somme chiffre par chiffre en tenant compte des retenues
unsigned int retenue= 0;
int i, j;
for(i=size() - 1, j = bi.size() - 1; j>=0; i--, j--) {
long long temp = (long long) ((unsigned long long int) (*this)[i] - (unsigned long long int) bi[j] - (unsigned long long int) retenue);
if ( temp >= 0 ) {
diff.chiffres[i]= (unsigned int) temp;
retenue = 0;
}
else {
diff.chiffres[i]= (unsigned int) (temp + base);
retenue = 1;
}
}
while (retenue > 0) {
long long int temp = (long long int) ((unsigned long long int) (*this)[i] - (unsigned long long int) retenue);
if ( temp >= 0 ) {
diff.chiffres[i]= (unsigned int) temp;
retenue = 0;
}
else {
diff.chiffres[i]= (unsigned int) (temp + base);
}
i--;
}
diff.shorten();
return diff;
}
BigInt BigInt::abs(const BigInt& a) {
BigInt b = a;
b.positif = true;
return b;
}
BigInt BigInt::operator- (const BigInt &bi) const {
BigInt result(0, true, base);
BigInt a = *this;
BigInt b = bi;
if (positif && bi.positif) {
if (*this == bi)
return result;
if (*this > bi) {
result = a.sub(b);
} else {
result = b.sub(a);
result.positif = false;
}
} else if (!positif && bi.positif) {
if (abs(b) > abs(a)) {
a = bi;
b = *this;
}
result = a.add(b);
} else if (positif && !bi.positif) {
if (abs(b) > abs(a)) {
a = bi;
b = *this;
}
result = a.add(b);
} else {
if (abs(*this) > abs(bi)) {
result = a.sub(b);
} else {
result = b.sub(a);
result.positif = true;
}
}
return result;
}
BigInt& BigInt::operator-= (const BigInt &bi) {
*this = *this - bi;
return *this;
}
BigInt BigInt::addZeros (unsigned int n) {
BigInt result(0, positif, base);
result.chiffres.resize(size() + n, 0);
nbChiffres += n;
for (unsigned int i = 0; i < size(); i++) {
result.chiffres[i] = chiffres[i];
}
return result;
}
BigInt BigInt::multiply (const BigInt &bi) const {
BigInt produit(0, true, this->base);
produit.clear();
if ( this->size() == 0 || bi.size() == 0 ) {
return produit;
}
int i = 0, j = bi.size() - 1;
produit = scaleUp(bi.chiffres[i]).addZeros(j);
while ( j > 0)
{
i++; j--;
produit += scaleUp (bi.chiffres[i]).addZeros(j);
}
produit.shorten();
return produit;
}
BigInt BigInt::karatsuba (const BigInt &bi) const {
if (size() >= bi.size()) {
unsigned int n = size() / 2;
BigInt a = arraySub(0, size() - n);
BigInt b = arraySub(size() - n, n);
if (bi.size() > n) {
BigInt c = bi.arraySub(0, bi.size() - n);
BigInt d = bi.arraySub(bi.size() - n, n);
BigInt ac = a * c;
BigInt bd = b * d;
BigInt ad_bc = (a + b) * (c + d) - ac - bd;
ac = ac.addZeros(2*n);
ad_bc = ad_bc.addZeros(n);
return ac + ad_bc + bd;
} else {
BigInt aq = a * bi;
BigInt bq = b * bi;
aq = aq.addZeros(n);
return aq + bq;
}
}
return *this;
}
BigInt BigInt::operator* (const BigInt &bi) const {
// D´el´eguer les petites multiplications `a la m´ethode scolaire
BigInt result(0, true, base);
if (size() < bi.size())
result = bi * *this;
else if (bi.size() < karatsuba_treshold)
result = multiply(bi);
else
result = karatsuba(bi);
if (!positif && bi.positif || positif && !bi.positif)
result.positif = false;
else
result.positif = true;
return result;
}
BigInt& BigInt::operator*= (const BigInt &bi) {
*this = *this * bi;
return *this;
}
BigInt BigInt::operator/ (const BigInt &bi) const {
if (bi == 0) {
cerr<<"Error : b is null!";
return 0;
}
if (bi > *this) {
return 0;
}
BigInt result(0, true, base);
BigInt reste(0, true, base);
result = burnikel_ziegler(bi, reste);
if (!positif && bi.positif || positif && !bi.positif)
result.positif = false;
else
result.positif = true;
return result;
}
BigInt& BigInt::operator/= (const BigInt &bi) {
*this = *this / bi;
return *this;
}
BigInt BigInt::operator% (const BigInt& bi) const {
if (bi == BigInt(0)) {
cerr<<"Error : b is null!";
return 0;
}
if (bi > *this)
return *this;
BigInt reste(0, true, base);
burnikel_ziegler(bi, reste);
reste.shorten();
if (!positif && bi.positif || positif && !bi.positif)
reste.positif = false;
else
reste.positif = true;
return reste;
}
BigInt BigInt::pow (const BigInt& exp) {
BigInt un(1, true, base);
BigInt deux (2, true, base);
BigInt zero (0, true, base);
if (exp.isNull()) {
return un;
} else if (exp % deux == zero) {
BigInt a = pow(exp / deux);
return (a * a);
} else {
return (*this) * pow (exp - un);
}
}
BigInt BigInt::prodMod (const BigInt &b, const BigInt &n) const {
if(isNull()) {
return 0;
} else {
// a = 2 * q + e
BigInt q = *this / BigInt(2, true, base);
BigInt e = *this % BigInt(2, true, base);
BigInt r = BigInt(2, true, base) * q.prodMod(b, n) % n;
return e == 0 ? r : (r + b) % n;
}
}
BigInt BigInt::modOfPow (const BigInt& exp, const BigInt& mod) const {
/*BigInt result (1, true, base);
BigInt one(1, true, base);
BigInt two (2, true, base);
BigInt zero(0, true, base);
BigInt e = exp, bs;
bs = *this;
while (e > zero) {
if (e % two == one)
result = result * bs % mod;
e /= two;
//std::cout<<"e : "<<e<<"base : "<<bs<<"result : "<<result<<std::endl;
bs = bs * bs % mod;
}
return result;*/
BigInt e = exp.convert(2);
BigInt bs = *this;
BigInt result (1, true, base);
BigInt zero(0, true, 2);
while (e > zero) {
if ((e & BigInt(1, true, 2)) > zero) {
result = result * bs % mod;
}
e >>= 1;
bs = bs * bs % mod;
}
return result;
}
BigInt& BigInt::operator%= (const BigInt &bi) {
*this = *this % bi;
return *this;
}
BigInt BigInt::arraySub (int n, int length) const {
const_cast<BigInt*>(this)->shorten();
BigInt result(0, true, this->base);
if (n >= 0 && n + length <= size() && length > 0) {
result.chiffres.resize(length, 0);
for (int i = n, j = 0; j < length; i++, j++) {
result.chiffres[j] = chiffres[i];
}
}
return result;
}
BigInt BigInt::operator<< (int n) const {
BigInt result(0, positif, base);
result.chiffres.resize(size() + n, 0);
for (unsigned int i = 0; i < size(); i++) {
result.chiffres[i] = chiffres[i];
}
return result;
}
BigInt BigInt::operator>> (int n) const {
if (n < 0)
return *this;
if (isNull())
return *this;
if (n > size())
n = size();
BigInt result (0, true, base);
int l = ((int) size() - n) < 0 ? 0 : size() - n;
result.chiffres.resize(l, 0);
for (unsigned int i = 0; i < result.size(); i++)
result.chiffres[i] = chiffres[i];
return result;
}
BigInt& BigInt::operator<<= (int n) {
BigInt result(0, positif, base);
result.chiffres.resize(size() + n, 0);
for (unsigned int i = 0; i < size(); i++) {
result.chiffres[i] = chiffres[i];
}
*this = result;
return *this;
}
BigInt& BigInt::operator>>= (int n) {
if (n < 0)
return *this;
if (isNull())
return *this;
if (n > size())
n = size();
BigInt result (0, true, base);
int l = ((int) size() - n) < 0 ? 0 : size() - n;
result.chiffres.resize(l, 0);
for (unsigned int i = 0; i < result.size(); i++)
result.chiffres[i] = chiffres[i];
*this = result;
return *this;
}
BigInt BigInt::operator& (const BigInt& n) const {
BigInt result (0, true, base);
unsigned int max = (n.size() < size()) ? size() : n.size();
BigInt b = n;
BigInt a = *this;
for (unsigned int i = 0; i < max; i++) {
if (i >= a.size())
a.insert(0, 0);
if (i >= b.size())
b.insert(0, 0);
}
result.chiffres.resize(max, 0);
for (unsigned int i = 0; i < max; ++i) {
result.chiffres[i] = a.chiffres[i] & b.chiffres[i];
}
result.shorten();
return result;
}
BigInt BigInt::scaleUp (unsigned int n) const {
unsigned long long int accu = 0;
unsigned int retenue = 0;
BigInt result(0, true, base);
result.chiffres.resize(size() + 1, 0);
if (n >= 0 && n < base) {
if (n == 0)
return 0;
for (int i = size(); i > 0; i--) {
accu = (unsigned long long int) chiffres[i-1] * n + (unsigned long long int) retenue;
result.chiffres[i] = (unsigned int) (accu % base);
retenue = (unsigned int) (accu / base);
}
result.chiffres[0] = retenue;
if (retenue == 0)
result.shorten();
}
return result;
}
BigInt BigInt::scaleDown (unsigned long long int n, BigInt& r) const {
unsigned long long int accu = 0;
unsigned int retenue = 0;
BigInt result = *this;
if (n >= 0 && n < base * base) {
for (unsigned int i = 0; i < size(); i++) {
accu = (unsigned long long) chiffres[i] + (unsigned long long int) retenue * base;
result.chiffres[i] = (unsigned int) (accu / n);
retenue = (unsigned int) (accu % n);
}
}
r = BigInt(retenue, true, base);
result.shorten();
return result;
}
BigInt BigInt::burnikel_ziegler(const BigInt &bi, BigInt &r) const {
BigInt q(0, true, base);
if (bi.size() <= 2) {
unsigned long long int b2 = (bi.size() < 2) ? bi.chiffres[0] : bi.chiffres[0] * base + bi.chiffres[1];
q = scaleDown(b2, r);
return q;
}
unsigned int n = (bi.size() - 1) / 2;
// D´ecouper a et b en deux moiti´es
BigInt a0, a1;
a0 = arraySub(size() - n, n);
a1 = arraySub(0, size() - n);
if (a1 >= bi) {
BigInt q1(0, true, base), r1(0, true, base), q0(0, true, base), r0(0, true, base);
q1 = a1.burnikel_ziegler (bi, r1);
r1 = r1.addZeros(n);
q0 = (r1 + a0).burnikel_ziegler (bi, r0);
q1 = q1.addZeros(n);
r = r0;
return q1 + q0;
}
BigInt b0(0, true, base), b1(0, true, base), q1(0, true, base), r1(0, true, base),
a0_r1(0, true, base), b0_q1(0, true, base);
b0 = bi.arraySub(bi.size() - n, n);
b1 = bi.arraySub(0, bi.size() - n);
q1 = a1.burnikel_ziegler(b1, r1);
r1 = r1.addZeros(n);
a0_r1 = r1 + a0;
b0_q1 = b0 * q1;
if (a0_r1 >= b0_q1) {
r = a0_r1 - b0_q1;
return q1;
}
BigInt minus_x = b0_q1 - a0_r1;
r = bi - minus_x;
return q1 - BigInt(1, true, base);
}
BigInt BigInt::m_invert(const BigInt& b) const
{
BigInt n0 = b;
BigInt b0 = *this;
BigInt t0 (0, true, base);
BigInt t (1, true, base);
BigInt q = n0/b0;
BigInt r = n0 - (q * b0);
BigInt temp = 0;
while (r > 0)
{
temp = t0 - (q * t);
if (temp >= 0)
temp = temp % b;
else
temp = b - ((-temp) % b);
t0 = t;
t = temp;
n0 = b0;
b0 = r;
q = n0/b0;
r = n0 - (q * b0);
}
if (b0 != 1)
return 0;
return t;
}
bool BigInt::miller(unsigned int nbBits, BigInt& n) {
BigInt n2 = n.convert(2);
if ((n2 & 1) == 0)
return false;
BigInt n1 = n-1;
BigInt m = n1;
unsigned int k = 1;
BigInt zero(0, true, n.base);
BigInt one(1, true, n.base);
//std::cout<<"cond 1 : "<<(n1 % (BigInt(1 << (k + 2), true, n.base)) == zero)<<std::endl;
while (n1 % (BigInt(1 << (k + 2), true, n.base)) == zero) {
k += 2;
m >>= 2;
}
for (unsigned int i = 0; i < 10; i++) {
BigInt a = genRandom(nbBits, n.base);
//std::cout<<"a : "<<a<<" a >= n ?"<<(a >= n)<<std::endl;
while (a >= n) {
a = genRandom(nbBits, n.base);
}
BigInt b = a.modOfPow(m, n);
if (b % n != one) {
unsigned int j;
for (j = 0; j < k && b % n != n1; ++j) {
b *= b;
}
if (j >= k)
return false;
}
}
return true;
/*BigInt d=(n2-BigInt(1, true, 2))>>1;
int s = 1;
while ((d & 1) == 0) {
s += 1;
d >>= 1;
}
int k = 10;
while (k) {
k--;
std::cout<<"k : "<<k<<std::endl;
BigInt a = genRandom(nbBits, 2);
if (a.modOfPow(d, n2) != BigInt(1, true, 2)) {
while (s) {
s--;
std::cout<<"d : "<<d<<std::endl<<"s : "<<s<<std::endl<<"d<<s : "<<(d<<s)<<std::endl;
if (a.modOfPow(d<<s, n2) != n2 - BigInt(1, true, 2))
return false;
}
}
}
std::cout<<"true"<<std::endl;
return true;*/
}
bool BigInt::isMersennePrime(const BigInt& p, unsigned int base) {
if (p == 2) {
return true;
} else {
BigInt s(4, true, base);
BigInt div = BigInt(2, true, base).pow(p) - 1;
for (BigInt i = 3; i <= p; i++) {
s = (s * s - BigInt(2, true, base)) % div;
}
return s == 0;
}
}
BigInt BigInt::convert (unsigned int b) const {
BigInt newBi = *this;
if (b != base) {
newBi = BigInt (0, true, 10);
BigInt bs = BigInt(base, true, 10);
for (int i = 0; i < size(); i++) {
BigInt exp (size() - i - 1, true, 10);
BigInt c1 (chiffres[i], true, 10);
BigInt c2 = c1 * bs.pow(exp);
newBi += c2;
}
if (b != 10) {
BigInt max(1, true, 10);
bs = BigInt (b, true, 10);
BigInt r(0, true, 10);
while (newBi >= max) {
max = max * bs;
}
max /= bs;
newBi.shorten();
BigInt a = newBi;
newBi.clear();
newBi.nbChiffres = 0;
while (max > 0) {
BigInt c;
c = a / max;
if (c == 0) {
newBi.chiffres.push_back(0);
newBi.computeNbC(0);
} else {
unsigned int somme = 0;
for (unsigned int i = 0; i < c.size(); i++) {
somme += c.chiffres[i] * math::Math::power(10, c.size() - i - 1);
}
newBi.chiffres.push_back(somme);
a %= max;
newBi.computeNbC(somme);
}
max /= bs;
}
}
newBi.shorten();
newBi.base = b;
return newBi;
}
return newBi;
}
// Conversion valeur -> symbole pour la sortie
char symbole( unsigned int valeur) {
return ((valeur< 10) ? 48 + valeur : 55 + valeur);
}
std::string BigInt::toStr(unsigned int base) {
BigInt bi = *this;
if (base != this->base) {
bi = convert(base);
}
if ( bi.size()== 0 ) return ( "0" );
std::string str="";
if (!bi.positif)
str+="-";
for( int i = 0; i < bi.size(); i++) {
str+=symbole(bi.chiffres[i]);
}
return str;
}
// Op´erateur de sortie (afficher les chiffres, ou bien "0" pour une suite vide)
ostream& operator<< ( ostream& out, const BigInt& bi) {
if ( bi.size()== 0 ) return ( out << 0 );
if (!bi.positif)
out<<"-";
for( int i = 0; i < bi.size(); i++) {
out<<symbole(bi.chiffres[i]);
if (i != bi.size()-1)
out<<" ";
}
return out;
}
}
J'utilise la multiplication de karatsuba et la division de Burnikel_Ziegler.
Pour le calcul de la racine carrée, j'utilise un autre algorithme (par recherche binaire si je ne dis pas de bêtises).
Je n'avais pas trouvé l'algorithme de division dont tu parles, je vais aller voir de quoi il retourne.
EDIT : Avec ma classe, je suis capable de gérer un nombre de 2^29*2^64 bits sur ma machine, de là à montrer qu'il est premier comme un nombre premier de Mersenne, c'est encore une autre paire de manche.
- Edité par P'tit Ju 10 janvier 2025 à 8:21:32
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
J'ai tenté de faire une classe BigInt une fois mais elle est trop lente pour générer de très grand nombres premiers et je ne sais pas comment faire pour optimiser.
1. en commençant par déterminer ce qui est trop lent.
Trop lent par rapport à quoi ? un exemple ? Comparé avec quoi ?
2. ensuite viendra la question de pourquoi c'est trop lent
3. et ensuite peut être, ce qu'on pourrait changer pour que ça marche mieux.
- Edité par michelbillaud 9 janvier 2025 à 10:42:40
> Pour le calcul de la racine carrée, j'utilise un autre algorithme (par recherche binaire si je ne dis pas de bêtises). Et l'algorithme de Newton (est-ce bien lui?) ?
racine' = (nombre / racine + racine) / 2
à condition que la valeur de départ soit assez proche de la vraie valeur.
Si tu connais le nombre de bits du nombre, racine pourrait être 2^(nombre de bits / 2)
Le Tout est souvent plus grand que la somme de ses parties.
@PierrotLeFou : Non, c'est une recherche par dichotomie. J'ai vu qu'il y avait l'algorithme de Newton mais il utilise des nombres décimaux, chose que je n'ai pas encore codée.
Bon, j'ai réussi à coder la logique de Dalfab avec l'exemple développé, par contre ça plante dès que je passe à longest_type=unsigned long long. Le code correspondant est pour l'instant sur la branche : https://github.com/Julien-Livet/TestInteger/tree/Julien-Livet-patch-division. EDIT : J'ai corrigé le problème, le test de Dalfab passe mais pas un autre et là je sèche. Un peu d'aide serait la bienvenue :-) .
@OmbreNoire : J'ai regardé ton code mais je n'ai pas tout compris (il manque le header correspondant pour avoir la définition de BigInt) et je pense que je n'ai pas fait les mêmes choix que toi et que tu as moyen d'optimiser.
EDIT : J'ai réussi à implémenter la division de Burnikel-Ziegler à partir d'un code Python et ça marche très bien. Je passe désormais le test du grand nombre premier en 30 secondes (avec 100'000 nombres premiers à tester pour la racine carrée et une itération de Miller-Rabin par contre) ! Si vous avez d'autres suggestions d'amélioration de code ou d'algorithme, je suis preneur !
- Edité par P'tit Ju 11 janvier 2025 à 9:08:30
Le premier et meilleur outil de l'Homme reste encore et toujours son cerveau.
Salut, j'ai cru que le .h n'était pas nécessaire pour comprendre le code mais je ne sais pas comment tu fais, moi, j'ai essayé de tester avec des nombres de 1024 octets pour savoir si ils sont premiers pour la génération de clés pour le chiffrement RSA. La fonction next_prime de gmp dure quelques secondes et la méthode pour générer les clés de openssl est rapide également tandis que la mienne avec le test de miller_Rabbin est trop lente.
Voici le .h.
#ifndef BIG_INT_HPP
#define BIG_INT_HPP
#include <string>
#include <vector>
#include <iostream>
#include <limits>
#include "../../../include/odfaeg/Math/maths.h"
namespace odfaeg {
class BigInt {
public :
friend char symbole( unsigned int valeur);
friend std::ostream& operator<< (std::ostream& out, const BigInt& bi);
BigInt(const std::string& number, unsigned int base = 10);
BigInt(unsigned long long integer=0, bool positif=true, unsigned int b=10);
static BigInt genRandom (unsigned int nbBits, unsigned int base=2);
static BigInt genPrime(unsigned int nbBits, unsigned int base=2);
static BigInt abs(const BigInt& a);
void setStr(const std::string& number, unsigned int base = 10);
bool isPositif();
BigInt operator+(const BigInt& bi) const;
BigInt& operator+=(const BigInt& bi);
BigInt operator-(const BigInt& bi) const;
BigInt& operator-=(const BigInt& bi);
BigInt operator*(const BigInt& bi) const;
BigInt& operator*=(const BigInt& bi);
BigInt operator/(const BigInt& bi) const;
BigInt& operator/=(const BigInt& bi);
BigInt operator%(const BigInt& bi) const;
BigInt& operator%=(const BigInt& bi);
bool operator== (const BigInt& bi ) const;
bool operator!= (const BigInt& bi ) const;
bool operator<= (const BigInt& bi ) const;
bool operator< (const BigInt& bi ) const;
bool operator>= (const BigInt& bi ) const;
bool operator> (const BigInt& bi ) const;
BigInt operator<< (int n) const;
BigInt operator>> (int n) const;
BigInt& operator<<= (int n);
BigInt& operator>>= (int n);
BigInt operator& (const BigInt& n) const;
BigInt operator-() const;
BigInt pow (const BigInt& exp);
BigInt prodMod (const BigInt &b, const BigInt &n) const;
BigInt modOfPow (const BigInt& exp, const BigInt& mod) const;
bool isNull() const;
unsigned int getNbChiffres();
BigInt convert(unsigned int base) const;
BigInt m_invert (const BigInt& b) const;
BigInt sqrt();
static bool isMersennePrime(const BigInt& p, unsigned int base);
static BigInt pgcd(BigInt a, BigInt b);
unsigned int size() const;
std::string toStr(unsigned int base);
static bool isPrime(unsigned int nbBits, BigInt& p);
static bool miller (unsigned int nbBits, BigInt& n);
BigInt operator++(int i);
BigInt operator--(int i);
private :
static const unsigned int karatsuba_treshold = 20;
static int jacobien(BigInt& a, BigInt& b);
void computeNbC(unsigned long long int c);
BigInt scaleUp (unsigned int n) const;
BigInt scaleDown (unsigned long long int n, BigInt &r) const;
BigInt arraySub (int n, int length) const;
BigInt addZeros(unsigned int n);
void insert (unsigned int c, int pos);
unsigned int operator[](unsigned int i) const;
void shorten();
void clear();
BigInt add(const BigInt& bi) const;
BigInt sub(const BigInt& bi) const;
int comparaison(const BigInt& b) const;
BigInt multiply(const BigInt& bi) const;
BigInt karatsuba(const BigInt& bi) const;
BigInt burnikel_ziegler (const BigInt& bi, BigInt &r) const;
std::vector<unsigned int> chiffres;
unsigned int base;
unsigned long long int nbChiffres;
bool positif;
};
}
#endif // BIG_INT
Le Tout est souvent plus grand que la somme de ses parties.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Le Tout est souvent plus grand que la somme de ses parties.