PDA

View Full Version : What would the best language be for very large numbers?



cprofitt
April 3rd, 2007, 12:36 AM
I want to write a program that will determine if a number is a Lychrel number, but curious what programming language allows for very large numbers.

Thanks.

raja
April 3rd, 2007, 01:06 AM
Python can handle very large numbers and will also be very easy to write the code in. I would suggest trying python with numpy.

WW
April 3rd, 2007, 01:16 AM
You need a library that can handle arbitrarily large integers. You could use C with the GNU MP (http://gmplib.org/) library. (Has the GNU MP web page always been in French? The online manual (http://gmplib.org/manual/) is in English.)

You could also use C++ with the CLN library (http://www.ginac.de/CLN).

You can see an example of both of these here (http://math.colgate.edu/~wweckesser/software/cln).

cprofitt
April 3rd, 2007, 01:28 AM
Thanks WW -- those look like good possibilities.

raja -- what is the largest integer Python can handle... I am talking about integers with millions of places.

b1g4L
April 3rd, 2007, 02:00 AM
Integers that large may not be ideal for computing on a desktop computer. The time it would take to calculate anything would probobly take days...

samjh
April 3rd, 2007, 02:25 AM
Thanks WW -- those look like good possibilities.

raja -- what is the largest integer Python can handle... I am talking about integers with millions of places.

I've just tried:

print 10 ** 1000000which froze the Python interpreter.

But the following command worked OK, but there was a delay of around 3 seconds while it was processed:

print 10 ** 100000

Using the power of 10000 was almost instant, but there was a perceptible delay.

So it looks like Python will handle up to 10,000 places without suffering severe performance problems. My machine is upper-middle spec: Intel Core 2 Duo 6300, 2GB DDR RAM, etc. Your mileage may vary.

[EDIT: Added result using Java]

I've also tried the same as above, using Java. I used the java.math.BigInteger class:

import java.math.BigInteger;

public class ArbInt {
public static void main (String args[]) {
BigInteger x = new BigInteger("10");
x = x.pow(1000000);
String huge = new String();
huge = x.toString();
System.out.println(huge);
}
}

Similar result: good performance up to 10.000 places, sluggish at 100,000 places, hangs the JVM at 1,000,000 places.

[EDIT: Revised results WITHOUT output to console]

I've just retried the above methods, without outputting to console. So these are merely 10 to the power of 1000000, within system memory only. No printing.

Using Python, it was able to x = 10 ** 1000000 after around two seconds. But using x = 10 ** 10000000 hung the interpreter. So heavy calculations involving up to 1 million digits is possible using Python, but the performance penalty is heavy.

Using Java, doing x = x.pow(1000000) was also possible, but the delay was around 15 seconds. So it was slower than Python.

WW
April 3rd, 2007, 02:40 AM
The time it would take to calculate anything would probobly take days...
...or even years: Lychrel number at wikipedia (http://en.wikipedia.org/wiki/Lychrel_number). (Check out the section called "196 palindrome quest".)

cprofitt
April 3rd, 2007, 02:51 AM
I am not concerned with the time it takes -- I am concerned that it will not error out due to a limit on the size of integers; that was the problem I had when using .Net.

WW
April 3rd, 2007, 03:12 AM
This piqued my curiousity, so I had to try it. It occurred to me that, since all you want to do is reverse the digits and add, even using GMP or some other big integer library is probably overkill. Here is a C++ program that implements a class just for doing Lychrel computations:


//
// lychrel.cpp
//

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>

using namespace std;

class Linteger
{
private:

// digits is a vector of the digits of the number
// digits[0] is the least significant digit
vector<char> digits;

public:

Linteger(string s);
Linteger(long m);
void next();
bool is_palindrome();
long num_digits();
void print();
};

Linteger::Linteger(string s)
{
for (string::reverse_iterator p = s.rbegin(); p != s.rend(); ++p)
digits.push_back(*p - '0');
}

Linteger::Linteger(long m)
{
while (m > 0)
{
digits.push_back((char)(m%10));
m = m / 10;
}
}

void Linteger::next()
{
vector<char> rdigits;

for (vector<char>::reverse_iterator p = digits.rbegin(); p != digits.rend(); ++p)
{
rdigits.push_back(*p);
}
size_t n = digits.size();
int carry = 0;
for (int i = 0; i < n; ++i)
{
int s = digits[i] + rdigits[i] + carry;
digits[i] = s % 10;
carry = s/10;
}
if (carry != 0)
digits.push_back(carry);
}

bool Linteger::is_palindrome()
{
size_t n = digits.size();
for (int i = 0; i < n/2; ++i)
if (digits[i] != digits[n-i-1])
return false;
return true;
}

long Linteger::num_digits()
{
return digits.size();
}

void Linteger::print()
{
for (vector<char>::reverse_iterator p = digits.rbegin(); p != digits.rend(); ++p)
{
cout << (int) *p;
}
cout << endl;
}


int main(int argc, char **argv)
{
if (argc != 3)
{
cerr << "use: lychrel integer max_iterations\n";
return -1;
}

Linteger N(argv[1]);
int m = atoi(argv[2]);

int k = 0;
while(!N.is_palindrome() & (k < m))
{
N.next();
++k;
}
if (N.is_palindrome())
{
cout << argv[1] << " resulted in a palindrome after " << k << " iterations.\n";
N.print();
}
else
{
cout << argv[1] << " did not result in a palindrome after " << k << " iterations. (" << N.num_digits() << " digits)\n";
}
return 0;
}

Here are a couple sample runs:


$ time ./lychrel 196 100000
196 did not result in a palindrome after 100000 iterations. (41490 digits)

real 6m39.460s
user 6m38.273s
sys 0m0.448s
$ time ./lychrel 89 200
89 resulted in a palindrome after 24 iterations.
8813200023188

real 0m0.004s
user 0m0.000s
sys 0m0.004s
$

cprofitt
April 3rd, 2007, 03:57 AM
My C# code that I used below:



private void Lychrel(UInt64 i)
{
// will continue until iterations = 65,000
string s = i.ToString();
char[] reverse = s.ToCharArray();
Array.Reverse(reverse);
string sreverse = new string(reverse);

// progress bar
pgBarReg.Value += 1;

if (s == sreverse)
{
_lychrel = true;
}
else
{
if (_iterations < 65000)
{
_iterations += 1;

// convert reverse to int64 and add it to i
i += Convert.ToUInt64(sreverse);
Lychrel(i);
}
}
}


I exceed the size allowed for UInt64 at 41 iterrations when I reach the value:
13,305,261,530,450,734,933 reverse it and try to add it to itself. I reach this in under 1s of processing time.

I will try running your code on my Ubuntu box tomorrow... it is an interesting concept... at least for me.

pmasiar
April 3rd, 2007, 01:36 PM
My C# code that I used below:

Looks like you use 64-bit integers, right? Python has arbitrary-length integers, just add L:



>>> d = 111111111111111111111111111111111111111111111L
>>> dd = d * d
>>> dd
12345679012345679012345679012345679012345678987654 320987654320987654320987654320987654321L
>>> d4 = dd * dd
>>> d4
15241579027587258039932937052278616064624295016003 65797896662094192958390489254686785550992226794695 93049839963420210333790580704160950464868160341411 370217954580094497789971041L
>>> d8 = d4 * d4
>>> d8
23230573125418774637910283573050778943185939574816 86003447277668373393643618058620539297355540739096 01616346109149637669266376874559143308499618356529 40905766086109090632013527814813118982976659244266 24736411398210795196223991137443430360235800538675 17574683563005879130259422082346295319450696372436 82277216887204765259588529402738944970976999618623 681L


results are fast.

lnostdal
April 3rd, 2007, 02:14 PM
SBCL (or Common Lisp in general) has also got support for arbitrary long integers:



Test> (time
(let* ((d 111111111111111111111111111111111111111111111)
(d2 (* d d))
(d4 (* d2 d2))
(d8 (* d4 d4)))
(princ d2) (terpri)
(princ d4) (terpri)
(princ d8) (terpri)))


12345679012345679012345679012345679012345678987654 320987654320987654320987654320987654321
15241579027587258039932937052278616064624295016003 65797896662094192958390489254686785550992226794695 93049839963420210333790580704160950464868160341411 370217954580094497789971041
23230573125418774637910283573050778943185939574816 86003447277668373393643618058620539297355540739096 01616346109149637669266376874559143308499618356529 40905766086109090632013527814813118982976659244266 24736411398210795196223991137443430360235800538675 17574683563005879130259422082346295319450696372436 82277216887204765259588529402738944970976999618623 681
Evaluation took:
0.005 seconds of real time
0.004 seconds of user run time
0.0 seconds of system run time


..I bet most of that time is spent printing the result.

edit:
It switches from a native numeric type to a bignum type automatically when needed .. so code using smaller numbers will be very fast, especially when declarations are added (as fast as C .. sometimes faster: http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/200606-IMECS ).

Ubuntist
April 3rd, 2007, 04:10 PM
I want to write a program that will determine if a number is a Lychrel number, but curious what programming language allows for very large numbers.

Thanks.

Common Lisp can handle large numbers and can even handle integers or rationals in arbitrary bases. Common Lisp also allows you to compile your code for speed of execution.

cprofitt
April 3rd, 2007, 09:56 PM
Looks like I need to learn Python or Lisp... now I am off to do some reading...

Thanks guys!

dwblas
April 4th, 2007, 01:06 AM
Python's decimal type claims that numbers can be as large as needed

Unlike hardware based binary floating point, the decimal module has a user settable precision (defaulting to 28 places) which can be as large as needed for a given problem:from this link
http://docs.python.org/lib/module-decimal.html
However, if you are dealing with very large numbers you don't want to consider using anything other than C/C++ or assembly. Other languages AFAIK will multiply the execution time by some multiple.

pmasiar
April 4th, 2007, 03:37 AM
However, if you are dealing with very large numbers you don't want to consider using anything other than C/C++ or assembly.

Yes, C/Asm solution would run faster, but "best solution" also depends on how often I plan to run the program, and how fast I need the solution. If I plan to run it 5 times, and can hack in 2 hours Python code which runs 10 minutes, Python might be "better" than spending week on Asm code which runs 5 sec. Heck, let it run overnight and get some sleep :-)

dwblas
April 4th, 2007, 03:55 AM
If 10 to 20 minutes running time is OK, then you are in Python's ballpark. I've used significant digits in the 30-40 range, but nothing larger. I will try a for loop tomorrow, multiplying by 10 each time to see how high it will go.

Edit: Running this code went up to 10,000 digits with no problem. The time was
real 15m20.478s
user 13m3.797s
sys 0m1.976s
so doing anything with numbers in the 10,000 digit range will literally take days or weeks.

import decimal

number = decimal.Decimal( 1 )
incr = decimal.Decimal( 10 )
decimal.getcontext().prec = 10002
for j in range( 0, 10000 ) :
number *= incr
print len(str(number))