mersenneforum.org Novice Q how long it take.....
 Register FAQ Search Today's Posts Mark Forums Read

 2013-11-24, 11:25 #1 abumichal   "Beny Yacovi" Nov 2013 Tel Aviv C16 Posts Novice Q how long it take..... 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
 2013-11-24, 11:58 #2 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 6,379 Posts 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.
2013-11-24, 15:10   #3
abumichal

"Beny Yacovi"
Nov 2013
Tel Aviv

22×3 Posts

Quote:
 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) ?

2013-11-24, 15:15   #4
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 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.

2013-11-24, 15:17   #5
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

600510 Posts

Quote:
 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.

 2013-11-24, 15:27 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 2·19·241 Posts open windows calculator (say, win 7) chick on the button which shows a "2" on it click that button which says "xy" 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... Last fiddled with by LaurV on 2013-11-24 at 15:29
2013-11-24, 15:58   #7
davieddy

"Lucan"
Dec 2006
England

194A16 Posts

Quote:
 Originally Posted by abumichal Thank how many digits are for example in 5**(2**23) ?
Quote:
 Originally Posted by R.D. Silverman This last question makes me believe that you are lying about having been a math grad student.
Quote:
 Originally Posted by retina Or maybe just lazy to calculate it.
Or maybe too rusty to guess that ** means ^ (assuming it does).

2013-11-24, 17:22   #8
casevh

Dec 2005

23 Posts

Quote:
 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.

Code:
$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.

 2013-11-25, 01:00 #9 ewmayer ∂2ω=0     Sep 2002 República de California 2D4216 Posts 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]. Last fiddled with by ewmayer on 2013-11-25 at 02:16
 2013-11-25, 07:10 #10 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2×3×151 Posts [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: Code: $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.
2013-11-25, 09:29   #11
abumichal

"Beny Yacovi"
Nov 2013
Tel Aviv

22×3 Posts

Quote:
 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. .....

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH Aliquot Sequences 4 2010-04-13 19:43 grandpascorpion Programming 7 2009-10-04 12:13 panic Hardware 9 2009-09-11 05:11 EbonezerCabbage Miscellaneous Math 3 2006-04-13 00:03 [Leo_01] Factoring 3 2005-05-27 18:03

All times are UTC. The time now is 12:40.

Mon Jan 25 12:40:31 UTC 2021 up 53 days, 8:51, 0 users, load averages: 2.24, 2.50, 2.69