2

If I wanted to compute numbers with hundreds of millions of digits (positive integers), which programming language would be best suited for that?

Currently I'm using python and the script is running and it was easy to code, but I have concerns for its speed.

I don't really know much about assembly at all so while it MAY be the fastest, I would rather not use that. Is C the best choice here?

The specific operations I have to use are *, -, % (mod), exponentiation, equality testing (if statements), and basic looping and some sort of outputting capability (console output for example).

Many thanks.

6
  • 1
    can you provide some more context? What are you trying to do? What OS are you on? What kind of speed are you looking for? Sep 30, 2011 at 22:09
  • Ah, I apologize for not specifying the OS. Currently I'm using Windows 7 and as for what I'm trying to do, I'm just running some very large numbers through some algorithm for fun =D Sep 30, 2011 at 22:11
  • 1
    compute numbers with hundreds of millions of digits sounds a little bit tricky. Addition, substraction and modulo... maybe. But multiplication? That's going to be slow, no matter what programming language...
    – Dennis
    Sep 30, 2011 at 22:12
  • You might want to try the GMP library, written in C, it does what you want yet you will not end up creating your own implementation: gmplib.org
    – too
    Sep 30, 2011 at 22:15
  • Spend your time on algorithmic improvements, rather than language hopping.
    – hardmath
    Oct 1, 2011 at 8:56

3 Answers 3

4

You can use GMP with plain C, but note that a lot of dynamic languages use it for arbitrary precision numbers, python too. You might not gain much by using C.

8
  • Could you elaborate on this part? This computation may run for days or weeks so any speed boost I can get is not negligible. How much of an overhead do you think python is over just writing it in plain C? Sep 30, 2011 at 22:15
  • depends on what you're trying to do... if 90% of the time is spent in GMP, and 10% Python then you won't gain much.. if there's a lot of control structure, manipulating containers etc then it might worth it. Sep 30, 2011 at 22:18
  • 4
    @Mark Byers: uhm no.. with hunders of millions of digits that's definitely highly unrealistic. python is just a thin wrapper for those calculations. Sep 30, 2011 at 22:21
  • 3
    @Mark - normally I wouldn't doubt that, but in this case, a lot of time will be spent in the GMP code for each basic math operation - e.g. multiplying two hundreds-of-millions-of-digits will take a fair amount of time. In comparison, the time spent in the Python-coded algorithm could easily be trivial.
    – user180247
    Sep 30, 2011 at 22:24
  • 2
    @yi_H: uhm no.. Python uses it own implementation for arbitrary precision numbers. The gmpy module [ code.google.com/p/gmpy ] provides a wrapper for the GMP library. For numbers in millions of digits, gmpy is much faster. Quick test: raising a million digit number to the 100th power takes about 4 seconds on a fast 64-bit machine. Multiplying two 100 million digits numbers takes about 3 seconds. The overhead for using Python is extremely low. Disclaimer: I maintain gmpy.
    – casevh
    Oct 1, 2011 at 20:48
2

GMP library with C/C++.

http://gmplib.org/

0

Here is your resource to read up on. This refutes the argument that C is fastest, unless you use the C99 restrict feature. If anything C++ is faster than C. It really comes down to the compiler understanding when two separate but sequential operations 'read' reference the same memory location. This allows the compiler to reorder the operations for optimization. It appears Fortran is best at doing this.

http://en.wikipedia.org/wiki/Pointer_aliasing

Also you can see here that Fortran blows C++ away at the Mandelbrot routine. But when it comes to text manipulation C++ appears to be tops.

http://shootout.alioth.debian.org/u32/fortran.php

3
  • This should be a comment, not an answer. Apr 13, 2012 at 20:59
  • All that link shows is that poorly written C++ code performs poorly using a specific compiler, it doesn't mean at all that C++ or Fortran is inherently faster than the other.
    – dreamlax
    Apr 13, 2012 at 21:27
  • @MooingDuck and dreamlax: I'm guessing you two probably understand compilers better that I do so feel free to contribute to the discussion. Programming is nothing more than a hobby of mine ..., a hobby I've spent far too much time with.
    – user922475
    Apr 20, 2012 at 15:58

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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