Skip to content

Instantly share code, notes, and snippets.

@theSage21

theSage21/FiboMod.ipynb

Created July 28, 2019 06:40
Show Gist options
  • Save theSage21/414bdf7868432c8540ca4c8adf16d631 to your computer and use it in GitHub Desktop.
Save theSage21/414bdf7868432c8540ca4c8adf16d631 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
FiboMod.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Populating the interactive namespace from numpy and matplotlib\n"
]
}
],
"source": [
"%pylab inline\n",
"import pandas as pd\n",
"import seaborn as sns\n",
"plt.style.use('ggplot')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Nothing fancy here. Just a function to help us calculate fibonacci numbers the old fashioned way."
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [],
"source": [
"def fibo(n, cache={0: 0, 1: 1, 2: 1}):\n",
" if n not in cache:\n",
" cache[n] = fibo(n-1) + fibo(n-2)\n",
" return cache[n]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now let's calculate fibo up to a 100 since that's what my laptop supports. What we will also do is calculate F(n)%m for different values of m too. Say till 10"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>0</th>\n",
" <th>1</th>\n",
" <th>2</th>\n",
" <th>3</th>\n",
" <th>4</th>\n",
" <th>5</th>\n",
" <th>6</th>\n",
" <th>7</th>\n",
" <th>8</th>\n",
" <th>9</th>\n",
" <th>...</th>\n",
" <th>90</th>\n",
" <th>91</th>\n",
" <th>92</th>\n",
" <th>93</th>\n",
" <th>94</th>\n",
" <th>95</th>\n",
" <th>96</th>\n",
" <th>97</th>\n",
" <th>98</th>\n",
" <th>99</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>fibo(n)</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>5</td>\n",
" <td>8</td>\n",
" <td>13</td>\n",
" <td>21</td>\n",
" <td>34</td>\n",
" <td>...</td>\n",
" <td>2880067194370816120</td>\n",
" <td>4660046610375530309</td>\n",
" <td>7540113804746346429</td>\n",
" <td>12200160415121876738</td>\n",
" <td>19740274219868223167</td>\n",
" <td>31940434634990099905</td>\n",
" <td>51680708854858323072</td>\n",
" <td>83621143489848422977</td>\n",
" <td>135301852344706746049</td>\n",
" <td>218922995834555169026</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%1</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>...</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%2</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>...</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%3</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>...</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%4</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>...</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%5</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>0</td>\n",
" <td>3</td>\n",
" <td>3</td>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" <td>...</td>\n",
" <td>0</td>\n",
" <td>4</td>\n",
" <td>4</td>\n",
" <td>3</td>\n",
" <td>2</td>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" <td>2</td>\n",
" <td>4</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%6</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>5</td>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" <td>4</td>\n",
" <td>...</td>\n",
" <td>4</td>\n",
" <td>5</td>\n",
" <td>3</td>\n",
" <td>2</td>\n",
" <td>5</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%7</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>5</td>\n",
" <td>1</td>\n",
" <td>6</td>\n",
" <td>0</td>\n",
" <td>6</td>\n",
" <td>...</td>\n",
" <td>6</td>\n",
" <td>5</td>\n",
" <td>4</td>\n",
" <td>2</td>\n",
" <td>6</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%8</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>5</td>\n",
" <td>0</td>\n",
" <td>5</td>\n",
" <td>5</td>\n",
" <td>2</td>\n",
" <td>...</td>\n",
" <td>0</td>\n",
" <td>5</td>\n",
" <td>5</td>\n",
" <td>2</td>\n",
" <td>7</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>fibo(n)%9</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>5</td>\n",
" <td>8</td>\n",
" <td>4</td>\n",
" <td>3</td>\n",
" <td>7</td>\n",
" <td>...</td>\n",
" <td>1</td>\n",
" <td>5</td>\n",
" <td>6</td>\n",
" <td>2</td>\n",
" <td>8</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"<p>10 rows × 100 columns</p>\n",
"</div>"
],
"text/plain": [
" 0 1 2 3 4 5 6 7 8 9 ... 90 \\\n",
"fibo(n) 0 1 1 2 3 5 8 13 21 34 ... 2880067194370816120 \n",
"fibo(n)%1 0 0 0 0 0 0 0 0 0 0 ... 0 \n",
"fibo(n)%2 0 1 1 0 1 1 0 1 1 0 ... 0 \n",
"fibo(n)%3 0 1 1 2 0 2 2 1 0 1 ... 1 \n",
"fibo(n)%4 0 1 1 2 3 1 0 1 1 2 ... 0 \n",
"fibo(n)%5 0 1 1 2 3 0 3 3 1 4 ... 0 \n",
"fibo(n)%6 0 1 1 2 3 5 2 1 3 4 ... 4 \n",
"fibo(n)%7 0 1 1 2 3 5 1 6 0 6 ... 6 \n",
"fibo(n)%8 0 1 1 2 3 5 0 5 5 2 ... 0 \n",
"fibo(n)%9 0 1 1 2 3 5 8 4 3 7 ... 1 \n",
"\n",
" 91 92 93 \\\n",
"fibo(n) 4660046610375530309 7540113804746346429 12200160415121876738 \n",
"fibo(n)%1 0 0 0 \n",
"fibo(n)%2 1 1 0 \n",
"fibo(n)%3 2 0 2 \n",
"fibo(n)%4 1 1 2 \n",
"fibo(n)%5 4 4 3 \n",
"fibo(n)%6 5 3 2 \n",
"fibo(n)%7 5 4 2 \n",
"fibo(n)%8 5 5 2 \n",
"fibo(n)%9 5 6 2 \n",
"\n",
" 94 95 96 \\\n",
"fibo(n) 19740274219868223167 31940434634990099905 51680708854858323072 \n",
"fibo(n)%1 0 0 0 \n",
"fibo(n)%2 1 1 0 \n",
"fibo(n)%3 2 1 0 \n",
"fibo(n)%4 3 1 0 \n",
"fibo(n)%5 2 0 2 \n",
"fibo(n)%6 5 1 0 \n",
"fibo(n)%7 6 1 0 \n",
"fibo(n)%8 7 1 0 \n",
"fibo(n)%9 8 1 0 \n",
"\n",
" 97 98 99 \n",
"fibo(n) 83621143489848422977 135301852344706746049 218922995834555169026 \n",
"fibo(n)%1 0 0 0 \n",
"fibo(n)%2 1 1 0 \n",
"fibo(n)%3 1 1 2 \n",
"fibo(n)%4 1 1 2 \n",
"fibo(n)%5 2 4 1 \n",
"fibo(n)%6 1 1 2 \n",
"fibo(n)%7 1 1 2 \n",
"fibo(n)%8 1 1 2 \n",
"fibo(n)%9 1 1 2 \n",
"\n",
"[10 rows x 100 columns]"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"limit = 100\n",
"x = np.arange(0, limit)\n",
"f = [fibo(n) for n in x]\n",
"m = [[i%m for i in f] for m in range(1, 10)]\n",
"m = [f]+m\n",
"\n",
"df = pd.DataFrame(m)\n",
"\n",
"df.index = [f'fibo(n)%{i}' if i > 0 else 'fibo(n)' for i in df.index]\n",
"df"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"so we see that even though the fibonacci number grows to very large sizes, the mod does not. There is hope! If we can directly calculate the mod value we might be able to skip the heavy computation. Let's write a function to calculate the periods.\n",
"\n",
"Which means to get `fib(n)%m` we don't need to calculate `fib(n)`. All we need is WHERE does this modded number fall on the repeating period. Let's find the period first.\n",
"\n",
"Imagine that `fibo(10000) % 3` is being asked. We then don't have to calculate more than 8 fibonacci numbers."
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 1, 1, 2, 0, 2, 2, 1]"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def period(m, cache={}):\n",
" if m not in cache:\n",
" seq = []\n",
" i = 0\n",
" l = 0\n",
" while True:\n",
" seq.append(fibo(i)%m)\n",
" l += 1\n",
" i += 1\n",
" if l % 2 == 0: # even length\n",
" pre, post = seq[:l//2], seq[l//2:]\n",
" if pre==post:\n",
" cache[m] = pre\n",
" return cache[m]\n",
" return cache[m]\n",
"period(3)"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"377 ns ± 16.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"def answer(n, m):\n",
" seq = period(m)\n",
" return seq[n%len(seq)]\n",
"\n",
"answer(239, 1000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That's fast enough for our purposes. Let's test the other case given in the input."
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"328 ns ± 14.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"answer(2816213588, 239)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"works for us I think. For the sake of completeness let's compare it to the vanilla method of getting the answer."
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"390 ns ± 16.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"def suppandi_answer(n, m):\n",
" return fibo(n) % m\n",
"suppandi_answer(239, 1000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That works out well due to the cache. But we can already start seeing the cracks in the code. It's a little slower. Let's hit it with a higher number."
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"476 ns ± 17.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"\n",
"def suppandi_answer(n, m):\n",
" return fibo(n) % m\n",
"suppandi_answer(500, 1000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And we see that it starts to grow"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.7"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment