20131124, 11:25  #1 
"Beny Yacovi"
Nov 2013
Tel Aviv
2^{2}×3 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 
20131124, 11:58  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
6,323 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 stateoftheart 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. 
20131124, 15:10  #3  
"Beny Yacovi"
Nov 2013
Tel Aviv
2^{2}·3 Posts 
Quote:
how many digits are for example in 5**(2**23) ? 

20131124, 15:15  #4 
Nov 2003
16100_{8} Posts 

20131124, 15:17  #5 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5,879 Posts 

20131124, 15:27  #6 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·7·11·29 Posts 
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... Last fiddled with by LaurV on 20131124 at 15:29 
20131124, 15:58  #7  
"Lucan"
Dec 2006
England
6,451 Posts 
Quote:


20131124, 17:22  #8  
Dec 2005
2·11 Posts 
Quote:
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 

20131125, 01:00  #9 
∂^{2}ω=0
Sep 2002
República de California
9,833 Posts 
Since no one has actually given a proper answer to the OP, assuming ncomputerword 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 bigO notation (at least in my usage thereof, quibbles by various CS texts notwithstanding) should be quite close to unity for welltuned software: add/sub should need less than 2 cycles per input word on modern superscalar CPUs (2/F cycles per word if Fway hardware SIMD arithmetic is available); a welltuned FFTbased mul has a constant of perhaps 3, and using that to build a multiword div increases the cost by perhaos 35x (assuming the divisor is not reused) due to the expense of iteratively precomputing the inverse. [Note that mul/div of nword inputs typically requires zeropadding 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 LLtestsoftware writers/users have the luxury of FFTmuls which need no zeropadding, due to fast DWTbased FFTweighting for our special moduli]. Last fiddled with by ewmayer on 20131125 at 02:16 
20131125, 07:10  #10 
"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 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. 
20131125, 09:29  #11 
"Beny Yacovi"
Nov 2013
Tel Aviv
2^{2}×3 Posts 
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. ..... 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Novice Questions About Merges  EdH  Aliquot Sequences  4  20100413 19:43 
Using long long's in Mingw with 32bit Windows XP  grandpascorpion  Programming  7  20091004 12:13 
I think it's gonna be a long, long time  panic  Hardware  9  20090911 05:11 
ECM question from a novice  EbonezerCabbage  Miscellaneous Math  3  20060413 00:03 
A question about ecm's top100 (novice)  [Leo_01]  Factoring  3  20050527 18:03 