function [] = Problem25()
%ProjectEuler/Octave/Problem25.m
%Matthew Ellison
% Created: 03-26-19
%Modified: 03-28-19
%What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
%This project uses the symbolic library. Make sure that you install the symbolic library as well as sympy before running this script
%The way to do this is run this command in octave: pkg install -forge symbolic
%This library requires sympy as well. This is easily installed with pip: pip install sympy
%{
	Copyright (C) 2019  Matthew Ellison

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Lesser General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
%}


pkg load symbolic;
digits(500)	%Keep track of enough digits to do this calculation correctly

NUM_DIGITS = 1000;	%The number of digits to calculate up to


%Setup the variables
syms number;	%The current Fibonacci number
syms x;	%A helper that will allow us to do easy math with the symbolics
number = x;
number = subs(number, x, 0);	%Set the number to 0
indexNum = 2;	%The index of the just calculated Fibonacci number

%Start the timer
startTime = clock();

%Move through all Fibonacci numbers until you reach the one with at least NUM_DIGITS digits
while(size(char(number))(2) < NUM_DIGITS)
	indexNum += 1;	%Increase the index number. Doing this at the beginning keeps the index correct at the end of the loop
	number = getFib(indexNum);
	printf("Index: %d\n", indexNum)
end

%Stop the timer
endTime = clock();

%Print the results
printf("The first Fibonacci number with %d digits is %s\n", NUM_DIGITS, char(number))
printf("The index is %d\n", indexNum);
printf("It took %f seconds to run this algorithm\n", etime(endTime, startTime));


end	%Problem25


function [num] = getFib(goalSubscript)
	%Setup the variables
	fibNums = {};
	syms tempNum;
	syms x;
	tempNum = x;
	tempNum = subs(tempNum, x, 1);
	fibNums(end + 1) = tempNum;
	fibNums(end + 1) = tempNum;
	tempNum = x;
	tempNum = subs(tempNum, x, 0);
	fibNums(end + 1) = tempNum;

	%If the number is <= 0 return 0
	if(goalSubscript <= 0)
		num = 0;
		return;
	end

	%Loop through the list, generating Fibonacci numbers until it finds the correct subscript
	fibLoc = 2;
	while(fibLoc <= goalSubscript)
		tempNum = x;
		tempNum = subs(tempNum, x, fibNums(mod((fibLoc - 1), 3) + 1));
		fibNums(mod(fibLoc, 3) + 1) = tempNum;
		tempNum = x;
		tempNum = subs(tempNum, x, fibNums(mod((fibLoc - 2), 3) + 1));
		fibNums(mod(fibLoc, 3) + 1) += tempNum;
		fibLoc += 1;
	end

	%Make sure the correct number is chosen for return
	answerLocation = mod((fibLoc - 1), 3);
	if(answerLocation == 0)
		answerLocation = 3;
	end
	num = fibNums(answerLocation);

end	%getFib

%{
Results:
I partially tested this and it seems to be working propperly.
Because I am using the symbolic package to simulate a bigint library it is very slow.
It looks as though it would take several days before it finished.
%}