mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2013-11-24, 11:25   #1
abumichal
 
"Beny Yacovi"
Nov 2013
Tel Aviv

22×3 Posts
Default 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
abumichal is offline   Reply With Quote
Old 2013-11-24, 11:58   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×29×109 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2013-11-24, 15:10   #3
abumichal
 
"Beny Yacovi"
Nov 2013
Tel Aviv

22·3 Posts
Default

Quote:
Originally Posted by fivemack View Post
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) ?
abumichal is offline   Reply With Quote
Old 2013-11-24, 15:15   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by abumichal View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-11-24, 15:17   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

580810 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This last question makes me believe that you are lying about
having been a math grad student.
Or maybe just lazy to calculate it.
retina is online now   Reply With Quote
Old 2013-11-24, 15:27   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·3·739 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2013-11-24, 15:58   #7
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

144638 Posts
Default

Quote:
Originally Posted by abumichal View Post
Thank

how many digits are for example in 5**(2**23) ?
Quote:
Originally Posted by R.D. Silverman View Post
This last question makes me believe that you are lying about
having been a math grad student.
Quote:
Originally Posted by retina View Post
Or maybe just lazy to calculate it.
Or maybe too rusty to guess that ** means ^ (assuming it does).
davieddy is offline   Reply With Quote
Old 2013-11-24, 17:22   #8
casevh
 
Dec 2005

101102 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
casevh is offline   Reply With Quote
Old 2013-11-25, 01:00   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

9,791 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2013-11-25, 07:10   #10
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

[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.
danaj is offline   Reply With Quote
Old 2013-11-25, 09:29   #11
abumichal
 
"Beny Yacovi"
Nov 2013
Tel Aviv

22·3 Posts
Default

Quote:
Originally Posted by retina View Post
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. .....
abumichal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Novice Questions About Merges EdH Aliquot Sequences 4 2010-04-13 19:43
Using long long's in Mingw with 32-bit Windows XP grandpascorpion Programming 7 2009-10-04 12:13
I think it's gonna be a long, long time panic Hardware 9 2009-09-11 05:11
ECM question from a novice EbonezerCabbage Miscellaneous Math 3 2006-04-13 00:03
A question about ecm's top100 (novice) [Leo_01] Factoring 3 2005-05-27 18:03

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

Sun Oct 25 05:40:50 UTC 2020 up 45 days, 2:51, 0 users, load averages: 1.56, 1.76, 1.66

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.