fork download

#include <gmp.h>

mp_bitcnt_t gmp_zgetbits(mpz_t y_) {
        mp_bitcnt_t prev_bits = 0;
        mp_bitcnt_t bits;

        bits = mpz_scan1(y_, prev_bits);
        if (bits == -1) {
                return 1;
        }
        prev_bits = 1;

        for (;;) {
                bits = mpz_scan1(y_, prev_bits);
                if (bits == -1) {
                        break;
                }
                prev_bits = bits + 1;
        }

        return prev_bits;
}

//
// 一般項
//
static inline void sub_gmp_fibonacci_f(unsigned int n_, mpz_t y_, mp_bitcnt_t prec_) {

	mpf_t r5;
	mpf_t ltmp;
	mpf_t rtmp;

	mpf_init2(r5, prec_);
	mpf_init2(ltmp, prec_);
	mpf_init2(rtmp, prec_);

	mpf_sqrt_ui(r5, 5);
	mpf_add_ui(rtmp, r5, 1);
	mpf_div_ui(rtmp, rtmp, 2);

	mpf_pow_ui(ltmp, rtmp, n_);
	mpf_ui_sub(rtmp, 1, rtmp);
	mpf_pow_ui(rtmp, rtmp, n_);
	mpf_sub(ltmp, ltmp, rtmp);
	mpf_div(ltmp, ltmp, r5);
	mpf_set_d(rtmp, 0.5);
	mpf_add(ltmp, ltmp, rtmp);
	mpz_set_f(y_, ltmp);

	mpf_clear(ltmp);
	mpf_clear(rtmp);
	mpf_clear(r5);
}

void gmp_fibonacci_f(unsigned int n_, mpz_t y_) {
	mp_bitcnt_t est_res_bits;
	sub_gmp_fibonacci_f(n_, y_, 32);
	est_res_bits = gmp_zgetbits(y_) + 64;
	gmp_printf("calculation %dbits\n", est_res_bits);

	sub_gmp_fibonacci_f(n_, y_, est_res_bits);
}

#include <time.h>
#include <sys/time.h>

inline static double baka_sec_count(void) {
	struct timeval tv;
    gettimeofday(&tv, NULL);
	return (double)tv.tv_sec + ((double)tv.tv_usec / 1000000.0);
 
}

int main(int argc, char* argv[]) {
	mpz_t fy;
	mpz_t gy;

	unsigned int const n = 10000000;

	double s;
	double e;
	clock_t us;
	clock_t ue;

	mpz_init(fy);
	mpz_init(gy);
	
	s = baka_sec_count();
	us = clock();
	gmp_fibonacci_f(n, fy);
	ue = clock();
	e = baka_sec_count();
	gmp_printf("f,%d,%lf,%lf\n", n, e - s, (double)(ue - us) / CLOCKS_PER_SEC);

	s = baka_sec_count();
	us = clock();
	mpz_fib_ui(gy, n);
	ue = clock();
	e = baka_sec_count();
	gmp_printf("g,%d,%lf,%lf\n", n, e - s, (double)(ue - us) / CLOCKS_PER_SEC);

	if (mpz_cmp(fy, gy)) {
		gmp_printf("validation error\n");
	}

	mpz_clear(fy);
	mpz_clear(gy);
	return 0;
}

/home/mPrV95/ccf1hZlP.o: In function `gmp_zgetbits':
prog.c:(.text+0x11): undefined reference to `__gmpz_scan1'
prog.c:(.text+0x2b): undefined reference to `__gmpz_scan1'
/home/mPrV95/ccf1hZlP.o: In function `gmp_fibonacci_f':
prog.c:(.text+0x67): undefined reference to `__gmpf_init2'
prog.c:(.text+0x74): undefined reference to `__gmpf_init2'
prog.c:(.text+0x81): undefined reference to `__gmpf_init2'
prog.c:(.text+0x8e): undefined reference to `__gmpf_sqrt_ui'
prog.c:(.text+0x9e): undefined reference to `__gmpf_add_ui'
prog.c:(.text+0xae): undefined reference to `__gmpf_div_ui'
prog.c:(.text+0xbc): undefined reference to `__gmpf_pow_ui'
prog.c:(.text+0xcc): undefined reference to `__gmpf_ui_sub'
prog.c:(.text+0xda): undefined reference to `__gmpf_pow_ui'
prog.c:(.text+0xe8): undefined reference to `__gmpf_sub'
prog.c:(.text+0xf6): undefined reference to `__gmpf_div'
prog.c:(.text+0x106): undefined reference to `__gmpf_set_d'
prog.c:(.text+0x114): undefined reference to `__gmpf_add'
prog.c:(.text+0x11f): undefined reference to `__gmpz_set_f'
prog.c:(.text+0x127): undefined reference to `__gmpf_clear'
prog.c:(.text+0x12f): undefined reference to `__gmpf_clear'
prog.c:(.text+0x137): undefined reference to `__gmpf_clear'
prog.c:(.text+0x154): undefined reference to `__gmp_printf'
prog.c:(.text+0x15f): undefined reference to `__gmpf_init2'
prog.c:(.text+0x16a): undefined reference to `__gmpf_init2'
prog.c:(.text+0x175): undefined reference to `__gmpf_init2'
prog.c:(.text+0x182): undefined reference to `__gmpf_sqrt_ui'
prog.c:(.text+0x192): undefined reference to `__gmpf_add_ui'
prog.c:(.text+0x1a2): undefined reference to `__gmpf_div_ui'
prog.c:(.text+0x1b0): undefined reference to `__gmpf_pow_ui'
prog.c:(.text+0x1c0): undefined reference to `__gmpf_ui_sub'
prog.c:(.text+0x1ce): undefined reference to `__gmpf_pow_ui'
prog.c:(.text+0x1dc): undefined reference to `__gmpf_sub'
prog.c:(.text+0x1ea): undefined reference to `__gmpf_div'
prog.c:(.text+0x1fa): undefined reference to `__gmpf_set_d'
prog.c:(.text+0x208): undefined reference to `__gmpf_add'
prog.c:(.text+0x213): undefined reference to `__gmpz_set_f'
prog.c:(.text+0x21b): undefined reference to `__gmpf_clear'
prog.c:(.text+0x223): undefined reference to `__gmpf_clear'
prog.c:(.text+0x22b): undefined reference to `__gmpf_clear'
/home/mPrV95/ccf1hZlP.o: In function `main':
prog.c:(.text.startup+0x1f): undefined reference to `__gmpz_init'
prog.c:(.text.startup+0x27): undefined reference to `__gmpz_init'
prog.c:(.text.startup+0xd2): undefined reference to `__gmp_printf'
prog.c:(.text.startup+0x119): undefined reference to `__gmpz_fib_ui'
prog.c:(.text.startup+0x17d): undefined reference to `__gmp_printf'
prog.c:(.text.startup+0x188): undefined reference to `__gmpz_cmp'
prog.c:(.text.startup+0x19a): undefined reference to `__gmp_printf'
prog.c:(.text.startup+0x1a2): undefined reference to `__gmpz_clear'
prog.c:(.text.startup+0x1aa): undefined reference to `__gmpz_clear'
collect2: error: ld returned 1 exit status

Standard output is empty