In [1]:
versioninfo()
Julia Version 1.2.0
Commit c6da87ff4b (2019-08-20 00:03 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

※一般項を求める関数は、一番成績の良かった fib4 を採用(リファイン)

In [2]:
function fib_n(n::Integer)
    d = Dict(zero(n)=>big"0", one(n)=>big"1")
    fib_n(n, d)
end
function fib_n(n, d)
    if haskey(d, n)
        return d[n]
    end
    if n < 0
        result = iseven(n) ? -fib_n(-n, d) : fib_n(-n, d)
        d[n] = result
        return result
    end
    m = n ÷ 2
    result = if iseven(n)
        (2 * fib_n(m - 1, d) + fib_n(m, d)) * fib_n(m, d)
    else
        fib_n(m, d) ^ 2 + fib_n(m + 1, d) ^ 2
    end
    d[n] = result
    return result
end
Out[2]:
fib_n (generic function with 2 methods)

struct FibType

In [3]:
struct FibType end
const Fib = FibType()
Out[3]:
FibType()
In [4]:
Base.getindex(::FibType, index::Integer) = fib_n(index)
In [5]:
Fib[10]
Out[5]:
55
In [6]:
[Fib[n] for n=1:10]
Out[6]:
10-element Array{BigInt,1}:
  1
  1
  2
  3
  5
  8
 13
 21
 34
 55
In [7]:
Fib[5000]
Out[7]:
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

範囲指定

仕様:

julia> fib_1_10 = Fib[1:10]
# => 《何らかのオブジェクト》

julia> for v in fib_1_10
           println(v)
       end
# => 1
#    1
#    2
#    3
#    5
#    8
#    13
#    21
#    34
#    55

julia> sum(fib_1_10)
# => 143

julia> collect(Fib[-5:5])
# => BigInt[5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5]
In [8]:
struct FibRange{R<:AbstractRange{<:Integer}}
    range::R
end
In [9]:
Base.getindex(::FibType, r::AbstractRange{<:Integer}) = FibRange(r)
In [10]:
Fib[1:10]
Out[10]:
FibRange{UnitRange{Int64}}(1:10)
In [11]:
Base.IteratorEltype(::Type{<:FibRange}) = Base.HasEltype()
In [12]:
# Base.eltype(fr::FibRange) = BigInt
Base.eltype(::Type{<:FibRange}) = BigInt
In [13]:
Base.IteratorSize(::Type{<:FibRange}) = Base.HasShape{1}()
In [14]:
Base.length(fr::FibRange) = length(fr.range)
In [15]:
Base.size(fr::FibRange) = size(fr.range)
In [16]:
function Base.iterate(fr::FibRange{<:UnitRange})
    index = fr.range.start
    start = Fib[index]
    prev = Fib[index - 1]
    len = length(fr)
    iterate(fr, (start, prev, len))
end
function Base.iterate(fr::FibRange{<:UnitRange}, (current, prev, len)::Tuple{BigInt, BigInt, Int})
    len <= 0 && return nothing
    (current, (current + prev, current, len - 1))
end

※↑ len <= 0 && return nothing は「全部列挙し終わったらイテレーション終了」という意味

※確認

In [17]:
fib_1_10 = Fib[1:10]
Out[17]:
FibRange{UnitRange{Int64}}(1:10)
In [18]:
for v in fib_1_10
    println(v)
end
1
1
2
3
5
8
13
21
34
55
In [19]:
collect(fib_1_10)
Out[19]:
10-element Array{BigInt,1}:
  1
  1
  2
  3
  5
  8
 13
 21
 34
 55
In [20]:
collect(fib_1_10) == [Fib[n] for n=1:10]
Out[20]:
true
In [21]:
sum(fib_1_10)
Out[21]:
143
In [22]:
print(collect(Fib[-5:5]))
BigInt[5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5]

Performance

In [23]:
@time [Fib[n] for n=1:100]
  0.038797 seconds (57.95 k allocations: 2.765 MiB)
Out[23]:
100-element Array{BigInt,1}:
                     1
                     1
                     2
                     3
                     5
                     8
                    13
                    21
                    34
                    55
                    89
                   144
                   233
                     ⋮
   1779979416004714189
   2880067194370816120
   4660046610375530309
   7540113804746346429
  12200160415121876738
  19740274219868223167
  31940434634990099905
  51680708854858323072
  83621143489848422977
 135301852344706746049
 218922995834555169026
 354224848179261915075
In [24]:
@time collect(Fib[1:100])
  0.000055 seconds (315 allocations: 7.023 KiB)
Out[24]:
100-element Array{BigInt,1}:
                     1
                     1
                     2
                     3
                     5
                     8
                    13
                    21
                    34
                    55
                    89
                   144
                   233
                     ⋮
   1779979416004714189
   2880067194370816120
   4660046610375530309
   7540113804746346429
  12200160415121876738
  19740274219868223167
  31940434634990099905
  51680708854858323072
  83621143489848422977
 135301852344706746049
 218922995834555169026
 354224848179261915075

仕様2:

julia> fr2 = Fib[0:2:20]
# => 《何らかのオブジェクト》

julia> for v in fr2
           println(v)
       end
# => 0
#    1
#    3
#    8
#    21
#    55
#    144
#    377
#    987
#    2584
#    6765

julia> collecr(Fib[10:-1:1])
# => BigInt[55, 34, 21, 13, 8, 5, 3, 2, 1, 1]

julia> sum(Fib[1:2:19]) == Fib[20]
# => true

参考:

$$ \begin{eqnarray*} F_{n+m−1} &=& F_nF_m + F_{n−1}F_{m−1} \\ F_{n+m} &=& F_n F_m + F_{n−1} F_m + F_n F_{m−1} \end{eqnarray*} $$
In [25]:
function Base.iterate(fr::FibRange{<:StepRange})
    n = fr.range.start
    m = oftype(n, fr.range.step)
    d = Dict(zero(n)=>big"0", one(n)=>big"1")
    fₙ = fib_n(n, d)
    fₙ₋₁ = fib_n(n - one(n), d)
    fₘ = fib_n(m, d)
    fₘ₋₁ = fib_n(m - one(n), d)
    len = length(fr)
    iterate(fr, (fₙ, fₙ₋₁, fₘ, fₘ₋₁, len))
end

function Base.iterate(fr::FibRange{<:StepRange}, (fₙ, fₙ₋₁, fₘ, fₘ₋₁, len)::Tuple{BigInt, BigInt, BigInt, BigInt, Int})
    len <= 0 && return nothing
    fₙ₊ₘ = fₙ * fₘ + fₙ₋₁ * fₘ + fₙ * fₘ₋₁
    fₙ₊ₘ₋₁ = fₙ * fₘ + fₙ₋₁ * fₘ₋₁
    (fₙ, (fₙ₊ₘ, fₙ₊ₘ₋₁, fₘ, fₘ₋₁, len - 1))
end
In [26]:
fr2 = Fib[0:2:20]
Out[26]:
FibRange{StepRange{Int64,Int64}}(0:2:20)
In [27]:
for v in fr2
    println(v)
end
0
1
3
8
21
55
144
377
987
2584
6765
In [28]:
collect(Fib[10:-1:1])
Out[28]:
10-element Array{BigInt,1}:
 55
 34
 21
 13
  8
  5
  3
  2
  1
  1
In [29]:
sum(Fib[1:2:19]) == Fib[20]
Out[29]:
true
In [30]:
collect(Fib[0:10:100])
Out[30]:
11-element Array{BigInt,1}:
                     0
                    55
                  6765
                832040
             102334155
           12586269025
         1548008755920
       190392490709135
     23416728348467685
   2880067194370816120
 354224848179261915075

Performance

In [31]:
collect(Fib[0:10:1000]) == [Fib[n] for n=0:10:1000]
Out[31]:
true
In [32]:
@time [Fib[n] for n=0:10:1000]
  0.040208 seconds (65.97 k allocations: 2.922 MiB, 15.54% gc time)
Out[32]:
101-element Array{BigInt,1}:
                                                                                                                                                                                                                 0
                                                                                                                                                                                                                55
                                                                                                                                                                                                              6765
                                                                                                                                                                                                            832040
                                                                                                                                                                                                         102334155
                                                                                                                                                                                                       12586269025
                                                                                                                                                                                                     1548008755920
                                                                                                                                                                                                   190392490709135
                                                                                                                                                                                                 23416728348467685
                                                                                                                                                                                               2880067194370816120
                                                                                                                                                                                             354224848179261915075
                                                                                                                                                                                           43566776258854844738105
                                                                                                                                                                                         5358359254990966640871840
                                                                                                                                                                                                                 ⋮
                        446184850393440287353551321079998010096266511882573834391947602833382607375990863441330685129004358886041832982707488151056879493596639158471653309720606784970791309358613512937906236145
                      54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800
                    6749438202405646566036528344330116878577367608510319331278487323923063395123537981035948334462494041348222696506072562356190473002473827542549247906420341256327639978792400829342400405236255
                  830126021787055047622441572678655992350572415327460154154529445889109757788994107326186690751365241695215886721154737728593181500199549345260535478509541567521282541694147401525840003191120565
               102098751241605365210994276911130356942241829717669088641675843357036577144651151663139927014083462234470205844005526668054605134051542095639503314608767192463861424988401337986848977992102593240
             12557316276695672865904673618496355247903394482857970442771974203469609879034302660458884836041514489598140102925958625432987838306839478214313647161399855131487433991031670424980898453025427847955
           1544447803282326157141063860798140565135175279561812695372311151183404978544074576084779694906092198758336762454048905401589449506607204278264939097537573413980490519471907060934663660744135522705225
         189954522487449421655484950204552793156378655991620103560351499621355342751042138555767443588613298932785823641745089405770069301474379286748373195349960130064468846461053536824538649373075643864894720
       23362861818152996537467507811299195417669439511689710925227862142275523753399638967783310781704529676533897971172191948004316934631842045065771638088947558424515687624190113122357319209227560059859345335
     2873442049110331124686847975839596483580184681281842823699466692000268066325404550898791458706068536914736664630537864515125212890415097163803163111745199726085365108928922860513125724085616811718834581485
   353410009178752575339944833520459068284945046358154977604109175253890696634271360121583566110064725510836075851584985143412396868586425109102723291106570618750075392710633321729992106743321640281356794177320
 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
In [33]:
@time collect(Fib[0:10:1000])
  0.000431 seconds (2.38 k allocations: 70.695 KiB)
Out[33]:
101-element Array{BigInt,1}:
                                                                                                                                                                                                                 0
                                                                                                                                                                                                                55
                                                                                                                                                                                                              6765
                                                                                                                                                                                                            832040
                                                                                                                                                                                                         102334155
                                                                                                                                                                                                       12586269025
                                                                                                                                                                                                     1548008755920
                                                                                                                                                                                                   190392490709135
                                                                                                                                                                                                 23416728348467685
                                                                                                                                                                                               2880067194370816120
                                                                                                                                                                                             354224848179261915075
                                                                                                                                                                                           43566776258854844738105
                                                                                                                                                                                         5358359254990966640871840
                                                                                                                                                                                                                 ⋮
                        446184850393440287353551321079998010096266511882573834391947602833382607375990863441330685129004358886041832982707488151056879493596639158471653309720606784970791309358613512937906236145
                      54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800
                    6749438202405646566036528344330116878577367608510319331278487323923063395123537981035948334462494041348222696506072562356190473002473827542549247906420341256327639978792400829342400405236255
                  830126021787055047622441572678655992350572415327460154154529445889109757788994107326186690751365241695215886721154737728593181500199549345260535478509541567521282541694147401525840003191120565
               102098751241605365210994276911130356942241829717669088641675843357036577144651151663139927014083462234470205844005526668054605134051542095639503314608767192463861424988401337986848977992102593240
             12557316276695672865904673618496355247903394482857970442771974203469609879034302660458884836041514489598140102925958625432987838306839478214313647161399855131487433991031670424980898453025427847955
           1544447803282326157141063860798140565135175279561812695372311151183404978544074576084779694906092198758336762454048905401589449506607204278264939097537573413980490519471907060934663660744135522705225
         189954522487449421655484950204552793156378655991620103560351499621355342751042138555767443588613298932785823641745089405770069301474379286748373195349960130064468846461053536824538649373075643864894720
       23362861818152996537467507811299195417669439511689710925227862142275523753399638967783310781704529676533897971172191948004316934631842045065771638088947558424515687624190113122357319209227560059859345335
     2873442049110331124686847975839596483580184681281842823699466692000268066325404550898791458706068536914736664630537864515125212890415097163803163111745199726085365108928922860513125724085616811718834581485
   353410009178752575339944833520459068284945046358154977604109175253890696634271360121583566110064725510836075851584985143412396868586425109102723291106570618750075392710633321729992106743321640281356794177320
 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

無限列

仕様:

julia> fibseq1 = Fib[0:end]
# => 《何らかのオブジェクト》

julia> for v in fibseq1
           println(v)
           v >= 1000 && break  # ←途中で break しない限り列挙し続ける!
       end
# => 0
#    1
#    1
#    2
#    3
#    5
#    8
#    13
#    21
#    34
#    55
#    89
#    144
#    233
#    377
#    610
#    987
#    1597

julia> collect(Iterators.take(Fib[0:-1:end], 21))
# => BigInt[0, 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, 89, -144, 233, -377, 610, -987, 1597, -2584, 4181, -6765]

Point: ○[△:end]getindex(○, △:lastindex(○)) に変換されて評価される
 ↓

  1. Base.lastindex(○) を実装(多重定義)して適切なオブジェクト(= )を返すようにする
  2. △:□ を実装(多重定義)して適切なオブジェクト(= )を返すようにする
  3. Base.getindex(○, ▼) を実装(多重定義)して適切なオブジェクト(無限列)を返すようにする

Point 1.(

In [34]:
struct EndOfFib end
In [35]:
Base.lastindex(::FibType) = EndOfFib()

Point 2.(

In [36]:
abstract type AbstractSequence{I<:Integer} end
In [37]:
struct UnitSequence{I<:Integer} <: AbstractSequence{I}
    start::I
end
In [38]:
struct StepSequence{I<:Integer} <: AbstractSequence{I}
    start::I
    step::I
end
In [39]:
Base.:(:)(start::Integer, ::EndOfFib) = UnitSequence(start)
Base.:(:)(start::I, step::I, ::EndOfFib) where {I<:Integer} = StepSequence(start, step)
Base.:(:)(start::Integer, step::Integer, ::EndOfFib) = StepSequence(promote(start, step)...)

Point 3.(無限列)

In [40]:
struct FibSequence{S<:AbstractSequence}
    sequence::S
end
In [41]:
Base.getindex(::FibType, s::AbstractSequence) = FibSequence(s)
In [42]:
Base.IteratorEltype(::Type{<:FibSequence}) = Base.HasEltype()
In [43]:
# Base.eltype(fr::FibSequence) = BigInt
Base.eltype(::Type{<:FibSequence}) = BigInt
In [44]:
Base.IteratorSize(::Type{<:FibSequence}) = Base.IsInfinite()

※↑ Base.length(::FibSequence)Base.size(::FibSequence) の実装不要(むしろ実装してはいけない)

In [45]:
function Base.iterate(fr::FibSequence{<:UnitSequence})
    index = fr.sequence.start
    start = Fib[index]
    prev = Fib[index - 1]
    iterate(fr, (start, prev))
end
function Base.iterate(fr::FibSequence{<:UnitSequence}, (current, prev)::Tuple{BigInt, BigInt})
    (current, (current + prev, current))
end

※↑無限列なので len <= 0 && return nothing がない(いらない)ことに注意

In [46]:
fibseq1 = Fib[0:end]
Out[46]:
FibSequence{UnitSequence{Int64}}(UnitSequence{Int64}(0))
In [47]:
for v in fibseq1
    println(v)
    v >= 1000 && break
end
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
In [48]:
collect(Iterators.take(fibseq1, 21))
Out[48]:
21-element Array{BigInt,1}:
    0
    1
    1
    2
    3
    5
    8
   13
   21
   34
   55
   89
  144
  233
  377
  610
  987
 1597
 2584
 4181
 6765
In [49]:
function Base.iterate(fr::FibSequence{<:StepSequence})
    n = fr.sequence.start
    m = oftype(n, fr.sequence.step)
    d = Dict(zero(n)=>big"0", one(n)=>big"1")
    fₙ = fib_n(n, d)
    fₙ₋₁ = fib_n(n - one(n), d)
    fₘ = fib_n(m, d)
    fₘ₋₁ = fib_n(m - one(n), d)
    iterate(fr, (fₙ, fₙ₋₁, fₘ, fₘ₋₁))
end
function Base.iterate(fr::FibSequence{<:StepSequence}, (fₙ, fₙ₋₁, fₘ, fₘ₋₁)::Tuple{BigInt, BigInt, BigInt, BigInt})
    fₙ₊ₘ = fₙ * fₘ + fₙ₋₁ * fₘ + fₙ * fₘ₋₁
    fₙ₊ₘ₋₁ = fₙ * fₘ + fₙ₋₁ * fₘ₋₁
    (fₙ, (fₙ₊ₘ, fₙ₊ₘ₋₁, fₘ, fₘ₋₁))
end
In [50]:
fibseq_m1 = Fib[0:-1:end]
Out[50]:
FibSequence{StepSequence{Int64}}(StepSequence{Int64}(0, -1))
In [51]:
collect(Iterators.take(fibseq_m1, 21))
Out[51]:
21-element Array{BigInt,1}:
     0
     1
    -1
     2
    -3
     5
    -8
    13
   -21
    34
   -55
    89
  -144
   233
  -377
   610
  -987
  1597
 -2584
  4181
 -6765
In [ ]: