Large numbers

I simply want a type that can hold something big enough to print the following value when the 'n' constant is equal to at least 100. Is this possible? If not, how can I get this value?

Code:

---

#include <iostream>

const int n = 66;

int main(void) {
    unsigned long long sum;
   
    for (int i=1;i<n;i++)
        sum*=(n-i);
   
    // this value is way too big if I use any 'n' value higher than 66
    // I can get as far as n=66 with an unsigned long long
    // it prints: 9 223 372 036 854 775 808
    std::cout << sum;

    return 0;
}

---

Thankful for help..

To store numbers that large you'll need to use a library of some kind, such as GMP.

[edit] Or you can implement it yourself, of course. You could represent a number as

Code:

---

char number[DIGITS];

---

or something and do the multiplication by hand. [/edit]

A type, i think an unsigned long long is as far as you can go (might be wrong).

Quote:

---

Originally Posted by dwks

To store numbers that large you'll need to use a library of some kind, such as GMP.

[edit] Or you can implement it yourself, of course. You could represent a number as

Code:

---

char number[DIGITS];

---

or something and do the multiplication by hand. [/edit]

---

Yes, I was actually thinking about doing that by separating it into two parts and somehow multiply them with eachother, but gave up on that idea after a while. That GMP library looks interesting though, do you know of any that works under Windows?

Unless you want to use non-standard compiler extensions, you can't get a larger native type than an unsigned long long. Well, you could use a float or a double, but you wouldn't get exact values.

You realize that sum is uninitialized in your code?

Code:

---

    unsigned long long sum;
   
    for (int i=1;i<n;i++)
        sum*=(n-i);

---

I'm assuming you set it to 1, right?

[edit] GMP works under Windows as far as I know. I'll look into it. [/edit]
[edit=2] Sure it works. http://www.google.ca/search?hl=en&q=...G=Search&meta= [/edit]

Quote:

---

Originally Posted by dwks

You realize that sum is uninitialized in your code?

---

Oh, I forgot to add that back. I remade the program since I made a change to the original where I separated the sum into many parts. Strangely enough, it worked regardless :/

Quote:

---

[edit] GMP works under Windows as far as I know. I'll look into it. [/edit]
[edit=2] Sure it works. http://www.google.ca/search?hl=en&q=...G=Search&meta= [/edit]

---

Ok, thank you..

I have a large integer class I wrote a while back... Once I found gmp though, I stopped working on this, but for simple problems like you are doing, it works great. I've attached the source and you are welcomed to use it. If you need any help, you can email or pm me.


usage:
add these to your project.
include the header

change: unsigned long long sum;
to: dbInt sum;

compile and run

base 256 arithmetic... yikes.

Yikes indeed.

I suggest taking a look at the bigint class on my website (link is in my sig; See the useful classes page). It works in basically the same way 64bit math operations are emulated on a 32-bit processor, using two-complement numbers of arbitrary size. Memory layout is identical to what you would expect from a native type of the specified size.
It even has a factorial function built-in!

Darryl, you might want to check it out too. I see you used Duff's Device in yours, btw.

Quote:

---

Originally Posted by CodeMonkey

base 256 arithmetic... yikes.

---

I do not use base 256. Base 256 would internally store each digit as a byte, while my code stores each digit as a long long.

ie base 10 = 10 values/digit
base 256 = 256/digit
mine using long long is
base 18446744073709551615 = 18446744073709551615/digit

Quote:

---

Yikes indeed.

.... Memory layout is identical to what you would expect from a native type of the specified size.
...

Darryl, you might want to check it out too. I see you used Duff's Device in yours, btw.

---

My memory layout is as efficient as using a native int64

It's not the best approach I admit, but it's far better than the naive approach of storing digits as chars like most newbies would. I'll check your's out for curiousity sake but I use gmp now.

Duff's Device was one of my many attempts at speeding up performance.

I had tried Karatsuba multiplication but I never could get it working properly with a deque. In retrospect, a more c-like solution would have been speedier over my more c++ approach.