On Mon, 16 Dec 2019 18:28:35 -0800 Bakul Shah <ba...@bitblocks.com> wrote: > On Tue, 17 Dec 2019 09:46:52 +1100 Rob Pike <robp...@gmail.com> wrote: > > % ivy > > 652342**52342 > > 1.85475753442e+304341 > > > > )cpu > > 8.291ms > > > > (652342**52342)/34232342 > > 9.27378767209e+304340/17116171 > > > > )cpu > > 9.217ms > > > > float _ > > 5.41814385477e+304333 > > On plan9/pi4 I get > % ivy > (652342**52342)/34232342 > 9.27378767209e+304340/17116171 > > )cpu > 181.842ms > > Somewhat surprisingly this is better than on linux/pi4: > > $ ivy > (652342**52342)/34232342 > 9.27378767209e+304340/17116171 > > )cpu > 247.783ms > > For comparison, gambit-scheme (on linux) takes 126ms. > $ gsi > ... > > (time (begin (/ (expt 652342 52342) 34232342) #f)) > (time (begin (/ (expt 652342 52342) 34232342) #f)) > 128 ms real time > 126 ms cpu time (116 user, 10 system) > 3 collections accounting for 3 ms real time (3 user, 0 system) > 545796 bytes allocated > 1051 minor faults > 1 major fault > #f > > But it doesn't have big floats so exact->inexact conversion > returns +inf and takes 15 seconds to do so! > > > 50 minutes feels excessive; dc seems to work very hard. > > The excessive slow down is dc using nothing fancier than the > grade-school multiplication algorithm that has an O(n^2) > complexity. For large numbers Go's math/big package uses the > Karatsuba algorithm which has is approx. O(n^1.58). > Gambit-Scheme uses the Schönhage–Strassen algorithm for really > large numbers (in addition to Karatsuba where it is better) > but that doesn't matter much for this computation.
Forgot to add that dc's "bignum" representation is base 100 (each 0..99 "digit" can be stored in a byte). Go's math/big seems to use a number base that is machine word size (2^32 or 2^64). This means dc has a bigger constant multiplier (the big O notation hides this). ------------------------------------------ 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/Te871fd8fbfd16f42-M0d9a711e58134a1c951a65d4 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription
