From: Bakul Shah <bakul@bitblocks.com>
To: 9fans <9fans@9fans.net>
Subject: Re: [9fans] dc(1) exponent limits
Date: Mon, 16 Dec 2019 18:28:35 -0800 [thread overview]
Message-ID: <20191217022843.1A4ED156E42D@mail.bitblocks.com> (raw)
In-Reply-To: Your message of "Tue, 17 Dec 2019 09:46:52 +1100." <CAKzdPgw54qzwJksTfMvCGvu=0L_V1jUFWSToB-oOvCPOOS0hyA@mail.gmail.com>
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.
next prev parent reply other threads:[~2019-12-17 2:28 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-12-16 21:41 Lyndon Nerenberg
2019-12-16 22:46 ` [9fans] " Rob Pike
2019-12-16 22:47 ` Rob Pike
2019-12-17 2:28 ` Bakul Shah [this message]
2019-12-17 2:53 ` Bakul Shah
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20191217022843.1A4ED156E42D@mail.bitblocks.com \
--to=bakul@bitblocks.com \
--cc=9fans@9fans.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).