{"id":5516,"date":"2018-09-02T13:00:08","date_gmt":"2018-09-02T13:00:08","guid":{"rendered":"http:\/\/writeasync.net\/?p=5516"},"modified":"2018-08-29T15:04:08","modified_gmt":"2018-08-29T15:04:08","slug":"data-structure-kata-exact-square-roots","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5516","title":{"rendered":"Data structure kata: exact square roots"},"content":{"rendered":"<p>Many programming courses introduce the concept of data structures with <a href=\"https:\/\/en.wikipedia.org\/wiki\/Complex_number\">complex numbers<\/a> as a <a href=\"http:\/\/www2.lawrence.edu\/fast\/GREGGJ\/CMSC210\/structs\/structs.html\">motivating<\/a> <a <a href=\"http:\/\/cds.iisc.ac.in\/wp-content\/uploads\/DS286.Aug16.A02.pdf\">example<\/a>. Most commonly, these structures use <a href=\"https:\/\/en.wikipedia.org\/wiki\/Floating-point_arithmetic\">floating-point values<\/a> to represent the parts, e.g.:<\/p>\n<pre class=\"brush: csharp; title: ; notranslate\" title=\"\">\r\n\/\/ Real + Imag * i\r\npublic struct Complex\r\n{\r\n    public double Real;\r\n    public double Imag;\r\n}\r\n<\/pre>\n<p>This is fine for approximations, but what if we want to <strong>exactly<\/strong> represent the solutions to the equation <em>x<sup>2<\/sup> + 50 = 0<\/em>? That is, rather than <code>\u00b17.0710678...*i<\/code>, we want <code>\u00b15*sqrt(2)*i<\/code> &#8212; yes, that includes <a href=\"https:\/\/brilliant.org\/wiki\/simplify-radicals\/\">simplification of the value under the radical<\/a> (making it <a href=\"https:\/\/en.wikipedia.org\/wiki\/Square-free_integer\">square-free<\/a> as a math professor would say).<\/p>\n<p>It turns out that this is a nice little <a href=\"https:\/\/en.wikipedia.org\/wiki\/Kata_(programming)\">code kata<\/a> &#8212; simple enough to express in a few sentences, but with many possible solutions and nearly endless potential for extension.<\/p>\n<p>Here is my solution to the problem, using a C# struct called <code>RootTerm<\/code> to represent a possibly irrational and possibly imaginary quantity involving a square root: <a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commits\/master\/projects\/RootSample\">RootSample on GitHub<\/a>.<\/p>\n<p>A brief overview of my process:<\/p>\n<ul>\n<li>Start with a simple case, where the numbers are perfect squares (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/c1064724a6cf65ecd8a9fadbce612d1740a56f18#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>Extend this to support extracting factors of four, e.g. <code>sqrt(8) = 2*sqrt(2)<\/code> (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/69c77635a4e426a0de44f2d475431ab7dedf49cb#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>Extract factors of nine (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/21f8633ccb2d412c2bd42366cfa0e7c3d3408a05#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>Extract factors of 25 (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/f7055a778c1799815766efd28e2affb1953a3cc0#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>Add cases for irreducible composites, i.e. numbers like 15 which are already square-free (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/ed1b8d9b5c7936b944a30de6dff719d9e2821e8f#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>For good measure, add cases for prime numbers, which are always irreducible (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/dd6274f4b0ee2752894330e73e01fa7debe77dba#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>At this point, we need to start supporting all possible positive Int32 values, so we need a huge table of prime numbers! (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/866749416fbafe5b6217ead7f9a3b2c0f7f5a5b9#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>After a few refactorings, move on to tackle imaginary numbers by allowing the value to be negative (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/066932d07a46d5d401ee793d6fb4bb63b02c2221#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>Ensure the string output is formatted correctly by adding a few more tests (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/c069e31c90eef7ec5de309f577802a120d661def#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>The struct is mostly functional at this point so tests are added without much fanfare (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/da15bfcc94bd626cfa53fd7a117052a176c46f6e#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/li>\n<li>Solve one final issue with the special case for int.MinValue (<a href=\"https:\/\/github.com\/brian-dot-net\/writeasync\/commit\/c1f7799355c089f48fbeac76f92365479cb94f16#diff-5d122c28a12618940fae7ab79474afe6\">commit link<\/a>)<\/ul>\n<p>As I mentioned, this solution can be extended to support many other features. For example, adding two <code>RootTerm<\/code>s poses an interesting challenge, in that the answer may be some totally different type of number that we cannot yet represent like <code>sqrt(2) + sqrt(3)<\/code> (our friendly math professor would say that &#8220;RootTerm is not <a href=\"https:\/\/en.wikipedia.org\/wiki\/Closure_(mathematics)\">closed<\/a> under addition&#8221;). Solving that would require another data structure. Stay tuned for further exploration of this and other problems.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Many programming courses introduce the concept of data structures with complex numbers as a motivating<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[91,103,41],"tags":[],"class_list":["post-5516","post","type-post","status-publish","format-standard","hentry","category-design","category-math","category-tdd"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5516","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5516"}],"version-history":[{"count":2,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5516\/revisions"}],"predecessor-version":[{"id":5518,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5516\/revisions\/5518"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5516"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5516"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5516"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}