Efficiently working with huge exponents

wanna_code_perl has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
Re: Efficiently working with huge exponents by syphilis (Archbishop) on Mar 20, 2015 at 13:34 UTC
I'd go straight to Math::MPFR (which uses the mpfr library, which in turn uses the gmp library). However, in doing so I'm plugging one of my own modules - which perhaps lessens the value of my advice. Anyway, on my Windows box: `C:\_32>perl -MMath::MPFR=":mpfr" -le "Rmpfr_set_default_prec(1024001); +$x = Math::MPFR->new(2); $x = 1024000; print $x;" >out.txt` [download] The output file reveals: `5.194693363199925.....490149376e308254` [download] The result is instant (maybe a quarter of a second). The length of the string that is output correlates nicely to yours. It is 308263, which is 308255 + 1 (for the decimal point) + 7 (for the "e308254"). Do we also agree on the value ? Maximum precision for my mpfr library (and hence for my Math::MPFR) is 1073741823 bits. Update: Just noticed that the OP now specifies that full precision is not required: `perl -MMath::MPFR=:mpfr -le "Rmpfr_set_default_prec(28);print Math::MP +FR->new(2) 1024000;" 5.194693363e308254` [download] Cheers, Rob	[reply] [d/l] [select]
Re: Efficiently working with huge exponents by RichardK (Parson) on Mar 20, 2015 at 12:46 UTC
Math::BigFloat can swap the library it uses, have you tried 'GMP' ? `use Math::BigFloat lib => 'GMP';` [download] AFIACT that calls Math::BigInt::GMP so you'll need to install that too. `use Math::BigInt; # or make it faster with huge numbers: install (optional) # Math::BigInt::GMP and always use (it will fall back to # pure Perl if the GMP library is not installed): # (See also the L<MATH LIBRARY> section!) # will warn if Math::BigInt::GMP cannot be found use Math::BigInt lib => 'GMP';` [download]	[reply] [d/l] [select]
Re: Efficiently working with huge exponents by LanX (Saint) on Mar 20, 2015 at 12:19 UTC
This might be of interest: Theory: Re^6: Decimal Floating Point (DFP) and does Perl needs DFP? and Proof of concept: Re^3: Decimal Floating Point (DFP) and does Perl needs DFP? (50 digits precision) You can minimize the number of operations to twice the number of bits the exponent has, by applying exponention laws. Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :)} PS: Je suis Charlie!	[reply]
Re: Efficiently working with huge exponents by Ea (Chaplain) on Mar 20, 2015 at 12:11 UTC
Not quite what you asked, but how about transforming the problem domain and using logarithms? It's monotonic increasing, so the sort order remains the same. Different bases are scaled by an easily calculated factor and if you need the big integer, then you leave the calculation to the end. Sometimes I can think of 6 impossible LDAP attributes before breakfast.	[reply]
Re^2: Efficiently working with huge exponents by wanna_code_perl (Friar) on Mar 20, 2015 at 12:22 UTC
I thought of this as well, but I still need to be able to perform other arithmetic operations on the result, such as addition, multiplication, and even further exponentiation. Plus if I do `$n->blog(10)` to get the base-10 exponent, I still have to wait out the 3-minute calculation of `$n` in the first place, or maybe there's some clever math that I learned too many decades ago that would help. :-)	[reply] [d/l] [select]
Re: Efficiently working with huge exponents (approx) by tye (Sage) on Mar 20, 2015 at 13:39 UTC
Math::BigApprox - tye	[reply]
Re: Efficiently working with huge exponents by Laurent_R (Canon) on Mar 20, 2015 at 16:19 UTC
Just a quick calculation in a one-liner: `$ time perl -E 'my $c = log(2) * 1024000; my $d = $c / log(1e100); > $d = int $d; say $d; $c = $c - log(1e100) for 1..$d; > say $c; say "Value is: ", exp $c, " x 1e${d}00";' 3082 125.987232628425 Value is: 5.19469341155068e+54 x 1e308200 real 0m0.039s user 0m0.030s sys 0m0.000s` [download] The last decimals are certainly wrong, but it seems that we can say that 5.194693e+308254 is a fair approximation, obtained in 39 milliseconds. Update (at 16:36 UTC): A better version of more or less the same: `$ time perl -E 'my $c = log(2) * 1024000; my $d = int ( $c / log(1e10 +0)); > say $d; $c = $c - $d * log(1e100); > say $c; say "Value is: ", exp $c, " x 1e${d}00";' 3082 125.987232618965 Value is: 5.19469336241126e+54 x 1e308200 real 0m0.036s user 0m0.000s sys 0m0.046s` [download] Update 2: fixed a wrong print out of the value. Je suis Charlie.	[reply] [d/l] [select]
Re^2: Efficiently working with huge exponents (yeah) by tye (Sage) on Mar 20, 2015 at 17:53 UTC
Yeah, that's the same type of thing that Math::BigApprox makes much easier: `$ time perl -MMath::BigApprox=c -le'print c(2)**1024000' 5.194693e+308254 real 0m0.021s user 0m0.012s sys 0m0.004s` [download] And it makes a good guess at how many decimal places to show as well. - tye	[reply] [d/l]
Re^3: Efficiently working with huge exponents (yeah) by Laurent_R (Canon) on Mar 20, 2015 at 21:54 UTC
Thank you, tye ++, I did not know about this module until today, it looks very interesting, I'll look at it and at its code. I was only trying to give a very basic proof of concept to try to help the OP. Surely, your module offers much more than my poor basic attempts. Congrats for it. Je suis Charlie.	[reply]
Re^4: Efficiently working with huge exponents (yes) by tye (Sage) on Mar 20, 2015 at 22:48 UTC
Re^3: Efficiently working with huge exponents (yeah) by wanna_code_perl (Friar) on Mar 21, 2015 at 13:55 UTC
Thanks to you both. While I'll probably just use Math::BigApprox for my current need, re-learning a little math never hurt anyone (much).	[reply]
Re^4: Efficiently working with huge exponents (yeah) by syphilis (Archbishop) on Mar 22, 2015 at 01:14 UTC
Re^5: Efficiently working with huge exponents (yeah) by wanna_code_perl (Friar) on Mar 22, 2015 at 13:04 UTC
Re: Efficiently working with huge exponents by BrowserUk (Patriarch) on Mar 20, 2015 at 15:21 UTC
21024000 Are all your big numbers powers of 2? With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]
Re^2: Efficiently working with huge exponents by BrowserUk (Patriarch) on Mar 21, 2015 at 13:00 UTC
The point I was getting at is that 21024000, is already logarithmic. Ie. 1024000 is log₂ of your number. Thus, to convert it to log₁₀(), you only need divide it by log₂( 10 ). Then all you need is: `sub log2{ log( $_[0] ) / log( 2 ) } sub log2ToLog10{ $_[0] / log2( 10 ) } print log2ToLog10( 1024000 );; 308254.715559917` [download] And once you have that, displaying it in human readable form becomes: `my $log10 = log2ToLog10( 1024000 ); printf "%.16fe%d\n", 10( $log10 - int( $log10 )), int( $log10 );; 5.1946933632179482e308254` [download] Which is pretty accurate according to wolfram/alpha: Read more... (943 Bytes) With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply] [d/l] [select]
Re^3: Efficiently working with huge exponents by wanna_code_perl (Friar) on Mar 21, 2015 at 13:54 UTC
A good observation and valid question, but, no, my calculations are not all powers of 2. Thanks for the math reminder. :-)	[reply]
Re^4: Efficiently working with huge exponents by BrowserUk (Patriarch) on Mar 21, 2015 at 20:24 UTC
Re^5: Efficiently working with huge exponents by wanna_code_perl (Friar) on Mar 22, 2015 at 13:17 UTC


"be consistent"
	PerlMonks