Performing math on large numbers. How can I express large numbers

[keanedawg]

OK, so I'm working on a combinations problem (I'm struggling through it, so if anyone is curious, I'm trying to find the total combinations to arrange n people in a circle of k chairs, such that no person is sitting next to anyone else)

Regardless, what I'm trying to figure out right now is how to do operations using large numbers. To be specific, I probably just need to do multiplication and division. Also, I would imagine that the largest number I would ever need is maybe (1000!).

The largest data type I know is long which is 64 bits. However, that's certainly not big enough, and I'm not sure how to get around this. One option I've used in the past is to create a linked list (one node for each 3 digits). However, I just don't like that solution - epsecially since I will need to think up an algorithm to multiply and divide with it.

Any suggestions appreciated.

Thanks!

- Cam

[Thomas1965]

Max value for an unsigned long long is: 18,446,744,073,709,551,615.

Is this really not big enough ??

[cire]

Is this really not big enough ??

Considering that 1000! has ~2500 digits, probably not.

I don't know about the OP, but I find it rather annoying when people ask questions that are answered in the first post. =P

Boost may have what you need:
http://www.boost.org/doc/libs/1_53_0/libs/multiprecision/doc/html/boost_multiprecision/intro.html

[dhayden]

Do you need an exact answer? If not then type double or long double might work.

Also, when doing combinatorial calculations, it's easy to screw up and compute a really large numerator, then a really large denominator and then divide. Be smart and alternate multiplication and division to avoid the overflow if possible.

[keanedawg]

Is this really not big enough ??

I learned this only a couple of weeks ago.

Basically think about it like this


1000! = 1000 * 999 * 998 * 997.....64 for numbers later..........* (1000 - 64) * (1000-65) ....And so on... * 3 * 2 * 1

Basically,


You are multiplying 2 byitseft 64 times in 2 ^ 64. But in 1000 factorial, you are multiplying more than 64 numbers, all greater than 2. Hence, you will get a number larger than 2 ^ 64.

[keanedawg]

And if you're wondering why I need a number so big, it's becuase calculating all the possible combinations is a bitch.

[keanedawg]

Do you need an exact answer? If not then type double or long double might work.

Actually, I don't

I need to print out a number that is a modulo of 10000000 (or something close to that). So I suspect there is some way to do this avoiding large numbers altogether. I just am not sure what it is.


If you want a reference, my problem I'm trying to solve is fairly similar to this

http://math.stackexchange.com/questions/12587/how-many-ways-are-there-for-8-men-and-5-women-to-stand-in-a-line-so-that-no-two

[cire]

I need to print out a number that is a modulo of 10000000 (or something close to that). So I suspect there is some way to do this avoiding large numbers altogether. I just am not sure what it is.

Indeed there is. Just modulo by the value after every multiplication, since every digit outside that range will not affect the part of the result you're looking for with further multiplication.

[48T7M4Gy]

Might be of interest as a start on modular arithmetic online references:
http://www.artofproblemsolving.com/wiki/index.php/Modular_arithmetic/Introduction