GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 04-Nov-2008, 19:13
lance.kimbrough lance.kimbrough is offline
New Member
 
Join Date: Oct 2008
Posts: 9
lance.kimbrough is on a distinguished road

Creating large arrays with GMP


I thought I was finally getting a handle on using the GMP (GNU MP Library), until I started trying to create arrays (and loops). So, I'm having some issues...

What I'm really trying to do is simply something like this...

CPP / C++ / C Code:
for (i=0; i<x; i++) {
    q[i]=2*i;
     }

but using the mpz_t class for the variables x and i (because they'll be so large).

I would like to create a loop going from 1 to x, where x could be greater than 1000 decimal digits long (preferrebly a "for" loop, so that it can be more easily parallelized later). x will be stored in a "mpz_t" type (from GMP) so it can handle that many digits. I first started out by trying to initialize a very simple array by using the following code (BTW, I'm using Linux and g++)....

CPP / C++ / C Code:
	mpz_t i;    // initialize i as a mpz variable
	mpz_init_set_str (i, "3", 10);   // set i to 3, base 10
	
	mpz_t q[*i];    // initialize array q, with i elements

Whenever I compile, I get the following error...
Quote:
error: size of array ‘q’ has non-integral type ‘__mpz_struct’

I've also tried initializing it using mpz_t q[i], and it gives me a very similar error...
Quote:
error: size of array ‘q’ has non-integral type ‘__mpz_struct [1]’

Now, I'm sure that the problem is that I'm trying to create an array with a structure (a non-integer) that isn't supported...so how else could I create an array with x elements (where x could potentially have over 1,000 decimal digits?) and then assign an mpz_t variable to those elements? Maybe I'll have to use a huge, multidimensional array of integers? yikes...


I suppose I could use a "while loop" and use a compare function with the mpz_t variable to keep a loop going, but I still need to be able to address a specific element in the array (larger than 1,000 digits). Does anyone have any ideas how I could do this? I appreciate the help and the patience, I'm still very new at this.
  #2  
Old 04-Nov-2008, 19:29
lance.kimbrough lance.kimbrough is offline
New Member
 
Join Date: Oct 2008
Posts: 9
lance.kimbrough is on a distinguished road

Re: Creating large arrays with GMP


Well, I think I'm a bit closer...if I could only use i as an mpz_t instead of an integer...

CPP / C++ / C Code:
#include <stdio.h>
#include <iostream>
#include <gmpxx.h>

int main() {

	int i;

	mpz_t q[i];

	for (i=0; i<3; i++) {
		mpz_init_set_str (q[i], "1", 10);   // sets all elements of q to 1
	        }
	
	for (i=0; i<3; i++) {
		mpz_mul_ui (q[i], q[i], i);          // multiplies elements of q by i
		}		
	
	for (i=0; i<3; i++) {
		std::cout<< q[i] <<"\n";           // print elements of q
		}

	return 0;

}

This outputs:
0
1
2

But I need to be able to have i go up to a 1,000 decimal digit number...any ideas?
  #3  
Old 05-Nov-2008, 10:43
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 5,218
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Creating large arrays with GMP


Quote:
Originally Posted by lance.kimbrough
Well, I think I'm a bit closer

First of all, this is not valid C++:
CPP / C++ / C Code:
    mpz_t q[i];

Variable size arrays are not supported in standard C++. Even if your compiler supports this non-standard feature, I respectfully suggest that you stick to standard ways. (Note also that the size limits on variable length arrays for my compilers (GNU gcc/g++) are very much smaller than dynamically-allocated arrays.)

I strongly recommend this:
CPP / C++ / C Code:
    mpz_t *q = new mpz_t[i];
.
.
.
    delete [] q;

Of course, your program must have assigned a valid value to i before using either method.

Maybe your program could look like this:

CPP / C++ / C Code:
#include <iostream>
#include <gmpxx.h>
using namespace std;

int main()
{

    int i;
    int size;

    cout << "Enter the size of the array: ";
    cin >> size;
    if (!cin || (size <= 0)) {
        cout << "Invalid entry. It must be a positive integer." << endl;
    }


    mpz_t *q = new mpz_t[size];

    // Initial array elements to 1
    for (i = 0; i < size; i++) {
        mpz_init_set_str(q[i], "1", 10);
    }

    // Multiply the value by i (So the product will be i)
    for (i = 0; i < size; i++) {
        mpz_mul_ui(q[i], q[i], i);
    }

    // Print them out
    for (i = 0; i < size; i++) {
        cout << q[i] << endl; 
    }

    delete [] q ;

    return 0;

}
Quote:
Originally Posted by lance.kimbrough
But I need to be able to have i go up to a 1,000 decimal digit number...any ideas?
If you want have a loop that has limits that large, then, make it the loop variable an mpz_t, and you can do something like this:

CPP / C++ / C Code:
    mpz_t zi;
    mpz_init(zi);
    mpz_t zsize;
    mpz_init(zsize);

   // set zsize to some value with mpz_set_ui(zsize, size) or whatever

    for (mpz_set_ui(zi,0); mpz_cmp(zi, zsize) < 0; mpz_add_ui(zi, zi, 1)) {

        // whatever you want to do in the loop.

    }

Note that the index of an array must have an integer data type, so, if zi is an mpz_t you simply can't have q[zi] anywhere. If zi is an mpt_t whose value is less than the number of elements in the array you could have q[mpz_get_ui(zi)]

Regards,

Dave

Footnote: If you are doing C++, why note use the C++ objects? You can do assignment, arithmetic, etc. (You still can't use the objects as array index values, however)

CPP / C++ / C Code:
    mpz_class *q = new mpz_class[siz];
    mpz_class i;
    mpz_class size();

    // Set the value of size for the upper loop limit

    for (i= 0; i < size; i++) {
        // Do whatever you want to do with i
    }

I hate to repeat myself, but:

The index of an array must be an integer data type. If i has a value that is smaller than the number of elements in the array, you could have q[i.get_ui().
  #4  
Old 05-Nov-2008, 21:20
lance.kimbrough lance.kimbrough is offline
New Member
 
Join Date: Oct 2008
Posts: 9
lance.kimbrough is on a distinguished road

Re: Creating large arrays with GMP


Thanks Dave! Wow, you really cleared a lot up for me. I didn't realize that it is not a good idea to create a variable sized array. I appreciate you catching me on that one.

When I started trying to create arrays with the GMP objects involved, I started experiencing some memory errors (I probably wasn't allocating something correctly, I still have a lot to learn about that). The GMP manual goes a little more in-depth into the standard C ways of doing things, so I just resorted to using that for a while. I'm beginning to realize I should probably read/finish my c++ programming books before I get too much further into this project.

Anyways, I used your advice and began working with the C++ objects for the loop, and I think I've finally gotten it to work. I think that with all the issues of passing an mpz object to an array location (like the q[i], where i is an mpz object), I'm starting to look into another method for creating the individual elements in the loop. Rather than create an array, I'm thinking of creating a dynamic variable (or mpz object) for each element....

CPP / C++ / C Code:
// pseudo-code....

for (i=0; i<size; i++)
     mpz_class a+i;  // such that a+i is a dynamically combined string made up of the number i and the string stored in a.

It looks like I'd have to create my own class to do this sort of operation, somehow incorporating maps.

Here's a link to a site explaining that sort of operation....
Quote:
en.allexperts.com/q/C-1040/Dynamic-Variable-Names.htm

So, it looks like I'll spend some more time on this one. Much to learn! Thanks again Dave!


Best Regards,

Lance
  #5  
Old 06-Nov-2008, 09:24
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 5,218
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Creating large arrays with GMP


Quote:
Originally Posted by lance.kimbrough
...the standard C ways of doing things...
That's OK. I think there is value in learning about the C-style structs and functions.

Quote:
Originally Posted by lance.kimbrough
...issues of passing an mpz object to an array location (like the q[i], where i is an mpz object)...
What issues? It's a simple fact that you have to use an integer data type for the index of an array.

In general, for C and C++ programs:

If p is a pointer type and n is an integer data type, then the following two expressions have the exact same meaning.
Code:
p[n]

Is the same as

Code:
*(p + n)

Here's your program where I have changed it to use mpz_class objects for loop variable and loop limit expressions:
CPP / C++ / C Code:
#include <iostream>
#include <gmpxx.h>

using namespace std;

int main()
{

    int siz;

    cout << "Enter the size of the array: ";
    cin >> siz;
    if (!cin || (siz <= 0)) {
        cout << "Invalid entry. It must be a positive integer." << endl;
    }

    cout << "siz = " << siz << endl;

    //
    // For standard C++: the following will throw an exception and abort
    // if the // system can't give enough memory for the array
    //
    mpz_class *q = new mpz_class[siz]; 
    
    cout << "Allocation OK" << endl;

    mpz_class i;
    mpz_class size(siz); // set value to siz

    // Loop using mpz_class objects 
    for (i= 0; i < size; i++) {
        q[i.get_ui()] = 1;
    }

    //  the value by i (So the product will be i)
    for (i = 0; i < size; i++) {
        q[i.get_ui()] = q[i.get_ui()] * i;
    }

    // Print them out
    for (i = 0; i < size; i++) {
        cout << q[i.get_ui()] << endl; 
    }
    delete [] q ;

    return 0;
}

This isn't a practical example. Since the subscript must be an integer data type, it is (obviously) simpler to use ints for the loop variables. I just wanted to show how to allocate an array of mpz_class objects and to point out that arithmetic between such objects uses standard notation (+, *, ++) instead of having to call functions the way that C programs must do. Note also that the [] operator to access the array elements does not do bounds checking. It is necessary for the programmer to make sure that only valid array members are accessed.

Regards,

Dave
  #6  
Old 06-Nov-2008, 18:55
lance.kimbrough lance.kimbrough is offline
New Member
 
Join Date: Oct 2008
Posts: 9
lance.kimbrough is on a distinguished road

Re: Creating large arrays with GMP


Thanks for writing that code Dave! I started messing around with it, and I'm starting to realize just how much memory it would take to allocate an array as large as I wanted. When I run the code as you wrote (on my smaller computer with 4GB of memory), if I enter a number much greater than 60,000,000, I start running out of memory (it goes to the Swap), and much larger than that, it returns:

Quote:
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted

I could probably go greater than that on my server (with 16 GB), but nothing close to what I was hoping (something on the order of 10^1000). I guess it was pretty ridiculous to even think of creating an array that large, lol. I think I've come up with another approach to the problem, so I'm sure you'll be hearing from me again soon. Thanks again for all the help! I'm learning a lot and am enjoying the challenge.

Best Regards,
Lance
 
 

Recent GIDBlogProblems with the Navy (Chiefs) by crystalattice

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Need Help with input files. Efferus C++ Forum 2 24-Nov-2007 17:19
Arrays as function arguments - return arrays from functions pisuke C Programming Language 2 25-Jul-2007 12:03
Problem creating very large multidimensional array edechter C++ Forum 5 04-Jul-2006 16:41
Dynamic vs Static Arrays WaltP Miscellaneous Programming Forum 5 16-Feb-2006 16:54

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 22:39.


vBulletin, Copyright © 2000 - 2009, Jelsoft Enterprises Ltd.