Skip to content

Instantly share code, notes, and snippets.

@antimon2

antimon2/Project.toml

Last active March 14, 2024 12:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save antimon2/c2a0f1c2c452c615c893294dbcbe67b5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save antimon2/c2a0f1c2c452c615c893294dbcbe67b5 to your computer and use it in GitHub Desktop.
Download ZIP
fib_n_mod_m.jl
Display the source blob
Display the rendered blob
Raw
fib_n_mod_m.jl.ipynb
{
"cells": [
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:24:29.360Z",
"end_time": "2024-03-14T20:24:31.919000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "versioninfo()",
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"text": "Julia Version 1.10.2\nCommit bd47eca2c8a (2024-03-01 10:14 UTC)\nBuild Info:\n Official https://julialang.org/ release\nPlatform Info:\n OS: Linux (x86_64-linux-gnu)\n CPU: 12 × Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz\n WORD_SIZE: 64\n LIBM: libopenlibm\n LLVM: libLLVM-15.0.7 (ORCJIT, skylake)\nThreads: 1 default, 0 interactive, 1 GC (on 12 virtual cores)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:26:03.076Z",
"end_time": "2024-03-14T20:26:04.514000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using BenchmarkTools",
"execution_count": 5,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "ref: https://twitter.com/dannchu/status/1768180438743564351"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:25:24.651Z",
"end_time": "2024-03-14T20:25:26.224000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function fib_n(n::Integer)\n d = Dict(zero(n)=>big\"0\", one(n)=>big\"1\")\n fib_n(n, d)\nend\n\nfunction fib_n(n, d)\n if haskey(d, n)\n return d[n]\n end\n if n < 0\n result = iseven(n) ? -fib_n(-n, d) : fib_n(-n, d)\n d[n] = result\n return result\n end\n m = n ÷ 2\n result = if iseven(n)\n (2 * fib_n(m - 1, d) + fib_n(m, d)) * fib_n(m, d)\n else\n fib_n(m, d) ^ 2 + fib_n(m + 1, d) ^ 2\n end\n d[n] = result\n return result\nend",
"execution_count": 2,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 2,
"data": {
"text/plain": "fib_n (generic function with 2 methods)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:25:47.771Z",
"end_time": "2024-03-14T20:25:49.186000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "fib_n(2024) % 13",
"execution_count": 4,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 4,
"data": {
"text/plain": "8"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:26:15.073Z",
"end_time": "2024-03-14T20:26:23.199000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@btime fib_n(2024) % 13",
"execution_count": 6,
"outputs": [
{
"output_type": "stream",
"text": " 6.281 μs (204 allocations: 6.27 KiB)\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 6,
"data": {
"text/plain": "8"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:30:59.927Z",
"end_time": "2024-03-14T20:31:01.220000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function fib_n_mod_m(n::Integer, m::Integer)\n d = Dict(zero(n)=>0, one(n)=>1)\n fib_n_mod_m(n, m, d)\nend\n\nfunction fib_n_mod_m(n, m, d)\n if haskey(d, n)\n return d[n]\n end\n if n < 0\n result = iseven(n) ? mod(-fib_n_mod_m(-n, m, d), m) : fib_n_mod_m(-n, m, d)\n d[n] = result\n return result\n end\n n2 = n ÷ 2\n result = if iseven(n)\n mod((2 * fib_n_mod_m(n2 - 1, m, d) + fib_n_mod_m(n2, m, d)) * fib_n_mod_m(n2, m, d), m)\n else\n mod(fib_n_mod_m(n2, m, d) ^ 2 + fib_n_mod_m(n2 + 1, m, d) ^ 2, m)\n end\n d[n] = result\n return result\nend",
"execution_count": 7,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 7,
"data": {
"text/plain": "fib_n_mod_m (generic function with 2 methods)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:31:14.331Z",
"end_time": "2024-03-14T20:31:15.688000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "fib_n_mod_m(2024, 13)",
"execution_count": 8,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 8,
"data": {
"text/plain": "8"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:31:39.712Z",
"end_time": "2024-03-14T20:31:42.188000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@btime fib_n_mod_m(2024, 13)",
"execution_count": 9,
"outputs": [
{
"output_type": "stream",
"text": " 1.190 μs (7 allocations: 1.78 KiB)\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 9,
"data": {
"text/plain": "8"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### 参考"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:34:55.708Z",
"end_time": "2024-03-14T20:34:56.957000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "for n=0:100\n println(n, \": \", fib_n_mod_m(n, 13))\nend",
"execution_count": 11,
"outputs": [
{
"output_type": "stream",
"text": "0: 0\n1: 1\n2: 1\n3: 2\n4: 3\n5: 5\n6: 8\n7: 0\n8: 8\n9: 8\n10: 3\n11: 11\n12: 1\n13: 12\n14: 0\n15: 12\n16: 12\n17: 11\n18: 10\n19: 8\n20: 5\n21: 0\n22: 5\n23: 5\n24: 10\n25: 2\n26: 12\n27: 1\n28: 0\n29: 1\n30: 1\n31: 2\n32: 3\n33: 5\n34: 8\n35: 0\n36: 8\n37: 8\n38: 3\n39: 11\n40: 1\n41: 12\n42: 0\n43: 12\n44: 12\n45: 11\n46: 10\n47: 8\n48: 5\n49: 0\n50: 5\n51: 5\n52: 10\n53: 2\n54: 12\n55: 1\n56: 0\n57: 1\n58: 1\n59: 2\n60: 3\n61: 5\n62: 8\n63: 0\n64: 8\n65: 8\n66: 3\n67: 11\n68: 1\n69: 12\n70: 0\n71: 12\n72: 12\n73: 11\n74: 10\n75: 8\n76: 5\n77: 0\n78: 5\n79: 5\n80: 10\n81: 2\n82: 12\n83: 1\n84: 0\n85: 1\n86: 1\n87: 2\n88: 3\n89: 5\n90: 8\n91: 0\n92: 8\n93: 8\n94: 3\n95: 11\n96: 1\n97: 12\n98: 0\n99: 12\n100: 12\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "↑28周期→2024%28で計算してもOK"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:36:44.631Z",
"end_time": "2024-03-14T20:36:45.979000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "fib_n(2024 % 28) % 13 == fib_n_mod_m(2024 % 28, 13) == 8",
"execution_count": 12,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 12,
"data": {
"text/plain": "true"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:37:14.957Z",
"end_time": "2024-03-14T20:37:17.884000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@btime fib_n(2024 % 28) % 13",
"execution_count": 13,
"outputs": [
{
"output_type": "stream",
"text": " 975.231 ns (33 allocations: 1.05 KiB)\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 13,
"data": {
"text/plain": "8"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2024-03-14T11:37:26.748Z",
"end_time": "2024-03-14T20:37:29.502000+09:00"
}
},
"cell_type": "code",
"source": "@btime fib_n_mod_m(2024 % 28, 13)",
"execution_count": 14,
"outputs": [
{
"output_type": "stream",
"text": " 279.061 ns (4 allocations: 544 bytes)\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 14,
"data": {
"text/plain": "8"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### 参考2"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:52:40.360Z",
"end_time": "2024-03-14T20:52:41.595000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "# 周期を探すところから始めるパターン\nfunction fib_n_mod_m_v2(n, m)\n n₂ = 0\n n₁ = 1\n lst = [n₂, n₁]\n sizehint!(lst, m * m) # 周期は m^2 よりは小さいと期待\n for p=2:m*m\n f = mod(n₂ + n₁, m)\n if n₁ == 0 && f == 1\n # p-1 が周期\n return lst[mod(n, p - 1) + 1]\n end\n push!(lst, f)\n n₂, n₁ = n₁, f\n end\nend",
"execution_count": 17,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 17,
"data": {
"text/plain": "fib_n_mod_m_v2 (generic function with 1 method)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:52:40.682Z",
"end_time": "2024-03-14T20:52:41.934000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "fib_n_mod_m_v2(2024, 13)",
"execution_count": 18,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 18,
"data": {
"text/plain": "8"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2024-03-14T11:58:35.053Z",
"end_time": "2024-03-14T20:58:36.393000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "all(fib_n(2024) % M == fib_n_mod_m(2024, M) == fib_n_mod_m_v2(2024, M) for M=2:2024)",
"execution_count": 21,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 21,
"data": {
"text/plain": "true"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2024-03-14T11:53:05.956Z",
"end_time": "2024-03-14T20:53:08.653000+09:00"
}
},
"cell_type": "code",
"source": "@btime fib_n_mod_m_v2(2024, 13)",
"execution_count": 19,
"outputs": [
{
"output_type": "stream",
"text": " 332.595 ns (2 allocations: 1.41 KiB)\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 19,
"data": {
"text/plain": "8"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "",
"execution_count": null,
"outputs": []
}
],
"metadata": {
"kernelspec": {
"name": "julia-1.10",
"display_name": "Julia 1.10.2",
"language": "julia"
},
"language_info": {
"file_extension": ".jl",
"name": "julia",
"mimetype": "application/julia",
"version": "1.10.2"
},
"gist": {
"id": "",
"data": {
"description": "fib_n_mod_m.jl",
"public": true
}
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Raw
Project.toml
[deps]
BenchmarkTools = "6e4b80f9-dd63-53aa-95a3-0cdb28fa8baf"
[compat]
julia = "1.6"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment