Re: [9fans] dc(1) exponent limits

[Bakul Shah <bakul@bitblocks.com>]

On Mon, 16 Dec 2019 18:28:35 -0800 Bakul Shah <bakul@bitblocks.com> wrote:
> On Tue, 17 Dec 2019 09:46:52 +1100 Rob Pike <robpike@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).