2005/02/17

多倍長整数のビット表現でエラトステネス」をC++にした。うーん。普通に「配列でエラトステネス」とかのほうが早いのかもしれん。

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

#include <NTL/ZZ.h>

ZZ zebraBit(unsigned long span, ZZ length){
unsigned long i;
ZZ base, bit;
base = 2;
bit = power(base, (span - 1));

for (i = 1; i < (length/span) + 1; i++){
bit = LeftShift(power(base, (span - 1)), (i * span)) | bit;
}

return bit;
}

void binArray2intList(ZZ intasbin, unsigned long mistery){
ZZ num, mistery_base, shift_base;
unsigned long count;

count = 0;
shift_base = 1;
mistery_base = 2;
num = intasbin;

while (num > power(mistery_base, mistery)){
if ((intasbin & LeftShift(shift_base, count)) > 0){
;
}else{
cout << count + 1 << "\n";
}
num = RightShift(num, 1);
count = count + 1;
}
}

int main(){
unsigned long i, sqrt_order;
ZZ bit, shift_base, order;
bit = 0;
shift_base = 1;

order = 100000;
sqrt_order = 317;

for (i = 2; i < sqrt_order; i++){
bit = zebraBit(i, order) - LeftShift(shift_base, i - 1) | bit;
}
binArray2intList(bit, sqrt_order);
}

コンパイルと実行。

$ gcc ntl_test.cc -lstdc++ -lntl
$ time ./a.out > result.txt

real 0m18.692s
user 0m18.230s
sys 0m0.020s

misteryは、ミステリー。なんか、ビットシフトがうまくいかないので補正。っていうか、そんなことやってるからオーバーヘッドになってるっぽい。そして。しょせんNTLの使い方メモくらいにしかならないのであった。

No comments :