Skip to content

Instantly share code, notes, and snippets.

@antimon2

antimon2/IterationProtocolSample.jl.ipynb

Last active February 13, 2021 05:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save antimon2/87de53d948babc1b8e6c9e6f0513cdb4 to your computer and use it in GitHub Desktop.
Save antimon2/87de53d948babc1b8e6c9e6f0513cdb4 to your computer and use it in GitHub Desktop.
Download ZIP
IterationProtocolSample.jl
Display the source blob
Display the rendered blob
Raw
IterationProtocolSample.jl.ipynb
{
"cells": [
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:29:44.393Z",
"end_time": "2021-02-13T00:29:43.009000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "versioninfo()",
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"text": "Julia Version 1.6.0-rc1\nCommit a58bdd9010 (2021-02-06 15:49 UTC)\nPlatform Info:\n OS: Linux (x86_64-linux-gnu)\n CPU: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz\n WORD_SIZE: 64\n LIBM: libopenlibm\n LLVM: libLLVM-11.0.1 (ORCJIT, skylake)\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## Lv. 1"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:29:48.432Z",
"end_time": "2021-02-13T00:29:45.684000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "struct Squares\n count::Int\nend",
"execution_count": 2,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:30:02.314Z",
"end_time": "2021-02-13T00:29:59.569000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.iterate(sq::Squares, state::Int = 1)\n if state > sq.count\n return nothing\n end\n (state ^ 2, state + 1)\nend",
"execution_count": 3,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:30:19.621Z",
"end_time": "2021-02-13T00:30:16.953000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "for n in Squares(10)\n println(n)\nend",
"execution_count": 4,
"outputs": [
{
"output_type": "stream",
"text": "1\n4\n9\n16\n25\n36\n49\n64\n81\n100\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:30:30.570Z",
"end_time": "2021-02-13T00:30:28.326000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "225 ∈ Squares(20)",
"execution_count": 5,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 5,
"data": {
"text/plain": "true"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:30:37.131Z",
"end_time": "2021-02-13T00:30:34.384000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "50 ∉ Squares(10)",
"execution_count": 6,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 6,
"data": {
"text/plain": "true"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:30:47.809Z",
"end_time": "2021-02-13T00:30:45.402000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using Statistics",
"execution_count": 7,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:30:52.717Z",
"end_time": "2021-02-13T00:30:50.247000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "mean(Squares(100))",
"execution_count": 8,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 8,
"data": {
"text/plain": "3383.5"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:30:57.813Z",
"end_time": "2021-02-13T00:30:55.087000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "std(Squares(100))",
"execution_count": 9,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 9,
"data": {
"text/plain": "3024.355854282583"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## Lv. 2"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "```julia\ncollect(Squares(7))\n# @> ERROR: MethodError: no method matching length(::Squares)\n# Closest candidates are:\n# length(::Core.MethodTable) at reflection.jl:957\n# length(::CompositeException) at task.jl:41\n# length(::Cmd) at process.jl:638\n# ...\n```"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:34:17.002Z",
"end_time": "2021-02-13T00:34:14.461000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.IteratorSize(Squares)",
"execution_count": 10,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 10,
"data": {
"text/plain": "Base.HasLength()"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:34:44.590Z",
"end_time": "2021-02-13T00:34:41.833000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.length(sq::Squares) = sq.count",
"execution_count": 11,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:34:55.606Z",
"end_time": "2021-02-13T00:34:54.015000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(Squares(7))",
"execution_count": 12,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 12,
"data": {
"text/plain": "7-element Vector{Any}:\n 1\n 4\n 9\n 16\n 25\n 36\n 49"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:36:32.350Z",
"end_time": "2021-02-13T00:36:29.747000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.IteratorEltype(Squares)",
"execution_count": 13,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 13,
"data": {
"text/plain": "Base.HasEltype()"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:37:19.352Z",
"end_time": "2021-02-13T00:37:16.967000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "eltype(Squares(7))",
"execution_count": 14,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 14,
"data": {
"text/plain": "Any"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:37:24.008Z",
"end_time": "2021-02-13T00:37:21.246000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.eltype(::Type{Squares}) = Int",
"execution_count": 15,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:37:25.394Z",
"end_time": "2021-02-13T00:37:22.628000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "eltype(Squares(7))",
"execution_count": 16,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 16,
"data": {
"text/plain": "Int64"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-12T15:37:31.359Z",
"end_time": "2021-02-13T00:37:29.074000+09:00"
},
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "collect(Squares(7))",
"execution_count": 17,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 17,
"data": {
"text/plain": "7-element Vector{Int64}:\n 1\n 4\n 9\n 16\n 25\n 36\n 49"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "## Lv.3"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "original: [Julia で遊ぼう フィボナッチ数列 - Qiita](https://qiita.com/antimon2/items/ff31a74758eb4b63604e)"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### 1. 一般項を求めるアルゴリズム"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:06:32.424Z",
"end_time": "2021-02-13T13:06:31.424000+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": 18,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 18,
"data": {
"text/plain": "fib_n (generic function with 2 methods)"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### Fib の定義"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:06:43.066Z",
"end_time": "2021-02-13T13:06:41.957000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "struct FibType end\nconst Fib = FibType()",
"execution_count": 19,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 19,
"data": {
"text/plain": "FibType()"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### `Fib[n]` の実装"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:06:52.846Z",
"end_time": "2021-02-13T13:06:51.553000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.getindex(::FibType, index::Integer) = fib_n(index)",
"execution_count": 20,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:07:11.987Z",
"end_time": "2021-02-13T13:07:11.006000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": " Fib[5000]",
"execution_count": 21,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 21,
"data": {
"text/plain": "3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### `Fib[n:m]` の実装"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:07:27.567Z",
"end_time": "2021-02-13T13:07:26.286000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "struct FibRange{R<:AbstractRange{<:Integer}}\n range::R\nend\n\nBase.getindex(::FibType, r::AbstractRange{<:Integer}) = FibRange(r)",
"execution_count": 22,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:07:35.914Z",
"end_time": "2021-02-13T13:07:34.850000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Fib[1:10]",
"execution_count": 23,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 23,
"data": {
"text/plain": "FibRange{UnitRange{Int64}}(1:10)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:08:22.003Z",
"end_time": "2021-02-13T13:08:20.713000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "# IteratorEltype\nBase.IteratorEltype(::Type{<:FibRange}) = Base.HasEltype()\n# Base.eltype(fr::FibRange) = BigInt\nBase.eltype(::Type{<:FibRange}) = BigInt",
"execution_count": 24,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:08:22.671Z",
"end_time": "2021-02-13T13:08:21.381000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "# IteratorSize\nBase.IteratorSize(::Type{<:FibRange}) = Base.HasShape{1}()\nBase.length(fr::FibRange) = length(fr.range)\nBase.size(fr::FibRange) = size(fr.range)",
"execution_count": 25,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:08:23.433Z",
"end_time": "2021-02-13T13:08:22.143000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "# iterate\nfunction Base.iterate(fr::FibRange{<:UnitRange})\n index = fr.range.start\n start = Fib[index]\n prev = Fib[index - 1]\n len = length(fr)\n iterate(fr, (start, prev, len))\nend\nfunction Base.iterate(fr::FibRange{<:UnitRange}, (current, prev, len)::Tuple{BigInt, BigInt, Int})\n len <= 0 && return nothing\n (current, (current + prev, current, len - 1))\nend",
"execution_count": 26,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:08:45.030Z",
"end_time": "2021-02-13T13:08:43.775000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "fib_1_10 = Fib[1:10];\nfor v in fib_1_10\n println(v)\nend",
"execution_count": 27,
"outputs": [
{
"output_type": "stream",
"text": "1\n1\n2\n3\n5\n8\n13\n21\n34\n55\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:08:56.282Z",
"end_time": "2021-02-13T13:08:55.532000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(fib_1_10)",
"execution_count": 28,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 28,
"data": {
"text/plain": "10-element Vector{BigInt}:\n 1\n 1\n 2\n 3\n 5\n 8\n 13\n 21\n 34\n 55"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:09:06.396Z",
"end_time": "2021-02-13T13:09:05.114000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "sum(fib_1_10)",
"execution_count": 29,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 29,
"data": {
"text/plain": "143"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:09:22.060Z",
"end_time": "2021-02-13T13:09:20.760000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(Fib[-5:5])",
"execution_count": 30,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 30,
"data": {
"text/plain": "11-element Vector{BigInt}:\n 5\n -3\n 2\n -1\n 1\n 0\n 1\n 1\n 2\n 3\n 5"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:09:47.615Z",
"end_time": "2021-02-13T13:09:46.379000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(Fib[1:100]) == [Fib[n] for n=1:100]",
"execution_count": 31,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 31,
"data": {
"text/plain": "true"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:09:56.355Z",
"end_time": "2021-02-13T13:09:55.140000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time [Fib[n] for n=1:100];",
"execution_count": 32,
"outputs": [
{
"output_type": "stream",
"text": " 0.035689 seconds (45.10 k allocations: 2.482 MiB, 106.13% compilation time)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:10:05.567Z",
"end_time": "2021-02-13T13:10:04.341000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time collect(Fib[1:100]);",
"execution_count": 33,
"outputs": [
{
"output_type": "stream",
"text": " 0.000019 seconds (309 allocations: 11.492 KiB)\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### `Fib[n:s:m]` の実装"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:10:29.762Z",
"end_time": "2021-02-13T13:10:28.476000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.iterate(fr::FibRange{<:StepRange})\n n = fr.range.start\n m = oftype(n, fr.range.step)\n d = Dict(zero(n)=>big\"0\", one(n)=>big\"1\")\n fₙ = fib_n(n, d)\n fₙ₋₁ = fib_n(n - one(n), d)\n fₘ = fib_n(m, d)\n fₘ₋₁ = fib_n(m - one(n), d)\n len = length(fr)\n iterate(fr, (fₙ, fₙ₋₁, fₘ, fₘ₋₁, len))\nend\n\nfunction Base.iterate(fr::FibRange{<:StepRange}, (fₙ, fₙ₋₁, fₘ, fₘ₋₁, len)::Tuple{BigInt, BigInt, BigInt, BigInt, Int})\n len <= 0 && return nothing\n fₙ₊ₘ = fₙ * fₘ + fₙ₋₁ * fₘ + fₙ * fₘ₋₁\n fₙ₊ₘ₋₁ = fₙ * fₘ + fₙ₋₁ * fₘ₋₁\n (fₙ, (fₙ₊ₘ, fₙ₊ₘ₋₁, fₘ, fₘ₋₁, len - 1))\nend",
"execution_count": 34,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:10:38.147Z",
"end_time": "2021-02-13T13:10:37.047000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "fr2 = Fib[0:2:20]",
"execution_count": 35,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 35,
"data": {
"text/plain": "FibRange{StepRange{Int64, Int64}}(0:2:20)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:10:50.680Z",
"end_time": "2021-02-13T13:10:49.432000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "for v in fr2\n println(v)\nend",
"execution_count": 36,
"outputs": [
{
"output_type": "stream",
"text": "0\n1\n3\n8\n21\n55\n144\n377\n987\n2584\n6765\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:10:59.453Z",
"end_time": "2021-02-13T13:10:58.169000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(Fib[10:-1:1])",
"execution_count": 37,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 37,
"data": {
"text/plain": "10-element Vector{BigInt}:\n 55\n 34\n 21\n 13\n 8\n 5\n 3\n 2\n 1\n 1"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:11:11.710Z",
"end_time": "2021-02-13T13:11:10.447000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "sum(Fib[1:2:19]) == Fib[20] # F_1 + F_3 + … + F_19 == F_20",
"execution_count": 38,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 38,
"data": {
"text/plain": "true"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:11:18.355Z",
"end_time": "2021-02-13T13:11:17.057000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(Fib[0:10:100])",
"execution_count": 39,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 39,
"data": {
"text/plain": "11-element Vector{BigInt}:\n 0\n 55\n 6765\n 832040\n 102334155\n 12586269025\n 1548008755920\n 190392490709135\n 23416728348467685\n 2880067194370816120\n 354224848179261915075"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:11:28.737Z",
"end_time": "2021-02-13T13:11:27.493000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(Fib[0:10:1000]) == [Fib[n] for n=0:10:1000]",
"execution_count": 40,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 40,
"data": {
"text/plain": "true"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:11:37.012Z",
"end_time": "2021-02-13T13:11:35.734000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time [Fib[n] for n=0:10:1000];",
"execution_count": 41,
"outputs": [
{
"output_type": "stream",
"text": " 0.021909 seconds (51.69 k allocations: 2.574 MiB, 96.91% compilation time)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:11:44.162Z",
"end_time": "2021-02-13T13:11:42.901000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time collect(Fib[0:10:1000]);",
"execution_count": 42,
"outputs": [
{
"output_type": "stream",
"text": " 0.000135 seconds (2.06 k allocations: 68.852 KiB)\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "### 無限列挙"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:11:56.741Z",
"end_time": "2021-02-13T13:11:55.440000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "struct EndOfFib end\nBase.lastindex(::FibType) = EndOfFib()",
"execution_count": 43,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:12:17.174Z",
"end_time": "2021-02-13T13:12:15.888000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "abstract type AbstractSequence{I<:Integer} end\n\nstruct UnitSequence{I<:Integer} <: AbstractSequence{I}\n start::I\nend\n\nstruct StepSequence{I<:Integer} <: AbstractSequence{I}\n start::I\n step::I\nend",
"execution_count": 44,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:12:17.968Z",
"end_time": "2021-02-13T13:12:16.660000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.:(:)(start::Integer, ::EndOfFib) = UnitSequence(start)\nBase.:(:)(start::I, step::I, ::EndOfFib) where {I<:Integer} = StepSequence(start, step)\nBase.:(:)(start::Integer, step::Integer, ::EndOfFib) = StepSequence(promote(start, step)...)",
"execution_count": 45,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:12:58.434Z",
"end_time": "2021-02-13T13:12:57.132000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "struct FibSequence{S<:AbstractSequence}\n sequence::S\nend\n\nBase.getindex(::FibType, s::AbstractSequence) = FibSequence(s)",
"execution_count": 46,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:13:00.673Z",
"end_time": "2021-02-13T13:12:59.365000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.IteratorEltype(::Type{<:FibSequence}) = Base.HasEltype()\n# Base.eltype(fr::FibSequence) = BigInt\nBase.eltype(::Type{<:FibSequence}) = BigInt",
"execution_count": 47,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:13:01.176Z",
"end_time": "2021-02-13T13:12:59.868000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Base.IteratorSize(::Type{<:FibSequence}) = Base.IsInfinite()",
"execution_count": 48,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:13:15.623Z",
"end_time": "2021-02-13T13:13:14.328000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.iterate(fr::FibSequence{<:UnitSequence})\n index = fr.sequence.start\n start = Fib[index]\n prev = Fib[index - 1]\n iterate(fr, (start, prev))\nend\nfunction Base.iterate(fr::FibSequence{<:UnitSequence}, (current, prev)::Tuple{BigInt, BigInt})\n (current, (current + prev, current))\nend",
"execution_count": 49,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:13:16.272Z",
"end_time": "2021-02-13T13:13:14.970000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function Base.iterate(fr::FibSequence{<:StepSequence})\n n = fr.sequence.start\n m = oftype(n, fr.sequence.step)\n d = Dict(zero(n)=>big\"0\", one(n)=>big\"1\")\n fₙ = fib_n(n, d)\n fₙ₋₁ = fib_n(n - one(n), d)\n fₘ = fib_n(m, d)\n fₘ₋₁ = fib_n(m - one(n), d)\n iterate(fr, (fₙ, fₙ₋₁, fₘ, fₘ₋₁))\nend\nfunction Base.iterate(fr::FibSequence{<:StepSequence}, (fₙ, fₙ₋₁, fₘ, fₘ₋₁)::Tuple{BigInt, BigInt, BigInt, BigInt})\n fₙ₊ₘ = fₙ * fₘ + fₙ₋₁ * fₘ + fₙ * fₘ₋₁\n fₙ₊ₘ₋₁ = fₙ * fₘ + fₙ₋₁ * fₘ₋₁\n (fₙ, (fₙ₊ₘ, fₙ₊ₘ₋₁, fₘ, fₘ₋₁))\nend",
"execution_count": 50,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:13:24.269Z",
"end_time": "2021-02-13T13:13:23.220000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "fibseq1 = Fib[0:end]",
"execution_count": 51,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 51,
"data": {
"text/plain": "FibSequence{UnitSequence{Int64}}(UnitSequence{Int64}(0))"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:14:28.762Z",
"end_time": "2021-02-13T13:14:27.463000+09:00"
},
"trusted": true,
"scrolled": true
},
"cell_type": "code",
"source": "# for v in fibseq1\n# println(v)\n# end\ncnt = 0\nfor v in fibseq1\n println(v)\n cnt += 1\n cnt > 100 && break\nend",
"execution_count": 53,
"outputs": [
{
"output_type": "stream",
"text": "0\n1\n1\n2\n3\n5\n8\n13\n21\n34\n55\n89\n144\n233\n377\n610\n987\n1597\n2584\n4181\n6765\n10946\n17711\n28657\n46368\n75025\n121393\n196418\n317811\n514229\n832040\n1346269\n2178309\n3524578\n5702887\n9227465\n14930352\n24157817\n39088169\n63245986\n102334155\n165580141\n267914296\n433494437\n701408733\n1134903170\n1836311903\n2971215073\n4807526976\n7778742049\n12586269025\n20365011074\n32951280099\n53316291173\n86267571272\n139583862445\n225851433717\n365435296162\n591286729879\n956722026041\n1548008755920\n2504730781961\n4052739537881\n6557470319842\n10610209857723\n17167680177565\n27777890035288\n44945570212853\n72723460248141\n117669030460994\n190392490709135\n308061521170129\n498454011879264\n806515533049393\n1304969544928657\n2111485077978050\n3416454622906707\n5527939700884757\n8944394323791464\n14472334024676221\n23416728348467685\n37889062373143906\n61305790721611591\n99194853094755497\n160500643816367088\n259695496911122585\n420196140727489673\n679891637638612258\n1100087778366101931\n1779979416004714189\n2880067194370816120\n4660046610375530309\n7540113804746346429\n12200160415121876738\n19740274219868223167\n31940434634990099905\n51680708854858323072\n83621143489848422977\n135301852344706746049\n218922995834555169026\n354224848179261915075\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:14:45.495Z",
"end_time": "2021-02-13T13:14:44.205000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(Iterators.take(fibseq1, 21))",
"execution_count": 54,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 54,
"data": {
"text/plain": "21-element Vector{BigInt}:\n 0\n 1\n 1\n 2\n 3\n 5\n 8\n 13\n 21\n 34\n 55\n 89\n 144\n 233\n 377\n 610\n 987\n 1597\n 2584\n 4181\n 6765"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2021-02-13T04:14:55.463Z",
"end_time": "2021-02-13T13:14:54.203000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "collect(Iterators.take(Fib[0:-1:end], 21))",
"execution_count": 55,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 55,
"data": {
"text/plain": "21-element Vector{BigInt}:\n 0\n 1\n -1\n 2\n -3\n 5\n -8\n 13\n -21\n 34\n -55\n 89\n -144\n 233\n -377\n 610\n -987\n 1597\n -2584\n 4181\n -6765"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "",
"execution_count": null,
"outputs": []
}
],
"metadata": {
"kernelspec": {
"name": "julia-1.6",
"display_name": "Julia 1.6.0-rc1",
"language": "julia"
},
"language_info": {
"file_extension": ".jl",
"name": "julia",
"mimetype": "application/julia",
"version": "1.6.0"
},
"gist": {
"id": "",
"data": {
"description": "IterationProtocolSample.jl",
"public": true
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Raw
Project.toml
[compat]
julia = "1.5"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment