ピタゴリアントリプルの計算

Question

ピタゴラスのトリプルを計算するコードを書いていましたが、解決策ではない値がいくつかありました。コードは次のとおりです。

#include <iostream> 
#include <math.h> 

using namespace std; 

int main() 
{ 
int j, counter = 0; 
double candidate, sqrnbr; 
for (int i = 400; i <= 500; i++) //note that the range is only from 400-500 since I am still testing the code 
{ 
    for (j = i; j <= 500; j++) 
    { 
     candidate = i*i+j*j; 
     sqrnbr=sqrt(candidate); 
     if (candidate/sqrnbr==sqrnbr) 
     { 
      cout << i << " and " << j << " and " << sqrnbr << endl; 
      counter++; 
     } 
    } 

} 
cout << counter << endl; 
system("pause"); 
return 0; 
} 

出力の1つは、408,410、および578.415です。誰がなぜこれが起こるのか知っていますか？

Answer 1

doubleを計算し、それが整数値かどうかを決して確認しないでください。doubleという値が得られます。平方根がdoubleとして、一般的に表現することができませんので、あなたはそう

candidate/sqrnbr == sqrnbr 

がcandidateの多くの値は偽である、より多く得ることはありません。

ピタゴラスのトリプレットを生成するには、整数演算のみを使用してください。そして、ブルートフォースよりも良い方法があり、古典的な式は、すべてのピタゴラスのトリプレットは、いくつかのd, m, nため

d*(m^2 - n^2), d*2*m*n, d*(m^2 + n^2) 

形式である、があります。

Answer 2

ロジックに問題がありました。

私はあなたのコードを再フォーマットし、それが私の作品：

#include <iostream> 
#include <math.h> 

using namespace std; 

int main() { 
    int counter = 0; 
    float candidate; 

    for (int i = 1; i <= 500; i++) { 
    for (int j = 1; j <= 500; j++) { 
     candidate = sqrt(i*i + j*j); 

     if (int(candidate) == candidate) { 
     cout << i << " and " << j << " and " << candidate << endl; 
     counter++; 
     } 
    } 
    } 

    cout << counter << endl; 
    return 0; 
} 

sqrt(sum)がintあるかどうかを確認するには、ちょうどintにキャストすると、その値を変更するかどうかを確認してください。

Answer 3

2倍の平等の比較は、一般的に悪い考えです。注sqrt周りfloor

#include <iostream> 
#include <math.h> 

using namespace std; 

int main() { 
    int j, k, counter = 0, candidate; 
    double sqrnbr; 
    for (int i = 400; i <= 500; i++) { 
     for (j = i; j <= 500; j++) { 
      candidate = i*i+j*j; 
      sqrnbr=floor(sqrt(candidate)); 
      if ((sqrnbr*sqrnbr)==candidate) { 
       cout << i << " and " << j << " and " << sqrnbr << endl; 
       counter++; 
      } 
     } 
    } 
    cout << counter << endl; 
    system("pause"); 
    return 0; 
} 

：あなたは候補者のint行い、このようなプログラムを周りに変更する必要があり、それは、平方根の非整数部分を削除します。

Answer 4

あなたのアルゴリズムは間違っています。

if ((candidate/sqrnbr) == floor(sqrnbr))

これは、あなたが全体の数字を持っている場合、あなたのif文の内部で終わるを確認してください：

はあなたのifにを変更してみてください。

Answer 5

#include <iostream> 

using namespace std; 

int main() 
{ 
    int side1, side2, side3; 
    int counter=0; 
    for(side1=1;side1<=500;side1++) 
    for(side2=1;side2<=500;side2++) 
    for(side3=1;side3<=500;side3++) 
     { 
     int t1, t2, t3; 
     t3=side1 * side1 + side2 *side2; 
     t2=side1 * side1 + side3 * side3; 
     t1=side2 * side2 + side3 * side3; 
     if(t3==side3 * side3 || t2==side2 * side2 || t1==side1 * side1) 
     { 
      cout<<side1<<" , "<<side2<<", "<<side3<<endl; 
      counter++; 

     } 
     } 
    cout<<endl<<counter/6; 
} 

Answer 6

このプログラムはプリミティブトリプレットを生成します。開始と終了のコマンドライン引数をとります。また、多数のワーカースレッドを8つ使用します。 私はbとc <500000というプリミティブを生成するためにこれをテストしました。

#include <cmath> 
#include <iostream> 
#include <thread> 
#include <fstream> 
#include <chrono> 

using namespace std; 

#define MAX_INT64  (0X7FFFFFFFFFFFFFFFLL) 
#define MOD(a,b)  (a%b) 
#define SQRT(x)   (sqrt(x)) 
#define TRUNC(x)  ((MYTYPE)(x)) 
#define NUM_BLOCKS  (1000) 
#define WORKER_THREADS (8) 

typedef long long MYTYPE; 
typedef long double MYFLOATTYPE; 

// Structure for a Triple 
typedef struct Triple 
{ 
    MYTYPE A; 
    MYTYPE B; 
    MYTYPE C; 
} Triple; 

// Structure for a block of Triples 
typedef struct TripleBlock 
{ 
    Triple* Triples; 
    long NumTriples; 
    long NumTriplesAllocated; 
    TripleBlock* Next; 
} TripleBlock; 

// Structure for worker thread 
typedef struct ThreadStartData 
{ 
    MYTYPE Min; 
    MYTYPE StartMax; 
    MYTYPE Max; 
    MYTYPE NumDone; 
    MYTYPE NumThreads; 
    MYTYPE Complete; 
    TripleBlock* Block; 
} ThreadStartData; 

void PrintTriples(ThreadStartData* lpParam, ofstream* file); 
TripleBlock* AllocateTripleBlock(long numtriples); 
void AddTriple(MYTYPE a, MYTYPE b, MYTYPE c, TripleBlock* block); 
void CalculateTriples(ThreadStartData* lpParam); 
void ProgressTriples(ThreadStartData* lpParam); 

int main(int argc, char* argv[]) 
{ 
    MYTYPE min = 2; 
    MYTYPE max = 0; 

    if (argc == 1) 
    { 
     max = MAX_INT64; 
    } 
    else if (argc == 2) 
    { 
     max = atol(argv[1]); 
    } 
    else if (argc == 3) 
    { 
     min = atol(argv[1]); 
     max = atol(argv[2]); 
    } 
    else 
    { 
     cout << argv[0] << " [min] max" << endl; 
     return 0; 
    } 
    if (max <= min || min < 1) 
    { 
     cout << "Invalid parameters" << endl; 
     return 0; 
    } 

    int numThreads = WORKER_THREADS; 
    if ((max - min) <= (WORKER_THREADS * 2)) 
     numThreads = 1; 

    MYFLOATTYPE inc = ((MYFLOATTYPE)max - (MYFLOATTYPE)min)/((MYFLOATTYPE)numThreads); 
    MYFLOATTYPE current = (MYFLOATTYPE)min; 

    // set up ThreadStartData 
    ThreadStartData* data = new ThreadStartData[numThreads]; 
    for (int i = 0; i < numThreads; i++) 
    { 
     data[i].Min = min; 
     data[i].Max = max; 
     data[i].NumDone = 0; 
     data[i].NumThreads = numThreads; 
     data[i].Complete = 0; 
     data[i].Block = AllocateTripleBlock(NUM_BLOCKS); 

     current += inc; 
     MYTYPE startmax = TRUNC(current); 
     if (startmax > max) 
      startmax = max; 
     if (i == numThreads - 1) 
     { 
      startmax = max; 
     } 

     data[i].StartMax = startmax; 

     if (data[i].StartMax > max) 
      data[i].StartMax = max; 

     min = startmax + 1; 
     if (min > max) 
      min = max; 
    } 

    // start the threads 
    thread* hThreadArray = new thread[numThreads]; 
    for (int i = 0; i < numThreads; i++) 
    { 
     hThreadArray[i] = thread(CalculateTriples, &data[i]); 
    } 
    thread hProgressthread = thread(ProgressTriples, data); 

    // wait for threads to complete 
    for (int i = 0; i < numThreads; i++) 
    { 
     hThreadArray[i].join(); 
    } 
    hProgressthread.join(); 

    // print the results 
    ofstream* myfile = new ofstream; 
    myfile->open("triples.txt"); 
    PrintTriples(data, myfile); 
    myfile->close(); 

    // cleanup 
    for (int i = 0; i < numThreads; i++) 
    { 
     TripleBlock* block = data[i].Block; 
     while (block) 
     { 
      TripleBlock* next = block->Next; 
      if (block->NumTriplesAllocated > 0) 
       delete[] block->Triples; 
      delete block; 
      block = next; 
     } 
    } 

    delete[] data; 
    delete[] hThreadArray; 

    return 0; 
} 

/// <summary> 
/// Progresses thread for the triples. 
/// </summary> 
/// <param name="data">The data.</param> 
void ProgressTriples(ThreadStartData* data) 
{ 
    MYTYPE numThreads = data->NumThreads; 
    MYTYPE max = data->Max; 
    MYTYPE lastPercent = -1; 
    bool done = true; 
    ThreadStartData* dataStart = data; 

    do 
    { 
     MYTYPE total = 0; 
     done = true; 
     data = dataStart; 

     /// total up the number done 
     for (int i = 0; i < numThreads; i++, data++) 
     { 
      total += data->NumDone; 

      // check if thread is done 
      if (data->Complete == 0) 
       done = false; 
     } 

     // see if all threads are completed 
     if (done) 
     { 
      cout << "done." << endl; 
      break; 
     } 

     MYFLOATTYPE percentdone = ((MYFLOATTYPE)total/(MYFLOATTYPE)max) * 100; 
     if (lastPercent != TRUNC(percentdone)) 
     { 
      lastPercent = TRUNC(percentdone); 
      cout << lastPercent << "% done. (" << total << " of " << max << ")" << endl; 

      this_thread::sleep_for(chrono::seconds(2)); 
     } 
    } while (!done); 
} 

/// <summary> 
/// Calculates the triples. 
/// </summary> 
/// <param name="data">The data.</param> 
void CalculateTriples(ThreadStartData* data) 
{ 
    MYTYPE min = data->Min; 
    MYTYPE max = data->Max; 
    MYTYPE startmax = data->StartMax; 
    TripleBlock* block = data->Block; 

    for (MYTYPE a = min; a >= min && a <= startmax; a++) 
    { 
     data->NumDone++; 

     MYFLOATTYPE asquared = (MYFLOATTYPE)a * (MYFLOATTYPE)a; 
     for (MYTYPE b = a + 1; b > a; b += 2) 
     { 
      MYFLOATTYPE bSquared = (MYFLOATTYPE)b * (MYFLOATTYPE)b; 
      MYFLOATTYPE cSquared = asquared + bSquared; 
      MYFLOATTYPE cSquareRoot = SQRT(cSquared); 
      MYTYPE c = TRUNC(cSquareRoot); 

      // check for max and overflow 
      if (c > max || c < b) 
       break; 

      // check for a true square 
      if (cSquareRoot != c) 
       continue; 

      // check gcd 
      MYTYPE gcd = a; 
      for (; gcd >= 1; gcd--) 
      { 
       if ((MOD(c, gcd) != 0) || (MOD(b, gcd) != 0) || (MOD(a, gcd) != 0)) 
        continue; 

       break; 
      } 

      // if gcd != 1 then no triplet 
      if (gcd != 1) 
      { 
       continue; 
      } 

      AddTriple(a, b, c, block); 
      break; 
     } 
    } 

    data->Complete = -1; 
} 

/// <summary> 
/// Adds the triple. 
/// </summary> 
/// <param name="a">a.</param> 
/// <param name="b">b.</param> 
/// <param name="c">c.</param> 
/// <param name="block">block.</param> 
void AddTriple(MYTYPE a, MYTYPE b, MYTYPE c, TripleBlock* block) 
{ 
    while (block->NumTriples >= block->NumTriplesAllocated) 
    { 
     if (block->Next == NULL) 
     { 
      block->Next = AllocateTripleBlock(NUM_BLOCKS); 
     } 
     block = block->Next; 
    } 

    Triple* triple = &(block->Triples[block->NumTriples]); 
    triple->A = a; 
    triple->B = b; 
    triple->C = c; 
    block->NumTriples++; 
} 

/// <summary> 
/// Allocates a triple block. 
/// </summary> 
/// <param name="numtriples">The numtriples.</param> 
/// <returns>TripleBlock *</returns> 
TripleBlock* AllocateTripleBlock(long numtriples) 
{ 
    TripleBlock* block = new TripleBlock; 
    memset(block, 0, sizeof(TripleBlock)); 

    block->Triples = new Triple[numtriples]; 
    memset(block->Triples, 0, numtriples * sizeof(Triple)); 
    block->NumTriplesAllocated = numtriples; 

    return block; 
} 

/// <summary> 
/// Prints the triples. 
/// </summary> 
/// <param name="data">The data.</param> 
/// <param name="myfile">The file.</param> 
void PrintTriples(ThreadStartData* data, ofstream* theFile) 
{ 
    for (int i = 0; i < data->NumThreads; i++) 
    { 
     TripleBlock* block = data[i].Block; 
     while (block) 
     { 
      Triple* triple = block->Triples; 
      for (MYTYPE i = 0; i < block->NumTriples; i++, triple++) 
      { 
       (*theFile) << " " << triple->A << ", " << triple->B << ", " << triple->C << endl; 
      } 
      block = block->Next; 
     } 
    } 
}