【C++】コラッツ予想

こちらの記事の続きです。

どこまで行く？－＞私（笑）
タイトル通り。
「Python」のプログラムを、
今度は「C++」で書いてみました。

---

まずはコードです。
VC で。

#include "pch.h"
#include "atltime.h"
#include <iostream>
#include "CCollatz.h"

bool CCollatz::IsCollatz(unsigned long long N, unsigned long long judged_max_N, unsigned long long** N_list, unsigned long long* calc, unsigned long long calc_max)
{
    *N_list = new unsigned long long[calc_max];
    unsigned long long N_calc = N;
    for (unsigned long long loop = 0; loop < calc_max; loop++)
    {
        (*N_list)[loop] = N_calc;
        
        if (N_calc <= 1)
        {
            *calc = loop;
            return true;
        }
            
        else if(N_calc <= judged_max_N)
        {
            *calc = loop;
            return true;
        }
            
        else if((N_calc & 1) == 0)
        {
            N_calc >>= 1;
        }
            
        else
        {
            N_calc = (N_calc * 3) + 1;
        }
    }
            
    *calc = calc_max;
    return false;
}

void CCollatz::Collatz()
{
    // 開始時間記憶
    CTime StartTime = CTime::GetCurrentTime();

    // 統計情報
    unsigned long long CalcTotal = 0;
    unsigned long long CalcMax = 0;
    unsigned long long CalcMaxN = 0;
    unsigned long long IllegalN = 0;
    unsigned long long* N_ListMax = (unsigned long long*)0;
    unsigned long long* N_List = (unsigned long long*)0;
    bool is_collatz_N = true;

    // コラッツ予想チェック
    unsigned long long MaxN = 1000000000;    // 10億
    for (unsigned long long number = 1; number < MaxN; number++)
    {
        unsigned long long calc;
        is_collatz_N = IsCollatz(number, number - 1, &N_List, &calc, 700);
    
        if (is_collatz_N == false)
        {
            IllegalN = number;
            break;
        }
        
        CalcTotal += calc;
        if (CalcMax < calc)
        {
            if (N_ListMax != 0)
            {
                delete N_ListMax; 
            }

            CalcMax = calc;
            CalcMaxN = number;
            N_ListMax = N_List;
        }
        else
        {
            delete N_List; 
        }
    }
        
    // 結果表示
    if (is_collatz_N == true)
    {
        std::cout << "1 - " << MaxN << " is Collatz Number.\n";
    }
    else
    {
        std::cout << IllegalN << " is not Collatz Number.\n";
    }

    // 統計表示
    std::cout << "CalcTotal  = " << CalcTotal << "\n";
    std::cout << "CalcMax    = " << CalcMax << "\n";
    std::cout << "CalcMaxN   = " << CalcMaxN << "\n";
    std::cout << "N_List     = [";
    for (unsigned long long i = 0; i < CalcMax; i++)
    {
        std::cout << N_ListMax[i] << ", ";
    }
    std::cout << "]\n";

    // 処理時間表示
    CTime EndTime = CTime::GetCurrentTime();
    CTimeSpan ProcessingTime = (EndTime - StartTime);
     std::cout << "processing time is " << ProcessingTime.GetTimeSpan() << " sec\n";
}

実行結果

1 - 1000000000 is Collatz Number.
CalcTotal  = 5239038036
CalcMax    = 644
CalcMaxN   = 217740015
N_List     = [217740015, 653220046, 326610023, 979830070, 489915035, ・・・ 1829410312, 914705156, 457352578, 228676289, 686028868, 343014434, ]
processing time is 628 sec

---

10億。10分28秒。
うーん。

わかりました。
リスト作成はあきらめましょう。
10億回の new 、 delete はオーバーヘッドが大きいでしょう。

コードは割愛。
実行結果。

1 - 1000000000 is Collatz Number.
CalcTotal  = 5239038036
CalcMax    = 644
CalcMaxN   = 217740015
processing time is 43 sec

苦笑。

---

そうすると、Python でリスト作らない場合の処理時間も測定しないと不公平ですよね。
やはりコードは割愛。
実行結果はこちら。

Wellcome to Collatz!  1659774628.521399
1 - 1000000000 is Collatz Number
calc_total  =  5239038036
calc_max    =  644
calc_max_N  =  217740015
processing time is 2235 sec

37分15秒。

ネイティブコード強し。