How to Code a Solution To Deal With Large Numbers? [closed]

Question

I'm doing some Project Euler problems and most of the time, the computations involve large numbers beyond int, float, double etc.

Firstly, I know that I should be looking for more efficient ways of calculation so as to avoid the large number problem. I've heard of the Bignum libraries.

But, for academics interests, I'd like to know how to code my own solution to this problem.

Can any expert please help me out? (My language is C)

Triable

writing a big number library is going to be extremely difficult and error prone – Macedoine

I suggest you use an existing one. – Macedoine

Writing a simple bignum library that includes the basic operations is not at all difficult. It's a different thing if you want maximal efficiency or want to include complex operations, but that doesn't seem to be what this question is about. – Cassirer

Possible duplicate of Store and work with Big numbers in C – Smile

Answer 1

You need to store the big numbers in a base that your computer can easily handle with its native types, and then store the digits in a variable length array. I'd suggest that for simplicity you start by storing the numbers in base 10 just to get the hang of how to do this. It will make debugging a lot easier.

Once you have a class that can store the numbers in this form, it's just a matter of implementing the operations add, subtract, multiply, etc. on this class. Each operation will have to iterate over digits of its operands and combine them, being careful to carry correctly so that your digits are never larger than the base. Addition and subtraction are simple. Multiplication requires a bit more work as the naive algorithm requires nested loops. Then once you have that working, you can try implementing exponentiation in an efficient manner (e.g. repeated squaring).

If you are planning to write a serious bignum implementation, base 10 won't cut it. It's wasteful of memory and it will be slow. You should choose a base that is natural for the computer, such as 256 or the word size (2**32). However this will make simple operations more difficult as you will get overflows if you naively add two digits, so you will need to handle that very carefully.

Townsman

Usually, you would choose a base that is half the largest representable type so that there are no overflows. For instance, in modern C, you would choose uint32_t and do all the digit arithmetic in uint64_t. And don't forget: make the digit type unsigned so that there are no surprises. – Cassirer

Actually, base 10 is entirely adequate. It all depends on your purposes. If speed is paramount, then convolution is a great way to do a multiply, IF you have a fast convolver. And convolution will overflow if you use a large base. – Trixy

This is the best answer, as it is the only real answer to the question asked. – Sinotibetan

Answer 2

C is not a good choice for Project Euler. The benefits of C are raw speed, machine portability (to an extent, with standard C), language interoperability (if some language communicates with another, C is a popular first choice), sticking close to a specific library or platform's API (because C is common, e.g. OS API), and a stable language & stdlib. None of these benefits apply to solving Project Euler problems. Not even raw speed, because most of the problems aren't about raw computation, but understanding the algorithm required, and you can sit there all day and wait before submission.

If you are attempting Project Euler problems to broaden your experience with C, that's perfectly fine, just realize this experience doesn't necessarily apply to long-lived and real-world C projects you may work on.

For this kind of short, one-off problem those languages commonly described as "scripting languages" will work better, faster (in dev time), and easier. Try Python, it stays close to C in many ways, including a C API, and out of the various popular "scripting languages" is possibly the one for which you will find the most use in conjunction with C projects.

This may become an unpopular answer, but it isn't a rant—plus I really like C and use C/C++ often—and there is an explicit answer here to your problem: "don't use C", with your final large number solution depending on which alternative you choose. Again picking on Python, integers do not have an upper bound (note below), and I use this to naturally code answers to Project Euler problems, where in other languages I have to use a painful-by-comparison alternative number library.

(Python integers: There are two integer types in 2.x, 'int' and 'long' (which have been completely unified in 3.x). The conversion between them is practically seamless, and 'long' allows arbitrarily large values, instead of just being a bigger 'int' type as C's long is.)

Redletter

I don't disagree with what you have to say, but the OP wants to learn how to implement bigints. – Ribaldry

And I'm not saying he shouldn't learn (at some point) how they are implemented either (plus other answers cover that for him, no sense repeating it). But, in the context from the question, writing his own bigint library is not even an appropriate solution, much less a candidate for a good one. – Redletter

This is a bit of an older post but it deserves a -1. This is like answer the question "I own a bike and want to add a flasher to it, can you help?" With "A bike?!? Do you know how much more efficient a car is! It even has built in flasher support. Obviously you don't understand transportation." Sometimes it is just worth answering a specific question with an answer that fits that question. – Beatification

This shouldn't be the first answer, it doesn't answer the question at all. – Sinotibetan

Minus 1 for not answering the question but just sharing one person's opinion. – Effect

Answer 3

A popular bignum library for C/C++ is the GNU MP Bignum Library. I've used it for several Project Euler problems, but fact remains that C isn't a very suitable language for Euler-problems. If performance was more important C would have more to give, but now you're much better off using a language which built in bignum support, such as Ruby (there are lots of others).

Heuser

What's important in Project Euler is what you choose to make important. I did a bunch of problems when I was learning C++, and my objective was not to solve each one in 2 minutes, but to solve all the ones I'd done in 2 minutes total ;-) – Labarum

Answer 4

A simple way is to think of the number as its string representation in base b. Suppose b=10, simple arithmetic operation like addition on two such strings can be done using the same method we use when adding numbers by pen and paper. The same goes for other simple operations. For better results, you can take a larger base.

A simple bignum implementation like that should be enough for most Project Euler problems (probably all, but I haven't solved much at Euler so can't be sure), but there are ways of using much faster algorithms for operations such as multiplication and division/mod.

Although I recommend writing your own bignum for practice, if you are really stuck you can take ideas from the code of already implemented bigint libraries. For a serious implementation something like gmp is the obvious choice. But you cana also find small bigints coded by other people when solving similar practice problem online (e.g. Abednego's bigint.cpp).

Ribaldry

Answer 5

Here's a nice and simple bignum module for C. You can learn from it for ideas. The C code isn't the highest quality, but the algorithm is well implemented and quite common.

For more advanced stuff, look up GMP.

Lawman

Answer 6

If you want a nice C++ version (I know, you said C, but this is really interesting code), take a look at the internals of CGAL: http://www.cgal.org/

Josie