Bug 275661 - /usr/bin/dc really slow with a trivial calculation
Summary: /usr/bin/dc really slow with a trivial calculation
Status: New
Alias: None
Product: Base System
Classification: Unclassified
Component: standards (show other bugs)
Version: 13.2-RELEASE
Hardware: Any Any
: --- Affects Many People
Assignee: freebsd-standards (Nobody)
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2023-12-09 18:11 UTC by Dennis Clarke
Modified: 2023-12-10 21:01 UTC (History)
1 user (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Dennis Clarke 2023-12-09 18:11:42 UTC
While having a discussion about an article written by Martin Gardner
for Scientific American[1] magazine somewhere in the late '70s I was
reminded of the old seven digit calculator problem : 

    enter 1.0000001 if you can
    square that number
    repeat the square 27 times in total
    the result should be 674530.470741 or very close

A great many calculators of the era could not even get close to the
correct result. The Hewlett Packard HP41C and similar were exceptional
in that they compute all intermediate results with greater precision
than is displayed.

To demonstrate the calculation one may use bc :

callisto$ uname -a
FreeBSD callisto 13.2-RELEASE-p4 FreeBSD 13.2-RELEASE-p4 GENERIC amd64
callisto$ freebsd-version -kru
13.2-RELEASE-p4
13.2-RELEASE-p4
13.2-RELEASE-p5

callisto$ bc
scale=16
a=1.0000001
b=a*a
b
1.00000020000001
a=b*b
a
1.0000004000000600
b=a*a
b
1.0000008000002800
a=b*b
a
1.0000016000012000
b=a*a
b
1.0000032000049600
a=b*b
a
1.0000064000201600
b=a*a
b
1.0000128000812802
a=b*b
a
1.0000256003264024
b=a*a
b
1.0000512013081815
a=b*b
a
1.0001024052379369
b=a*a
b
1.0002048209627065
a=b*b
a
1.0004096838770397
b=a*a
b
1.0008195355949585
a=b*b
a
1.0016397428285084
b=a*a
b
1.0032821744135604
a=b*b
a
1.0065751214960018
b=a*a
b
1.0131934752146907
a=b*b
a
1.0265610182176220
b=a*a
b
1.0538275241240008
a=b*b
a
1.1105524506013214
b=a*a
b
1.2333267455366004
a=b*b
a
1.5210948612559022
b=a*a
b
2.3137295769391123
a=b*b
a
5.3533445552028435
b=a*a
b
28.6582979267199303
a=b*b
a
821.2980400566398555
b=a*a
b
674530.4706008780046192
^D
callisto$ 

That is not a bad result given that we were limited to 16 decimal
digits.  The same result *should* be from 1.0000001^( 2 ^ 27 ) :

callisto$ bc
scale=16
2^27
134217728
1.0000001^134217728

^C^C
interrupt (type "quit" to exit)

    0: (main)
ready for more input
^D
callisto$ 


Here we see that the old dc "desk calculator" underneath bc has locked
up in some strange way.


callisto$ which dc
/usr/bin/dc
callisto$ echo '16k  1.0000001  2  27^  p  ^  pq' | dc
134217728
^C^C
    0: (main)
ready for more input
callisto$ 

Just hangs. Never seems to return and I left it alone for quite some
time.  Eventually I hit the CTRL+C and you see the message above.

This seems like strange behavior. Curious about where this behavior
may have come from I went and powered up an old Sun SPARCStation 20.

Yes really ...

s20$ uname -a 
SunOS nix 5.8 Generic_117350-62 sun4m sparc SUNW,SPARCstation-20
s20$ echo '16k  1.0000001  2  27^  p  ^  pq' | dc
134217728
exp too big
empty stack
s20$ 

Similar behavior is seen on an old SGI Indigo running IRIX 5.3 as
well as on an IBM OS400 machine on powerpc.

The calculation can be easily done with logarithms given that the
identity ln( a ^ b ) = b * ln( a ) : 

callisto$ bc -l
scale=16
e( 2^27 * l( 1.0000001 ) )
674530.4707410543814025
^D
callisto$ 

It would be best if dc would not just hang. Seemingly forever.

Dennis Clarke
RISC-V/SPARC/PPC/ARM/CISC
UNIX and Linux spoken

[1] my memory may have failed me but I think it was Martin Gardner
Comment 1 Mark Millard 2023-12-09 20:01:36 UTC
FYI: https://www.jstor.org/stable/24969338 indicates:

JOURNAL ARTICLE
COMPUTER RECREATIONS

How to handle numbers with thousands of digits, and why one might want to

Fred Gruenberger

Scientific American
Vol. 250, No. 4 (April 1984), pp. 19-27 (13 pages)

as an example that involves the calculation.
Comment 2 Dennis Clarke 2023-12-10 05:37:07 UTC
(In reply to Mark Millard from comment #1)

Excellent !  Thank you. I knew it was from Scientific American but clearly
not Martin Gardner.

Also, it seems that dc is not hung or strangely locked up. It is just
very very very slow. Also it gets slower and slower depending on the
exponent in this trivial computation : 

(1) firstly I need something that will kick out the current UNIX time
    along with the subseconds :

https://git.sr.ht/~blastwave/bw/tree/bw/item/time_and_date/timenow/tn.c

pluto$ cc -std=iso9899:1999 -g -O0 -m64 -o $HOME/bin/tn /opt/bulk/users/dclarke/tn.c
pluto$ $HOME/bin/tn
1702150944
pluto$ bin/tn -f
1702150948.185400780

I can generally trust that time data down to the millisecond but no further.

(2) try that same computation with an exponent of 2^21 :

pluto$ bin/tn -f ; echo "16k 1.0000001 2 21^ ^ pq" | dc ; bin/tn -f
1702150982.359058318
1.2333267455406059
1702151041.388274513
pluto$ echo '16k 1702151041.388274513 1702150982.359058318 - pq' | dc
59.029216195

(3) same thing again with 2^22 :

pluto$ bin/tn -f ; echo "16k 1.0000001 2 22^ ^ pq" | dc ; bin/tn -f
1702151116.511391274
1.5210948612657825
1702151292.913553255
pluto$ echo '16k 1702151292.913553255 1702151116.511391274 - pq' | dc
176.402161981

(4) and now 2^23

pluto$ bin/tn -f ; echo "16k 1.0000001 2 23^ ^ pq" | dc ; bin/tn -f
1702151370.327805625
2.3137295769691702
1702151899.256797300
pluto$ echo '16k 1702151899.256797300 1702151370.327805625 - pq' | dc
528.928991675

(5) things are really getting slow with 2^24

pluto$ bin/tn -f ; echo "16k 1.0000001 2 24^ ^ pq" | dc ; bin/tn -f
1702152105.644851540
5.3533445553419354
1702153691.392552070
pluto$ echo '16k 1702153691.392552070 1702152105.644851540 - pq' | dc
1585.747700530

(6) again with 2^25

pluto$ bin/tn -f ; echo "16k 1.0000001 2 25^ ^ pq" | dc ; bin/tn -f
1702154005.973187537
28.6582979282091444
1702158766.756840716
pluto$  
pluto$ echo '16k 1702158766.756840716 1702154005.973187537 - pq' | dc
4760.783653179

It looks like a factor of three increase in time required with each
test.

The test for 2^26 is still running and I expect 5 hours or so will be
needed and that means the computation with 2^27 may be about 16 hours
or so.

Dennis
Comment 3 Dennis Clarke 2023-12-10 21:01:15 UTC
Indeed it look like /usr/bin/dc is doing something ... slowly :
 
pluto$ bin/tn -f ; echo "16k 1.0000001 2 26^ ^ pq" | dc ; bin/tn -f
1702174885.863497199
821.2980401419965396
1702189165.176900562

pluto$ echo '16k 1702189165.1769 1702174885.8635 - pq' | dc
14279.3134

Just under 4 hours.