Page 1 of 2

Large numbers (i mean really large!) (C++)

Posted: Sun Dec 23, 2007 3:15 pm
by Zacariaz
Well, i have an idea for an experiment that might be fun for me to do, im not going to explain it as it would be boring to read and hard for me to explain.

Anyway, one feature i need in order to do this is to pass very large values around between functions. 64 bit doesnt cut it so what do you do? I dont know, but i hope someone in here does.

Thanks.

Posted: Sun Dec 23, 2007 3:38 pm
by Alboin
Use GMP.

Posted: Sun Dec 23, 2007 3:55 pm
by Craze Frog
How to pass the numbers around depends on which bignum library you use. Apart from that, 80-bit floats exists, if 64-bit just doesn't cut it.

Posted: Sun Dec 23, 2007 3:59 pm
by Combuster
even 80-bit floats only have a 64-bit mantissa (i.e, the same precision as a 64 bit integer) :!:

Posted: Sun Dec 23, 2007 4:33 pm
by Zacariaz
Alboin wrote:Use GMP.
I've visited the site and its more or less italian to me, and i dont speak italian.

all i need is to be able to asign a exstremely large value to a variable so i can pass it around, is that really so hard?

I was thinking about using strings but it seems wrong somehow. It not like i need a bunch of arimethic functions and stuff.

Alternately i could just split the number up and store it in and aray or something, but that would complicated at best.

Posted: Sun Dec 23, 2007 7:35 pm
by GuiltySpark
Zacariaz wrote:
Alboin wrote:Use GMP.
all i need is to be able to asign a exstremely large value to a variable so i can pass it around, is that really so hard?
No, it's not so hard. Here's from the documentation of GMP itself:
Next: Assigning Integers, Previous: Integer Functions, Up: Integer Functions
5.1 Initialization Functions

The functions for integer arithmetic assume that all integer objects are initialized. You do that by calling the function mpz_init. For example,
{
mpz_t integ;
mpz_init (integ);
...
mpz_add (integ, ...);
...
mpz_sub (integ, ...);

/* Unless the program is about to exit, do ... */
mpz_clear (integ);
}

As you can see, you can store new values any number of times, once an object is initialized.
— Function: void mpz_init (mpz_t integer)

Initialize integer, and set its value to 0.
— Function: void mpz_init2 (mpz_t integer, unsigned long n)

Initialize integer, with space for n bits, and set its value to 0.

n is only the initial space, integer will grow automatically in the normal way, if necessary, for subsequent values stored. mpz_init2 makes it possible to avoid such reallocations if a maximum size is known in advance.

— Function: void mpz_clear (mpz_t integer)

Free the space occupied by integer. Call this function for all mpz_t variables when you are done with them.
— Function: void mpz_realloc2 (mpz_t integer, unsigned long n)

Change the space allocated for integer to n bits. The value in integer is preserved if it fits, or is set to 0 if not.

This function can be used to increase the space for a variable in order to avoid repeated automatic reallocations, or to decrease it to give memory back to the heap.

Hey ...

Posted: Fri Dec 28, 2007 12:37 pm
by DeletedAccount
Try to implement it using a doubly linked list ... you can easily implement addition and implemet subtraction using 10's complement method ... implement mulitplication using repeated addition and so on ....

Posted: Fri Dec 28, 2007 2:06 pm
by lukem95
i would attempt this by splitting the integer into 64 bit segments, and then, depending on how many arithmatic functions you need for it, write a function to translate this.

it would sort of be like long division lol

Posted: Fri Dec 28, 2007 2:19 pm
by Zacariaz
The linked list aproach was allso my first thought but its not where the prolem lies i think.

The problem is that i dont know how to assign a value to my specialized datatype in the first place.

mydatatype variable = somebiginteger // my compiler will never accept this, at least not with any aproach i know of. So i have one alternative left, and that is splitting thevalue up manually, whih i'd rather not.

On the bright side i have no need to able to assign decimal value, im perfectly happy using hex.

Allso let me remind you that i have no need for help with how toadd, subtract, divide or multiply these huge numbers, for starters i only need á a datatype which can store value and which makes assigning the value in the first place, somewhat easy.

anyhow, thanks for the help so far and keep em comming if you want.

Posted: Tue Jan 01, 2008 3:42 pm
by ~
Maybe using a "typedef struct".

To assign a value to it, or to otherwise compare, manipulate, add, substract, etc..., we could create a set of functions for that purpose.

These functions of course would "manually" handle the variable contents, either using C, assembly or a combination.

That's the easiest way I can think of without involving language syntax changes or "extensions", and maybe would be far more portable/maintainable.

Posted: Wed Jan 02, 2008 1:38 pm
by Candy
Zacariaz wrote:The linked list aproach was allso my first thought but its not where the prolem lies i think.

The problem is that i dont know how to assign a value to my specialized datatype in the first place.

mydatatype variable = somebiginteger // my compiler will never accept this, at least not with any aproach i know of.
Switch to a C++ compiler if you didn't already use one and try this:

Code: Select all

class mydatatype {
public:
    mydatatype(const somebigintegertype &val) { ...; valuecount = sizeof(somebigintegertype) / sizeof(unsigned long); }
    mydatatype() { valuecount = 0; }
    const mydatatype &operator=(const mydatatype &rhs) { ... }
private:
    unsigned long *value;
    unsigned int valuecount;
};

Posted: Wed Jan 02, 2008 9:35 pm
by Zacariaz
sprry, but i dont understand.
SomeBigIntetegerType is exactly what im missing.
Then problem is that i have no way to pass the value to mydatatype in the first place, other than possible as a string, however that would not be the most ideal way i think.
I glad you made the effort but if i am to use your advice, you have to explain further.

And by the way, i do use a C++ compiler.

Thanks

Posted: Wed Jan 02, 2008 9:52 pm
by Alboin
Zacariaz wrote:ther than possible as a string, however that would not be the most ideal way i think.
See the C++ example on the middle of this page. It uses strings, and explains why. It's quite elegant, IMO.

If you want incredible speed, you'll never be able to get as fast as the GMP folks. They've been at it for years, and have optimized their code to a fanciful place.

Posted: Fri Jan 04, 2008 3:43 pm
by Candy
Zacariaz wrote:sprry, but i dont understand.
SomeBigIntetegerType is exactly what im missing.
Then problem is that i have no way to pass the value to mydatatype in the first place, other than possible as a string, however that would not be the most ideal way i think.
I glad you made the effort but if i am to use your advice, you have to explain further.

And by the way, i do use a C++ compiler.

Thanks
Aah... that part...

You could use ULL postfixes but that only reaches 18.000.000.000.000.000.000. You can of course use 1000000000000000000 * mydatatype(some_other_huge_number) + some_huge_number to create a larger number.

What are you going to use such numbers for though?

Posted: Sat Jan 05, 2008 9:04 am
by Zacariaz
Candy wrote:What are you going to use such numbers for though?
Well, im not reslly gonna "use" them as such, though i have for a long time been interested in mersenne primes.
What i need them for is some experiments involving how to handle the various calculations. Obiously ill have to split these huge numers up into smaller pieces, fx. an array of ulongs. Then the interesting part is the various ways you can add, subtract, multiply, divide, etc. two such numbers. I have of course read about some methodes, but i myself have a few ideas i would like to try out, ut i would really hate assigning a 1000+ digits number to and array, vector, linked list, whatever, manually.
What i want is this:
mydatatype hugenumber = 123456789887764311234567876543... (and so on)

But it seems impossile.
As discussed earlier it might be possible doing it through the terminal/console, and that is probaly what im going to do, but i would prefer the other methode.