mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2022-01-16, 21:46   #1
hunson
 
Feb 2020
Germany

2·52 Posts
Default GNU MP: Cannot reallocate memory - Why?

Hey everyone,


I am again playing with the GMP library and experiencing some problems with code.


The program I am trying to write generates prime number candidates and eliminates composite numbers by simple trail division.
The main for-loop generates the candidate with GMP and checks for a prime factor with previously generated primes (sieve of the erastothenes).
Code:
[...]    mpz_t tmp_a;
    mpz_t tmp_b;
    mpz_t n;
    mpz_t m;
    mpz_t base;
    mpz_t mod_result;

    //////////init
    mpz_init(tmp_a);
    mpz_init(tmp_b);
    mpz_init(n);
    mpz_init(m);
    mpz_init(mod_result);
    mpz_set_str(m,middle,10);
    mpz_init_set_ui(base,10);

[...] sieve of the erastothenes

for(p=1;p<num_primes;p++) //start at 1, skipping primes_lst[0] = 2, no even numbers were generated
    {
        for (e = n_min;e < n_max;e+=2)
        {
            printf("%d\n",e);
            if (candidates[index] == 1)
            {
                f = (int)((e-len_m)/2);
                //10^e-xxx*10^f-1
                mpz_pow_ui(tmp_a,base,e);
                mpz_pow_ui(tmp_b,base,f);
                mpz_mul(tmp_b,m,tmp_b);
                mpz_sub(n,tmp_a,tmp_b);
                //mpz_add(n,tmp_a,tmp_b);
                //mpz_add_ui(n,n,1);
                mpz_sub_ui(n,n,1);
                //mpz_mod_ui(mod_result,n,primes_lst[p]);
                if (mpz_mod_ui(mod_result,n,primes_lst[p]) == 0)
                {
                    count_eliminated++;
                    candidates[index] = 0;
                }
            }
            if (e % 1111 == 0)
            {
                printf("\r%d candidates eliminated, p = %d \n", count_eliminated, primes_lst[p]);
                fflush(stdout);
            }
            index++;
        }
        index=0;
    }
[...]
The code worked fine at some point, but know I get a "GNU MP: Cannot reallocate memory (old_size=80 new_size=84)" error after a couple of loop-iterations. What am I doing wrong here? I initialized the mpz variables and cleared them at the end. The amount of memory GMP tries to allocate does not seem to much...

My programming skills are mediocre and I am new to programming in c. Any hint in the right direction is appreciated.


regards



hunson
hunson is offline   Reply With Quote
Old 2022-01-16, 22:12   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×23×31 Posts
Default

How is index controlled?

It might be easier to debug if you attached the whole program.
paulunderwood is offline   Reply With Quote
Old 2022-01-17, 05:37   #3
hunson
 
Feb 2020
Germany

2×52 Posts
Default

Here is the whole code.



Code:
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <math.h>
#include <string.h>
#include <time.h>

int main()
{
    mpz_t tmp_a;
    mpz_t tmp_b;
    mpz_t n;
    mpz_t m;
    mpz_t base;
    mpz_t mod_result;
    unsigned int e,f;
    clock_t start;
    char middle[] = "77777";
    unsigned int n_min = 10;
    unsigned int n_max = 10000;

    if (n_min % 2 == 0)
    {
        n_min +=1;
        printf("n_min was even, starting at n_min+1\n");
    }

    char *candidates;
    candidates = malloc(sizeof(char) * floor((n_max-n_min)/2));
    int len_m = sizeof(middle)-1;
    char ABC_header[32];

    #define sieve_depth 1000
    #define num_primes 168 //we know how many primes there are below sieve_depth
    //  n         PI(n)
    //  100       25
    //  150       35
    //  500       95
    //  1000      168
    //  10000     1229
    //  50000     5133
    //  100000    9592
    //  750000    60238
    //  1000000   78498
    //  10000000  664579

    char *primes;
    primes = malloc(sizeof(char) * sieve_depth);
    unsigned long x,i,y,z,p;
    unsigned int primes_lst[num_primes];
    unsigned int count_primes = 0;
    unsigned int count_eliminated = 0;
    unsigned int index = 0;
    unsigned int array_size = lroundf((n_max-n_min)/2);
    unsigned int cnt_candidate = 0;
    unsigned int cnt_primes = 0;
    FILE *fp;
    //////////init
    mpz_init(tmp_a);
    mpz_init(tmp_b);
    mpz_init(n);
    mpz_init(m);
    mpz_init(mod_result);
    mpz_set_str(m,middle,10);
    mpz_init_set_ui(base,10);
    //////////////
    fp = fopen("candidates.txt", "w");
    if(fp == NULL)
    {
        printf("file can't be opened\n");
        exit(1);
    }
    //write ABC header
    strcat(ABC_header, "ABC 10^$a-");
    strcat(ABC_header, middle);
    strcat(ABC_header,"*10^$b-1\n");
    fprintf(fp, ABC_header);
    start = clock();

     //////////////////////////////
    //sieve of erastothenes
    //fill array with 1, all numbers are prime
    for (i=0;i<=sieve_depth;i++)
    {
        primes[i] = 1;
    }
    //sieve, from 2 to sqrt(max)
    for (x = 2;x*x < sieve_depth;x++)
    {
        if (primes[x] == 1)
        {
          for (y = 2*x;y<=sieve_depth;y += x) //remove multiples of x, x-wide-steps
          {
            primes[y] = 0;
          }
        }
    }

    for (z = 2;z<sieve_depth;z++)
    {
      if (primes[z] == 1)
      {
        primes_lst[cnt_primes] = z;
        cnt_primes++;
      }
    }
    //////////////////////////////



    //fill candidates array with ones
    for (e = 0;e <= array_size;e++)
    {
        candidates[e] = 1;
    }

    //trail division "sieve"
    printf("%d\n",primes_lst[10]);
    //exit(0);
    for(p=1;p<num_primes;p++) //start at 1, skipping primes_lst[0] = 2, no even numbers were generated
    {
        for (e = n_min;e < n_max;e+=2)
        {
            printf("%d\n",e);
            if (candidates[index] == 1)
            {
                f = (int)((e-len_m)/2);
                //10^e-xxx*10^f-1
                mpz_pow_ui(tmp_a,base,e);
                mpz_pow_ui(tmp_b,base,f);
                mpz_mul(tmp_b,m,tmp_b);
                mpz_sub(n,tmp_a,tmp_b);
                //mpz_add(n,tmp_a,tmp_b);
                //mpz_add_ui(n,n,1);
                mpz_sub_ui(n,n,1);
                //mpz_mod_ui(mod_result,n,primes_lst[p]);
                if (mpz_mod_ui(mod_result,n,primes_lst[p]) == 0)
              //  if (mpz_fdiv_ui(n,primes_lst[p]) == 0)
                {
                    count_eliminated++;
                    candidates[index] = 0;
                }
            }
            if (e % 1111 == 0)
            {
                printf("\r%d candidates eliminated, p = %d \n", count_eliminated, primes_lst[p]);
                fflush(stdout);
            }
            index++;
        }
        index=0;
    }

    //write candidates to file
    for (i=0;i<=array_size;i++)
    {
        e = n_min+(i*2);
        f = (int)((e-len_m)/2);
        if (candidates[i] == 1)
        {
            fprintf(fp, "%d %d\n", e,f);
        }
    }
    printf("%d candidates left\n", (n_max-n_min)/2-count_eliminated);
    printf("\n%f\n", (float)(clock()-start)/CLOCKS_PER_SEC);
    //cleanup
    free(primes_lst);
    free(candidates);
    mpz_clear(tmp_a);
    mpz_clear(tmp_b);
    mpz_clear(n);
    mpz_clear(m);
    mpz_clear(base);
    mpz_clear(mod_result);
    fclose(fp);
    return 0;
}
hunson is offline   Reply With Quote
Old 2022-01-17, 06:26   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×23×31 Posts
Default

Code:
gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/11/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Debian 11.2.0-13' --with-bugurl=file:///usr/share/doc/gcc-11/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-11 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-11-KdLYb3/gcc-11-11.2.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-11-KdLYb3/gcc-11-11.2.0/debian/tmp-gcn/usr --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu --with-build-config=bootstrap-lto-lean --enable-link-serialization=2
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.2.0 (Debian 11.2.0-13)
Code:
gcc -o hunson hunson.c -lgmp
hunson.c: In function ‘main’:
hunson.c:167:5: warning: ‘free’ called on unallocated object ‘primes_lst’ [-Wfree-nonheap-object]
  167 |     free(primes_lst);
      |     ^~~~~~~~~~~~~~~~
hunson.c:50:18: note: declared here
   50 |     unsigned int primes_lst[num_primes];
      |                  ^~~~~~~~~~
Commenting out line 167 makes the program run.

Last fiddled with by paulunderwood on 2022-01-17 at 06:26
paulunderwood is offline   Reply With Quote
Old 2022-01-17, 07:39   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·23·31 Posts
Default

I get "corrupted size vs. prev_size" which means you have a memory leak somewhere caused by out-of-bounds access.

Last fiddled with by paulunderwood on 2022-01-17 at 07:40
paulunderwood is offline   Reply With Quote
Old 2022-01-17, 08:08   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×23×31 Posts
Default

I changed to primes = malloc(sizeof(int) * sieve_depth); and now get no errors
paulunderwood is offline   Reply With Quote
Old 2022-01-17, 10:52   #7
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

2×34×37 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I changed to primes = malloc(sizeof(int) * sieve_depth); and now get no errors
Seems odd to me that you needed to do that. Is this just masking another issue by making the memory allocation bigger?

edit: Could assigning ints to elements of a char array be causing issues? I believe it will cast it normally but I am not certain it would for an array.

Last fiddled with by henryzz on 2022-01-17 at 10:55
henryzz is offline   Reply With Quote
Old 2022-01-17, 12:18   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

427810 Posts
Default

Quote:
Originally Posted by henryzz View Post
Seems odd to me that you needed to do that. Is this just masking another issue by making the memory allocation bigger?

edit: Could assigning ints to elements of a char array be causing issues? I believe it will cast it normally but I am not certain it would for an array.
primes[] is assigned 0 and 1 which are 4 bytes -- char is 1 byte.

To save save memory space the coder could use char and assign and test '0' and '1'. Or use a smaller integer type.

Last fiddled with by paulunderwood on 2022-01-17 at 12:44
paulunderwood is offline   Reply With Quote
Old 2022-01-17, 14:11   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

599410 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
primes[] is assigned 0 and 1 which are 4 bytes -- char is 1 byte.

To save save memory space the coder could use char and assign and test '0' and '1'. Or use a smaller integer type.
My concern is that one assignment is overwriting four array elements. Could assign (char) 0 or (char) 1 or '\0' or '\1' to assign one element without complicating things by using the ASCII values of 0 and 1.
henryzz is offline   Reply With Quote
Old 2022-01-17, 17:59   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·23·53 Posts
Default

The compiler should know to cast 0 and 1 hardcoded constants into the appropriate size (char). The problem is that the primes array is being overrun by this line:

Code:
for (i=0;i<=sieve_depth;i++)
It was only initialized with sieve_depth elements and that loop goes over sieve_depth+1 values.

Later it also tries to read past the end of the allocated primes array.

The 'candidates' array has a similar problem, but changing '<=' to '<' in loops using sieve_depth fixed it for me.
bsquared is offline   Reply With Quote
Old 2022-01-17, 20:19   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·23·31 Posts
Default

Quote:
Originally Posted by bsquared View Post
The compiler should know to cast 0 and 1 hardcoded constants into the appropriate size (char). The problem is that the primes array is being overrun by this line:

Code:
for (i=0;i<=sieve_depth;i++)
It was only initialized with sieve_depth elements and that loop goes over sieve_depth+1 values.

Later it also tries to read past the end of the allocated primes array.

The 'candidates' array has a similar problem, but changing '<=' to '<' in loops using sieve_depth fixed it for me.
Nice one. I had narrowed it down to a problem with SOE.
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 memory ET_ Software 4 2018-05-14 13:55
error failled to reallocate cardmaker Msieve 10 2016-07-05 13:09
"Hybrid Memory Cube" offers 1 Tb/s memory bandwith at just 1.4 mW/Gb/s ixfd64 Hardware 4 2011-12-14 21:24
Memory available to P-1 lycorn Software 23 2010-05-09 22:15
available memory Unregistered Information & Answers 2 2008-04-11 07:40

All times are UTC. The time now is 01:59.


Sun Sep 25 01:59:39 UTC 2022 up 37 days, 23:28, 0 users, load averages: 0.98, 1.12, 1.16

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.

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