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]:

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)

Iteration protocol (https://docs.julialang.org/en/v1/base/collections/#lib-collections-iteration-1)

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

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]:

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

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(○)) に変換されて評価される
　↓

Base.lastindex(○) を実装（多重定義）して適切なオブジェクト（＝ □ ）を返すようにする
△:□ を実装（多重定義）して適切なオブジェクト（＝ ▼ ）を返すようにする
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

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 [ ]:

struct FibType¶