가장 빠른 분해 알고리즘은 무엇입니까?

ProgramingTip

가장 빠른 분해 알고리즘은 무엇입니까?

bestdevel 2021. 1. 9. 16:28

가장 빠른 분해 알고리즘은 무엇입니까?

Amicable Pairs를 찾는 프로그램을 작성했습니다. 이를 위해 적절한 수의 제수의 합을 찾아야합니다.

내 현재 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;
}

그래서 저는 많은 분해를해야한다는 것이 제 응용 프로그램의 실제 병목 현상이 시작되었습니다. 나는 MAPLE에 엄청난 숫자를 입력하고 그것을 엄청나게 빠르게 고려했습니다.

더 빠른 분해 알고리즘 중 하나는 무엇입니까?

이 다른 질문에 대한 내 대답에서 직접 가져 왔습니다 .

이 방법은 작동하지만 느립니다. "당신의 숫자는 얼마나 섭섭니까?" 사용할 방법을 결정합니다.

2 ^ 16 미만 : 조회 테이블.
2 ^ 70 정도 : 리처드 브렌트의 수정 의 폴라드의 (ρ) 알고리즘 .
10 ^ 50 곡 : Lenstra 타원 곡선 분해
10 ^ 100 미만 : 2 차 체
10 ^ 100 이상 : General Number Field Sieve

제목 (및 마지막 줄)의 질문은 질문의 실제 본문과 거의 관련이없는 것입니다. 우호적 인 인을 찾거나 여러 숫자에 대한 제수의 합을 계산하려는 경우 각 숫자를 인합 적으로 인수 분해하는 것 (가장 빠른 알고리즘을 사용) 절대적으로 비효율적 방법입니다.

합 오브 약수 함수 ,, σ(n) = (sum of divisors of n)A는 곱셈 함수 , 우리 프라임 m 및 n σ(mn) = σ(m)σ(n)은가 그렇게

σ (p ₁^{k ₁} … p _r^{k _r} ) = [(p ₁^{k ₁ +1} -1) / (p ₁ -1)]… [(p _r^{k _r +1} -1) / (p _r -1 )].

따라서 간단한 체 (예 : 에라토스테네스 체의 증강 버전 )를 사용 하여 최대.까지 소수 를 찾고n그 과정에서 최대 n까지의 모든 수를 분해합니다. (예를 들어, 체를 할 때 각 n 의 가장 작은 소인수를 저장합니다 . 그런 다음 나중에 n반복하여 임의의 숫자 를 분해 할 수 있습니다 .)이 별도의 분해 알고리즘을 여러 번 사용하는 것보다 사용합니다. .

BTW : 우호적 쌍의 여러 목록이 이미 존재합니다 (예 : 여기 및 MathWorld 의 링크 참조 ). 기록을 확장하려고, 아니면 그냥 재미로하고 있나요?

쇼어의 알고리즘 : http://en.wikipedia.org/wiki/Shor%27s_algorithm

물론 양자 컴퓨터가 필요합니다 : D

Maple에서 사용 된 것과 동일한 알고리즘 인 Quadratic Sieve 에서 시작하는 것이 좋습니다.

인수 분해 할 홀수 n 을 선택하고 ,
자연수 k ,
모든 p <= k를 검색 하여 k ^ 2 가 (n mod p) 와 합동하지 마십시오 B = p1, p2, ..., pt ,
r > floor (n) 에서 시작 하여 인수
t + 1 값을 검색하여 y ^ 2 = r ^ 2-n이 모두 B의 만 갖도록합니다.
방금 계산 된 모든 y1 , y2 , ..., y (t + 1)에 대해 벡터 v (yi) = (e1, e2, ..., et)를 생성합니다. 여기서 ei 는 모듈로 2를 통해 지수 pi를 계산합니다. 의 이순신 ,
가우스 제거 를 사용 하여 함께 더해져 널 벡터를 제공하는 벡터를 찾습니다.
집합 X 의 생성물로서 RI 관련된 이순신 이전-step와 세트에서 발견 Y 의 분해 검색된 지수는 지수의 절반 P1 ^ A * B * ^ P2 P3 ^ C * .. * ^ Z PT로서 이
d = mcd (xy, n)을 계산 합니다. 1 <d <n 이면 d 는 n의 사소하지 않은 인수이고 이름 2 단계부터 시작하여 더 큰 k를 선택합니다.

알고리즘의 문제는 수치 미적분학에서 많은 이론을 암시한다는 것입니다.

이것은 Maple의 Integer Factorization에 관한 논문입니다.

"매우 간단한 몇 가지 지침 ("Maple에서 정수 분해 속도 향상 ")부터 시작하여 Maple과 C의 조합으로 Quadratic Sieve 분해 알고리즘을 구현했습니다."

http://www.cecm.sfu.ca/~pborwein/MITACS/papers/percival.pdf

숫자가 얼마나 큰지에 따라 증가합니다. 우호적 인 쌍을 소유하고 많은 분해를 수행하고 있으므로 가능한 한 빨리 고려하지 않고 서로 다른 통화간에 가능한 많은 작업을 공유하는 것이 핵심 일 수 있습니다. 시도 분할 속도를 높이기 위해 메모 화 및 / 또는 관심있는 가장 큰 숫자의 제곱근까지 소수를 미리 계산할 수 있습니다. sqrt (n)까지 반복하는 것보다 소인수 분해를 얻은 다음 그로부터 모든 수단의 합을 계산하는 것이 더 빠 사용합니다.

2 ^ 64보다 큰 정말 큰 우호적 쌍을 갖고있는 인수, 작은 수의 기계에서는 인수 분해가 아무리 빠르면서 모든 하나의 숫자를 분해하여 수행 할 수 없습니다. 후보 후보 찾는 데 사용하는 단축키는이를 고려하는 데 도움이 될 수 있습니다.

1GB 메모리를위한 2015 년 C ++ 버전 2 ²⁷ 룩업 테이블 구현 :

#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;
}

업데이트 : 또는 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;
}

참조 URL : https://stackoverflow.com/questions/2267146/what-is-the-fastest-factorization-algorithm

'ProgramingTip' 카테고리의 다른 글

사용할 설치 제품은 무엇입니까? (0)	2021.01.09
jqGrid의 숨겨진 열 (0)	2021.01.09
Notepad ++ 탐욕스럽지 않은 정규 탐욕 (0)	2021.01.09
숫자를 담을 수있을만큼 큰 변수 유형을 자동으로 선택 (0)	2021.01.09
jQuery를 사용하여 두 번 클릭을 방지하는 방법은 무엇입니까? (0)	2021.01.09

현재글가장 빠른 분해 알고리즘은 무엇입니까?

bestdevel

가장 빠른 분해 알고리즘은 무엇입니까?

가장 빠른 분해 알고리즘은 무엇입니까?

이 다른 질문에 대한 내 대답에서 직접 가져 왔습니다 .

'ProgramingTip' 카테고리의 다른 글

'ProgramingTip'의 다른글

티스토리툴바

가장 빠른 분해 알고리즘은 무엇입니까?

가장 빠른 분해 알고리즘은 무엇입니까?

이 다른 질문에 대한 내 대답에서 직접 가져 왔습니다 .

'ProgramingTip' 카테고리의 다른 글

'ProgramingTip'의 다른글

관련글

티스토리툴바