8

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)

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
0cool
  • 81
  • 1
  • 1
  • 3
  • 5
    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 05 '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 05 '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 05 '12 at 16:34
  • 3
    `The worst part is python cant handle operations on 10^6` What? https://ideone.com/t71j8 python gracefully manage arbitrary big integers. Actually it is almost too easy to solve big int problems with it. – Simon Bergot Jan 05 '12 at 17:15
  • I say use FORTRAN. – JeffO Jan 05 '12 at 17:55
  • If you can't use any extra libraries, have you considered writing your *own* library for arbitrarily large numbers? – FrustratedWithFormsDesigner Jan 05 '12 at 18:40
  • 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](http://programmers.stackexchange.com/a/101197/22493) 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 06 '12 at 13:42

5 Answers5

7

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.

Ryathal
  • 13,317
  • 1
  • 33
  • 48
  • 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 05 '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 05 '12 at 16:39
4

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. Equations with factorials, such as binomial probabilities can typically be simplified or calculated (indirectly) using mathematical techniques rather than brute force.

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.

For your example; calculate a related (approximate), but simplified equation.

 \frac{10^6}{2147483647}  ≅  \frac{1 * 10^6}{2 * 10^9} \frac{1 * 10^6}{2 * 10^9} = \frac{1}{2} * \frac{10^6}{10^9} \frac{1}{2} * \frac{10^6}{10^9} = 0.5 * 10^{-3} = 0.0005

which is very close to the correct or exact answer

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.

mctylr
  • 1,173
  • 6
  • 12
  • 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 06 '12 at 13:57
1

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:

Alexander Galkin
  • 1,870
  • 1
  • 14
  • 18
  • Common Lisp comes with bignums and rational numeric types. – David Thornley Jan 05 '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](http://accu.org/index.php/journals/c293/) (p9-13 of the [pdf](http://accu.org/var/uploads/journals/overload101.pdf))? It's only the second article in his [series](http://programmers.stackexchange.com/a/101197/22493) on the *Floating Point Blues*. – Mark Booth Jan 06 '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 06 '12 at 14:56
1

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.

rjzii
  • 11,274
  • 6
  • 46
  • 71
  • 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 05 '12 at 23:54
0

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?

Charles E. Grant
  • 16,612
  • 1
  • 46
  • 73