mersenneforum.org Init GMP variable with char or bit shift?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-11-25, 15:46 #1 hunson   Feb 2020 Germany 37 Posts Init GMP variable with char or bit shift? Hi, I started learning C a couple of days ago and thought it might be fun to make use of the speed of C and learn the language with an 'useful' application: calculating with GMP. I played around with some functions and thought it might be fun to generate huge solinas numbers (2^a +/- 2^b +/-1). I calculated the 2^x terms with mpz_pow_ui() individually and added them. This works fine so far. Then I realized that these numbers have a special form in base 2 (e.g. 2^10+2^6-1 = 10000111111). So they might be generated way faster by bit shifting or construction of a 'bit' char/string than doing the mpz_pow_ui() calculations for large exponents. Now my questions is: Is there a way to import/convert a char into a mpz_t variable for further calculation? I tried mzp_set_str() base 2 but I can not make it work if I construct the char variable with a loop. A predefined variable like char *num = "10000000000"; gives the correct number of 1024, but no further manipulation is possible. Any help or pointing in the right direction is very much appreciated. hunsun
 2021-11-25, 19:03 #2 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 2·32·5·17 Posts You need only mpz_setbit(), this is optimal in speed/complexity, (you set the ones in the expansion). For example this runs in 0 second: (maybe you should build up from the other direction, because in my code the memory could be a little fragmented if you enlarge the number multiple times) Code: #include #include #include "gmp.h" int main(){ mpz_t n; mpz_init(n); time_t sec=time(NULL); for(int i=0;i<1000000;i++) mpz_setbit(n,i); gmp_printf("%Zd\n",n); printf("time=%ld sec.\n",time(NULL)-sec); mpz_clear(n); return 0; }
 2021-11-25, 20:04 #3 hunson   Feb 2020 Germany 3710 Posts Aha! That's how you use this function. I have read in the manual but did not understand it right away how and for what to use it. Thank you. I did some testing, that's exactly what I needed :) Code: #include #include #include #include int main() { mpz_t n; mpz_t a; mpz_t b; mpz_t c; mpz_t base; int x; int i; mpz_init(n); mpz_init(a); mpz_init(b); mpz_init(c); mpz_init_set_ui(base,2); time_t sec; sec=time(NULL); for (x = 1;x <1000000;x++) { //2^a+2^b-1 //2^5000+2^1000-1 mpz_setbit(n,5000); for(i=0;i<=999;i++) { mpz_setbit(n,i); } } printf("time=%ld sec.\n",time(NULL)-sec); sec=time(NULL); for (x = 0;x <1000000;x++) { //2^a+2^b-1 //2^5000+2^1000-1 mpz_pow_ui(a,base,5000); mpz_pow_ui(b,base,1000); mpz_add(c,a,b); mpz_sub_ui(c,c,1); } printf("time=%ld sec.\n",time(NULL)-sec); mpz_clear(n); mpz_clear(a); mpz_clear(b); mpz_clear(c); return 0; } I guess the idea was not half bad, but its the slower solution. The loop method takes 3 sec. on my machine and the GMP implementation 0 sec. At least my idea works hunson Last fiddled with by hunson on 2021-11-25 at 20:48
2021-11-25, 21:08   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

153010 Posts

Quote:
 Originally Posted by hunson guess the idea was not half bad, but its the slower solution. The loop method takes 3 sec. on my machine and the GMP implementation 0 sec. At least my idea works
Up to constant factor it should be the same speed.
Then analyse how much memory your code needs. Also if you'd contruct all integers in that way then your code runs in quadratic time and needs much more memory.

 2021-11-28, 18:54 #5 hunson   Feb 2020 Germany 37 Posts Thanks for the clarification where the problem is. Programming is just a hobby to me and I never looked into memory usage and or the 'order of time' in which my programs/scripts run. I try to optimize my code as good as I can, but this was never the topic. Usually I use python, so everything is slow ;)

 Similar Threads Thread Thread Starter Forum Replies Last Post masser Lounge 74 2022-01-16 19:33 ewmayer Linux 29 2018-03-08 21:42 Explorer09 Software 3 2017-03-01 09:55 CrashM Software 0 2012-05-18 01:01 science_man_88 Programming 13 2011-06-24 06:52

All times are UTC. The time now is 05:32.

Wed Jan 19 05:32:10 UTC 2022 up 180 days, 1 min, 0 users, load averages: 1.05, 1.20, 1.40