Euler Problem 2 using Theano
Posted on by James Thomas.
Solving Euler Problem 2 using the Golden Ratio and Theano (and the "scan" function).
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
The purpose of this blog post is to play around with the Theano symbolic math library and to possibly make people ask questions, whether it be new ideas or just wondering why I did something that way. Theano is commonly used for machine learning, but in this example we will be using it for a math problem. This particular program code was outlined in the Theano documentation here.
The assumptions that I made within this solution begin with my understanding of the number system.
Two of the same parity type will always sum to be an even parity. This means an odd number plus and another odd number will always sum to be even and an even number and another even number will be even too. An odd number and an even number will sum to be an odd parity. This means that every third number in the Fibonacci sequence will always be even.
The ratio between numbers in the Fibonacci sequence tends towards the golden ratio, phi, as the numbers increase. In a continuous number system, the error generated by multiplying a Fibonacci number by the golden ratio in order to obtain the next Fibonacci number will be inversely proportional to the distance from zero. Another way to say that is the error will be greater the closer the sequence is to zero. Continuous number system meaning a system capable of representing infinitesimal and infinitely large values, or in this case the perfect representation of the golden ratio, phi, and any of its products (multiplication).
However, computers use discrete number systems. Meaning, in this case, that only certain values can be represented because of the limited amount of storage space. In a discrete system the introduction of a limited mantissa size will cause phi to become more accurate around the Fibonacci numbers with the same number of significant figures as the constant (or slightly less) and will also generate error after that point as the system goes to an infinite mantissa size. Edit: As the numbers start growing larger you will generate an increasing amount of error because of granularity but this is overshadowed by the accuracy gained by approaching the same number of digits as just discussed.
The use of phi cubed allows us to skip 2 Fibonacci numbers in the sequence - this reasoning is explained in the parity paragraph above. It is acceptable to use the constant phi cubed instead of cubing and simplifying Ptolemy’s theorem because additional accuracy is not obtained when using 16 digits until we begin raising the ratio to the power of 4 or higher. We basically are right at the cutoff for this optimization.
Given the error generated in the very beginning and that the error minimizes as the numbers increase below the upper bound of the constant’s mantissa in scientific representation, we can deduce that rounding to the nearest integer will provide the correct Fibonacci number within these limits.
The purpose of explaining the choices in some detail is to attempt to prove that the math and logic being used is not just magical or random. Changing from one number system to another is in my opinion logical for solving problems especially in regards to computing. When I say number system, I am not in this case referring to the base but the level of discreteness. Of course, this is just a made up problem though.
A Note on Theano's Scan
In this particular problem we used Theano’s scan function and like I said earlier its basically taken out of the book’s example for scan with a conditional. There are a lot of nuances to the scan function and one of those that will be important is that the order of the parameters given to scan is fixed and that the order they are given correspond with the order that they are passed into the function used within scan.
Scan loops over the inputs using the outputs_info as the initial state of the outputs (technically inputs at that point) as well as to define properties of the outputs. Other sequence and non-sequence inputs can be used as well. Shared variables can be used and scan will understand them for what they are, however, to avoid confusion its best to have them as inputs into the scan function as per the documentation.