Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Well, I've just started doing puzzles and it's so annoying to see puzzles which are easy to do but also need to handle very large numbers. That's the problem.

Say I have to deal with numbers like 10 ^ 6 / 2147483647 / etc. Need to do arithmetic operations on!

However, I feel that these shouldn't be handled in brute force way but the math theorems/ statements just don't click in my mind at times.

How could I possible handle such puzzles (shouldn't use external lib)

share|improve this question
4  
You use some sort of BigInt class (latest python does this by default), and/or you look for tricks to help you simplify the math. It is hard to help you without a specific example. –  Job Jan 5 '12 at 16:22
2  
What language are you using? Many languages have some form of BigInt in there somewhere. In some languages (erlang) it is the default while in others you have to somehow ask for it. –  Zachary K Jan 5 '12 at 16:30
    
I use python. The worst part is python cant handle operations on 10^6. Do you guys remember/ learn math statements for such problems. The issue is I should even write "Efficient" code. NOT JUST CODE. –  0cool Jan 5 '12 at 16:34
3  
The worst part is python cant handle operations on 10^6 What? ideone.com/t71j8 python gracefully manage arbitrary big integers. Actually it is almost too easy to solve big int problems with it. –  Simon Jan 5 '12 at 17:15
1  
If you are talking about integers, arbitrary size integers aren't too much of a problem. If you are looking at floating point techniques though (since your example resolved to a non integer answer), you may want to read the references in this answer of mine. Incidentally, even in quite elderly versions of python, 10**6/2147483647 correctly returns 0 with integer arithmetic, just as 10**60/2147483647 returns 465661287524579692410575082716799845321476387475373L. *8') –  Mark Booth Jan 6 '12 at 13:42
show 2 more comments

5 Answers

Large numbers are used in code challenges because they are hard to deal with, its the same reason they are used for encryption. There are BigInt classes for most languages that can help make them more manageable. Most code challenges can be solved while minimally dealing with large numbers though, there are clever solutions that find ways to avoid having to work with big numbers until absolutely necessary.

share|improve this answer
    
Yeah, I am facing this problem in solving code challenges and the worst part is that the code should be "efficient". Even though I managed to write code for large numbers using BigInt's.. I wouldn't be efficient. Sometimes people even mention "NO NumPy" –  0cool Jan 5 '12 at 16:38
    
I don't know about other languages except C, Python. If someone can't handle such things in python.. its too hard in other languages. For Sure. –  0cool Jan 5 '12 at 16:39
add comment

While the exact solution depends on the actual problem, there are various approaches you can try to take before simply calculating in brute force using an arbitrary or multiple precision math library (BigInt, GMP, MPFR, ARPREC, etc.).

First, use some math. Can the expressions be simplified? You said that the source of these tasks involves puzzles, so I would be very inclined to look at this approach for a solution, as this may be a factor in the puzzles' aha moment.

Factoring the numbers and cancelling common factors would be one of the first things I would try, by hand if need be. A multiple precision calculator can helpful.

Would re-framing the question or its values in either a different base (e.g. binary, hexadecimal) or a difference scale (e.g. logarithmic base 2, 10, or e -- natural) make the values easier to deal with? One example of a logarithmic scale, is the decibel, used for RF, and audio levels.

Using techniques not as commonly taught nowadays, but well known amongst programmers, engineers, mathematicians who are familiar with the slide rule can sometime be helpful.

Depending on the question, doing an approximation first can sometimes lead you towards the correct answer by preventing the minutiae from distracting you from attacking the problem creatively.

Another "trick" is to use modulo (mod, %, modulo, a \bmod n ) which is one of my favourite ways to reduce numbers, so if you know some basic abstract algebra you can sometimes work with modular arithmetic.

That is an off-the-cuff, very rough guide to how I would approach a "puzzle" equation or programming problem that involves large numbers.

share|improve this answer
    
What an excellent attempt to answer the deeper aspects of this question rather than just answering the superficially apparent aspects. It's what I was trying to get at with my comment on the question, but you've done that far better. –  Mark Booth Jan 6 '12 at 13:57
add comment

Every programming language supports the use of big numbers: some have this support directly in the standard library, others have special libraries written for this purpose (even several ones).

As long as you are fine with integer numbers you should look for something like BigInteger that is present in many languages. If you need real numbers, then you should look for arbitrary precision arithmetics libraries.

Here are some examples:

share|improve this answer
    
Common Lisp comes with bignums and rational numeric types. –  David Thornley Jan 5 '12 at 17:46
    
@DavidThornley - Have you seen Richard Harris' article Why Rationals Won’t Cure Your Floating Point Blues in the Accu journal Overload (p9-13 of the pdf)? It's only the second article in his series on the Floating Point Blues. –  Mark Booth Jan 6 '12 at 13:47
    
@Mark Booth: No, thank you for the link. There are some places where rationals are useful, and then it's handy to have that type. It is at least more useful than the format specifier that integers are to be printed in Roman numerals. (There are times when I think the Common Lisp standardization committee was having just a little too much fun.) –  David Thornley Jan 6 '12 at 14:56
add comment

If you are working your way through a puzzle challenge and large numbers start to show up then the challenge isn't so much finding the answer (as others have noted, libraries exist for working with large numbers) but rather the challenge is to develop your own library to work with large numbers. This can be quite challenging as you are usually going to have to split the number up in some way across several different memory spaces. For integers this is fairly straightforward, if time consuming to read up on and implement; however, support for floating point values will definitely improve your math skills!

To get you started, the following sites have some open source code that you might want to read through to see how they work with the numbers:

Plus, the Wikipedia page on arbitrary-precision arithmetic can send you off on some interesting directions as well.

share|improve this answer
1  
Right, if it's a programming challenge and they start working with large integers, then the challenge is to write your own arbitrary precision math library. Either that, or there's some trick in the question which means you don't actually have to do anything with a BigInt library (but we can't tell that without knowing specifically what the question(s) is/are). –  Dean Harding Jan 5 '12 at 23:54
add comment

Those really aren't particularly huge numbers. Your example is well within the range supported by a C 'unsigned int' or 'long' on a typical x86 compiler, and vanilla configurations of python will automatically support arbitrary precision arithmetic. Part of your problem may be that in Python "^" is not the exponentiation operator, it's the bitwise 'XOR' operator. Try using 10**6 instead. Of course, using integer division the answer will be zero. Do you want floating point division instead?

share|improve this answer
    
I know that. I mentioned ^ for power as its written usually. non-python programmers wouldn't understand otherwise. –  0cool Jan 6 '12 at 3:24
    
@0cool, hmm, I'm not sure what your question is then. Python has no trouble evaluating your example. –  Charles E. Grant Jan 6 '12 at 4:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.