Databases
StackOverflow2013
Postsdbo
POHow can I make my implementation of Project Euler 25 faster, so I can actually compute the answer?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow can I make my implementation of Project Euler 25 faster, so I can actually compute the answer?
    primarykey
    data
    text
    <p>Here is my implementation of <a href="http://projecteuler.net/index.php?section=problems&amp;id=25" rel="nofollow">Problem 25 - Project Euler</a> (see comments in code for explanation of how it works):</p> <pre><code>#include &lt;iostream&gt; //Declare headers and use correct namespace #include &lt;math.h&gt; using namespace std; //Variables for the equation F_n(newTerm) = F_n-1(prevTerm) + Fn_2(currentTerm) unsigned long long newTerm = 0; unsigned long long prevTerm = 1; //F_1 initially = 1 unsigned long long currentTerm = 1; //F_2 initially = 2 unsigned long long termNo = 2; //Current number for the term void getNextTerms() { //Iterates through the Fib sequence, by changing the global variables. newTerm = prevTerm + currentTerm; //First run: newTerm = 2 unsigned long long temp = currentTerm; //temp = 1 currentTerm = newTerm; //currentTerm = 2 prevTerm = temp; //prevTerm = 1 termNo++; //termNo = 3 } unsigned long long getLength(unsigned long long number) //Returns the length of the number { unsigned long long length = 0; while (number &gt;= 1) { number = number / 10; length++; } return length; } int main (int argc, const char * argv[]) { while (true) { getNextTerms(); //Gets next term in the Fib sequence if (getLength(currentTerm) &lt; 1000) { //Checks if the next terms size is less than the desired length } else { //Otherwise if it is perfect print out the term. cout &lt;&lt; termNo; break; } } } </code></pre> <p>This works for the example, and will run quickly as long as this line:</p> <pre><code> if (getLength(currentTerm) &lt; 1000) { //Checks if the next term's size is less than the desired length </code></pre> <p>says 20 or lower instead of 1000. But if that number is greater than 20 it takes a forever, my patience gets the better of me and I stop the program, how can I make this algorithm more efficient?</p> <p>If you have any questions just ask in the comments. </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USiCodez
    1. USDair
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COThe max value of an 128bit `unsigned long long` is something like 3*10^38. That's much too small to hold a thousand-digit number.
      singulars
      1. POHow can I make my implementation of Project Euler 25 faster, so I can actually compute the answer?
      1. USMat
    2. CO@Mat: Do you have any suggestion on what to do about that?
      singulars
      1. POHow can I make my implementation of Project Euler 25 faster, so I can actually compute the answer?
      1. USDair
    3. COGenerally speaking, a `long long` will be 64-bits - the largest number that can be represented by such a type (if it's unsigned) is `18446744073709551615`, which has 20 digits. There's no way to represent a number that has 1000 digits with that type (which is why it's taking your program forever - it can't be done). To find a fibonacci number with 1000 digits, you won't be able to just use `long long` types - you'll need represent the numbers in some other way,
      singulars
      1. POHow can I make my implementation of Project Euler 25 faster, so I can actually compute the answer?
      1. USMichael Burr
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload