1

Given $t=\log_b(n)$ (assume that $b=2$) with $n\in \Bbb N$, where $n$ is not a power of $b$, how many decimal digits of $t$ must be preserved so that rounding $b^t$ (in this case, $2^t$) to the nearest natural number is $n$?

What about a generalized form where $b$ can be any number, or a natural logarithm?

Vivek Kaushik
  • 3,394
Danyil Bee
  • 109
  • 1
  • 7
  • 1
    You need $log_b (n-.5) < v <log_b (n+.5)$ so margin is $\log_b (n+.5)(n-.05) $ which requires $log_{10}\log_b (n+.5)(n-.5) $ decimal places. I hope. – fleablood May 16 '17 at 03:52
  • @fleablood Thank you for your input, can you please post an answer? Also, your notation is confusing--the lack of parentheses makes me question if (n-0.5) is included in the logb. Can you edit parentheses in? Thanks. – Danyil Bee May 17 '17 at 18:12
  • No. Ross Millikan's answer seems to express me idea better and in more detail than mine. My comment was only to be food for thought to thing about how to solve it. I hadn't actually worked it out or done all the details. – fleablood May 17 '17 at 18:41

2 Answers2

1

Let $\Delta t$ be the absolute value of the error in the log, caused by truncation or whatever. You want $$2^{t+\Delta t}-2^t \lt \frac 12\\ 2^{\Delta t}-1 \lt \frac 1{2n}\\ e^{\Delta t \ln 2}-1 \lt \frac 1{2n}\\ \Delta t \ln 2 \lt \frac 1{2n}\\ \Delta t \lt \frac 1{2 (\ln 2) n}\\ \log_{10} \Delta t \lt \log_{10} \frac 1{2 (\ln 2) n}$$ Which shows the number of places you need to keep in $t$ increases with $\log n$. I assume $\Delta t \ln 2$ is small going from the third to fourth line and kept only one term of the Taylor series.

Ross Millikan
  • 374,822
  • "... Increases with log n" What base is this log, as well as the one in the last part of the proof, referring to? – Danyil Bee May 17 '17 at 20:42
  • I'd assume"log" is base ten? Please specify, as the nature of this question involves generalized logarithms with any base – Danyil Bee May 17 '17 at 20:57
  • It needs to be the same on both sides. To use it for counting places it should be base $10$. I'll update. – Ross Millikan May 17 '17 at 21:02
1

Okay, let's think this out.

We have $t = \log_b n; b^t = n$. We want to find the range of $v$ so that $|n - b^v|< 1/2$ and how many decimal places $v$ may vary from $t$

So let $b^{v_1} = n - \frac 12$ so $v_1 = \log_b (n-\frac 12)$. So $t - v = \log_b n - \log_b (n - \frac 12) = \log_b {n}{n- \frac 12}$. How many leading zeros does this have? It has $\lfloor -\log_{10} (\log_b \frac{n}{n- \frac 12})\rfloor$ decimal places.

Likewise $b^{v_2} = n + \frac 12$ so $v_2$ is within $\lfloor-\log_{10}(\log_b \frac{n+\frac 12}n)\rfloor$ decimal places.

So to find $round[b^v] = n$ we need to solve $v = \log_b n$ within $\min (\lfloor -\log_{10} (\log_b \frac{n}{n- \frac 12})\rfloor,\lfloor-\log_{10}(\log_b \frac{n+\frac 12}n)\rfloor) = \lfloor -\log_{10} (\log_b \frac{n}{n- \frac 12})\rfloor$ decimal places.

.....

Hmm I guess I should test that.

If $8^t = 5,673$ then $t = \log_8 5673 = \ln 5673/\ln 8 = 4.1566320495569725555773549220362$. If we calculate that to within $[-\log_{10} \log_8 {\frac {5673}{5672.5}}]=[-\log \log_8 \frac {11346}{11345}] = [-\log 4.2386703739308141293762517391067e-5] = [4.3727703556302006379851110164063] = 4$.

So $8^{4.1566} = 5672.6219344912076083978179288225$. Yep, that's within a margin of error of 1/2. Seems to work.

fleablood
  • 124,253