큰 파일 다루기 시작

LogExpert 프로그램을 깔았다. 메모장이나 vscode 는 기가바이트 단위의 텍스트를 못 연다.

더 큰 수를 사용하기 위해 쿠다 프로그래밍을 시작했다.

%%writefile coll_nums_100_000_000.cu
#include <cstdlib>
#include <fstream>
#include <cstring>
#include <fstream>
using namespace std;

__device__ void cal(unsigned long long int n,unsigned long long int road[1000],unsigned int x);
__device__ __managed__ unsigned long long int all_road[100000001][1000]={};
fstream f;

__global__ void go_cal(){
    for(unsigned long long int i=2;i<=100000000;i++){
        unsigned long long int road[1000];
        unsigned int x=0;
        cal(i,road,x);
    }
}
int main(){
    f.open("col_dataset_100m.txt", ios::in | ios::out);
    cudaDeviceSetLimit(cudaLimitStackSize, 256 * 1024);
    go_cal<<<390625,256>>>();
    for(int i=2;i<100000001;i++){
        for(int j=1;j<1000;j++){
            f << all_road[i][j] << ",";
        }
        f << endl;
    }
    f.close();
    cudaDeviceSynchronize();
    return 0;
}

__device__ unsigned long long int big_int=18446744073709551614;

__device__ void cal(unsigned long long int n,unsigned long long int road[1000],unsigned int x){
    x+=1;
    if(x>=1000){printf("%llu over 1000 count.",n);}
    road[x]=n;
    if(n==1){
        for(int i=1;i<1000;i++){
            if(road[i]==0){ return;}
            all_road[road[1]][i]=road[i];
        }
        return;
    }
    if(n%2==0){
        cal(n>>1,road,x);
    }
    else{
        if(n>=big_int){
            printf("start_num: %llu over",road[1]);
            return;
        }
        cal((n<<1)+n+1,road,x);
    }
}

진행 중이다.

gpu 를 쓴다는 건, gpu에서 만든 파일을 cpu 로 옮겨야 하는데, gpu 입장에서 옮기는 방법이 없다고 한다. 그래서, 모든 경로를 배열로 저장하면 메모리가 터지고, cpu 로 값을 계속 이동시키면 그냥 cpu 만 쓰는 것보다 느리다. 물론 방법은 있겠지만, gpu프로그래밍이 처음인데 나에겐 어려운 문제를 만난 것 같아서 일단 보류 해두었다.

cpu를 이용해서, 2부터 10000까지의 경로를 모두 저장해두고, 진행하다가 10000이하의 수가 나오면 저장해둔 경로를 바로 붙여서 조금 더 빠르게 만들었다.

다이나믹 프로그래밍을 써보려고 생각을 했으나, 텍스트가 커서 숫자를 탐색하는 데 더 시간이 걸릴 것 같아서, 일단 10000까지의 숫자만 캐시해둬서 dp 흉내를 냈다.

#include<iostream>
#include<set>
#include<cmath>
#include <cstdlib>
#include <fstream>
#include <cstring>
#include <fstream>
using namespace std;
string cash[10001]={"0",
"1",
"2, 1", ...(
"9999, 29998, 14999, 44998, 22499, 67498, 33749, 101248, 50624, 25312, 12656, 6328, 3164, 1582, 791, 2374, 1187, 3562, 1781, 5344, 2672, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1"
"10000, 5000, 2500, 1250, 625, 1876, 938, 469, 1408, 704, 352, 176, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1",
};
void cal(unsigned long long int n);
fstream f;
int main(){
    
    f.open("../col_cash.txt", ios::in | ios::out);
    for(unsigned long long int i=2;i<=100000000;i++){
        cal(i);
    }
    f.close();
    return 0;
}
void cal(unsigned long long int n){
    if(n<=10000){
        f<< cash[n] <<endl;
        return;
    }
    f << n << ",";
    if(n%2==0){
        cal(n>>1);
    }
    else{
        if(n>=8446744073709551615){
            cout << "count: overnum is"<<n;
            return;
        }
        cal((n<<1)+n+1);
    }
}

1억까지의 경로 데이터를 만들었고, pyArrow,Parquet 라이브러리 사용해 압축 후 허깅페이스에 올릴 것이다.

110GB 이다.

g++ -Ofast -funroll-loops -march=native coll.cpp -o coll 최적화 컴파일 해봤다.

현재 증명되었다고 알려진 $2^{64}$ 보다 큰 수를 돌려봤다.

const POINT:u128=2_u128.pow(64);
const POINT_LAST:u128=2_u128.pow(126);
fn main(){
    let mut flag = String::from("all pass");
    for i in POINT..POINT+10000{
        if cal(i) {
            print!("{}g ",i);//good
        }
        else{
            print!("{}b ",i);//bad
            flag=format!("false at {}",i)
        }
    }
    print!("{}",flag);
}
fn cal(n:u128)->bool{
    if n<POINT{
        true
    }
    else if n%2==0 {
        cal(n>>1)
    }
    else if n<POINT_LAST {
        cal((n<<1)+n+1)
    }
    else{
        print!("over_2^126");
        false
    }
}

1000개의 숫자를 돌려보니 all pass 가 나왔다.