Terje Mathisen
Guest
|
 Posted: Wed Aug 06, 2008 8:48 pm Post subject: Re: Large integer arithmatic |
 |
|
atul58 wrote:
| Quote: | I wish to know about any software which can handle arithmetic
operations of very large integers (having few million digits). If i
wish to compute nth root of a very large integer, how much time it may
take. OR if i wish to compute m^n where m & n are three digit
integers, how much time it may take ( on a normal p4 PC).
|
The canonical answer would be to use GMP:
http://en.wikipedia.org/wiki/GNU_Multi-Precision_Library
| Quote: |
Any information on above is welcome
|
Using GMP you have close-to-optimal routines avaialable for both your
tasks, but it would be a lot more fun to figure out how to do it yourself!
Calculating something like 456^321 can be handled very efficiently with
some asm code for the inner loops:
First you should note that raising a number to a power p, where p = a+b
is the same as raising it to a, then to b, and then multiply the two
results, right?
a+b=p => n^p = n^a * n^b
Using this, and taking a,b,c.. etc to be successive powers of two, you
can figure out the standard way of doing such an integer power:
bigint power(bigint n, unsigned p)
{
bigint prod = 1;
while (p) {
if (p & 1) // If the low bit is set,
prod *= n; // multiply by the current power of n
n *= n;
p >>= 1;
}
return prod;
}
With a three-digit power p, you're looking at 7-10 iterations of the
code above, and the maximum length of the operands will be 10 k bits for
n squared 10 times, and about twice that, i.e. 20 k bits for the final
product.
With 32 bits stored in each dword, you need 320 dwords to store n, and
640 for the product, and the final multiplication would (naively, using
O(n*n) algorithms, require about 320*320 =~ 100 k MULs.
All the operands will fit easily in L1 cache!
Worst case it should take 500 k cycles, so significantly less than a ms.
GMP might be 3-4 times faster.
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
