A = [0, 1, undef]
A[3] = 1
println(A)
In the above script, is there any way to suppress the Any
appearing in front of the array values in (square) brackets of array A
?
A = [0, 1, undef]
A[3] = 1
println(A)
In the above script, is there any way to suppress the Any
appearing in front of the array values in (square) brackets of array A
?
That isn’t how you’d use undef
to make uninitialized elements. You don’t have an uninitialized element, which would throw an error upon indexing, it’s actually holding an instance that’s used as a flag for uninitialized array construction.
Are you sure you want to suppress the array’s element type parameter? It’s important to distinguish that normally. You could instead make a new array with a new element type after all elements are valid Int
s: convert(Vector{Int}, A)
or even let it automatically happen in elementwise conversion: Int.(A)
.
That does it. Thanks.
I am doing a Fibonacci sequence problem where 0
and 1
are the first two terms and the remaining ones are generated by the well-known recurrence relation.
I tried A = [0, 1, 1]
and used push!
to append the rest. But I had to generate element 3 again within the while
loop. I used undef
to avoid that. Perhaps that is not the correct thing to do.
Is there somewhere a script my be posted for dissection and improvement?
It would also help if there were simple but complete use cases like generating the Fibonacci sequence, and doing things with it, in a tutorial. Is there one (or more) such on the Web?
Not knowing what your code is, I can’t comment on that exactly. But I can’t imagine the need to make the 3rd uninitialized element in advance.
julia> A = [0,1]; for _ in 1:10 push!(A, A[end-1] + A[end]) end
julia> println(A) # 2+10=12 terms
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
Bear in mind that fixed width integers overflow silently so you’ll have to stop at 47 numbers on 32-bit systems or 93 on 64-bit systems:
julia> last2 = [0,1]; i = 2; notoverflowed=true; while notoverflowed
newterm = last2[1] + last2[2]
if newterm < last2[end]
notoverflowed = false
else
global i += 1
last2[begin] = last2[end]
last2[end] = newterm
end
end
julia> last2, i
([4660046610375530309, 7540113804746346429], 93)
Besides Bennys solution – here is the place t ask for such improvements
Welcome to the Julia discourse
My script is shown below for solving the Euler Two problem:
# Generate the Fibonacci numbers which do not exceed 4 million
const MAX = 4000000;
F = [0, 1, undef]
i = 3 # Array already has three elements
#
while true
global i
F[i] = F[i-1] + F[i-2]
# println("$(i)" , " ", "$(F[i])") # for troubleshooting
(F[i] + F[i-1]) <= MAX || break
push!(F, F[i]) # append to array
i += 1
end
#
println(i)
println(Int.(F))
#
# Sum of even Fibonacci numbers in F
#
E = F[1:3:end]
println(Int.(E))
println(sum(E)) # This is what we want
It looks primitive compared to @Benny’s one-liner! Please dissect it and help me write better scripts. Thanks.
Make sure to write your code as a function, don’t write it in global scope, and definitely don’t use the global
keyword. I strongly recommend against it.
Here’s one solution that uses push!
, if you have an estimate of the array size you will need, you can use that, or let’s say if you know how many numbers you want in advance:
function myfib(maxval)
val = i = 1
F = [0, val]
while val <= maxval
push!(F, val)
val += F[i+=1]
end
return F
end
I didn’t see this at first. Here’s an efficient implementation. It is not super elegant, but it really flies:
function fibsumeven(maxval)
prev, current = 0, 1 # previous and updated Fibonacci numbers
accum = prev # this is the accumulated sum
prev, current = current, prev + current
prev, current = current, prev + current
while current <= maxval
accum += current # only sum every third Fibo number
prev, current = current, prev + current
prev, current = current, prev + current
prev, current = current, prev + current
end
return accum
end
Performance comparison with the vector-based implementation:
julia> @btime sum(@view myfib(4181)[1:3:end])
279.044 ns (3 allocations: 496 bytes)
3382
julia> @btime fibsumeven(4181)
6.600 ns (0 allocations: 0 bytes)
3382
Edit: Here’s one that collapses the repeated lines, if you like that better. It’s also slightly faster:
function fibsum3(maxval)
prev, current = 0, 1
accum = prev
prev, current = prev + current, prev + 2current
while current <= maxval
accum += current
prev, current = prev + 2current, 2prev + 3current
end
return accum
end
Slightly nicer way (just as fast though):
fib_even_next(m2, m1) = 4*m1 + m2
function fib_even_sum(max_val, ini0 = 0, ini1 = 2)
sum = ini0
while ini1 ≤ max_val
sum += ini1
n = fib_even_next(ini0, ini1)
(ini0, ini1) = (ini1, n)
end
sum
end
The idea is that instead of summing every third Fibonacci number, we could directly operate on the sequence of even Fibonacci numbers.
The Fibonacci numbers are defined by the recurrence a_n = a_{n-1} + a_{n-2}, while even Fibonacci numbers seem to conform to the similar recurrence a_n = {4 \cdot a_{n-1}} + a_{n-2}. The latter was obtained using the Guess
package of Fricas, with the guessPRec
function.
That’s also what is going on in fibsum3
, only using a slightly different recurrence.
Thanks for this.
I found the line val += F[i+=1]
a little difficult to get my head around. I wanted something a little easier that I could relate directly to the recurrence relation. So, I tried the following:
function myfib(maxval)
val = 1
F = [0, val]
while val <= maxval
push!(F, val)
val += F[end-1]
end
return F
end
In the process, the pesky i
which I had to previously declare global has also vanished. I think the moral is that wrapping the whole thing within a function does away with local
versus global
variables.
I am grateful for your example. The other examples here have a “horsepower” that is a little too high for me to grasp straightaway! More exposure to the Julia style will hopefully demystify them.
What do the expressions 2current
and 3current
mean? I searched the docs but could not find the name for this action.
Are they a short-form for multiplication? If so, how is ambiguity in meaning avoided?
Yeah, it’s implicit multiplication by a constant: Numeric Literal Coefficients
Here is a functional solution:
using Chain, IterTools
fibo_step(a, b) = (b, a+b)
@chain (0, 1) begin
IterTools.iterated(splat(fibo_step), _)
Iterators.map(first, _)
Iterators.takewhile(<(4000000), _)
collect(_)
end
One central point is that if you are just looking to calculate an aggregate scalar value (eg. the sum of the even numbers), it is wasteful to first build a full vector, and then later iterate and sum over it. If you can “sum as you go”, you can often get a huge performance payoff. So as a general rule, I always ask myself if I really need to build an array.
I think this is an explanation for fibsun3
and it is so much clearer now.
I also appreciate the general philosophy of why it is wasteful to use arrays in such cases.
Thank you.
Thank you for the links to Fricas and Guess.
In light of the wealth of help I have got here, may I suggest something.
Could someone with administrator privileges please change the subject of this thread to better reflect the knowledge contained herein.
Thank you all.
The title of your thread should have a pencil icon at the end, click it and you can edit the title. Your comments will also have a pencil icon at the bottom right with this functionality. Press the appearing check icon to save changes and the X icon to discard changes.
That is pretty much how I would write it. Except you should start with just a 1-element vector or else the original prompt in the link of starting with [1,2] does not work, i.e. F = [0, val]
should just be F[0]
. Then val
will be pushed to F
inside the loop.
function myfib(maxval=4e6, first=0, second=1)
val = second
F = [first]
while val <= maxval
push!(F, val)
val += F[end-1]
end
return F
end
Even the literal version without val
isn’t much slower.
function myfib_nathan(maxval=4e6, first=0, second=1)
F = [first, second]
while F[end] < maxval
push!(F, F[end] + F[end-1])
end
return F[1:end-1]
end
julia> @btime myfib_DNF(4e6)
244.149 ns (3 allocations: 496 bytes)
julia> @btime myfib_nathan(4e6)
302.834 ns (4 allocations: 832 bytes)