Geekly Articles each Day

倱われた時間の10の新しい物語

こんにちはHabr a 5 + b 5 + c 5 + d 5 = e 5の圢のディオファントス方皋匏を解くためのプログラムのいく぀かの改良版を曞くこずにより、オむラヌ仮説に関する 䞀連の 蚘事を続けるこずにしたした。


ご存知のように、耇雑な蚈算䞊の問題を解決するには、少なくずも次の点に泚意する必芁がありたす。

  1. 効率的なアルゎリズム
  2. 迅速な実装
  3. 匷力な鉄
  4. 䞊列化

最初の点に最も泚意を払いたした。 その結果を芋おみたしょう。

すぐに、コヌドがC ++で蚘述され、32ビットMS Visual C ++ 2008コンパむラがコンパむルされ、i5-2410M 2.3Ghzマシンのシングルスレッドで起動されたこずに泚目したす。 それほど匷力ではないラップトップに暪たわっおいる間にコヌドを曞く方が䟿利で、64ビットコンパむラが面倒だずいうだけです。 ブラりザヌなどの他のプロセスが動䜜時間にわずかに圱響を䞎える可胜性がある䞀方で、コヌドが枬定のために1回以䞊実行されるこずはめったにないため、時間枬定は正確に茝きたせん。 ただし、私たちの目的では、粟床は蚱容範囲です。

それでも、 Dimchanskyの提出により、a、b、c、d、e> 0の䞊蚘の方皋匏の敎数解を探すこずを明確にしたす。 3番目の解決策がありたすが、倉数は負の倀を取るこずができたす。 それらはすべおここにありたす 。

Oの物語1n 5 


可胜な限り愚かな解決策から始めたしょう。 コヌド

コヌド
long long gcd( long long x, long long y ) { while (x&&y) x>y ? x%=y : y%=x; return x+y; } void tale1( int n ) { for (int a=1; a<=n; a++) for (int b=a+1; b<=n; b++) for (int c=b+1; c<=n; c++) for (int d=c+1; d<=n; d++) for (int e=d+1; e<=n; e++) { long long a5 = (long long)a*a*a*a*a; long long b5 = (long long)b*b*b*b*b; long long c5 = (long long)c*c*c*c*c; long long d5 = (long long)d*d*d*d*d; long long e5 = (long long)e*e*e*e*e; if (a5 + b5 + c5 + d5 == e5) if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } }


実際、これは最も愚かなものではありたせん。1からnたでのすべおの倉数を操䜜し、最埌にa <b <c <d <eであるこずを確認できるためです。 しかし、それから私はあたりにも長く埅たなければなりたせん。 䜜業時間
n時間
1001563ms
20040代
50074m

長所フェルトブヌツのようにシンプルで、すぐに蚘述でき、O1メモリが必芁であり、叀兞的な解27 5 + 84 5 + 110 5 + 133 5 = 144 5を芋぀けたす。
短所 犁止されおいたす。

Oの物語2n 4 log n


゜リュヌションを少しスピヌドアップしたしょう。 実際、このオプションは同志drBasicによっお提案されたものず同等です 。

コヌド
 void tale2( int n ) { vector< pair< long long, int > > vec; for (int a=1; a<=n; a++) vec.push_back( make_pair( (long long)a*a*a*a*a, a ) ); for (int a=1; a<=n; a++) for (int b=a+1; b<=n; b++) for (int c=b+1; c<=n; c++) for (int d=c+1; d<=n; d++) { long long a5 = (long long)a*a*a*a*a; long long b5 = (long long)b*b*b*b*b; long long c5 = (long long)c*c*c*c*c; long long d5 = (long long)d*d*d*d*d; long long sum = a5+b5+c5+d5; vector< pair< long long, int > >::iterator it = lower_bound( vec.begin(), vec.end(), make_pair( sum, 0 ) ); if (it != vec.end() && it->first==sum) if (gcd( a, gcd( gcd( b, c ), gcd( d, it->second ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, it->second ); } }


ここで配列を䜜成し、1からnたでのすべおの数倀の5乗を栌玍したす。次に、バむナリ怜玢で4぀のネストされたルヌプ内で、数倀a 5 + b 5 + c 5 + d 5が配列にあるかどうかを確認したす。
n時間1時間2
1001563ms318ms
20040代4140ms
50074m189
100055m

このオプションはすでに高速で実行されおおり、プログラムがn = 1000で動䜜し終わるのを埅぀忍耐さえありたした。

長所ただ非垞にシンプルで、愚かな゜リュヌションよりも速く、曞くのが簡単で、叀兞的な゜リュヌションを芋぀けたす。
短所 Onメモリが必芁ですが、ただ抑制されおいたす。

On 4 log nの物語3、ただしO1メモリ


実際、すべおの孊䜍を配列に保存し、そこでビンポ怜玢で䜕かを探すのは意味がありたせん。 この配列の䜍眮iの番号はすでにわかっおいたす。 「仮想」アレむで単玔にビン怜玢を実行できたす。 すぐに蚀っおやった

コヌド
 void tale3( int n ) { for (int a=1; a<=n; a++) for (int b=a+1; b<=n; b++) for (int c=b+1; c<=n; c++) for (int d=c+1; d<=n; d++) { long long a5 = (long long)a*a*a*a*a; long long b5 = (long long)b*b*b*b*b; long long c5 = (long long)c*c*c*c*c; long long d5 = (long long)d*d*d*d*d; long long sum = a5+b5+c5+d5; if (sum <= (long long)n*n*n*n*n) { int mi = d, ma = n; // invariant: for mi <, for ma >= while ( mi+1 < ma ) { int s = ((mi+ma)>>1); long long tmp = (long long)s*s*s*s*s; if (tmp < sum) mi = s; else ma = s; } if (sum == (long long)ma*ma*ma*ma*ma) if (gcd( a, gcd( gcd( b, c ), gcd( d, ma ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, ma ); } } }


これで配列は䞍芁になり、玔粋なバむナリ怜玢ができたした。
n時間1時間2時間3
1001563ms318ms490ms
20040代4140ms6728ms
50074m189352秒
100055m

残念ながら、おそらくビン怜玢内で毎回5乗を再蚈算するため、ランタむムは䜎䞋したした。 いいでしょう

長所 O1メモリが必芁で、叀兞的な゜リュヌションを芋぀けたす。
短所以前の゜リュヌションよりも遅い。

Oの物語4n 4 


方皋匏をもう䞀床芋おみたしょう。

a 5 + b 5 + c 5 + d 5 = e 5

たたは、簡単にするために、A =B。

アルゎリズムに4぀のネストされたルヌプを実行させたす。 倀a、b、およびcを修正し、dおよびeの倀の動䜜を確認したす。 いく぀かのd = xに぀いお、A <= Bがyず等しいeの最小倀ずしたす。 d = xの堎合、倀e> yを考慮するこずは意味がありたせん。 たた、d = x + 1の堎合、A <= Bであるeの最小倀はy以䞊です。 ぀たり、dに沿っおeの倀をい぀でも穏やかに増やすこずができ、これにより䜕も芋逃すこずがなくなりたす。 dずeの倀は増加するだけなので、それらに沿った䞀般的な経過にはOn時間かかりたす。 この考え方は、2ポむンタヌメ゜ッドず呌ばれたす。

コヌド
 void tale4( int n ) { for (int a=1; a<=n; a++) for (int b=a+1; b<=n; b++) for (int c=b+1; c<=n; c++) { int e = c+1; for (int d=c+1; d<=n; d++) { long long a5 = (long long)a*a*a*a*a; long long b5 = (long long)b*b*b*b*b; long long c5 = (long long)c*c*c*c*c; long long d5 = (long long)d*d*d*d*d; long long sum = a5+b5+c5+d5; while (e<n && (long long)e*e*e*e*e < sum) e++; if (sum == (long long)e*e*e*e*e) if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } } }


コヌドはビン怜玢の堎合よりも少なく、より倚くの利点がありたす。
n時間1時間2時間3時間4
1001563ms318ms490ms360ms
20040代4140ms6728ms4339ms
50074m189352秒177
100055m46m

隠された定数が倧きいため、この゜リュヌションは、゜リュヌション番号2をOn 4 log nで500のオヌダヌでのみ远い越し始めたす。もちろん、5番目の环乗をより慎重に蚈算するこずで加速できたすが、それを行いたせん。

長所゜リュヌション2よりも挞近的に高速であるため、O1メモリが必芁です。 はい、そうです。
短所最適ずはほど遠い、倧きな隠れた定数。

Oの物語5n 3 


2぀のポむンタヌを䜿甚しおアむデアを開発し、゜リュヌションの残りの郚分を逆さたにしたしょう。 方皋匏A + B = Cがあり、A、B、Cのそれぞれに぀いお、それらを遞択するnA、nB、nCの方法があるずしたす。 Cの倀を修正し、AずBのすべおの有効な倀を昇順で゜ヌトしたしょう。 次に、2぀のポむンタヌを䜿甚しおAずBの倀に沿っお実行し、OnA+ nBに぀いお、Cの珟圚の倀に必芁なすべおをチェックしたす ぀たり、いく぀かの固定Aに぀いおは、Bの倀を枛らしたすが、A + B> Cです。 A + B <= Cになるずすぐに、Bをさらに枛らす意味はありたせん。 次に、Aを増やし、Bを枛らすプロセスを続けたす。アルゎリズム党䜓はOnAlog nA+ nBlog nB+nA+ nBn C。

AずBが同じセットの芁玠である堎合、珟圚のAずBが䞀臎するずすぐに、固定Cをチェックするアルゎリズムを停止できたす䞀般性を倱うこずなく、A <Bず仮定できるため。

ここで、方皋匏では、Aに察しおa 5 + b 5 、Bに察しおc 5 + d 5 、Cに察しおe 5を瀺したす。そしお、次のコヌドを蚘述したす。

コヌド
 void tale5( int n ) { vector< pair< long long, int > > vec; for (int a=1; a<=n; a++) for (int b=a+1; b<=n; b++) { long long a5 = (long long)a*a*a*a*a; long long b5 = (long long)b*b*b*b*b; if (a5 + b5 < (long long)n*n*n*n*n) // avoid overflow for n<=5000 vec.push_back( make_pair( a5+b5, (a<<16)+b ) ); } sort( vec.begin(), vec.end() ); for (int e=1; e<=n; e++) { long long e5 = (long long)e*e*e*e*e; int i = 0, j = (int)vec.size()-1; while( i < j ) { while ( i < j && vec[i].first + vec[j].first > e5 ) j--; if ( vec[i].first + vec[j].first == e5 ) { int a = (vec[i].second >> 16); int b = (vec[i].second & ((1<<16)-1)); int c = (vec[j].second >> 16); int d = (vec[j].second & ((1<<16)-1)); if (b < c && gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } i++; } } }


ペアa、bおよびc、dの順序はn 2であるため、゜ヌトにはOn 2 log nが必芁になり、ポむンタヌを䜿甚した以降のチェックはOn 3 になりたす。 総ネットキュヌブ。

゚クササむズ 。 䞊蚘のコヌドで論理゚ラヌを芋぀けたす。

答えを芋る前に数分考えおください。
私たちの堎合、゜ヌトされた配列では、理論的には同じ合蚈が萜ち、2぀のポむンタヌがいく぀かの等匏をスキップする可胜性がありたす。 しかし、実際には、それらはすべお次の掚論ずは異なりたす偶然の䞀臎がある堎合、x、y、z、tに぀いおx ^ 5 + y ^ 5 = z ^ 5 + t ^ 5であり、 この仮説に察する反䟋を芋぀けたした。 修正ずしお、あなたができる最も簡単なこずは、すべおの数倀が本圓に異なるこずを確認するこずです。

n12345
1001563ms318ms490ms360ms82ms
20040代4140ms6728ms4339ms121ms
50074m189352秒177516ms
100055m46m3119ms
2000幎22秒
5000328

倧幅な加速により、蚱容可胜な時間内でn = 5000をドラッグできたす。 オヌバヌフロヌを回避するために、配列にペアを远加するずきに必芁なチェック。

長所おそらく最速の挞近アルゎリズム。
短所隠された倧きな定数で、最倧5000のオヌダヌのnたでしか機胜せず、On 2 のメモリを消費したす。

信じられないほど小さな隠れた定数を持぀On 4 log nの物語6


突然。 このコメントからのナヌザヌの提出erwins22から、5乗を11で陀算するこずによっお埗られる残差を考慮したす。぀たり、aをx 5 = a mod 11ず比范できるものです。aの可胜な倀は0、1および-1mod 11ご自身で確認しおください。

次に、等匏a 5 + b 5 + c 5 + d 5 = e 5ナニットずマむナスナニットでは、合蚈数は偶数でありパリティが収束するように互いにバランスをずる必芁がありたす、数a、b、c、 d、eは0からモゞュヌル11たで、぀たり11で割った倀に盞圓したす。1方向に分けお、2぀のオプションのいずれかを取埗したす。

a 5 + b 5 +c 5 + d 5 = e 5 ; e = 0 mod 11

e 5 -a 5 -b 5 + c 5 = d 5 ; d = 0 mod 11

信じられたせんが、数倀xが11で割り切れる堎合、数倀x 5は161051で割り切れたす。したがっお、䞊蚘の等匏の巊偎は161051で割り切れるはずです。 ご芧のずおり、䞊蚘の匏では、括匧を䜿甚しお既にいく぀かの数倀が慎重にペアリングされおいたす。 ここで、最初のブラケットを修正するず、2番目のブラケットは161051で割ったずきにすべおの可胜な161051残基のうちの1぀だけを持぀こずができたす。したがっお、O すべおを調べお、結果が正確な5床たずえば、5床の配列の双県鏡であるかどうかを確認するず、On 4 log n / 161051ですべおの解が芋぀かりたす。 コヌド

コヌド
 void tale5( int n ) { vector< pair< long long, int > > vec; for (int a=1; a<=n; a++) for (int b=a+1; b<=n; b++) { long long a5 = (long long)a*a*a*a*a; long long b5 = (long long)b*b*b*b*b; if (a5 + b5 < (long long)n*n*n*n*n) // avoid overflow for n<=5000 vec.push_back( make_pair( a5+b5, (a<<16)+b ) ); } vector< pair< long long, int > > pows; for (int a=1; a<=n; a++) pows.push_back( make_pair( (long long)a*a*a*a*a, a ) ); // a^5 + b^5 + c^5 + d^5 = e^5 for (int a=1; a<=n; a++) for (int b=a+1; b<=n; b++) { long long a5 = (long long)a*a*a*a*a; long long b5 = (long long)b*b*b*b*b; long long rem = (z - (a5+b5)%z)%z; for (int i=0; i<(int)vec[rem].size(); i++) { long long sum = a5 + b5 + vec[rem][i].first; vector< pair< long long, int > >::iterator it = lower_bound( pows.begin(), pows.end(), make_pair( sum, 0 ) ); if (it != pows.end() && sum == it->first) { int c = (vec[rem][i].second >> 16); int d = (vec[rem][i].second & ((1<<16)-1)); int e = it->second; if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } } } // e^5 - a^5 - b^5 - c^5 = d^5 for (int e=1; e<=n; e++) for (int a=1; a<e; a++) { long long e5 = (long long)e*e*e*e*e; long long a5 = (long long)a*a*a*a*a; long long rem = (e5-a5)%z; for (int i=0; i<(int)vec[rem].size(); i++) if (e5-a5 > vec[rem][i].first) { long long sum = e5 - a5 - vec[rem][i].first; vector< pair< long long, int > >::iterator it = lower_bound( pows.begin(), pows.end(), make_pair( sum, 0 ) ); if (it != pows.end() && sum == it->first) { int b = (vec[rem][i].second >> 16); int c = (vec[rem][i].second & ((1<<16)-1)); int d = it->second; if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } } } }


この゜リュヌションの䜜業時間
n123456
1001563ms318ms490ms360ms82ms129ms
20040代4140ms6728ms4339ms121ms140ms
50074m189352秒177516ms375ms
100055m46m3119ms2559ms
2000幎22秒38代
500032828m

この衚は、n = 500およびn = 1000の堎合、この゜リュヌションが立方䜓の゜リュヌションを远い抜くこずさえ瀺しおいたす。 しかし、それでもキュヌビック゜リュヌションは匷く远い越し始めたす。 挞近的、圌女は-あなたは圌女を欺くこずはできたせん。

長所非垞に匷力なクリッピング。
短所挞近的な動䜜が倧きいため、このアむデアを3次解に結び付ける方法は明確ではありたせん。

物語7 On 3 の128ビット数


モゞュヌルのトリックを䞀時的に忘れたしょう少し埌で芚えたすそしお、キュヌビック゜リュヌションをやり盎しお、n> 5000で正しく動䜜するようにしたす。 これを行うために、128ビット敎数を実装したす。

コヌド
 typedef unsigned long long uint64; typedef pair< uint64, uint64 > uint128; uint128 operator+ (const uint128 & a, const uint128 & b) { uint128 re = make_pair( a.first + b.first, a.second + b.second ); if ( re.second < a.second ) re.first++; return re; } uint128 operator- (const uint128 & a, const uint128 & b) { uint128 re = make_pair( a.first - b.first, a.second - b.second ); if ( re.second > a.second ) re.first--; return re; } uint128 power5( int x ) { uint64 x2 = (uint64)x*x; uint64 x3 = (uint64)x2*x; uint128 re = make_pair( (uint64)0, (uint64)0 ); uint128 cur = make_pair( (uint64)0, x3 ); for (int i=0; i<63; i++) { if ((x2>>i)&1) re = re + cur; cur = cur + cur; } return re; } void tale7( int n ) { vector< pair< uint128, int > > vec = vector< pair< uint128, int > >( n*n/2 ); uint128 n5 = power5( n ); int ind = 0; for (int a=1; a<=n; a++) for (int b=a+1; b<=n; b++) { uint128 a5 = power5( a ); uint128 b5 = power5( b ); if (a5 + b5 < n5) vec[ind++] = make_pair( a5+b5, (a<<16)+b ); } sort( vec.begin(), vec.begin()+ind ); for (int e=1; e<=n; e++) { uint128 e5 = power5( e ); int i = 0, j = ind-1; while( i < j ) { while ( i < j && vec[i].first + vec[j].first > e5 ) j--; if ( vec[i].first + vec[j].first == e5 ) { int a = (vec[i].second >> 16); int b = (vec[i].second & ((1<<16)-1)); int c = (vec[j].second >> 16); int d = (vec[j].second & ((1<<16)-1)); if (b < c && gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } i++; } } }


完了する必芁のあった操䜜は、加算ず5乗です。 ただ枛算があり、この゜リュヌションでは必芁ありたせんが、埌で必芁になりたす。 したがっお、それをさせおください。 128ビットの数倀はペアずしお実装されおいるため、既に<、>、=操䜜があり、必芁に応じお正確に機胜したす。

最初に、ベクトルのサむズをすぐに蚭定したす。 最適化のためにこれが行われおいるわけではありたせん。64ビットコンパむラを発芋するには遅すぎたす。32ビットで䜿甚できるメモリは2 GBのみです。 n = 10000の堎合、ベクタヌごずに玄1.2 GBが必芁です。 push_backを䜿甚しおベクトルを展開するず、展開䞭に最埌に2 GB以䞊をキャプチャしたす長さNから2 * Nに増やすには、3 * Nの䞭間メモリが必芁です。
n1234567
1001563ms318ms490ms360ms82ms129ms20ms
20040代4140ms6728ms4339ms121ms140ms105ms
50074m189352秒177516ms375ms1014ms
100055m46m3119ms2559ms7096ms
2000幎22秒38代52代
500032828m13m
10,00089m

プログラムが゜リュヌション5に比べおほが2倍遅くなったこずがわかりたすが、新しい難攻䞍萜のピヌクn = 10000を埁服したした

長所 n> 5000でオヌバヌフロヌしないようになりたした。
短所解決策5の2倍遅く動䜜し、倧量のメモリを消費したす。

隠された定数が小さいOn 3 の物語8


11で割ったずきの剰䜙に぀いおもう䞀床思い出しおください。2぀の等匏がありたす。

a 5 + b 5 +c 5 + d 5 = e 5 ; e = 0 mod 11

e 5 -a 5 -b 5 + c 5 = d 5 ; d = 0 mod 11

11を法ずする5床の剰䜙には垞に0、1、たたは-1の剰䜙がありたす。 a <b <c <dずいう圢匏の制玄を削陀し、数倀をあるブラケットから別のブラケットに任意に移動させたす。 その埌、すべおのケヌスを考慮するこずにより各ブラケットが11を法ずしお0に等しくなるようにい぀でも移動できるこずを瀺すのは簡単です。それでは、1からnたでの数字のすべおのペアを゜ヌトし、5床の合蚈ず差を芋぀け、 11で割り切れるものだけを芚えおおいおください。そしお、残りのペアは単玔に捚おるこずができたす。

この事実を定匏化できたす。そのようなペアの数は、ペアの総数の玄51/121になりたすこれがなぜそうなのかを考えおください。 残念ながら、このようなペアの2぀の配列を保存する必芁がありたす合蚈ず差分。これにより、メモリゲむンは102/121になりたす。 たあ、15も削枛です。 しかし、その埌、これらの配列で少し実行する必芁がありたす。

最埌に、最良のニュヌス倉数の1぀キュヌビック゜リュヌションで最も倖郚的を11のステップで敎理するのが理にかなっおいたす。悪いニュヌスは、䞡方のタむプの等匏を別々に解決する必芁があるずいうこずです。 悲しいこずに、悲しいこずに、これは、゜リュヌション6のように11 5倍ではなく、プログラムを11倍だけ高速化したす実際、ただ事実ではありたせん。

コヌド
 void tale8( int n ) { vector< pair< uint128, pair< int, int > > > vec_p, vec_m; uint128 n5 = power5( n ); for (int a=1; a<=n; a++) for (int b=1; b<a; b++) { uint128 a5 = power5( a ); uint128 b5 = power5( b ); int A = a%11; int B = b%11; int A5 = (A*A*A*A*A)%11; int B5 = (B*B*B*B*B)%11; if ( (A5+B5)%11 == 0 ) vec_p.push_back( make_pair( a5+b5, make_pair( a, b ) ) ); if ( (A5-B5+11)%11 == 0) vec_m.push_back( make_pair( a5-b5, make_pair( a, b ) ) ); } sort( vec_p.begin(), vec_p.end() ); sort( vec_m.begin(), vec_m.end() ); // (a^5 + b^5) + (c^5 + d^5) = e^5 for (int e=11; e<=n; e+=11) { uint128 e5 = power5( e ); int i = 0, j = (int)vec_p.size()-1; while( i < j ) { while ( i < j && vec_p[i].first + vec_p[j].first > e5 ) j--; if ( vec_p[i].first + vec_p[j].first == e5 ) { int a = vec_p[i].second.first; int b = vec_p[i].second.second; int c = vec_p[j].second.first; int d = vec_p[j].second.second; if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } i++; } } // (e^5 - a^5) - (b^5 + c^5) = d^5 for (int d=11; d<=n; d+=11) { uint128 d5 = power5( d ); int i = 0, j = 0, mx_i = (int)vec_m.size(), mx_j = (int)vec_p.size(); while (i < mx_i && j < mx_j) { while (j < mx_j && vec_m[i].first > vec_p[j].first && vec_m[i].first - vec_p[j].first > d5) j++; if ( j < mx_j && vec_m[i].first > vec_p[j].first && vec_m[i].first - vec_p[j].first == d5 ) { int e = vec_m[i].second.first; int a = vec_m[i].second.second; int b = vec_p[j].second.first; int c = vec_p[j].second.second; if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } i++; } } }


ここでは、ベクタヌの展開により、幞運であり、n = 10000のプログラムは2GBに収たりたす。
n12345678
1001563ms318ms490ms360ms82ms129ms20ms16ms
20040代4140ms6728ms4339ms121ms140ms105ms49ms
50074m189352秒177516ms375ms1014ms472ms
100055m46m3119ms2559ms7096ms2110ms
2000幎22秒38代52代13秒
500032828m13m161s
10,00089m20m

悲しいかな、プログラムは4.5倍だけ加速したした。 ご芧のずおり、2番目の匏の倚数のチェックにより、隠れた定数が倧きく損なわれおいたす。 たあ、䜕も、最適化の䜙地はただありたせん。 今最倧の問題野生のメモリ消費。 珟圚のレコヌドに間に合うようにnがすでに蚱容できる堎合、メモリからは適合しなくなりたす。

長所おそらく最速の゜リュヌションが提案されたした。
短所䟝然ずしおメモリ消費量が倚いずいう問題。

On 3 log nのメモリ消費量がOnの堎合の物語9


メモリ消費をどのように削枛したすか ここで説明したトリックを掻甚したしょう。 すなわち、nよりも倧きい玠数pを取りたすが、あたり倚くは取りたせん。 私たちが持っおいる最初の方皋匏を考えたす2番目の方皋匏も同様に考えられたす

a 5 + b 5 +c 5 + d 5 = e 5 ; e = 0 mod 11

次に、a 5 + b 5 = w mod pを0からp-1たでの䞀郚のwずしたす。 この比范を満たすペアa、bの数は線圢数です。 これを瀺すために、パラメヌタヌaを1からnたで繰り返したす。 次に、bを芋぀けるには、b 5 =w-a 5 = u mod pずいう比范を解く必芁がありたす。 そしお、この比范には垞に1぀以䞊の解決策はないず䞻匵されおいたす。 これは、 e-maxxのこのペヌゞから続きたす。 そこで、1぀からすべおの解を埗るための公匏に泚意を払う必芁がありたす。



぀たり、すべおの解の䞭で、gcd5、phip= gcd5、p-1です。 ぀たり、p = 5q + 1の堎合、5぀の゜リュヌションたたはなしがあり、残りのケヌスでは1぀しか゜リュヌションがありたせん。

ちなみに、この匏の由来ず動䜜はわかりたせん。゜ヌスを知っおいる人がいる堎合は、どこで明確に蚘述されおいるか、リンクを共有しおください。

ここで問題は、固定uのbを芋぀ける方法ですか これを䞀床だけ、しかし迅速に行うには、数字の理論をかなり理解する必芁がありたす。 しかし、uのすべおの可胜な倀に察しおbが必芁なので、各bに察しおuを芋぀けおプレヌトに曞き蟌むこずができたす。そのようなuの堎合、そのような解はbです。

さらに、固定wおよび固定e 5の堎合、c 5 + d 5 =e 5 -wmod pが埗られたす。 比范を満たす線圢の数のペアもありたす。

぀たり、固定のwず固定のeに察しお、゜ヌトする必芁がある線圢の数のペアを取埗し残念なこずに、挞近線の䜙分な察数がここに衚瀺されたす、2぀のポむンタヌを䜿甚したす。 wずeの異なる倀は次数Onであるため、䞀般的な挞近挙動はOn 3 log nです。

怖いテストコヌドを曞きたしょう

コヌド
 bool is_prime( int x ) { if (x<2) return false; for (int a=2; a*a<=x; a++) if (x%a==0) return false; return true; } void tale9( int n ) { int p = n+1; while ( p%5==1 || !is_prime( p ) ) p++; vector< int > sols = vector< int >( p, -1 ); for (int i=1; i<=n; i++) { uint64 tmp = ((uint64)i*i)%p; tmp = (((tmp*tmp)%p)*i)%p; sols[(unsigned int)tmp] = i; } for (int w=0; w<p; w++) { // (a^5 + b^5) + (c^5 + d^5) = e^5 // (a^5 + b^5) = w (mod p) vector< pair< uint128, pair< int, int > > > vec1; for (int a=1; a<=n; a++) { uint64 a5p = ((uint64)a*a)%p; a5p = ((a5p*a5p)%p*a)%p; int b = sols[ (w - a5p + p)%p ]; if (b!=-1 && b<a) { uint128 a5 = power5( a ); uint128 b5 = power5( b ); int A = a%11, A5 = (A*A*A*A*A)%11; int B = b%11, B5 = (B*B*B*B*B)%11; if ( (A5+B5)%11 == 0 ) vec1.push_back( make_pair( a5+b5, make_pair( a, b ) ) ); } } sort( vec1.begin(), vec1.end() ); for (int e=11; e<=n; e+=11) { // (a^5 + b^5) + (c^5 + d^5) = e^5 // (a^5 + b^5) = w (mod p) // (c^5 + d^5) = (e^5 - w) = q (mod p) uint64 e5p = ((uint64)e*e)%p; e5p = ((e5p*e5p)%p*e)%p; int q = (int)((e5p - w + p)%p); vector< pair< uint128, pair< int, int > > > vec2; for (int c=1; c<=n; c++) { uint64 c5p = ((uint64)c*c)%p; c5p = ((c5p*c5p)%p*c)%p; int d = sols[ (q - c5p + p)%p ]; if (d!=-1 && d<c) { uint128 c5 = power5( c ); uint128 d5 = power5( d ); int C = c%11, C5 = (C*C*C*C*C)%11; int D = d%11, D5 = (D*D*D*D*D)%11; if ( (C5+D5)%11 == 0 ) vec2.push_back( make_pair( c5+d5, make_pair( c, d ) ) ); } } sort( vec2.begin(), vec2.end() ); uint128 e5 = power5( e ); int i = 0, j = (int)vec2.size()-1, mx_i = (int)vec1.size(); while( i < mx_i && j >= 0 ) { while ( j >= 0 && vec1[i].first + vec2[j].first > e5 ) j--; if ( j >= 0 && vec1[i].first + vec2[j].first == e5 ) { int a = vec1[i].second.first; int b = vec1[i].second.second; int c = vec2[j].second.first; int d = vec2[j].second.second; if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } i++; } } // (e^5 - a^5) - (b^5 + c^5) = d^5 // (b^5 + c^5) = w (mod p) // already computed as vec1 for (int d=11; d<=n; d+=11) { // (e^5 - a^5) = (d^5 + w) = q (mod p) uint64 d5p = ((uint64)d*d)%p; d5p = ((d5p*d5p)%p*d)%p; int q = (int)((d5p + w)%p); vector< pair< uint128, pair< int, int > > > vec2; for (int e=1; e<=n; e++) { uint64 e5p = ((uint64)e*e)%p; e5p = ((e5p*e5p)%p*e)%p; int a = sols[ (e5p - q + p)%p ]; if (a!=-1 && a<e) { uint128 e5 = power5( e ); uint128 a5 = power5( a ); int E = e%11, E5 = (E*E*E*E*E)%11; int A = a%11, A5 = (A*A*A*A*A)%11; if ( (E5-A5+11)%11 == 0 ) vec2.push_back( make_pair( e5-a5, make_pair( e, a ) ) ); } } sort( vec2.begin(), vec2.end() ); uint128 d5 = power5( d ); int i = 0, j = 0, mx_i = (int)vec2.size(), mx_j = (int)vec1.size(); while (i < mx_i && j < mx_j) { while (j < mx_j && vec2[i].first > vec1[j].first && vec2[i].first - vec1[j].first > d5) j++; if ( j < mx_j && vec2[i].first > vec1[j].first && vec2[i].first - vec1[j].first == d5 ) { int e = vec2[i].second.first; int a = vec2[i].second.second; int b = vec1[j].second.first; int c = vec1[j].second.second; if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } i++; } } } }


この残酷なブリキを実行したす
n123456789
1001563ms318ms490ms360ms82ms129ms20ms16ms219ms
20040代4140ms6728ms4339ms121ms140ms105ms49ms1741ms
50074m189352秒177516ms375ms1014ms472ms25秒
100055m46m3119ms2559ms7096ms2110ms200代
2000幎22秒38代52代13秒28m
500032828m13m161s
10,00089m20m

玳士、石噚時代ぞようこそなぜそれは䞍敬lyに遅くなるのですかそうそう、3぀の入れ子になったルヌプの䞀番䞋にpower5関数があり、ルヌプ内で既に63回の反埩が行われおいたす。組み蟌み関数を曞き換えたすか静かに、次の゜リュヌションでは、事前に蚈算されたプレヌトから答えをドラッグするだけです。

しかし、今ではメモリをほずんど消費せず、1぀の非垞に䟿利なプロパティが登堎したした。タスクを独立したサブタスクに分割できるようになりたした。぀たり、「䞊列化」、぀たり蚈算を耇数のコアに分散できたす぀たり、各コアに察しお、パラメヌタヌwの独自の倀を指定したす。これらのwを0からp-1たでのすべおの数倀でカバヌする堎合、問題のすべおのケヌスをカバヌしたすが、すべおのカヌネルの負荷はほが均等に分散されたす。

長所わずかなメモリしか消費せず、分散コンピュヌティングをサポヌトしたす。
短所二日酔いの靎屋のように遅くなりたす。

筋金入りの最適化によるOn 3 log nの物語10


゜リュヌション9を採甚し、ハヌドコアな最適化を远加したす。たあ、実際、圌らはそれほどハヌドコアではありたせん。しかし、それらの倚くがありたす。


そしお、コヌドを取埗したす。

コヌド
 #define MAXN 100500 int pow5modp[MAXN]; int sols[MAXN]; uint128 vec1[MAXN], vec2[MAXN]; int vec1_sz, vec2_sz; uint128 pow5[MAXN]; int pow5mod11[MAXN]; void init_arrays( int n, int p ) { for (int i=1; i<=n; i++) { uint64 i5p = ((uint64)i*i)%p; i5p = (((i5p*i5p)%p)*i)%p; pow5modp[i] = (int)i5p; } for (int i=0; i<p; i++) sols[i] = -1; for (int i=1; i<=n; i++) sols[pow5modp[i]] = i; for (int i=1; i<=n; i++) pow5[i] = power5(i); for (int i=1; i<=n; i++) { int ii = i%11; pow5mod11[i] = (ii*ii*ii*ii*ii)%11; } } void tale10( int n, int start=0, int step=1 ) { int p = n+1; while ( p%5==1 || !is_prime( p ) ) p++; init_arrays( n, p ); for (int w=start; w<p; w+=step) { cerr << "n=" << n << " p=" << p << " w=" << w << "\n"; // (a^5 + b^5) + (c^5 + d^5) = e^5 // (a^5 + b^5) = w (mod p) vec1_sz = 0; for (int a=1; a<=n; a++) { int tmp = w - pow5modp[a]; int b = sols[ tmp<0 ? tmp+p : tmp ]; if (b!=-1 && b<a) if ( (pow5mod11[a]+pow5mod11[b])%11 == 0 ) vec1[vec1_sz++] = pow5[a]+pow5[b]; } sort( vec1, vec1 + vec1_sz ); for (int e=11; e<=n; e+=11) { // (a^5 + b^5) + (c^5 + d^5) = e^5 // (a^5 + b^5) = w (mod p) // (c^5 + d^5) = (e^5 - w) = q (mod p) int q = (int)((pow5modp[e] - w + p)%p); uint128 e5 = pow5[e]; vec2_sz = 0; for (int c=1; c<e; c++) { int tmp = q - pow5modp[c]; int d = sols[ tmp<0 ? tmp+p : tmp ]; if (d!=-1 && d<c) if ( pow5mod11[c]+pow5mod11[d]==0 || pow5mod11[c]+pow5mod11[d]==11 ) { uint128 s = pow5[c]+pow5[d]; if (s < e5) vec2[vec2_sz++] = s; } } sort( vec2, vec2 + vec2_sz ); int i = 0, j = vec2_sz-1, mx_i = vec1_sz-1; while( i < mx_i && j >= 0 ) { while ( j >= 0 && vec1[i] + vec2[j] > e5 ) j--; if ( j >= 0 && vec1[i] + vec2[j] == e5 ) { int a=-1, b=-1, c=-1, d=-1; for (int A=1; A<=n; A++) for (int B=1; B<A; B++) if (pow5[A]+pow5[B]==vec1[i]) { a=A; b=B; } for (int C=1; C<=n; C++) for (int D=1; D<C; D++) if (pow5[C]+pow5[D]==vec2[j]) { c=C; d=D; } if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } i++; } } // (e^5 - a^5) - (b^5 + c^5) = d^5 // (b^5 + c^5) = w (mod p) // already computed as vec1 for (int d=11; d<=n; d+=11) { // (e^5 - a^5) = (d^5 + w) = q (mod p) int q = (int)((pow5modp[d] + w)%p); uint128 d5 = pow5[d]; vec2_sz = 0; for (int e=d+1; e<=n; e++) { int tmp = pow5modp[e]-q; int a = sols[ tmp<0 ? tmp+p : tmp ]; if (a!=-1 && a<e) if ( pow5mod11[e]==pow5mod11[a] ) { uint128 s = pow5[e]-pow5[a]; if (s > d5) vec2[vec2_sz++] = s; } } sort( vec2, vec2 + vec2_sz ); int i = 0, j = 0, mx_i = vec2_sz, mx_j = vec1_sz; while (i < mx_i && j < mx_j) { while (j < mx_j && vec2[i] > vec1[j] && vec2[i] - vec1[j] > d5) j++; if ( j < mx_j && vec2[i] > vec1[j] && vec2[i] - vec1[j] == d5 ) { int e=-1, a=-1, b=-1, c=-1; for (int E=1; E<=n; E++) for (int A=1; A<E; A++) if (pow5[E]-pow5[A]==vec2[i]) { e = E; a = A; } for (int B=1; B<=n; B++) for (int C=1; C<B; C++) if (pow5[B]+pow5[C]==vec1[j]) { b = B; c = B; } if (gcd( a, gcd( gcd( b, c ), gcd( d, e ) ) ) == 1) printf( "%d^5 + %d^5 + %d^5 + %d^5 = %d^5\n", a, b, c, d, e ); } i++; } } } }


コヌドは、よりコンパクトでシンプルで芪切になりたした。そしお圌はより速くなりたした
n12345678910
1001563ms318ms490ms360ms82ms129ms20ms16ms219ms8ms
20040代4140ms6728ms4339ms121ms140ms105ms49ms1741ms30ms
50074m189352秒177516ms375ms1014ms472ms25秒379ms
100055m46m3119ms2559ms7096ms2110ms200代2993ms
2000幎22秒38代52代13秒28m24秒
500032828m13m161s405s
10,00089m20m59m

倚少の惚めな10 MBのメモリを䜿甚しお、n = 10000のすべおのオプションを倚少蚱容できる時間でチェックしたした。

長所十分に速く、ほずんどメモリを消費したせん。
短所そうではありたせん。

おずぎ話にも、説明するペンにもありたせん


そしお今、私は64ビットのコンパむラヌ、6コアのi7-5820K 3.3GHzず4コアのi7-3770 3.4GHzをワむドレッグから取り出し、16の独立したストリヌムで数日間゜リュヌション10を実行したす。
n総コアリアルタむムストリヌム
10,00029m29m1
20000318m58m6
50,000105時間7時間16
100,000970h62時間16

n = 100000の正確な時間
00 221897112ms
01 221697012ms
02 221413313ms
03 219200228ms
04 222362721ms
05 221386814ms
06 221880726ms
07 219676217ms **
08 222212701ms
09 221865811ms
10 213299815ms *
11 211880251ms
12 211634584ms **
13 210114095ms
14 211691320ms *
15 212125515ms
* found 27^5 + 133^5 + 133^5 + 110^5 = 144^5
** found 85282^5 + 28969^5 + 28969^5 + 55^5 = 85359^5
00-09 : i7-5820K 3.3GHz
10-15 : i7-3770 3.4GHz
sum ~ 970h
max ~ 62h


より高速なマシンでの64ビットプログラム以前にi5-2410M 2.3Ghzでコヌドをテストしたこずを思い出しおくださいは、玄2倍速く動䜜したす。その結果、ドラッグN = 100000に管理され、所望のディオファントス方皋匏の第二の解決策を芋぀けるこず

55 5 + 3183 5 + 28969 5 + 85282 5 = 85359 5

おずぎ話はうそですが、その䞭のヒント


そのため、ここでは最速の挞近的振る舞いが実際には最良ではない最速の゜リュヌションではありたせん。

理論的には、コヌドを高速化するか、察数を挞近線から切り捚おるこずができたすが、珟時点では最適化にうんざりしおいたす-すでに十分な時間を倱っおいたす。解決策の察数に関しおは、クむック゜ヌトを基数゜ヌトに眮き換えたすただし、定数は宇宙次元に増加したす、たたは2぀のポむンタヌのアむデアの代わりにハッシュテヌブルを䜿甚したすここでは、どちらが実際に速いかを既に確認しお確認する必芁がありたす。プロファむリングにより、n = 10000の堎合、゜ヌトは党䜓の玄半分になりたす。぀たり、nの倀が小さい堎合、察数は非垞に蚱容範囲です。加速に関しおは、確かに、プログラムを5〜10倍高速化できるモゞュヌルにはただいく぀かのトリックがありたす。

ドラッグ


たた、nを100䞇個たですべおチェックするずいうワむルドなアむデアもありたす。予想される怜蚌時間は、原則ずしお珟実的であり、玄100䞇コア時間です。しかし、これに察する私の胜力は明らかに十分ではありたせん。䞀緒に匕っ匵るしかし、誰が既に敎理したかに぀いおの情報は芋぀かりたせんでした。すべおが長い間数えられおきたので、癟䞇たで調べおも意味がないかもしれたせん。誰かがこれに関する情報を持っおいるなら、退䌚しおください。

これで物語は終わり、誰がマスタヌしたか-よくやった

Source: https://habr.com/ru/post/J318244/

More articles:


All Articles