-
Notifications
You must be signed in to change notification settings - Fork 0
/
an-unreasonably-deep-dive-into-project-euler-problem-4.html
133 lines (133 loc) · 31.4 KB
/
an-unreasonably-deep-dive-into-project-euler-problem-4.html
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
<!doctype html><html lang=en><head><meta charset=utf-8><meta name=mobile-web-app-capable content="yes"><meta name=viewport content="width=device-width,initial-scale=1"><title>An Unreasonably Deep Dive Into Project Euler Problem 4 - Adam Drake
</title><meta name=description content="Adam Drake is an advisor to scale-up tech companies. He writes about ML/AI/crypto/data, leadership, and building tech teams."><link rel="shortcut icon" href=https://adamdrake.com/static/favicon.ico><link rel=authorization_endpoint href=https://indieauth.com/auth><link rel=token_endpoint href=https://tokens.indieauth.com/token><link rel=me href=https://github.com/adamdrake><link rel=stylesheet href=https://adamdrake.com/css/style.min.css crossorigin=anonymous media=screen><meta property="og:url" content="https://adamdrake.com/"><meta property="og:title" content="Adam Drake"><meta property="og:site_name" content="Adam Drake"><meta property="og:type" content="website"><meta property="og:description" content="Adam Drake is an advisor to scale-up tech companies. He writes about ML/AI/crypto/data, leadership, and building tech teams."><meta property="og:image" content="/static/images/twitter-card.jpg"><meta name=twitter:title content="Adam Drake"><meta name=twitter:description content="Adam Drake is an advisor to scale-up tech companies. He writes about ML/AI/crypto/data, leadership, and building tech teams."><meta name=twitter:card content="summary_large_image"><meta name=twitter:image content="/static/images/twitter-card.jpg"></head><body><header><section><div class="header flex row"><div class="header__item flex row"><a id=site__name href=https://adamdrake.com/>Adam Drake</a></div><div class="flex row"><nav aria-label="page menu" class="flex row"><ul role=menubar class="flex row"><li role=none><a class=sidebar-nav-itemmenu__item href=/ title>Latest</a></li><li role=none><a class=sidebar-nav-itemmenu__item href=/about.html title>About</a></li><li role=none><a class=sidebar-nav-itemmenu__item href=/cases.html title>Case Studies</a></li><li role=none><a class=sidebar-nav-itemmenu__item href=/contact.html title>Contact</a></li><li role=none><a class="sidebar-nav-item activemenu__item" href=/posts.html title=Posts>Posts</a></li><li role=none><a class=sidebar-nav-itemmenu__item href=/press.html title>Press</a></li><li><button class="subscribe subscribe-btn">
<a href=https://www.digitalmaneuver.com/#/portal>Subscribe to newsletter</a></button></li></ul></nav></div></div></section></header><main aria-role=main><section><ul id=feed__ul><li class="feed__li h-entry"><div class=feed__content><time class="hidden dt-published">2019-08-16 00:00:00 +0000 UTC</time><div class="flex properties__row"><div rel=author class="flex left p-author h-card hidden"><img class=u-photo src=https://adamdrake.com/static/images/adam_drake_240.jpg alt="Adam Drake" id=author-img><div><p rel=me class=p-name id=author-name>Adam Drake</p><p class=properties>Aug 16, 2019</p></div></div><div class="flex right properties"></div></div><article class="md p-summary e-content"><h1 class=p-name>An Unreasonably Deep Dive Into Project Euler Problem 4</h1><h1 id=or-how-to-make-your-solution-8000x-faster-with-math-and-short-circuit-evaluation class=anchor-link><a href=#or-how-to-make-your-solution-8000x-faster-with-math-and-short-circuit-evaluation>Or: How to make your solution 8000x faster with math and short-circuit evaluation.</a></h1><h1 id=introduction class=anchor-link><a href=#introduction>Introduction</a></h1><p>It has been a couple of years since my last Project Eueler effort, <a href=https://adamdrake.com/an-unreasonably-deep-dive-into-project-euler-problem-3.html>An Unreasonably Deep Dive into Project Euler Problem 3</a>, and since I’ve also been wanting to do more work with Rust recently, I thought it would be a good opportunity to do both things at once by doing Project Euler problem 4 in Rust instead of my default of Go as before.</p><h1 id=problem-statement class=anchor-link><a href=#problem-statement>Problem Statement</a></h1><blockquote><p>A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.</p><p>Find the largest palindrome made from the product of two 3-digit numbers.</p></blockquote><p>The general approach to the solution will be to find a working version first (as always), then focus on making it faster by reducing the search space. Along the way, there are a couple of programming techniques we can employ for great speedups as well.</p><p>All of this results in the final version being about <em>8000x faster</em> than the naive version.</p><p>For the full code, see <a href=https://github.com/adamdrake/projecteuler>the github repository</a>.</p><h1 id=helper-functions class=anchor-link><a href=#helper-functions>Helper function(s)</a></h1><p>To start with, we will need a function that tells us if a number is palindromic. This is not the most efficient way to write this helper function, but it works.</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-rust data-lang=rust><span style=display:flex><span><span style=color:#75715e>// We will need a helper function to determine if a number is palindromic
</span></span></span><span style=display:flex><span><span style=color:#75715e>//
</span></span></span><span style=display:flex><span><span style=color:#75715e>// is_palindromic_v1() will convert the number to a string, reverse the string, and compare that with the
</span></span></span><span style=display:flex><span><span style=color:#75715e>// string representation of the number.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span><span style=color:#66d9ef>fn</span> <span style=color:#a6e22e>is_palindromic_v1</span>(i: <span style=color:#66d9ef>i32</span>) -> <span style=color:#66d9ef>bool</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>return</span> i.to_string().chars().rev().collect::<span style=color:#f92672><</span>String<span style=color:#f92672>></span>() <span style=color:#f92672>==</span> i.to_string();
</span></span><span style=display:flex><span>}
</span></span></code></pre></div><h1 id=v0---time-required-102000000ns class=anchor-link><a href=#v0---time-required-102000000ns>v0() - time required: ~102,000,000ns</a></h1><p>As a naive/brute-force first version, let’s just multiply all three-digit numbers, check each time if the product is palindromic, keep it if it is, and continue that process until we have checked all products of three-digit numbers.</p><p>This is slow but it works.</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-rust data-lang=rust><span style=display:flex><span><span style=color:#75715e>// v0() is the naive attempt: multiply three-digit numbers. When a palindromic number is found,
</span></span></span><span style=display:flex><span><span style=color:#75715e>// if it's larger than the most recent palindromic number found then keep it. Iterate until the end 999.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span><span style=color:#66d9ef>fn</span> <span style=color:#a6e22e>v0</span>() -> <span style=color:#66d9ef>i32</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> <span style=color:#66d9ef>mut</span> res <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> i <span style=color:#66d9ef>in</span> <span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> j <span style=color:#66d9ef>in</span> <span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> prod <span style=color:#f92672>=</span> i <span style=color:#f92672>*</span> j;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>if</span> is_palindromic_v1(prod) <span style=color:#f92672>&&</span> prod <span style=color:#f92672>></span> res {
</span></span><span style=display:flex><span> res <span style=color:#f92672>=</span> prod;
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> <span style=color:#66d9ef>return</span> res;
</span></span><span style=display:flex><span>}
</span></span></code></pre></div><h1 id=v1---time-required-7300000ns-14x-speedup-from-v0 class=anchor-link><a href=#v1---time-required-7300000ns-14x-speedup-from-v0>v1() - time required: 7,300,000ns (~14x speedup from v0())</a></h1><p>This isn’t really an algorithm change, but it is a slight change in the code that makes a massive performance difference. We are taking advantage of the <a href=https://en.wikipedia.org/wiki/Short-circuit_evaluation>Short-circuit evaluation</a> present in Rust. This means that for a given sequence of arguments chained together with certain operators, like <code>&&</code>, the evaluation will take place from left to right and will terminate as soon as possible. This prevents the remaining elements in the sequence from being evaluated unnecessarily. In our case, that makes a big difference since we are iterating through many numbers and therefore would be executing <code>is_palindromic_v1()</code> many times. Since <code>prod > res</code> has a much lower computational cost than <code>is_palindromic_v1(prod)</code> and since <code>prod > res</code> happens sufficiently frequently, this cuts down runtime by a factor of 14.</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-rust data-lang=rust><span style=display:flex><span><span style=color:#75715e>// v1(): FUN FACT - Rust has short-circuit evaluation.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span><span style=color:#66d9ef>fn</span> <span style=color:#a6e22e>v1</span>() -> <span style=color:#66d9ef>i32</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> <span style=color:#66d9ef>mut</span> res <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> i <span style=color:#66d9ef>in</span> <span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> j <span style=color:#66d9ef>in</span> <span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> prod <span style=color:#f92672>=</span> i <span style=color:#f92672>*</span> j;
</span></span><span style=display:flex><span> <span style=color:#75715e>// Note that this order changed.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span> <span style=color:#75715e>// Consequently, the right-hand side of the && is only evaluated if needed.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span> <span style=color:#75715e>// This is important since string casting and reversing is so slow and the search
</span></span></span><span style=display:flex><span><span style=color:#75715e></span> <span style=color:#75715e>// space is so large. Many languages have short-circuit/lazy evaluation.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span> <span style=color:#75715e>// This matters less as we start restricting the search space.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span> <span style=color:#66d9ef>if</span> prod <span style=color:#f92672>></span> res <span style=color:#f92672>&&</span> is_palindromic_v1(prod) {
</span></span><span style=display:flex><span> res <span style=color:#f92672>=</span> prod;
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> <span style=color:#66d9ef>return</span> res;
</span></span><span style=display:flex><span>}
</span></span></code></pre></div><h1 id=v2---time-required-1800000ns-57x-speedup-from-v0 class=anchor-link><a href=#v2---time-required-1800000ns-57x-speedup-from-v0>v2() - time required: ~1,800,000ns (~57x speedup from v0())</a></h1><p>If you think about it, starting at the lower end of the range and iterating all the way to the higher end does not make very much sense when looking for the largest product. The chances that the largest product will come from the lower end of the range are very small, so we should start the iteration from the large numbers and work our way down instead. This results in a much smaller search space since we break out as soon as we find the large palindromic number.</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-rust data-lang=rust><span style=display:flex><span><span style=color:#75715e>// v2(): Start from the biggest numbers, which makes a lot more sense.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span><span style=color:#66d9ef>fn</span> <span style=color:#a6e22e>v2</span>() -> <span style=color:#66d9ef>i32</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> <span style=color:#66d9ef>mut</span> res <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> i <span style=color:#66d9ef>in</span> (<span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span>).rev() {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> j <span style=color:#66d9ef>in</span> (<span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span>).rev() {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> prod <span style=color:#f92672>=</span> i <span style=color:#f92672>*</span> j;
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span> <span style=color:#66d9ef>if</span> prod <span style=color:#f92672>></span> res <span style=color:#f92672>&&</span> is_palindromic_v1(prod) {
</span></span><span style=display:flex><span> res <span style=color:#f92672>=</span> prod;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>break</span>;
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> <span style=color:#66d9ef>return</span> res;
</span></span><span style=display:flex><span>}
</span></span></code></pre></div><h1 id=v3---time-required-1050000ns-97x-speedup-from-v0 class=anchor-link><a href=#v3---time-required-1050000ns-97x-speedup-from-v0>v3() - time required: ~1,050,000ns (~97x speedup from v0())</a></h1><p>Now we start to take advantage of some convenient math. Since we are multiplying two numbers, and multiplication is a <a href=https://en.wikipedia.org/wiki/Transitive_relation>commutative binary operation</a>, we know that we do not need to check <code>p * q</code> and <code>q * p</code> since they are the same. So if we get to a point in the evaluation where our product is less than the result we would currently return then we can also skip checking any smaller numbers that would come after that on the inner loop. This additional restriction of the search space gives us even more speedup.</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-rust data-lang=rust><span style=display:flex><span><span style=color:#75715e>// v3(): Now stop if result is greater than current product. If you
</span></span></span><span style=display:flex><span><span style=color:#75715e>// are multiplying and the product is smaller than the current number, you won't be
</span></span></span><span style=display:flex><span><span style=color:#75715e>// able to get around the fact that p * q = q * p, so you can stop.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span><span style=color:#66d9ef>fn</span> <span style=color:#a6e22e>v3</span>() -> <span style=color:#66d9ef>i32</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> <span style=color:#66d9ef>mut</span> res <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> i <span style=color:#66d9ef>in</span> (<span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span>).rev() {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> j <span style=color:#66d9ef>in</span> (<span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span>).rev() {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> prod <span style=color:#f92672>=</span> i <span style=color:#f92672>*</span> j;
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span> <span style=color:#66d9ef>if</span> prod <span style=color:#f92672>></span> res <span style=color:#f92672>&&</span> is_palindromic_v1(prod) {
</span></span><span style=display:flex><span> res <span style=color:#f92672>=</span> prod;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>break</span>;
</span></span><span style=display:flex><span> } <span style=color:#66d9ef>else</span> <span style=color:#66d9ef>if</span> res <span style=color:#f92672>></span> prod {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>break</span>;
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> <span style=color:#66d9ef>return</span> res;
</span></span><span style=display:flex><span>}
</span></span></code></pre></div><h1 id=v4---time-required-195000ns-517x-speedup-from-v0 class=anchor-link><a href=#v4---time-required-195000ns-517x-speedup-from-v0>v4() - time required: ~195,000ns (~517x speedup from v0())</a></h1><p>Now we can reduce search space a little more by examining the general shape of our palindromic number in question, and doing some factoring. This leads us to the conclusion that we don’t need to check every factor, but only cases where one of the factors is divisible by 11. For details, see the code comment below.</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-rust data-lang=rust><span style=display:flex><span><span style=color:#75715e>// v4(): Note that the number is probably 6 digits, i.e. abccba = p * q where each letter is some number between 1 and 9
</span></span></span><span style=display:flex><span><span style=color:#75715e>// then we can rewrite as a * 100000 + b * 10000 + c * 1000 + c * 100 + b * 10 + a * 1 = p * q
</span></span></span><span style=display:flex><span><span style=color:#75715e>// which we can rewrite as a * 100001 + b * 10010 + c * 1100 = p * q
</span></span></span><span style=display:flex><span><span style=color:#75715e>// which can be factored to 11 * (a * 9091 + b * 910 + c * 100) = p * q
</span></span></span><span style=display:flex><span><span style=color:#75715e>// therefore p * q must be divisible by 11
</span></span></span><span style=display:flex><span><span style=color:#75715e>// therefore either p or q must be divisible by 11.
</span></span></span><span style=display:flex><span><span style=color:#75715e>//
</span></span></span><span style=display:flex><span><span style=color:#75715e>// Since p or q must be divisible by 11, just start the iteration at 990 because it is
</span></span></span><span style=display:flex><span><span style=color:#75715e>// the largest possible number in the given range that is also divisible by 11 and
</span></span></span><span style=display:flex><span><span style=color:#75715e>// work our way down in steps of 11.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span><span style=color:#66d9ef>fn</span> <span style=color:#a6e22e>v4</span>() -> <span style=color:#66d9ef>i32</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> <span style=color:#66d9ef>mut</span> res <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> i <span style=color:#66d9ef>in</span> (<span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>990</span>).rev().step_by(<span style=color:#ae81ff>11</span>) {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> j <span style=color:#66d9ef>in</span> (<span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span>).rev() {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> prod <span style=color:#f92672>=</span> i <span style=color:#f92672>*</span> j;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>if</span> prod <span style=color:#f92672>></span> res <span style=color:#f92672>&&</span> is_palindromic_v1(prod) {
</span></span><span style=display:flex><span> res <span style=color:#f92672>=</span> prod;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>break</span>;
</span></span><span style=display:flex><span> } <span style=color:#66d9ef>else</span> <span style=color:#66d9ef>if</span> res <span style=color:#f92672>></span> prod {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>break</span>;
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> <span style=color:#66d9ef>return</span> res;
</span></span><span style=display:flex><span>}
</span></span></code></pre></div><h1 id=aside-finding-palindromic-integers class=anchor-link><a href=#aside-finding-palindromic-integers>Aside: finding palindromic integers</a></h1><p>Our naive helper function for checking palindromic integers is convenient but inefficient.</p><p>It has to cast our integer to a string, reverse that string to make a new string, and then compare that to another string-casted version of our original integer.</p><p>Fortunately, there is a much faster way to determine if an integer is palindromic. We can just continually divide the original number by 10 and append the remainder on the right side of a new number each time to construct the reverse of the original number. If the new number and the original number match, then the number is palindromic.</p><p>This version is a ~16x speedup over the version that uses string reversal and comparison.</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-rust data-lang=rust><span style=display:flex><span><span style=color:#75715e>// is_palindromic_v2() will build up a new number `reverse` by shifting `reverse` one decimal place
</span></span></span><span style=display:flex><span><span style=color:#75715e>// and adding the 10s place of the candidate number until no places are left in the candidate
</span></span></span><span style=display:flex><span><span style=color:#75715e>// number. In this way, `reverse` is constructed as the sequence of successive tens place numbers
</span></span></span><span style=display:flex><span><span style=color:#75715e>// from the original candidate number. This version is ~16x faster than is_palindromic_v1().
</span></span></span><span style=display:flex><span><span style=color:#75715e></span><span style=color:#66d9ef>fn</span> <span style=color:#a6e22e>is_palindromic_v2</span>(i: <span style=color:#66d9ef>i32</span>) -> <span style=color:#66d9ef>bool</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> <span style=color:#66d9ef>mut</span> reversed <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> <span style=color:#66d9ef>mut</span> number <span style=color:#f92672>=</span> i;
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span> <span style=color:#66d9ef>while</span> number <span style=color:#f92672>></span> <span style=color:#ae81ff>0</span> {
</span></span><span style=display:flex><span> reversed <span style=color:#f92672>=</span> reversed <span style=color:#f92672>*</span> <span style=color:#ae81ff>10</span> <span style=color:#f92672>+</span> number <span style=color:#f92672>%</span> <span style=color:#ae81ff>10</span>;
</span></span><span style=display:flex><span> number <span style=color:#f92672>=</span> number <span style=color:#f92672>/</span> <span style=color:#ae81ff>10</span>;
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> <span style=color:#66d9ef>return</span> reversed <span style=color:#f92672>==</span> i <span style=color:#f92672>||</span> i <span style=color:#f92672>==</span> number <span style=color:#f92672>/</span> <span style=color:#ae81ff>10</span>;
</span></span><span style=display:flex><span>}
</span></span></code></pre></div><h1 id=v5---time-required-13000ns-8000x-speedup-from-v0 class=anchor-link><a href=#v5---time-required-13000ns-8000x-speedup-from-v0>v5() - time required: ~13,000ns (~8000x speedup from v0())</a></h1><p>This version loops 1627 times, a ~500x reduction from <code>v0()</code> and <code>v1()</code>. The ~500x overall reduction in search space, the short-circuit evaluation change, plus the ~16x reduction due to the improved method of palindromic number checking is what gets us to the ~8000x reduction relative to the initial version.</p><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-rust data-lang=rust><span style=display:flex><span><span style=color:#75715e>// v5(): Get rid of the slow string reversing and use the numerical palindrome helper function.
</span></span></span><span style=display:flex><span><span style=color:#75715e></span><span style=color:#66d9ef>fn</span> <span style=color:#a6e22e>v5</span>() -> <span style=color:#66d9ef>i32</span> {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> <span style=color:#66d9ef>mut</span> res <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> i <span style=color:#66d9ef>in</span> (<span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>990</span>).rev().step_by(<span style=color:#ae81ff>11</span>) {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>for</span> j <span style=color:#66d9ef>in</span> (<span style=color:#ae81ff>100</span><span style=color:#f92672>..=</span><span style=color:#ae81ff>999</span>).rev() {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>let</span> prod <span style=color:#f92672>=</span> i <span style=color:#f92672>*</span> j;
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span> <span style=color:#66d9ef>if</span> prod <span style=color:#f92672>></span> res <span style=color:#f92672>&&</span> is_palindromic_v2(prod) {
</span></span><span style=display:flex><span> res <span style=color:#f92672>=</span> prod;
</span></span><span style=display:flex><span> <span style=color:#66d9ef>break</span>;
</span></span><span style=display:flex><span> } <span style=color:#66d9ef>else</span> <span style=color:#66d9ef>if</span> res <span style=color:#f92672>></span> prod {
</span></span><span style=display:flex><span> <span style=color:#66d9ef>break</span>;
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> }
</span></span><span style=display:flex><span> <span style=color:#66d9ef>return</span> res;
</span></span><span style=display:flex><span>}
</span></span></code></pre></div><h1 id=summary class=anchor-link><a href=#summary>Summary</a></h1><p>While there are still some performance gains likely to be had, they would probably be nominal and require extensive effort. By simply pursuing our general problem solving strategy of reducing the search space, combined with a couple of domain knowledge improvements in the form of taking advantage of short-circuit evaluation and a different helper function to check if a number is palindromic, we were able to get an approximately <em>8000x</em> speedup over the original naive version.</p><a class=hidden href=https://brid.gy/publish/mastodon></a><a class=hidden href=https://brid.gy/publish/twitter></a><a class=hidden href=https://fed.brid.gy/></a><data class=p-bridgy-omit-link value=false></data></article></div><div id=webmentions></div></li></ul></section></main><hr><footer class="flex col"><section class="footer-bio content"><p><strong>Adam Drake</strong> leads technical business transformations in global and multi-cultural environments. He has a passion for helping companies become more productive by improving internal leadership capabilities, and accelerating product development through technology and data architecture guidance. Adam has served as a White House Presidential Innovation Fellow and is an IEEE Senior Member.</p></section><button class="subscribe subscribe-btn">
<a href=https://www.digitalmaneuver.com/#/portal>Subscribe to newsletter</a></button><div class=social-icons><a rel=me href=https://github.com/adamdrake title=GitHub><svg width="24" height="24" viewBox="0 0 24 24" fill="none" stroke="currentcolor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round" class="feather feather-github"><path d="M9 19c-5 1.5-5-2.5-7-3m14 6v-3.87a3.37 3.37.0 00-.94-2.61c3.14-.35 6.44-1.54 6.44-7A5.44 5.44.0 0020 4.77 5.07 5.07.0 0019.91 1S18.73.65 16 2.48a13.38 13.38.0 00-7 0C6.27.65 5.09 1 5.09 1A5.07 5.07.0 005 4.77 5.44 5.44.0 003.5 8.55c0 5.42 3.3 6.61 6.44 7A3.37 3.37.0 009 18.13V22"/></svg></a></div></footer></body></html>