<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Paul Ariri on Medium]]></title>
        <description><![CDATA[Stories by Paul Ariri on Medium]]></description>
        <link>https://medium.com/@ariripaulcoc?source=rss-ed100fa318db------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*tPW3A27J_oq26tO_AxOGbA.jpeg</url>
            <title>Stories by Paul Ariri on Medium</title>
            <link>https://medium.com/@ariripaulcoc?source=rss-ed100fa318db------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 13:44:52 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@ariripaulcoc/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[What is the Pisano Period? How is it applied to coding problems?]]></title>
            <link>https://medium.com/@ariripaulcoc/what-is-the-pisano-period-how-is-it-applied-to-coding-problems-5e70590fb3da?source=rss-ed100fa318db------2</link>
            <guid isPermaLink="false">https://medium.com/p/5e70590fb3da</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[c]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[pisano]]></category>
            <dc:creator><![CDATA[Paul Ariri]]></dc:creator>
            <pubDate>Wed, 10 Jun 2020 21:27:23 GMT</pubDate>
            <atom:updated>2020-06-10T21:27:23.545Z</atom:updated>
            <content:encoded><![CDATA[<p>A week ago, I was watching various videos from my favorite “math” YouTuber — Numberphile, and I stumbled upon a video he made about the Pisano Period. Not knowing what this was, I was intrigued as to what mysteries were yet to unfold.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/989/1*bp7qb7dwaS5Bbvt-GGUuEw.png" /><figcaption>Pisano Period(Paul Ariri)</figcaption></figure><p>Before breaking the ice, let’s talk about Fibonacci, well, “Leonardo Fibonacci of Pisa.” He was an Italian mathematician who invoked the Fibonacci Series — 1, 1, 2, 3, 5, 8. The pattern is clear from the series and can be represented as Fn = Fn-1 + Fn-2; although it seems like a basic, hardly used series, it was used widely to calculate the growth of rabbit populations.</p><p>The existence of this periodic occurrence called the Pisano Period was discovered by “Joseph Louis Lagrange,” he noticed that if every number in the Fibonacci sequence were to be divided by a number, there would be a point where the remainders would start repeating themself. For example, the Pisano Period of 10 is 60 and that of 4 is 6 as seen in the diagram above.</p><p>Now we know a little bit about the Fibonacci sequence and the Pisano period, what coding problem we can encounter that may require us to use this Lagrange-found logic?</p><p>Answer: Find the remainder when the nth Fibonacci number is divided by m:</p><p>Sample Cases:</p><p>i. Input: n = 5, m = 3; Output: F(5) % 3 = 5 % 3 = 2</p><p>ii. Input: n = 6, m = 2; Output: F(6) % 2 = 8 % 2 = 0</p><p>iii. Input: n = 115, m = 1000; Output: F(115) % 1000 = 483162952612010163284885 % 1000 = 885;</p><p>Now the normal naive approach in C++is shown in the image below:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/1*-SPJNQIYm-YuAcfMU1T7Pg.png" /></figure><p>This approach would work for some cases, but could take days if not months to successfully give a solution for big/large numbers. This is where the Pisano Period comes in.</p><p>Efficient Approach: Now, the thing about the Pisano Period is that a new period starts when F(n) % m= 0 and F(n+1) % m = 1. In the case of 4, each Pisano period holds the numbers 1, 1, 2, 3, 1, 0…, so with intuition, if we are able to find the Pisano Period, we can find the remainder of any large Fibonacci number without actually finding or reaching that number.</p><p>If our input was n = 8 and m = 4, F(8) = 21, and 21 % 4 = 1, since we know the Pisano period when divided by 4 is 6 and 8 is 2 after that, that means F(2) % 4 == F(8) % 4. This explains the whole algorithm and the solution in C++ is below;</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/573/1*S7O7JBoZ6C5V804uoMBGwQ.png" /></figure><p>There are many more ways to use the Pisano period, and if you still find yourself lost in my explanation or implementation, there are many videos on YouTube that talk in-depth about it. But, I will recommend you watch this video by Numberphile → <a href="https://www.youtube.com/watch?v=Nu-lW-Ifyec">https://www.youtube.com/watch?v=Nu-lW-Ifyec</a></p><p>Check out my GitHub: <a href="https://www.github.com/paulAriri">https://www.github.com/paulAriri</a> and my website: <a href="https://www.paulariri.com/">https://www.paulariri.com</a>. Thank you!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5e70590fb3da" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>