Presto the Mathematical Magician says, quite correctly, that ln(x), the natural logarithm (to the base e=2.718...) of x, is magically well-approximated by 2047(x
1/2048 - 1). Hence logarithms can be calculated with fair accuracy using a primitive calculator that only does square roots along with basic arithmetic.
What is behind Presto's magic?
By the same token, log(x), the common (base 10) logarithm of x, may be approximated by the similar formula K(x1/2048 - 1) for a suitable value of K. For values of x between 1 and 10, explore the accuracy of this approximation, and that of similar formulas of the type K(x1/N-1) where N=2n, under the assumption that a 10-digit calculator is being used to compute the repeated square roots. What values for K and n would you recommend when a 10-digit calculator is being used?
The following program simulates what would happen in a 10-digit calculator using various values of n to compute the natural log of, in this case, 2:
10 P=11:D=2048
15 X=2
20 while P<60
30 P=P+1:D=D*2
40 L=X
50 for I=1 to P
60 L=int(sqrt(L)*10000000000+0.5)/10000000000
70 next
80 L=(L-1)*(D-1):DPlace=int(log(L)/log(10)+0.5)
90 if DPlace>10 then
91 :L=int(L/10^(DPlace-10)+0.5)*10^(DPlace-10)
92 :else if DPlace=10 then
93 :L=int(L+0.5)
94 :else
95 :L=int(L*10^(10-DPlace)+0.5)/10^(10-DPlace)
100 print P,D,L,log(X)
110 wend
sqrts n approx accurate
12 4096 0.6930365715 0.6931471805599453093
13 8192 0.6930921133 0.6931471805599453093
14 16384 0.6931204959 0.6931471805599453093
15 32768 0.6931334578 0.6931471805599453093
16 65536 0.693137481 0.6931471805599453093
17 131072 0.6931427693 0.6931471805599453093
18 262144 0.6931323063 0.6931471805599453093
19 524288 0.693107414 0.6931471805599453093
20 1048576 0.693108075 0.6931471805599453093
21 2097152 0.6931084055 0.6931471805599453093
22 4194304 0.6928988556 0.6931471805599453093
23 8388608 0.6928989382 0.6931471805599453093
24 16777216 0.6928989795 0.6931471805599453093
25 33554432 0.6912212786 0.6931471805599453093
26 67108864 0.6912212889 0.6931471805599453093
27 134217728 0.6845104077 0.6931471805599453093
28 268435456 0.6710886375 0.6931471805599453093
29 536870912 0.6442450932 0.6931471805599453093
30 1073741824 0.6442450938 0.6931471805599453093
31 2147483648 0.6442450941 0.6931471805599453093
32 4294967296 0.4294967294 0.6931471805599453093
Illegal parameter in 80
The best result is for n = 2^17, giving the closest match between the result determined by algorithm and the actual natural log of 2. When other numbers than 2 are used, the result similarly favors n=2^17.
Offhand we would expect the best value of k to be (n-1)/ln(10), so as to convert natural logs to common logs. However, we might worry that the approximation is consistently high or low, and therefore might benefit from a fudge factor. The following program uses n=2^17=131072 and tests the common logs as calculated on a 10-digit calculator against more accurate common logs:
10 P=17:D=131072:Conv=1/log(10):Conv2=int(Conv*10000000000+0.5)/10000000000
15 X=1.25
20 while X<10
30 X=X+0.25
40 L=X
50 for I=1 to P
60 L=int(sqrt(L)*10000000000+0.5)/10000000000
70 next
80 L=(L-1)*(D-1)*Conv2:DPlace=int(log(L)/log(10)+0.5)
90 if DPlace>10 then
91 :L=int(L/10^(DPlace-10)+0.5)*10^(DPlace-10)
92 :else if DPlace=10 then
93 :L=int(L+0.5)
94 :else
95 :L=int(L*10^(10-DPlace)+0.5)/10^(10-DPlace)
100 print X,L,log(X)*Conv,L/(log(X)*Conv)
110 wend
it results in
x approx log(x) accurate log(x) ratio
1.5 0.1760868828 0.1760912590556812419 0.9999751477972006653
1.75 0.24303450769 0.24303804868629444 0.999985430280099843
2.0 0.30102807988 0.3010299956639811951 0.9999936359033691323
2.25 0.3521794579 0.352182518111362484 0.9999913107232610664
2.5 0.3979401889 0.3979400086720376093 1.000000452902343225
2.75 0.4393292018 0.4393326938302626501 0.999992051512870109
3.0 0.477120655 0.4771212547196624371 0.9999987430455958422
3.25 0.5118837827 0.5118833609788743785 1.000000823861757911
3.5 0.5440682799 0.5440680443502756352 1.0000004329416638427
3.75 0.5740270717 0.5740312677277188513 0.9999926902453668399
4.0 0.6020561598 0.6020599913279623903 0.9999936359698076943
4.25 0.6283889302 0.6283889300503115379 1.0000000002382098964
4.5 0.6532075378 0.6532125137753436792 0.9999923823024838885
4.75 0.6766941376 0.6766936096248665709 1.0000007802277514067
5.0 0.6989682687 0.6989700043360188046 0.9999975168662345483
5.25 0.720160855 0.7201593034059568774 1.0000021545150299168
5.5 0.740362974 0.7403626894942438453 1.0000003842788949142
5.75 0.759665703 0.7596678446896304882 0.9999971807551873367
6.0 0.7781544272 0.7781512503836436323 1.000004082517832878
6.25 0.7958803777 0.7958800173440752189 1.0000004527766961451
6.5 0.8129118626 0.8129133566428555737 0.9999981621130427185
6.75 0.8293001129 0.8293037728310249212 0.9999955867425847741
7.0 0.8450963598 0.8450980400142568304 0.9999980118114381117
7.25 0.8603347572 0.8603380065709936966 0.999996223146055528
7.5 0.8750608439 0.8750612633917000465 0.9999995206144785558
7.75 0.8893030816 0.8893017025063102889 1.000001550760204129
8.0 0.903089932 0.9030899869919435856 0.99999993910690587
8.25 0.9164555491 0.9164539485499250875 1.000001746459903899
8.5 0.9294227024 0.9294189257142927332 1.0000040634912877033
8.75 0.9420084688 0.9420080530223132449 1.0000004413738135475
9.0 0.9542470024 0.9542425094393248745 1.0000047084054951243
9.25 0.9661439955 0.9661417327390326062 1.0000023420590279013
9.5 0.9777279098 0.9777236052888477662 1.0000044025848705596
9.75 0.9890044378 0.9890046156985368159 0.9999998201236536288
10.0 1.000002041 0.9999999999999999998 1.000002041
On a 10-digit calculator, the results seem accurate to only 5 significant digits. The ratios of the approximate log to the accurate log vary above and below 1. So it would seem no fudge factor should be applied, and the value of k should be 131071/ln(10) or 56923.41204, when rounded to 10 significant figures.
Edited on September 5, 2006, 3:56 pm
|
|
Posted by Charlie
on 2006-09-05 15:55:38 |
For the second part.
