* dc(1) exponent limits
@ 2019-12-16 21:41 Lyndon Nerenberg
2019-12-16 22:46 ` [9fans] " Rob Pike
0 siblings, 1 reply; 5+ messages in thread
From: Lyndon Nerenberg @ 2019-12-16 21:41 UTC (permalink / raw)
To: Plan 9 from Bell Labs
While running some silly benchmarks I discovered dc's '^' operator
limits exponents to '9999'. This seems arbitrary, perhaps a leftover
safety measure to keep things from eating all the CPU for days on
end on a slow machine? I upped the limit to 99999 and the test
expression ran fine on a Pi4:
/n/dump/2019/1215.2/sys/src/cmd/dc.c:328,334 - dc.c:328,334
neg++;
chsign(arg1);
}
- if(length(arg1)>=3) {
+ if(length(arg1)>=4) {
error("exp too big\n");
}
savk = sunputc(arg2);
If you're feeling bored and apply the above patch, consider running
this mini-bench and mailing the output directly to me:
echo -n `{cat /dev/cputype}^' ** ' ; echo 652342 52342 '^' 34232342 / p q | time dc >/dev/null
It will take a while to run (50 minutes on the Pi4).
--lyndon
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [9fans] dc(1) exponent limits
2019-12-16 21:41 dc(1) exponent limits Lyndon Nerenberg
@ 2019-12-16 22:46 ` Rob Pike
2019-12-16 22:47 ` Rob Pike
2019-12-17 2:28 ` Bakul Shah
0 siblings, 2 replies; 5+ messages in thread
From: Rob Pike @ 2019-12-16 22:46 UTC (permalink / raw)
To: 9fans
[-- Attachment #1: Type: text/plain, Size: 242 bytes --]
% ivy
652342**52342
1.85475753442e+304341
)cpu
8.291ms
(652342**52342)/34232342
9.27378767209e+304340/17116171
)cpu
9.217ms
float _
5.41814385477e+304333
50 minutes feels excessive; dc seems to work very hard.
-rob
[-- Attachment #2: Type: text/html, Size: 367 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [9fans] dc(1) exponent limits
2019-12-16 22:46 ` [9fans] " Rob Pike
@ 2019-12-16 22:47 ` Rob Pike
2019-12-17 2:28 ` Bakul Shah
1 sibling, 0 replies; 5+ messages in thread
From: Rob Pike @ 2019-12-16 22:47 UTC (permalink / raw)
To: 9fans
[-- Attachment #1: Type: text/plain, Size: 464 bytes --]
In case it's not clear, those calculations are integral, only the
presentation looks like floats.
-rob
On Tue, Dec 17, 2019 at 9:46 AM 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
>
>
> 50 minutes feels excessive; dc seems to work very hard.
>
> -rob
>
>
[-- Attachment #2: Type: text/html, Size: 861 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [9fans] dc(1) exponent limits
2019-12-16 22:46 ` [9fans] " Rob Pike
2019-12-16 22:47 ` Rob Pike
@ 2019-12-17 2:28 ` Bakul Shah
2019-12-17 2:53 ` Bakul Shah
1 sibling, 1 reply; 5+ messages in thread
From: Bakul Shah @ 2019-12-17 2:28 UTC (permalink / raw)
To: 9fans
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.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [9fans] dc(1) exponent limits
2019-12-17 2:28 ` Bakul Shah
@ 2019-12-17 2:53 ` Bakul Shah
0 siblings, 0 replies; 5+ messages in thread
From: Bakul Shah @ 2019-12-17 2:53 UTC (permalink / raw)
To: 9fans
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).
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2019-12-17 2:53 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-12-16 21:41 dc(1) exponent limits Lyndon Nerenberg
2019-12-16 22:46 ` [9fans] " Rob Pike
2019-12-16 22:47 ` Rob Pike
2019-12-17 2:28 ` Bakul Shah
2019-12-17 2:53 ` Bakul Shah
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).