Novice Q how long it take.....

[abumichal]

just for me curiosity , who long it take to do a simple arithmetic with huge number? Let assume a million digits number or even ten millions digits ? How long it take to add subtract multiply or divide it with another huge number, As I can remember it can be done in one run (assuming the numbers are already in hex format ) ?
Sorry if it sounds a silly Q . It is a long time since I was involve in such things. I was a grad student in math early 80th' and late 90th' was the last time I was doing any type of programming at all.

Thank you much
Beny

[fivemack]

It takes surprisingly little time. And it's one of the areas where code reuse has actually worked; most programs that need to work with big numbers link in libgmp, and libgmp uses pretty close to state-of-the-art algorithms and is under pretty active development.

So for arithmetic on big numbers you're not going to get very much faster than running the expressions in python - it calls to libgmp to work with big numbers. About thirteen seconds to do x=3**(2**24), eight seconds to do y=5**(2**23), less than a second to add x and y.

[abumichal]

Originally Posted by fivemack

It takes surprisingly little time. And it's one of the areas where code reuse has actually worked; most programs that need to work with big numbers link in libgmp, and libgmp uses pretty close to state-of-the-art algorithms and is under pretty active development.

So for arithmetic on big numbers you're not going to get very much faster than running the expressions in python - it calls to libgmp to work with big numbers. About thirteen seconds to do x=3**(2**24), eight seconds to do y=5**(2**23), less than a second to add x and y.

Thank

how many digits are for example in 5**(2**23) ?

[R.D. Silverman]

Originally Posted by abumichal

Thank

how many digits are for example in 5**(2**23) ?

This last question makes me believe that you are lying about
having been a math grad student.

[retina]

Originally Posted by R.D. Silverman

This last question makes me believe that you are lying about
having been a math grad student.

Or maybe just lazy to calculate it.

[LaurV]

open windows calculator (say, win 7)
chick on the button which shows a "2" on it
click that button which says "x^y" on it
click "2" again, than "3"
click the "*" button, for multiplication
click "5"
click the button which says "log"
click "="

Voila, that's the number! Over 5.8 millions digits. Don't ask us why, someone made us learn the procedure by heart, but we can not explain it...

[davieddy]

Originally Posted by abumichal

Thank

how many digits are for example in 5**(2**23) ?

Originally Posted by R.D. Silverman

This last question makes me believe that you are lying about
having been a math grad student.

Originally Posted by retina

Or maybe just lazy to calculate it.

Or maybe too rusty to guess that ** means ^ (assuming it does).

[casevh]

Originally Posted by fivemack

It takes surprisingly little time. And it's one of the areas where code reuse has actually worked; most programs that need to work with big numbers link in libgmp, and libgmp uses pretty close to state-of-the-art algorithms and is under pretty active development.

So for arithmetic on big numbers you're not going to get very much faster than running the expressions in python - it calls to libgmp to work with big numbers. About thirteen seconds to do x=3**(2**24), eight seconds to do y=5**(2**23), less than a second to add x and y.

Python uses its own large integer library and it is slower than libgmp. The gmpy2 module provides access to GMP, MPFR, and MPC. Evaluating "3**(2**24)" is approximately 50x faster using gmpy2.

$ time py27 -c "x=3**(2**24)"                                                  
real    0m9.441s                                                                                                              
user    0m9.398s                                                                                                              
sys     0m0.038s                                                                                                              

$ time py27 -c "from gmpy2 import mpz; x=mpz(3)**(mpz(2)**24)"
real    0m0.169s
user    0m0.154s
sys     0m0.015s

Disclaimer: I maintain gmpy2.

[ewmayer]

Since no one has actually given a proper answer to the OP, assuming n-computer-word inputs, here are the expected opcounts as n --> oo in asymptotic notation:

add/sub: O(n)
mul/div: O(n*lg(n))

The constants of proportionality implied by the big-O notation (at least in my usage thereof, quibbles by various CS texts notwithstanding) should be quite close to unity for well-tuned software: add/sub should need less than 2 cycles per input word on modern superscalar CPUs (2/F cycles per word if F-way hardware SIMD arithmetic is available); a well-tuned FFT-based mul has a constant of perhaps 3, and using that to build a multiword div increases the cost by perhaos 3-5x (assuming the divisor is not re-used) due to the expense of iteratively precomputing the inverse.

[Note that mul/div of n-word inputs typically requires zero-padding these to length n' = 2n, so the general estimate really should read O(ln'*lg(n')) with the stated constants of prop. - around these forums we often forget that we LL-test-software writers/users have the luxury of FFT-muls which need no zero-padding, due to fast DWT-based FFT-weighting for our special moduli].

[danaj]

[EWMayer answered the OP, this is rather a digression]

Fairly similar in Perl, though the default library is much slower than Python. It's ok for little stuff, but anything doing things over 1000 or so digits it's rubbish. I always try to use the GMP back end.

With GMP:

$ time perl -Mbigint=lib,GMP -E '$x = 3**(2**23);'
real    0m0.149s
user    0m0.127s
sys    0m0.010s

$time perl -Mbigint=lib,GMP -E '$x = 3**(2**23); $y = 5**(2**23); $n = $x+$y;'
real    0m0.192s
user    0m0.184s
sys    0m0.007s

$time perl -Mbigint=lib,GMP -E '$x = 3**(2**23); $y = 5**(2**23); $n = $x*$y;'

real    0m0.377s
user    0m0.363s
sys    0m0.013s

perl -Mbigint=lib,GMP -E '$x = 3**(2**23); $y = 5**(2**23); say length($x+$y); say length($x*$y);'
5863386
9865769

I definitely have found in Perl that for algorithms with many computations, C+GMP is going to be faster than Math::GMPz, which is faster than Math::BigInt::GMP. Each layer adds some overhead (not to the computation, but conversions / copying before and after). Sometimes the overhead is pretty small (where most of the time is spent in a few computations, like a lot of PK crypto), sometimes very large (e.g. factoring or primality proofs that involve many operations). Fortunately both Perl and Python offer ways to make C+GMP modules so you get the best speed while using it stays in Perl/Python. From looking at some numbers I did with primality tests, Python+GMPY2 is pretty efficient, but still slower than a C+GMP backend for the same algorithm and inputs.

I like GMP for speed and (especially) portability. There are other options, e.g. libtommath, FLINT, MPIR, etc. Depending on your task, Pari might work also.

[abumichal]

Originally Posted by retina

Or maybe just lazy to calculate it.

I was math student between the year 1977 and 1981. since then works as progrmer for abou 15 years and since 1995 worked at a biz rnvoirnment....
now I am semy r4etired and trying to return to math. I am sixty and thing that are very simple for you are extrimly complicated for me. .....