Init GMP variable with char or bit shift?

[hunson]

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

[R. Gerbicz]

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)

#include <stdio.h>
#include <time.h>
#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;
}

[hunson]

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 :)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <gmp.h>

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

[R. Gerbicz]

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.

[hunson]

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 ;)