Optimization of the matrix Riemann function in Julia
I implemented a function in Julia to create a Riemann matrix of size N. This is an N-by-N matrix associated with the Riemann hypothesis, which is true if and only if:
DET(A) = O( N! N^(-1/2+epsilon))
for each epsilon > 0
, DET()
denotes a determinant, !
denotes a factorial.
Where A = Riemann matrix, with
A = B(2:N+1, 2:N+1)
where
B(i,j) = i-1 if i divides j, and
-1 otherwise.
Here's my code, which works great but needs optimization:
function riemann(x::Int32)
R = zeros(Int32,x+1,x+1)
for i=1:x+1, j=1:x+1
if j%i == 0
R[i,j] = i-1
else
R[i,j] = -1
end
end
return R[2:x+1,2:x+1]
end
Hopefully I need to write it in a more efficient form like:
function riemann!{T}(R::AbstractMatrix{T}, x::T)
.
.
.
Any suggestions are greatly appreciated.
EDIT:
Well, this is another form I suggested above. I confined it to the source code and found no speed gain.
function calc_riemann!{T}(R::AbstractMatrix{T}, x::T)
for i=1:x+1, j=1:x+1
if j%i == 0
R[i,j] = i-1
else
R[i,j] = -1
end
end
end
function riemann(x::Int)
R = Array(Int, x+1,x+1)
calc_riemann!(R, x)
y = R[2:x+1,2:x+1]
end
source to share
This is much faster by cutting out all tests (we can just go to multiples).
function my_riemann(x::Int)
R = Array(Int,x+1,x+1)
fill!(R,-1)
for i=2:x+1
for j=i:i:x+1
R[i,j] = i - 1
end
end
return R[2:x+1,2:x+1]
end
EDIT
Yes, selection at the correct size Array
, not copying, makes things much faster. See if your time has been significantly reduced for this version.
function my_riemann2(x::Int)
R = Array(Int,x,x)
fill!(R,-1)
for i=1:x
for j=i:i+1:x
R[i,j] = i
end
end
return R
end
source to share