dc(1) exponent limits

dc(1) exponent limits

[Lyndon Nerenberg]

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

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

[Rob Pike]

[-- 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 --]

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

[Rob Pike]

[-- 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 --]

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

[Bakul Shah]

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.

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

[Bakul Shah]

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).