# Help with Project Euler #2: undef inits, printing, multiplication by juxtaposition, and more

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?

1. 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.

2. 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 Ints: convert(Vector{Int}, A) or even let it automatically happen in elementwise conversion: Int.(A).

4 Likes

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)

2 Likes

Besides Bennys solution â€“ here is the place t ask for such improvements
Welcome to the Julia discourse

2 Likes

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

1 Like

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.

1 Like

Thatâ€™s also what is going on in fibsum3, only using a slightly different recurrence.

1 Like

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.

1 Like

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.

4 Likes

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.

1 Like

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.

1 Like

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)