Algoritmics with Rust
Tags: mathematics, rust
Published: 2017-04-25 13:12:23

---
title: Algoritmics with Rust
published: true
description: 
tags: Mathematics, Rust
---

*Originaly posted on my [blog](https://mathieu-nivoliez.com/posts/2017-04-25-algoritmics-with-rust/)*.

<p style="text-align: justify;">Hello, today we are going to talk about Algoritmics!</p>

<h2 style="text-align: justify;">"Algoritmics? Is it eatable?"</h2>
<p style="text-align: justify;">Hell no, or only by your brain. Before speaking about algoritmics, let's talk about algorithm. According to <a href="https://en.wikipedia.org/wiki/Algorithm">Wikipedia</a>:</p>

<blockquote>In <a title="Mathematics" href="https://en.wikipedia.org/wiki/Mathematics">mathematics</a> and <a title="Computer science" href="https://en.wikipedia.org/wiki/Computer_science">computer science</a>, an <b>algorithm</b> (<span class="nowrap"><span class="noexcerpt"><a title="Listen" href="https://upload.wikimedia.org/wikipedia/commons/7/7f/En-us-algorithm.ogg"><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Speakerlink-new.svg/11px-Speakerlink-new.svg.png" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Speakerlink-new.svg/17px-Speakerlink-new.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Speakerlink-new.svg/22px-Speakerlink-new.svg.png 2x" alt="Listen" width="11" height="11" data-file-width="11" data-file-height="11" /></a><sup><span class="IPA"><a title="File:En-us-algorithm.ogg" href="https://en.wikipedia.org/wiki/File:En-us-algorithm.ogg">i</a></span></sup></span><span class="IPA nopopups"><a title="Help:IPA for English" href="https://en.wikipedia.org/wiki/Help:IPA_for_English">/<span title="/Ëˆ/ primary stress follows">Ëˆ</span><span title="/Ã¦/ short 'a' in 'bad'">Ã¦</span><span title="'l' in 'lie'">l</span><span title="'g' in 'guy'">É¡</span><span title="/É™/ 'a' in 'about'">É™</span><span title="'r' in 'rye'">r</span><span title="/Éª/ short 'i' in 'bid'">Éª</span><span title="/Ã°/ 'th' in 'thy'">Ã°</span><span title="/É™m/ 'm' in 'rhythm'">É™m</span>/</a></span></span> <span title="English pronunciation respelling"><a title="Help:Pronunciation respelling key" href="https://en.wikipedia.org/wiki/Help:Pronunciation_respelling_key"><i><b><span class="smallcaps">AL</span></b>-gÉ™-ri-dhÉ™m</i></a></span>) is a self-contained sequence of actions to be performed. Algorithms can perform <a title="Calculation" href="https://en.wikipedia.org/wiki/Calculation">calculation</a>, <a title="Data processing" href="https://en.wikipedia.org/wiki/Data_processing">data processing</a> and <a title="Automated reasoning" href="https://en.wikipedia.org/wiki/Automated_reasoning">automated reasoning</a> tasks.

An algorithm is an <a title="Effective method" href="https://en.wikipedia.org/wiki/Effective_method">effective method</a> that can be expressed within a finite amount of space and time<sup id="cite_ref-1" class="reference"><a href="https://en.wikipedia.org/wiki/Algorithm#cite_note-1">[1]</a></sup> and in a well-defined formal language<sup id="cite_ref-2" class="reference"><a href="https://en.wikipedia.org/wiki/Algorithm#cite_note-2">[2]</a></sup> for calculating a <a title="Function (mathematics)" href="https://en.wikipedia.org/wiki/Function_%28mathematics%29">function</a>.<sup id="cite_ref-3" class="reference"><a href="https://en.wikipedia.org/wiki/Algorithm#cite_note-3">[3]</a></sup> Starting from an initial state and initial input (perhaps <a title="Empty string" href="https://en.wikipedia.org/wiki/Empty_string">empty</a>),<sup id="cite_ref-4" class="reference"><a href="https://en.wikipedia.org/wiki/Algorithm#cite_note-4">[4]</a></sup> the instructions describe a <a title="Computation" href="https://en.wikipedia.org/wiki/Computation">computation</a> that, when <a title="Execution (computing)" href="https://en.wikipedia.org/wiki/Execution_%28computing%29">executed</a>, proceeds through a finite<sup id="cite_ref-5" class="reference"><a href="https://en.wikipedia.org/wiki/Algorithm#cite_note-5">[5]</a></sup> number of well-defined successive states, eventually producing "output"<sup id="cite_ref-6" class="reference"><a href="https://en.wikipedia.org/wiki/Algorithm#cite_note-6">[6]</a></sup> and terminating at a final ending state. The transition from one state to the next is not necessarily <a class="mw-redirect" title="Deterministic" href="https://en.wikipedia.org/wiki/Deterministic">deterministic</a>; some algorithms, known as <a class="mw-redirect" title="Randomized algorithms" href="https://en.wikipedia.org/wiki/Randomized_algorithms">randomized algorithms</a>, incorporate random input.<sup id="cite_ref-7" class="reference"><a href="https://en.wikipedia.org/wiki/Algorithm#cite_note-7">[7]</a></sup></blockquote>
<p style="text-align: justify;">This is quite difficult to eat. To put it simply, an algorithm is a sequence of operations which produce a result. For example, when you are baking bread, you follow an algorithm: you're putting the flour, then the yeast, etc... And it produces bread.</p>
<p style="text-align: justify;">And again according to <a href="https://en.wikipedia.org/wiki/Algorithmics">Wikipedia</a>:</p>

<blockquote><b>Algorithmics</b> is the science of <a title="Algorithm" href="https://en.wikipedia.org/wiki/Algorithm">algorithms</a>. It includes <a title="Algorithm design" href="https://en.wikipedia.org/wiki/Algorithm_design">algorithm design</a>, the art of building a procedure which can solve efficiently a specific problem or a class of problem, <a class="mw-redirect" title="Algorithmic complexity theory" href="https://en.wikipedia.org/wiki/Algorithmic_complexity_theory">algorithmic complexity theory</a>, the study of estimating the hardness of problems by studying the properties of algorithm that solves them, or <a class="mw-redirect" title="Algorithm analysis" href="https://en.wikipedia.org/wiki/Algorithm_analysis">algorithm analysis</a>, the science of studying the properties of a problem, such as quantifying resources in time and memory space needed by this algorithm to solve this problem.</blockquote>
<p style="text-align: justify;">We could say that algorithmics is studying and making algorithm. This include calculate the complexity or the cost of them.</p>

<h2 style="text-align: justify;">"Cost? I got to pay?"</h2>
<p style="text-align: justify;">Yes and no. An algorithm got a cost of resources. When you bake your bread, you use ingredients (those are the inputs) and for each action, you use resources (like your hand, a wooden spoon, etc...) and those represent the cost.</p>
<p style="text-align: justify;">What we want is to evaluate this cost, also called complexity.</p>
<p style="text-align: justify;">Again with <a href="https://en.wikipedia.org/wiki/Analysis_of_algorithms">Wikipedia</a> (yes, again):</p>

<blockquote>In <a title="Computer science" href="https://en.wikipedia.org/wiki/Computer_science">computer science</a>, the <b>analysis of algorithms</b> is the determination of the amount of time, storage and/or other resources necessary to <a title="Computation" href="https://en.wikipedia.org/wiki/Computation">execute them</a>. Most <a title="Algorithm" href="https://en.wikipedia.org/wiki/Algorithm">algorithms</a> are designed to work with inputs of arbitrary length. Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (<a title="Time complexity" href="https://en.wikipedia.org/wiki/Time_complexity">time complexity</a>) or storage locations (<a class="mw-redirect" title="Space complexity" href="https://en.wikipedia.org/wiki/Space_complexity">space complexity</a>).</blockquote>
<h2 style="text-align: justify;">"So, how do we measure that?"</h2>
<p style="text-align: justify;">First, it exists a specific notation: O(f(n)) ("Big O of f(n)") where f is a mathematical function of n.</p>
<p style="text-align: justify;">Look at the following algorithm:</p>

<pre class="EnlighterJSRAW" data-enlighter-language="null">Entries: array a of size n
For i from 1 to n do
  print a[i] // one action here
End for</pre>
<p style="text-align: justify;">We got an input array with n elements. For each of the, we are going to print it, so one action. At the end, the algorithm should have print n time. So n actions. So the complexity is O(n).</p>
<p style="text-align: justify;">It does not matter if you make one are two actions, the constant factor is always relative to n.</p>
<p style="text-align: justify;">But in the following algorithm:</p>

<pre class="EnlighterJSRAW" data-enlighter-language="null">Entries: array a of size n
For i from 1 to n do
  For j from 1 to n do
    print a[i] // one action
  End for
End for</pre>
<p style="text-align: justify;">We do a second loop inside the first one. So we are printing n messages n times. So the complexity is O(n<sup>2</sup>).</p>

<h2 style="text-align: justify;">"Ok, and the Rust"</h2>
<p style="text-align: justify;">It is juste the language I have chose to make the future algorithms.</p>
<p style="text-align: justify;">As this article starts to getting big, I shall end it here, see you next for the studying of bubble sort.</p>
<p style="text-align: right;">-- Mathieu</p>