Sign in to follow this  
Wutalife37

Big Numbers

Recommended Posts

Hello. I have done some work on the Erdos-Strauss Conjecture, and I think I have found a new way how to calculate results. Currently, a method has been developed that has calculated a solution for every number up to 10^14. I would like to match that number with my method. The problem is, I can't seem to find any way how to support numbers that large. Since the method I have involves multiplication, I may need to use numbers as large as 10^20 in my calculations. I also need to use an effecient language for this sort of thing, because as it is it will probably take days to run the program. Can anyone suggest a language to use, and a way to use numbers so large?

Share this post


Link to post
Share on other sites
I believe LISP supports ints of any size. And if you want to use c or c++ you can use
http://www.swox.com/gmp/

I'm assuming you only need ints (rationals shouldn't be to hard to add).

I've never used gmp, and my LISP is limited. So you may want to look for more experienced suggestions.

Share this post


Link to post
Share on other sites
Just in case you use Java you can use the BigInteger class. I actually don't know the limits for the numbers used, but i think it'll be ok. Once i experimentated and calcultated the factorial of 1000 (which is pretty big). And it was decently fast too.

Share this post


Link to post
Share on other sites
Under ANSI C++ you should have a variable keyword called the long long which according to specification should be 64 bits, i.e. ranged from 0 to 18446744073709551615.

Share this post


Link to post
Share on other sites
Quote:
Original post by Inmate2993
Under ANSI C++ you should have a variable keyword called the long long which according to specification should be 64 bits, i.e. ranged from 0 to 18446744073709551615.


That's not actually enough for 10^20, log-base 10 of 2^64 is only 19, which means you can only get up to 10^19 out of 2^64 bits.

I, personally, despite how much I despise LISP and its derivitives, have had great success using Scheme for large integer calculations. I've also used a BigInteger class in C# that supports memory-sized integers that works pretty nicely and can link in with any .NET language.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Still, 19 is close to 20, and with a little tweeking of the algorithm it might just be enough. It would certainly make the program run faster, especially on 64 bit hardware.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wutalife37
Hello. I have done some work on the Erdos-Strauss Conjecture, and I think I have found a new way how to calculate results. Currently, a method has been developed that has calculated a solution for every number up to 10^14. I would like to match that number with my method.


Hey, can you please bring this on topic? How is it related to game development?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Hey, can you please bring this on topic? How is it related to game development?


Isn't this the Math and Physics forum?

Share this post


Link to post
Share on other sites
Sorry, I didn't know it needed to be related to game development for this forum. If necessary, I have no problem with it being moved to the general programming section.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Still, 19 is close to 20, and with a little tweeking of the algorithm it might just be enough. It would certainly make the program run faster, especially on 64 bit hardware.


19 is close to 20? Do you know what the difference between 10^19 and 10^20 is? It's 9x10^19. There's more space in the difference between the two spaces than there is in 10^19. You lose a lot of information in differences between powers of a similar base. This means that, given a fairly standard distribution of the solution set across all possible results, the answer is more likely to be between 10^19 and 10^20 than it is to be under 10^19. Picture this... say someone asked you to guess a number between 1 and 10, it's a 10% chance of getting it right, and considering the odds of some Las Vegas casino games you may actually consider playing such a game for money. Now say someone asked you to guess a number between 1 and 100. The game just got an order of magnitude harder, you now have a 1% chance of success, and your guess more likely would not be in 1..10, but 11..100.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
jperalta, thanks for explaining the obvious. However, it might still be possible that the calculation doesn't need more than 64 bits. (Actually, the OP only says he "may" need to use numbers as large as 10^20.) In that case he could speed up the calculation significantly by NOT using a bigint library. That was the point of the post.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Quote:
Hey, can you please bring this on topic? How is it related to game development?


Isn't this the Math and Physics forum?


For GAME development, not math & physics in general. See the Forum FAQ.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wutalife37
Sorry, I didn't know it needed to be related to game development for this forum. If necessary, I have no problem with it being moved to the general programming section.


I'll let it stay since you're not looking for an answer to a question related to the math itself. My primary concern is to keep things as on the topic of game development as possible. But as long as off-topic questions are relatively few and don't look like requests for help to homework/schoolwork/related problems, I can let them remain open and in this forum.

Share this post


Link to post
Share on other sites
Thanks.

Looking at the algorithm, the biggest number I'll need stored in a single variable is 10^14. However, there is a point where I do a calculation involving the multiplication of a few variables, followed by a mod. It looks something like (10^14*10^14*10^10)%(10^9). This is only a rough example, but that is about the size I'll need.

In that case, would I need to use a language capable of supporting a number like 10^38, or would 10^14 be enough?

If necessary, I can look for another algorithm involving smaller numbers. However, that might take anywhere from a few weeks to a year, and I'd like to have this completed in time for my college applications because I'd really like to put this on it :).

Share this post


Link to post
Share on other sites
for very very large numbers, you shouldn't try to get the whole thing packed into one language variable type like long long, or whatever (it won't fit in anyway).
you need to do per-digit calculations (whatever the base), look into karatsuba algorithm for a fast multiplication (these can very well handle numbers of a few thousand digits in base 10 with no problem at all, and it's still relatively fast, one multiplication between two 20000 digits numbers can take only a few 10 ms on a decent processor (1-1.5GHz))

here is a sample if you don't really picture what kind of number this is :) http://etud.epita.fr/~bilalt_j/btest.txt (that's only a mul and an add)
you should be pretty safe about overflows with a system like this (there can't be any anyway), and it's pretty decent speed-wise if you've got really huge numbers.

Share this post


Link to post
Share on other sites
Did he say College Applications? This sounds like homework.

Anyways, for the rest of us since its and interesting thought experiement, I have a few things to offer.

For one, if speed isn't always neccessary, you could extend a two 32 bit integers into a single 63 bit number for multiplication purposes. I say 63 and not 64 because most high level languages do not allow access to the CARRY processor flag, so you'd have to claim a bit for this purpose in the MSB of the lesser int. Then just do multiplication the elementary school way.

while (right_multiplier--)
{
product_lo += left_multiplier;
if (product_lo & 0x80000000)
{
product_hi += 1;
product_lo &= 0x7fffffff;
}
}


Yes, this is SLOW. But pretend we have need for a 256 bit number, sure, why not.

Share this post


Link to post
Share on other sites
Actually you could just use a signed value for the most signifigant part and unsigned for the rest. This could be very fast and efficient, especially if you are willing to do some inline assembly.

Share this post


Link to post
Share on other sites
hi,

it's late, so apologies if I am mistaken here, but, if the only truly big sum you need is of the form

A*B*...*Z (mod M)

then can't you just do

((A mod M) * (B mod M) * ... * (Z mod M)) (mod m)

and stick to fairly small intermediate numbers throughout?

Share this post


Link to post
Share on other sites
Quote:
Original post by bambuti
hi,

it's late, so apologies if I am mistaken here, but, if the only truly big sum you need is of the form

A*B*...*Z (mod M)

then can't you just do

((A mod M) * (B mod M) * ... * (Z mod M)) (mod m)

and stick to fairly small intermediate numbers throughout?


Yes.

Share this post


Link to post
Share on other sites
@grhodes_at_work
About "off topic" ?
Maybe for some game (code) protection system ? Sure it's about decoding not encoding ... still a dual issue. Anyway we game coders, like any hackers, are sometimes facing math problems never previously tackled in the game industry and even sometimes never before anywhere else.

Just my thoughts. Might be farfetched.


Share this post


Link to post
Share on other sites
I could split it up into multiple mods, but I would still need to use numbers as large as 10^24.

Speed is unfortunately an issue for me. Based on my estimations of working with numbers less than 10^9, it will take me around a week to run the complete program.

I'm looking into GNU MP now. It'll take me a while to find what I'm looking for since the entire documentation is 133 pages long, which sucks since all I need is 1 data type.

Also, I looked into NTL and used the ZZ data type. It is incredibly slow. It took about 10x longer than using the "long" data type in doing calculations for numbers less than 10^9. Is this about how fast GNU MP will be also?

Share this post


Link to post
Share on other sites
you can use gmp with ntl.
Using NTL with GMP

and according to that gmp is a about 2-3 times faster.

and according to the GMP benchmarks.
GMPbench

getting an athlon64 (opteron is an athlon64 with 1 meg of cache like fx's and usually smp support) running on a 64bit os would help a lot. And it'll get faster when they add assembly optimizations for it.

When your using bignums. Multiplication and other ops are no longer O(1) so it's going to to take a speed hit. I think mult is is O(n log n) and addition is O(n), where N is the number of pieces the number is broken into, with GMP.

[Edited by - Cocalus on October 7, 2004 6:21:50 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this