GMPの練習
GMPというのはGNU Multiple Precision Arithmetic Libraryのことで、多倍長演算を行うためのライブラリです。
The GNU MP Bignum Library
今回作ったのは「0を除く2種類の数字のみで構成された平方数」を探索するというものです。探索法としては何も考えず全数探査してます。
#include <stdio.h> #include <stdlib.h> #include <limits.h> #include <string.h> #include <gmp.h> #define SMAX INT_MAX/10 int main(void) { mpz_t x,y; char num[2],ntmp[32],ptmp[16]; int i,j,len,flag; mpz_init(x); mpz_init(y); mpz_set_ui(x,10); for(i=0;i<=SMAX;i++){ flag=0; mpz_mul(y,x,x); mpz_get_str(ntmp,10,y); len=strlen(ntmp); num[0]=ntmp[0]; j=1; num[1]=ntmp[j]; while(1){ j++; if(j>=len){ flag=1; break; } if(num[0]!=num[1])break; num[1]=ntmp[j]; } if(flag==0){ for(j=0;j<len;j++){ if(ntmp[j]=='0'||(ntmp[j]!=num[0]&&ntmp[j]!=num[1])){ flag=j; break; } } } if(flag==0){ mpz_get_str(ptmp,10,x); printf("%s -> %s\n",ptmp,ntmp); } mpz_add_ui(y,x,1); mpz_set(x,y); if((i%2000000)==0)printf("(%d/%d)\n",i,SMAX); } mpz_clear(x); mpz_clear(y); return(0); }
ちなみにceleron2.6GHzな環境で実行すると
(0/214748364) 11 -> 121 12 -> 144 22 -> 484 26 -> 676 38 -> 1444 88 -> 7744 109 -> 11881 173 -> 29929 212 -> 44944 235 -> 55225 264 -> 69696 3114 -> 9696996 81619 -> 6661661161 (2000000/214748364) (4000000/214748364) (6000000/214748364) (8000000/214748364) (10000000/214748364) (12000000/214748364) (14000000/214748364) (16000000/214748364) (18000000/214748364) (20000000/214748364) (22000000/214748364) (24000000/214748364) (26000000/214748364) (28000000/214748364) (30000000/214748364) (32000000/214748364) (34000000/214748364) (36000000/214748364) (38000000/214748364) (40000000/214748364) (42000000/214748364) (44000000/214748364) (46000000/214748364) (48000000/214748364) (50000000/214748364) (52000000/214748364) (54000000/214748364) (56000000/214748364) (58000000/214748364) (60000000/214748364) (62000000/214748364) (64000000/214748364) (66000000/214748364) (68000000/214748364) (70000000/214748364) (72000000/214748364) (74000000/214748364) (76000000/214748364) (78000000/214748364) (80000000/214748364) (82000000/214748364) (84000000/214748364) (86000000/214748364) (88000000/214748364) (90000000/214748364) (92000000/214748364) (94000000/214748364) (96000000/214748364) (98000000/214748364) (100000000/214748364) (102000000/214748364) (104000000/214748364) (106000000/214748364) (108000000/214748364) (110000000/214748364) (112000000/214748364) (114000000/214748364) (116000000/214748364) (118000000/214748364) (120000000/214748364) (122000000/214748364) (124000000/214748364) (126000000/214748364) (128000000/214748364) (130000000/214748364) (132000000/214748364) (134000000/214748364) (136000000/214748364) (138000000/214748364) (140000000/214748364) (142000000/214748364) (144000000/214748364) (146000000/214748364) (148000000/214748364) (150000000/214748364) (152000000/214748364) (154000000/214748364) (156000000/214748364) (158000000/214748364) (160000000/214748364) (162000000/214748364) (164000000/214748364) (166000000/214748364) (168000000/214748364) (170000000/214748364) (172000000/214748364) (174000000/214748364) (176000000/214748364) (178000000/214748364) (180000000/214748364) (182000000/214748364) (184000000/214748364) (186000000/214748364) (188000000/214748364) (190000000/214748364) (192000000/214748364) (194000000/214748364) (196000000/214748364) (198000000/214748364) (200000000/214748364) (202000000/214748364) (204000000/214748364) (206000000/214748364) (208000000/214748364) (210000000/214748364) (212000000/214748364) (214000000/214748364) real 2m25.641s user 2m3.009s sys 0m1.194s