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

10000101101102 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

2×3×23×31 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)

2·34·37 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

E4916 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 02:43.


Sun Sep 25 02:43:14 UTC 2022 up 38 days, 11 mins, 0 users, load averages: 1.54, 1.29, 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.

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