All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Eleven Square Roots in a Logarithm (Posted on 2006-09-05) Difficulty: 2 of 5
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(x1/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?

See The Solution Submitted by Richard    
Rating: 3.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
For the second part. | Comment 2 of 6 |

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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information