# 如何以最快的速度计算第n个fibonacci数

``````function fibonacci(n::Int)
n < 2 && return n
x, y, bits = big(0), big(1), []
while n > 0
pushfirst!(bits, Bool(n&0x1))
n >>= 1
end
for bit ∈ bits[1:end-1]
u, v = x * (x + 2y), (x^2 + y^2)
x, y = bit ? (u + v, u) : (u, v)
end
u = x * (x + 2y)
bits[end] ? u + x^2 + y^2 : u
end

map(x->println(x, "\t=>\t", fibonacci(x)), 0:10)
@time fib = fibonacci(100000000)
@time len = ceil(Int, log10(fib))
println(len)
``````

``````function primeCount(maxn::Int)
mark_array = trues(maxn)
cnt = 1  # count for 2
for i in 3:2:maxn
if mark_array[i]
cnt += 1
j, delta = i^2, 2i
while j <= maxn
mark_array[j] = false
j += delta
end
end
end; cnt
end

@time println(primeCount(10^8))
``````
1赞

`map`的话会返回`nothing`，推荐直接写`foreach(x->println(x, "\t=>\t", fibonacci(x)), 0:10)`

``````julia> using Combinatorics

julia> @time fibonaccinum(100000000);
0.597373 seconds (683 allocations: 131.589 MiB, 1.73% gc time)

julia> @time fib = fibonacci(100000000);
0.844977 seconds (1.46 k allocations: 210.346 MiB, 1.34% gc time)
``````

`@inbounds` 可以加快速度

``````julia> function primeCount2(maxn::Int)
mark_array = trues(maxn)
cnt = 1  # count for 2
@inbounds for i in 3:2:maxn
if mark_array[i]
cnt += 1
j, delta = i^2, 2i
while j <= maxn
mark_array[j] = false
j += delta
end
end
end; cnt
end
primeCount2 (generic function with 1 method)
``````

``````julia> using BenchmarkTools

julia> @btime primeCount(10^8)
488.427 ms (3 allocations: 11.92 MiB)
5761455

julia> @btime primeCount2(10^8)
446.679 ms (3 allocations: 11.92 MiB)
5761455
``````

``````julia> foo(n) = Bool(n&0x1)
foo (generic function with 1 method)

julia> goo(n) = n % 2 != 0
goo (generic function with 1 method)

julia> @code_native foo(1)
.text
; Function foo {
; Location: REPL[84]:1
; Function Type; {
; Location: REPL[84]:1
andb    \$1, %dil
;}
movl    %edi, %eax
retq
nopw    (%rax,%rax)
;}

julia> @code_native goo(1)
.text
; Function goo {
; Location: REPL[85]:1
; Function !=; {
; Location: operators.jl:185
; Function ==; {
; Location: REPL[85]:1
andb    \$1, %dil
;}}
movl    %edi, %eax
retq
nopw    (%rax,%rax)
;}
``````

Julia进行类似于 `x[a:b]` 这种操作的时候用的是拷贝，所以对速度有影响。

``````julia> a = zeros(3); b = a[1:2]; b[1] = 1
1

julia> a
3-element Array{Float64,1}:
0.0
0.0
0.0
``````

``````for i in 1:lastindex(bits)-1
bit = bits[i]
...
end
``````

``````julia> a = falses(64);

julia> sizeof(a)
8

julia> sizeof(1) # Int64
8
``````

``````julia> for i in 1:10000
v = falses(i)
@assert sizeof(v) == 8cld(i, 8sizeof(UInt))
end

julia>
``````

https://docs.julialang.org/en/v1/manual/integers-and-floating-point-numbers/

``````julia> for i in 1:10000
v1 = falses(i)
v2 = Vector{Bool}(undef, i)
@assert sizeof(v1) == 8cld(i, 8sizeof(UInt))
@assert sizeof(v2) == i
end

julia> typeof(falses(2))
BitArray{1}

julia> typeof(Vector{Bool}(undef, 2))
Array{Bool,1}
``````

function primes(n::Int64)
nlen=ceil(n/2);
nlen=convert(Int64,nlen)
p=trues(nlen);
q = length§;
temp=sqrt(convert(Float64,n));
ua = floor(sqrt(n));
ub=convert(Int64,ua)
for k = 3:2:ub
if p[div(k+1,2)]
for i=div(k*k+1,2):k:q
p[i] = false;
end
end
end
s=0
for px in p
if px
s += 1
end
end
return s
end

1赞

bool是占用8个字节，和Int8，uint8一样的占用