forked from Hardmath123/hardmath123.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy patha-balance-of-powers.html
More file actions
314 lines (305 loc) · 14.3 KB
/
a-balance-of-powers.html
File metadata and controls
314 lines (305 loc) · 14.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" type="text/css" href="/static/base.css"/>
<title>A Balance of Powers - Comfortably Numbered</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta charset="utf-8"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
MathJax.Hub.Config({
tex2jax: {inlineMath: [['($','$)']]}
});
</script>
</head>
<body>
<header id="header">
<link rel="stylesheet" href="/octicons/octicons.css">
<script src="static/cheet.js" charset="utf-8"></script>
<script src="static/main.js"></script>
<h1>
<a href="/"><span class="left-word">Comfortably</span><span class="right-word">Numbered</span></a>
</h1>
<!-- You're reading the source to my blog? What do you think?
Do you have dinner plans? -->
</header>
<article id="postcontent" class="centered">
<section>
<h2>A Balance of Powers</h2>
<h4>Thursday, November 19, 2015 · 5 min read</h4>
<p>Wikipedia has an amusing article on <a href="https://en.wikipedia.org/wiki/Mathematical_coincidence">“mathematical
coincidence”</a>, where
they say that it’s a “coincidence” that ($ 2^{10} $) is very close to 1000
(it’s actually 1024). This is why it’s occasionally confusing whether you mean
1000 or 1024 bytes when you say
<a href="https://en.wikipedia.org/wiki/Kilobyte#Definitions_and_usage">“kilobyte”</a>.</p>
<p>I’m not sure whether this is something to get excited about, but you know what
we say about coincidence…</p>
<p><img src="static/coincidence.gif" alt="The universe is rarely so lazy."></p>
<p>Here are some fun facts to inspire today’s post:</p>
<ul>
<li><p>($ 2^{12864326} \approx 10^{3872548} $) <a href="http://www.wolframalpha.com/input/?i=2%5E12864326">to within
0.0001%</a>, which means it
begins with the digits “10000000…”.</p>
</li>
<li><p>($ 1337^{47168026} \approx \pi\cdot10^{147453447}$) <a href="http://www.wolframalpha.com/input/?i=1337%5E47168026">to within
0.00000001%</a>. It begins
with the digits “31415926…”.</p>
</li>
<li><p>The hex expansion of ($ e^{19709930078} $) is around 10 billion digits long,
and it begins with the digits <code>deadbeef...</code>.</p>
</li>
</ul>
<p>There is definitely something going on here. It’s time to investigate!</p>
<hr>
<p>Let’s go back to powers of two. It really comes down to the fact that we’re
trying to solve equations that look somewhat like this one</p>
<p>\[
2^{\alpha} = \delta10^{\beta}
\]</p>
<p>for integers, where we can make ($ \delta $) as close to 1 as we want.</p>
<p>It should feel intuitive to take logs of both sides at this point. So let’s go
ahead and do that:</p>
<p>\[
\alpha \ln(2) = \ln(\delta) + \beta\ln(10)
\]</p>
<p>Since ($ \delta $) is close to 1, its natural log is close to 0. So this
equation reduces to finding a very close <a href="https://en.wikipedia.org/wiki/Diophantine_approximation">rational
approximations</a> of the
ratio of the natural logs of 2 and 10.</p>
<p>Rational approximation, also called <em>Diophantine</em> approximation, is the “art”
of finding rational numbers very close to real numbers. Since the rationals are
dense in the reals, we can find a rational number arbitrarily close to any real
number. The naïve way to do this is to simply take the decimal expansion
to as many digits as we want. So, for example, we can find rational
approximations of pi such as 3/1, 31/10, 314/100, etc.</p>
<p>So, it follows that we can find arbitrarily precise rational approximations of
($ \ln(10) / \ln(2) $), which is what we’re looking for! The numerator gives
the power of 2 and the denominator gives the power of 10.</p>
<p>That ratio is around 3.321928094, so ($ 2^{3321928094} $) should be really
close to a power of 10, right?</p>
<p><a href="http://www.wolframalpha.com/input/?i=2%5E3321928094">…wrong.</a> The power of
10 is spot-on, but our first digit is completely off. This is tragic! We’re
close, but not close enough.</p>
<p>How can we fix this?</p>
<p>We could add more digits, but eventually WolframAlpha stops doing those
calculations for us. (There’s a nice online calculator
<a href="http://www.ttmath.org/online_calculator">here</a> that seems to handle much
bigger problems, but loses precision eventually.)</p>
<p>The problem is that even though we’re close, we’re not close <em>enough</em>. Remember
that our worst-case scenario with the decimal-truncation strategy is that we’re
off by ($1/\beta$). That is, we have</p>
<p>\[
\left| \frac{\alpha}{\beta} - \frac{\ln(10)}{\ln(2)} \right| = \frac{1}{\beta}
\]</p>
<p>Rearranging this a little bit, we have:</p>
<p>\[
\alpha \ln(2) = \ln(2) + \beta\ln(10)
\]</p>
<p>In other words, we have:</p>
<p>\[
2^\alpha = 2\times10^\beta
\]</p>
<p>We could be off by up to a factor of two! That means that even though our
rational approximation is getting closer, our first digit could still vary
pretty randomly.</p>
<p>What’s an easy fix here? We could start by rounding rather than truncating.
This means our worst-case scenario drops to ($ 1/(2\beta) $) (why?), which
corresponds to being off by up to a factor of the square root of two (around
1.4).</p>
<p>If we round the example above, we get ($ 2^{3321928095} $), which is
<a href="http://www.wolframalpha.com/input/?i=2%5E3321928095">better</a>. But
percent-error wise, we’re still doing <em>worse</em> than ($ 2^{10} $). We need to
take more drastic measures.</p>
<hr>
<p>It turns out that there is a way to find the <em>best</em> rational approximation of
a number for a given denominator. This is a beautiful field of number theory
that relates images like the one below to computing GCDs efficiently.</p>
<p><img src="static/ford-circle.png" alt="Ford circle, from Wikipedia Commons."></p>
<p>I’ll leave it to you to discover the math on your own, but the result we seek
is <a href="https://en.wikipedia.org/wiki/Dirichlet%27s_approximation_theorem">Dirichlet’s approximation
theorem</a>,
which states that we can always find a rational approximation which is within
($ 1/(\beta^2) $) of the target. In fact, there are an <em>infinite</em> number of
such rational approximations, which means ($ \beta $) can get as large as we
want (why?).</p>
<p>Since we have a ($ \beta^2 $) term in the denominator, the error decreases
<em>faster</em> than the denominator. This means we can get within ($ 2^{(1/\beta)}
$) of a power of 10. Since there’s a factor of ($ \beta $) in that expression,
we can make it as large as we want to get as close to a power of 10 as we want!
Win!</p>
<hr>
<p>How do we compute these best rational approximations? The trick is to express
our target number as a <a href="https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations">continued
fraction</a>,
and then to simplify those continued fractions.</p>
<p>It’s not hard to write code to do this quickly. WolframAlpha and Mathematica
come with a built-in function <code>Rationalize</code> that does exactly what we want.
With a little twiddling of the “delta” parameter, we <a href="http://www.wolframalpha.com/input/?i=Rationalize%5Bln%2810%29%2Fln%282%29%2C+%28log_2%281.00001%29%29%5E2%5D">can
get</a>
approximations within whatever interval we want, and they
<a href="http://www.wolframalpha.com/input/?i=2%5E254370">work</a>!</p>
<p>Pushing this gives us lovely results, like ($ 2^{44699994} $), which is around
($ 9.9999997\times10^{13456038} $), <a href="http://www.wolframalpha.com/input/?i=2%5E44699994">within
0.0000003%</a> of a power of
ten. Wonderful.</p>
<hr>
<p>The natural question to ask now is whether we can do <em>even</em> better. Can we get
an <em>arbitrary</em> sequence of digits at the beginning of the result? It turns out
we can. By manipulating Euclidean algorithm a bit, we can generate any
remainder, not necessarily one that is close to zero. Since the remainder
controls the first few digits, we need to find an approximation with error ($
\ln(\delta) $).</p>
<p>The trick is to use a “secondary” version of the Euclidean Algorithm where we
approximate ($ \ln(\delta) $) by adding together the errors of successively
more precise approximations.</p>
<p>Here’s an example. Suppose we compute a series of rational approximations of a
number and we get the following two rows:</p>
<table>
<thead>
<tr>
<th>Numerator</th>
<th>Denominator</th>
<th style="text-align:right">Error</th>
</tr>
</thead>
<tbody>
<tr>
<td>2</td>
<td>1</td>
<td style="text-align:right">0.0131</td>
</tr>
<tr>
<td>175</td>
<td>87</td>
<td style="text-align:right">0.0028</td>
</tr>
</tbody>
</table>
<p>Adding these two rows gives us a new row:</p>
<table>
<thead>
<tr>
<th>Numerator</th>
<th>Denominator</th>
<th style="text-align:right">Error</th>
</tr>
</thead>
<tbody>
<tr>
<td>177</td>
<td>88</td>
<td style="text-align:right">0.0159</td>
</tr>
</tbody>
</table>
<p>(Why does this work?)</p>
<p>This gives us an approximation with error 0.0159. We can keep doing this in a
method that resembles a cross between Gaussian elimination in matrices and the
Euclidean algorithm for integers, and get as close as we want to any target
“error”.</p>
<hr>
<p>You can download a Python program I wrote to generate these expressions
<a href="static/power-approx.py">here</a>. It uses the lovely
<a href="http://mpmath.org"><code>mpmath</code></a> library. A sample session with it, used to
compute one of the examples above:</p>
<pre><code>$ !!
Prefix? --> 0xdeadbeef
Base? ----> e
Radix? ---> 16
Accurate to 4 digits:
2.71828182845905^16311 ~~ 3735928559*16e+5875
Accurate to 5 digits:
2.71828182845905^4407903 ~~ 3735928559*16e+1589807
Accurate to 7 digits:
2.71828182845905^1044698524 ~~ 3735928559*16e+376795337
Accurate to 7 digits:
2.71828182845905^1044698524 ~~ 3735928559*16e+376795337
Accurate to 7 digits:
2.71828182845905^5021368668 ~~ 3735928559*16e+1811075911
Accurate to 7 digits:
2.71828182845905^5021368668 ~~ 3735928559*16e+1811075911
Accurate to 8 digits:
2.71828182845905^19709930078 ~~ 3735928559*16e+7108854587
</code></pre><hr>
<p>If you enjoyed that journey, here are some exploration questions:</p>
<ul>
<li>What happens when your base is 2 and your radix is 16? Why?</li>
<li>How is this related to <a href="https://en.wikipedia.org/wiki/Euclid%27s_orchard">Euclid’s
Orchard</a>? Does exploring
Euclid’s orchard give a natural way to prove Dirichlet’s approximation theorem?
As a hint, what principle is named after Dirichlet?</li>
</ul>
</section>
<div id="comment-breaker">◊ ◊ ◊</div>
<!--
<section>
<center>(<a id="comment-toggle" href="#comment-toggle">Click to load comments…</a>)</center>
<div id="disqus_thread"></div>
<script type="text/javascript">
var disqus_shortname = 'comfortablynumbered';
var disqus_identifier = 'a-balance-of-powers.md';
window.addEventListener(
'load',
(function() {
document.getElementById('comment-toggle').addEventListener('click',
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
}),
true);
}),
true
);
</script>
</section>
-->
</article>
<footer id="footer">
<div>
<ul>
<li><a href="http://github.com/Hardmath123">
<span class="octicon octicon-mark-github"></span>
Github</a></li>
<li><a href="feed.xml">
<span class="octicon octicon-rss"></span>
Subscribe (RSS)</a></li>
<li><a href="https://github.com/Hardmath123/hardmath123.github.io/issues/new?title=Hi&body=How's%20it%20going%3F">
<span class="octicon octicon-comment-discussion"></span>
Feedback</a></li>
<li><a href="mailto:contact-at-comfortablynumbered-dot-appspotmail-dot-com">
<span class="octicon octicon-mail-read"></span>
Email me</a></li>
<li><a href="http://creativecommons.org/licenses/by-nc/3.0/deed.en_US">
<span class="octicon octicon-law"></span>
CC BY-NC 3.0</a></li>
<li><a href="appreciation.html">
<span class="octicon octicon-beer"></span>
Other</a></li>
</ul>
</div>
<!--
<span class="sc">ComfortablyNumbered</span> · Hardmath123 (2013) · <a href="feed.xml">RSS Feed</a>
·
<a href="/appreciation.html">
<span class="octicon octicon-beer"></span></a>
<a rel="license" href="http://creativecommons.org/licenses/by-nc/3.0/deed.en_US">
<img
alt="Creative Commons License"
src="http://i.creativecommons.org/l/by-nc/3.0/80x15.png"/>
</a>
-->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46120535-1', 'hardmath123.github.io');
ga('require', 'displayfeatures');
ga('send', 'pageview');
</script>
</footer>
</body>
</html>