mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2021-11-25, 15:46   #1
hunson
 
Feb 2020
Germany

2×52 Posts
Default 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
hunson is offline   Reply With Quote
Old 2021-11-25, 19:03   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32×52×7 Posts
Default

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 <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;
}
R. Gerbicz is offline   Reply With Quote
Old 2021-11-25, 20:04   #3
hunson
 
Feb 2020
Germany

3216 Posts
Default

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

Last fiddled with by hunson on 2021-11-25 at 20:48
hunson is offline   Reply With Quote
Old 2021-11-25, 21:08   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

32×52×7 Posts
Default

Quote:
Originally Posted by hunson View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-11-28, 18:54   #5
hunson
 
Feb 2020
Germany

2×52 Posts
Default

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 ;)
hunson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Four char word game masser Lounge 118 2022-06-18 14:36
How to init an array in Posix bc? ewmayer Linux 29 2018-03-08 21:42
[Patch] Fix meaningless (char (*)[13]) to (char *) cast Explorer09 Software 3 2017-03-01 09:55
Init.d Script for MPrime CrashM Software 0 2012-05-18 01:01
Alt codes : should shift = +32 in them ? science_man_88 Programming 13 2011-06-24 06:52

All times are UTC. The time now is 02:34.


Sun Sep 25 02:34:20 UTC 2022 up 38 days, 2 mins, 0 users, load averages: 1.39, 1.36, 1.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔