Quel est l'algorithme de factorisation le plus rapide?
j'ai écrit un programme qui tente de trouver des couples Amicaux. Cela exige de trouver les sommes des diviseurs appropriés de nombres.
voici ma méthode actuelle sumOfDivisors() :
int sumOfDivisors(int n)
{
int sum = 1;
int bound = (int) sqrt(n);
for(int i = 2; i <= 1 + bound; i++)
{
if (n % i == 0)
sum = sum + i + n / i;
}
return sum;
}
j'ai Donc besoin de faire beaucoup de factorisation et qui commence à devenir le véritable goulot d'étranglement dans mon application. J'ai tapé un grand nombre dans MAPLE et il l'a fait incroyablement rapide.
Qu'est-ce que l'une des factorisations les plus rapides les algorithmes?
7 réponses
tire directement de ma réponse à cette autre question .
la méthode fonctionnera, mais sera lente. "De quelle taille sont vos chiffres?"détermine la méthode à utiliser:
- moins de 2^16 environ: table de recherche.
- moins de 2^70 ou plus: modification de Richard Brent de algorithme rho de Pollard .
- moins de 10^50: Lenstra courbe elliptique factorisation
- moins de 10^100: tamis quadratique 151980920"
- plus de 10^100: numéro général tamis de champ 151980920"
La question est dans le titre (et la dernière ligne) semble avoir peu à voir avec le corps de la question. Si vous essayez de trouver des paires amicales, ou en calculant la somme des diviseurs pour de nombreux nombres, alors séparément factoriser chaque nombre (même avec l'algorithme le plus rapide possible) est absolument une manière inefficace de le faire.
la fonction somme-de-diviseurs , σ(n) = (sum of divisors of n) , est une fonction multiplicative : pour m et n relativement premiers, nous avons σ(mn) = σ(m)σ(n) , donc
σ(p 1 k 1 ...p r k r ) = [(p 1 k 1 +1 -1)/(p 1 -1)]...[(p r k r +1 -1)/(p r -1)].
ainsi vous utiliserez n'importe quel tamis simple (par exemple une version augmentée du tamis de Eratosthenes ) à trouver les nombres premiers jusqu'à n , et, dans le processus, la factorisation de tous les nombres jusqu'à N. (Par exemple, pendant que vous faites votre tamis, stockez le plus petit facteur principal de chaque N. Vous pouvez ensuite factoriser n'importe quel nombre n en itérant.) Ce serait être plus rapide (dans l'ensemble) que l'utilisation de n'importe quel algorithme de factorisation séparé plusieurs fois.
BTW: plusieurs listes connues de couples Amicaux existent déjà (voir par exemple ici et les liens à MathWorld ) - alors vous essayez d'étendre le disque, ou le faire juste pour le plaisir?
algorithme de Shor: http://en.wikipedia.org/wiki/Shor%27s_algorithm
bien sûr, vous avez besoin d'un ordinateur quantique cependant: d
je suggère de partir du même algorithme utilisé dans Maple, le tamis quadratique .
- Choisissez votre nombre impair n factoriser,
- choisir un nombre naturel k ,
- Rechercher tout p <= k de sorte que k^2 n'est pas conforme à (n mod p) pour obtenir une base de facteur B = p1, p2,..., pt ,
- à partir de r > étage(n) "151970920 de recherche" au moins t+1 valeurs y^2 = r^2 - n tous viens de facteurs B,
- pour chaque y1 , y2 ,..., y (t+1) juste calculé vous générez un vecteur v (yi) = (e1, e2,..., et) où ei est calculé en réduisant sur le modulo 2 l'exposant pi dans yi ,
- utiliser élimination gaussienne pour trouver certains des vecteurs qui additionnés donnent un vecteur nul
- ensemble x comme le produit de ri lié à yi trouvé à l'étape précédente et régler y comme p1^a * p2^b * p3^c*.. * pt ^ z où les exposants sont la moitié des exposants trouvés dans la factorisation de yi 151980920"
- calculer d = mcd (x-y, n) , si 1 < D < n alors d est un facteur non trivial de n , sinon commencez à l'étape 2 En choisissant un plus grand K.
le problème à propos de ces algorithmes est qu'ils impliquent vraiment beaucoup de théorie en calcul numérique..
ceci est un papier de la factorisation Integer en érable.
"à partir de quelques instructions très simples -" rendre la factorisation entière plus rapide dans Maple" - nous avons mis en œuvre L'algorithme quadratique de factorisation de tamis une combinaison D'érable et de C..."
http://www.cecm.sfu.ca / ~pborwein / MITACS/papers / percival.pdf
dépend de la taille de vos numéros. Si vous cherchez des couples Amicaux, vous faites beaucoup de factorisations, donc la clé n'est peut-être pas de factoriser le plus rapidement possible, mais de partager le plus de travail possible entre différents appels. Pour accélérer la division de première instance, vous pouvez regarder la memoization, et/ou précalculer des nombres premiers jusqu'à la racine carrée du plus grand nombre que vous aimez. C'est plus rapide pour obtenir le premier factorisation, puis calculer la somme de tous les facteurs, qu'il est à boucle tout le chemin jusqu'à sqrt(n) pour chaque nombre.
si vous êtes à la recherche de paires amicales vraiment grandes, disons plus grandes que 2^64, alors sur un petit nombre de machines, vous ne pouvez pas le faire en factorisant chaque nombre simple, peu importe la vitesse de votre factorisation. Les raccourcis que vous utilisez pour trouver des candidats pourraient vous aider à les évaluer.
a more 2015 c++ version 2 27 mise en œuvre de la table de recherche pour la mémoire de 1Go:
#include <iostream.h> // cerr, cout, and NULL
#include <string.h> // memcpy()
#define uint unsigned __int32
uint *factors;
const uint MAX_F=134217728; // 2^27
void buildFactors(){
factors=new (nothrow) uint [(MAX_F+1)*2]; // 4 * 2 * 2^27 = 2^30 = 1GB
if(factors==NULL)return; // not able to allocate enough free memory
int i;
for(i=0;i<(MAX_F+1)*2;i++)factors[i]=0;
//Sieve of Eratosthenese
factors[1*2]=1;
factors[1*2+1]=1;
for(i=2;i*i<=MAX_F;i++){
for(;factors[i*2] && i*i<=MAX_F;i++);
factors[i*2]=1;
factors[i*2+1]=i;
for(int j=2;i*j<=MAX_F;j++){
factors[i*j*2]=i;
factors[i*j*2+1]=j;
}
}
for(;i<=MAX_F;i++){
for(;i<=MAX_F && factors[i*2];i++);
if(i>MAX_F)return;
factors[i*2]=1;
factors[i*2+1]=i;
}
}
uint * factor(uint x, int &factorCount){
if(x > MAX_F){factorCount=-1;return NULL;}
uint tmp[70], at=x; int i=0;
while(factors[at*2]>1){
tmp[i++]=factors[at*2];
cout<<"at:"<<at<<" tmp:"<<tmp[i-1]<<endl;
at=factors[at*2+1];
}
if(i==0){
cout<<"at:"<<x<<" tmp:1"<<endl;
tmp[i++]=1;
tmp[i++]=x;
}else{
cout<<"at:"<<at<<" tmp:1"<<endl;
tmp[i++]=at;
}
factorCount=i;
uint *ret=new (nothrow) uint [factorCount];
if(ret!=NULL)
memcpy(ret, tmp, sizeof(uint)*factorCount);
return ret;
}
void main(){
cout<<"Loading factors lookup table"<<endl;
buildFactors(); if(factors==NULL){cerr<<"Need 1GB block of free memory"<<endl;return;}
int size;
uint x=30030;
cout<<"\nFactoring: "<<x<<endl;
uint *f=factor(x,size);
if(size<0){cerr<<x<<" is too big to factor. Choose a number between 1 and "<<MAX_F<<endl;return;}
else if(f==NULL){cerr<<"ran out of memory trying to factor "<<x<<endl;return;}
cout<<"\nThe factors of: "<<x<<" {"<<f[0];
for(int i=1;i<size;i++)
cout<<", "<<f[i];
cout<<"}"<<endl;
delete [] f;
x=30637;
cout<<"\nFactoring: "<<x<<endl;
f=factor(x,size);
cout<<"\nThe factors of: "<<x<<" {"<<f[0];
for(int i=1;i<size;i++)
cout<<", "<<f[i];
cout<<"}"<<endl;
delete [] f;
delete [] factors;
}
mise à jour: ou sacrifier un peu de simplicité pour un peu plus de gamme juste après 2 28
#include <iostream.h> // cerr, cout, and NULL
#include <string.h> // memcpy(), memset()
//#define dbg(A) A
#ifndef dbg
#define dbg(A)
#endif
#define uint unsigned __int32
#define uint8 unsigned __int8
#define uint16 unsigned __int16
uint * factors;
uint8 *factors08;
uint16 *factors16;
uint *factors32;
const uint LIMIT_16 = 514; // First 16-bit factor, 514 = 2*257
const uint LIMIT_32 = 131074;// First 32-bit factor, 131074 = 2*65537
const uint MAX_FACTOR = 268501119;
//const uint64 LIMIT_64 = 8,589,934,594; // First 64-bit factor, 2^33+1
const uint TABLE_SIZE = 268435456; // 2^28 => 4 * 2^28 = 2^30 = 1GB 32-bit table
const uint o08=1, o16=257 ,o32=65665; //o64=4294934465
// TableSize = 2^37 => 8 * 2^37 = 2^40 1TB 64-bit table
// => MaxFactor = 141,733,953,600
/* Layout of factors[] array
* Indicies(32-bit) i Value Size AFactorOf(i)
* ---------------- ------ ---------- ----------------
* factors[0..128] [1..513] 8-bit factors08[i-o08]
* factors[129..65408] [514..131073] 16-bit factors16[i-o16]
* factors[65409..268435455] [131074..268501119] 32-bit factors32[i-o32]
*
* Note: stopping at i*i causes AFactorOf(i) to not always be LargestFactor(i)
*/
void buildFactors(){
dbg(cout<<"Allocating RAM"<<endl;)
factors=new (nothrow) uint [TABLE_SIZE]; // 4 * 2^28 = 2^30 = 1GB
if(factors==NULL)return; // not able to allocate enough free memory
uint i,j;
factors08 = (uint8 *)factors;
factors16 = (uint16 *)factors;
factors32 = factors;
dbg(cout<<"Zeroing RAM"<<endl;)
memset(factors,0,sizeof(uint)*TABLE_SIZE);
//for(i=0;i<TABLE_SIZE;i++)factors[i]=0;
//Sieve of Eratosthenese
//8-bit values
dbg(cout<<"Setting: 8-Bit Values"<<endl;)
factors08[1-o08]=1;
for(i=2;i*i<LIMIT_16;i++){
for(;factors08[i-o08] && i*i<LIMIT_16;i++);
dbg(cout<<"Filtering: "<<i<<endl;)
factors08[i-o08]=1;
for(j=2;i*j<LIMIT_16;j++)factors08[i*j-o08]=i;
for(;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
for(;i<LIMIT_16;i++){
for(;i<LIMIT_16 && factors08[i-o08];i++);
dbg(cout<<"Filtering: "<<i<<endl;)
if(i<LIMIT_16){
factors08[i-o08]=1;
j=LIMIT_16/i+(LIMIT_16%i>0);
for(;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
}i--;
dbg(cout<<"Setting: 16-Bit Values"<<endl;)
//16-bit values
for(;i*i<LIMIT_32;i++){
for(;factors16[i-o16] && i*i<LIMIT_32;i++);
factors16[i-o16]=1;
for(j=2;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
for(;i<LIMIT_32;i++){
for(;i<LIMIT_32 && factors16[i-o16];i++);
if(i<LIMIT_32){
factors16[i-o16]=1;
j=LIMIT_32/i+(LIMIT_32%i>0);
for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
}i--;
dbg(cout<<"Setting: 32-Bit Values"<<endl;)
//32-bit values
for(;i*i<=MAX_FACTOR;i++){
for(;factors32[i-o32] && i*i<=MAX_FACTOR;i++);
factors32[i-o32]=1;
for(j=2;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
for(;i<=MAX_FACTOR;i++){
for(;i<=MAX_FACTOR && factors32[i-o32];i++);
if(i>MAX_FACTOR)return;
factors32[i-o32]=1;
}
}
uint * factor(uint x, int &factorCount){
if(x > MAX_FACTOR){factorCount=-1;return NULL;}
uint tmp[70], at=x; int i=0;
while(at>=LIMIT_32 && factors32[at-o32]>1){
tmp[i++]=factors32[at-o32];
dbg(cout<<"at32:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
at/=tmp[i-1];
}
if(at<LIMIT_32){
while(at>=LIMIT_16 && factors16[at-o16]>1){
tmp[i++]=factors16[at-o16];
dbg(cout<<"at16:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
at/=tmp[i-1];
}
if(at<LIMIT_16){
while(factors08[at-o08]>1){
tmp[i++]=factors08[at-o08];
dbg(cout<<"at08:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
at/=tmp[i-1];
}
}
}
if(i==0){
dbg(cout<<"at:"<<x<<" tmp:1"<<endl;)
tmp[i++]=1;
tmp[i++]=x;
}else{
dbg(cout<<"at:"<<at<<" tmp:1"<<endl;)
tmp[i++]=at;
}
factorCount=i;
uint *ret=new (nothrow) uint [factorCount];
if(ret!=NULL)
memcpy(ret, tmp, sizeof(uint)*factorCount);
return ret;
}
uint AFactorOf(uint x){
if(x > MAX_FACTOR)return -1;
if(x < LIMIT_16) return factors08[x-o08];
if(x < LIMIT_32) return factors16[x-o16];
return factors32[x-o32];
}
void main(){
cout<<"Loading factors lookup table"<<endl;
buildFactors(); if(factors==NULL){cerr<<"Need 1GB block of free memory"<<endl;return;}
int size;
uint x=13855127;//25255230;//30030;
cout<<"\nFactoring: "<<x<<endl;
uint *f=factor(x,size);
if(size<0){cerr<<x<<" is too big to factor. Choose a number between 1 and "<<MAX_FACTOR<<endl;return;}
else if(f==NULL){cerr<<"ran out of memory trying to factor "<<x<<endl;return;}
cout<<"\nThe factors of: "<<x<<" {"<<f[0];
for(int i=1;i<size;i++)
cout<<", "<<f[i];
cout<<"}"<<endl;
delete [] f;
x=30637;
cout<<"\nFactoring: "<<x<<endl;
f=factor(x,size);
cout<<"\nThe factors of: "<<x<<" {"<<f[0];
for(int i=1;i<size;i++)
cout<<", "<<f[i];
cout<<"}"<<endl;
delete [] f;
delete [] factors;
}