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 :slight_smile:
Welcome to the Julia discourse :wave:

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)