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


#21

其实不是这样的,这里的BitArray{1}应该跟上面的那位老兄说的一样,是用整数来表示,根据索引取其某一位。

julia> sizeof(trues(64)) == sizeof(trues(8))
true

#22

TIM%E5%9B%BE%E7%89%8720180928204921
这是特殊的类型


#24

function primesCount2(maxn::Int64)
	mark_array = trues(maxn)
	sqrt_maxn = floor(Int64, sqrt(maxn))
	@inbounds for i = 3:2:sqrt_maxn
		if mark_array[i]
			@inbounds for j = i^2:2i:maxn
				mark_array[j] = false
			end
		end
	end
	cnt = 1 # count for prime 2
	@inbounds for i in 3:2:maxn
		if mark_array[i]
			cnt += 1
		end
	end; cnt
end

我也优化了一下,虽然还比你那个慢20+%,不过如果要给出所有素数,结果未必会这样。

522.937 ms (3 allocations: 11.92 MiB)
5761455
391.883 ms (3 allocations: 5.96 MiB)
5761455
[Finished in 28.0s]


#25

你这一测试


#26

nlen=cld(n, 2)


#27

谢谢,不知道有这个函数


#28

您这个确实很快,我试图做多种优化,也不能达到您这种速度。:smile:


#29

这是matlab的库函数,我发起的项目,转写matlab库函数到julia


#30

我想问一下您那里面多余的那个temp变量为什么不删除呢?


#31

应该是测试着写着,没有注意,删掉就行


#32

我把你的代码稍微修改了一下,省了将近一半内存。

function primes(maxn::Int64)
    half = cld(maxn, 2)
    p = trues(half)
    for i = 3:2:isqrt(maxn)
        if p[div(i + 1, 2)]
            for j = div(i^2 + 1, 2):i:half
                p[j] = false
            end
        end
    end
    p = (1:half)[p]
    p .*= 2
    p .-= 1
    p[1] = 2
    return p
end

#33

已经更新了你的版本到github。outyang/MatlabFun.jl/blob/master/primes.jl