Better Fibonacci sequence calculation











up vote
7
down vote

favorite
1












I attempted to make better Fibonacci sequence calculation algorithm in C++. This was the best I could:



constexpr unsigned fibonacci(unsigned n) {

    unsigned result[2] = {1, 0};

    for (unsigned i = 1; i < n; ++i)

        result[i%2] = result[0] + result[1];

    return result[1 - n%2];

}


...which runs at O(n) time complexity and O(1) space complexity.

Is there any better?






c++ c++11 fibonacci-sequence







share|improve this question


















  • 4




    Yes. Check out mathworld.wolfram.com/FibonacciQ-Matrix.html. Combined with exponentiation by squaring it yields $O(log{n})$ time complexity, while still $O(1)$ space.
    – vnp
    May 12 '17 at 1:59










  • @vnp That involves multiplication. Doesn't multiplication have worse complexity than addition?
    – Dannyu NDos
    May 12 '17 at 2:09






  • 5




    Everything else equal, an individual multiplication is (usually) slower than an individual addition. However the suggested approach performs so much less operations that individual complexity doesn't count. There is a rigorous proof of this intuition.
    – vnp
    May 12 '17 at 2:16






  • 1




    O(1) time and space if you're willing to go via floating-point for the closed-form expression - there's probably a crossover value of n for which that's better.
    – Toby Speight
    Jan 15 at 8:36






  • 1




    @greybeard, I don't consider solving a popular programming exercise to be reinventing the wheel. If there existed std::fibonacci (or similar in Boost etc), I think you'd be right.
    – Toby Speight
    Jan 15 at 8:37















up vote
7
down vote

favorite
1












I attempted to make better Fibonacci sequence calculation algorithm in C++. This was the best I could:



constexpr unsigned fibonacci(unsigned n) {

    unsigned result[2] = {1, 0};

    for (unsigned i = 1; i < n; ++i)

        result[i%2] = result[0] + result[1];

    return result[1 - n%2];

}


...which runs at O(n) time complexity and O(1) space complexity.

Is there any better?






c++ c++11 fibonacci-sequence







share|improve this question


















  • 4




    Yes. Check out mathworld.wolfram.com/FibonacciQ-Matrix.html. Combined with exponentiation by squaring it yields $O(log{n})$ time complexity, while still $O(1)$ space.
    – vnp
    May 12 '17 at 1:59










  • @vnp That involves multiplication. Doesn't multiplication have worse complexity than addition?
    – Dannyu NDos
    May 12 '17 at 2:09






  • 5




    Everything else equal, an individual multiplication is (usually) slower than an individual addition. However the suggested approach performs so much less operations that individual complexity doesn't count. There is a rigorous proof of this intuition.
    – vnp
    May 12 '17 at 2:16






  • 1




    O(1) time and space if you're willing to go via floating-point for the closed-form expression - there's probably a crossover value of n for which that's better.
    – Toby Speight
    Jan 15 at 8:36






  • 1




    @greybeard, I don't consider solving a popular programming exercise to be reinventing the wheel. If there existed std::fibonacci (or similar in Boost etc), I think you'd be right.
    – Toby Speight
    Jan 15 at 8:37













up vote
7
down vote

favorite
1









up vote
7
down vote

favorite
1






1





I attempted to make better Fibonacci sequence calculation algorithm in C++. This was the best I could:



constexpr unsigned fibonacci(unsigned n) {

    unsigned result[2] = {1, 0};

    for (unsigned i = 1; i < n; ++i)

        result[i%2] = result[0] + result[1];

    return result[1 - n%2];

}


...which runs at O(n) time complexity and O(1) space complexity.

Is there any better?






c++ c++11 fibonacci-sequence







share|improve this question













I attempted to make better Fibonacci sequence calculation algorithm in C++. This was the best I could:



constexpr unsigned fibonacci(unsigned n) {

    unsigned result[2] = {1, 0};

    for (unsigned i = 1; i < n; ++i)

        result[i%2] = result[0] + result[1];

    return result[1 - n%2];

}


...which runs at O(n) time complexity and O(1) space complexity.

Is there any better?






c++ c++11 fibonacci-sequence




c++ c++11 fibonacci-sequence






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked May 12 '17 at 1:31









Dannyu NDos

190113




190113








  • 4




    Yes. Check out mathworld.wolfram.com/FibonacciQ-Matrix.html. Combined with exponentiation by squaring it yields $O(log{n})$ time complexity, while still $O(1)$ space.
    – vnp
    May 12 '17 at 1:59










  • @vnp That involves multiplication. Doesn't multiplication have worse complexity than addition?
    – Dannyu NDos
    May 12 '17 at 2:09






  • 5




    Everything else equal, an individual multiplication is (usually) slower than an individual addition. However the suggested approach performs so much less operations that individual complexity doesn't count. There is a rigorous proof of this intuition.
    – vnp
    May 12 '17 at 2:16






  • 1




    O(1) time and space if you're willing to go via floating-point for the closed-form expression - there's probably a crossover value of n for which that's better.
    – Toby Speight
    Jan 15 at 8:36






  • 1




    @greybeard, I don't consider solving a popular programming exercise to be reinventing the wheel. If there existed std::fibonacci (or similar in Boost etc), I think you'd be right.
    – Toby Speight
    Jan 15 at 8:37














  • 4




    Yes. Check out mathworld.wolfram.com/FibonacciQ-Matrix.html. Combined with exponentiation by squaring it yields $O(log{n})$ time complexity, while still $O(1)$ space.
    – vnp
    May 12 '17 at 1:59










  • @vnp That involves multiplication. Doesn't multiplication have worse complexity than addition?
    – Dannyu NDos
    May 12 '17 at 2:09






  • 5




    Everything else equal, an individual multiplication is (usually) slower than an individual addition. However the suggested approach performs so much less operations that individual complexity doesn't count. There is a rigorous proof of this intuition.
    – vnp
    May 12 '17 at 2:16






  • 1




    O(1) time and space if you're willing to go via floating-point for the closed-form expression - there's probably a crossover value of n for which that's better.
    – Toby Speight
    Jan 15 at 8:36






  • 1




    @greybeard, I don't consider solving a popular programming exercise to be reinventing the wheel. If there existed std::fibonacci (or similar in Boost etc), I think you'd be right.
    – Toby Speight
    Jan 15 at 8:37








4




4




Yes. Check out mathworld.wolfram.com/FibonacciQ-Matrix.html. Combined with exponentiation by squaring it yields $O(log{n})$ time complexity, while still $O(1)$ space.
– vnp
May 12 '17 at 1:59




Yes. Check out mathworld.wolfram.com/FibonacciQ-Matrix.html. Combined with exponentiation by squaring it yields $O(log{n})$ time complexity, while still $O(1)$ space.
– vnp
May 12 '17 at 1:59












@vnp That involves multiplication. Doesn't multiplication have worse complexity than addition?
– Dannyu NDos
May 12 '17 at 2:09




@vnp That involves multiplication. Doesn't multiplication have worse complexity than addition?
– Dannyu NDos
May 12 '17 at 2:09




5




5




Everything else equal, an individual multiplication is (usually) slower than an individual addition. However the suggested approach performs so much less operations that individual complexity doesn't count. There is a rigorous proof of this intuition.
– vnp
May 12 '17 at 2:16




Everything else equal, an individual multiplication is (usually) slower than an individual addition. However the suggested approach performs so much less operations that individual complexity doesn't count. There is a rigorous proof of this intuition.
– vnp
May 12 '17 at 2:16




1




1




O(1) time and space if you're willing to go via floating-point for the closed-form expression - there's probably a crossover value of n for which that's better.
– Toby Speight
Jan 15 at 8:36




O(1) time and space if you're willing to go via floating-point for the closed-form expression - there's probably a crossover value of n for which that's better.
– Toby Speight
Jan 15 at 8:36




1




1




@greybeard, I don't consider solving a popular programming exercise to be reinventing the wheel. If there existed std::fibonacci (or similar in Boost etc), I think you'd be right.
– Toby Speight
Jan 15 at 8:37




@greybeard, I don't consider solving a popular programming exercise to be reinventing the wheel. If there existed std::fibonacci (or similar in Boost etc), I think you'd be right.
– Toby Speight
Jan 15 at 8:37










1 Answer
1






active

oldest

votes

















up vote
3
down vote



accepted










(Uh-oh: better - better define a quality measure!)




  • Your code doesn't tell what it's about.


  • constexpr looks good - "my" environment complains with C++11.

  • "The array&index manipulation" where "simultaneous assignment" is wanted is hard to read (could be worse: the elements of result could be non-interchangeable).

    Alas, what I found for "modern C++" is ghastly compared to python's a, b = b, a + b. I appreciate the attempt to avoid avoidable assignments; I'm mildly curious if it makes any difference in the code generated by an optimising compiler.


  • Is there any better? Well, with output size limited by a constant, there's a tighter limit:

    the runtime of your code is in O(1), just as any other.

    In a comment, you express concern about the complexity of multiplication. If you accept ("bit-wise") "shift" as a (very) cheap operation, you can take three steps in the Fibonacci sequence at once without an increase in "logic gate complexity":



#include <cstdlib>

#include <tuple>

#include <iostream>



/// Iterates an a,b = b,a+b sequence in steps of three.

//constexpr

static unsigned long tri(int previous, int current, const unsigned int n) {

    if (n < 2)

        return n ? current : previous;

    std::div_t split = std::div(n-2, 3);

    while (0 <= --split.rem)

        std::tie(previous, current)

            = std::make_tuple(current, current+previous);

    unsigned long

        a = current - previous,

        b = current + previous;      

    while (0 <= --split.quot)

        std::tie(a, b) = std::make_tuple(b, (b<<2)+a);



    return b;

}

/// Iterates the Fibonacci sequence in steps of three.

unsigned long fibonacci(const unsigned int n) {

    return tri(0, 1, n);

}

/// Iterates the Lucas numbers in steps of three.

unsigned long lucas(const unsigned int n) {

    return tri(2, 1, n);

}


(For variants using arrays of precomputed elements in stead of "the setup-loop" (and a main()), consult the edit history.)

(b*Phi³ coincidentally can be computed with just two summands (and no other power up to 2³² can).)






share|improve this answer























  • (Disclaimer: I haven't used C++ in earnest for over a decade, I never was up to speed with "modern C++", even C++03. Feel invited to improve (especially) the code above.)
    – greybeard
    Jan 15 at 1:15










  • I think I would move fib and luc into the scope of triFib() and triLuc() respectively (as static constants) - no need for them to be globally visible.
    – Toby Speight
    Jan 15 at 8:40






  • 1




    Woah... Never expected this old question to be answered! Thank you very much.
    – Dannyu NDos
    Jan 16 at 0:23










  • (For the curious: multipliers and step sizes for three summands: 3/2, (7/4((x<<3)-x, shift&mask instead of divmod)), 18/6; four summands: (7/4, shift&mask), 11/5, (47/8((x<<5)+(x<<4)-x, s&m)), 76/9, 322/12, 521/13)
    – greybeard
    Jan 17 at 8:04











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f163132%2fbetter-fibonacci-sequence-calculation%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
3
down vote



accepted










(Uh-oh: better - better define a quality measure!)




  • Your code doesn't tell what it's about.


  • constexpr looks good - "my" environment complains with C++11.

  • "The array&index manipulation" where "simultaneous assignment" is wanted is hard to read (could be worse: the elements of result could be non-interchangeable).

    Alas, what I found for "modern C++" is ghastly compared to python's a, b = b, a + b. I appreciate the attempt to avoid avoidable assignments; I'm mildly curious if it makes any difference in the code generated by an optimising compiler.


  • Is there any better? Well, with output size limited by a constant, there's a tighter limit:

    the runtime of your code is in O(1), just as any other.

    In a comment, you express concern about the complexity of multiplication. If you accept ("bit-wise") "shift" as a (very) cheap operation, you can take three steps in the Fibonacci sequence at once without an increase in "logic gate complexity":



#include <cstdlib>

#include <tuple>

#include <iostream>



/// Iterates an a,b = b,a+b sequence in steps of three.

//constexpr

static unsigned long tri(int previous, int current, const unsigned int n) {

    if (n < 2)

        return n ? current : previous;

    std::div_t split = std::div(n-2, 3);

    while (0 <= --split.rem)

        std::tie(previous, current)

            = std::make_tuple(current, current+previous);

    unsigned long

        a = current - previous,

        b = current + previous;      

    while (0 <= --split.quot)

        std::tie(a, b) = std::make_tuple(b, (b<<2)+a);



    return b;

}

/// Iterates the Fibonacci sequence in steps of three.

unsigned long fibonacci(const unsigned int n) {

    return tri(0, 1, n);

}

/// Iterates the Lucas numbers in steps of three.

unsigned long lucas(const unsigned int n) {

    return tri(2, 1, n);

}


(For variants using arrays of precomputed elements in stead of "the setup-loop" (and a main()), consult the edit history.)

(b*Phi³ coincidentally can be computed with just two summands (and no other power up to 2³² can).)






share|improve this answer























  • (Disclaimer: I haven't used C++ in earnest for over a decade, I never was up to speed with "modern C++", even C++03. Feel invited to improve (especially) the code above.)
    – greybeard
    Jan 15 at 1:15










  • I think I would move fib and luc into the scope of triFib() and triLuc() respectively (as static constants) - no need for them to be globally visible.
    – Toby Speight
    Jan 15 at 8:40






  • 1




    Woah... Never expected this old question to be answered! Thank you very much.
    – Dannyu NDos
    Jan 16 at 0:23










  • (For the curious: multipliers and step sizes for three summands: 3/2, (7/4((x<<3)-x, shift&mask instead of divmod)), 18/6; four summands: (7/4, shift&mask), 11/5, (47/8((x<<5)+(x<<4)-x, s&m)), 76/9, 322/12, 521/13)
    – greybeard
    Jan 17 at 8:04















up vote
3
down vote



accepted










(Uh-oh: better - better define a quality measure!)




  • Your code doesn't tell what it's about.


  • constexpr looks good - "my" environment complains with C++11.

  • "The array&index manipulation" where "simultaneous assignment" is wanted is hard to read (could be worse: the elements of result could be non-interchangeable).

    Alas, what I found for "modern C++" is ghastly compared to python's a, b = b, a + b. I appreciate the attempt to avoid avoidable assignments; I'm mildly curious if it makes any difference in the code generated by an optimising compiler.


  • Is there any better? Well, with output size limited by a constant, there's a tighter limit:

    the runtime of your code is in O(1), just as any other.

    In a comment, you express concern about the complexity of multiplication. If you accept ("bit-wise") "shift" as a (very) cheap operation, you can take three steps in the Fibonacci sequence at once without an increase in "logic gate complexity":



#include <cstdlib>

#include <tuple>

#include <iostream>



/// Iterates an a,b = b,a+b sequence in steps of three.

//constexpr

static unsigned long tri(int previous, int current, const unsigned int n) {

    if (n < 2)

        return n ? current : previous;

    std::div_t split = std::div(n-2, 3);

    while (0 <= --split.rem)

        std::tie(previous, current)

            = std::make_tuple(current, current+previous);

    unsigned long

        a = current - previous,

        b = current + previous;      

    while (0 <= --split.quot)

        std::tie(a, b) = std::make_tuple(b, (b<<2)+a);



    return b;

}

/// Iterates the Fibonacci sequence in steps of three.

unsigned long fibonacci(const unsigned int n) {

    return tri(0, 1, n);

}

/// Iterates the Lucas numbers in steps of three.

unsigned long lucas(const unsigned int n) {

    return tri(2, 1, n);

}


(For variants using arrays of precomputed elements in stead of "the setup-loop" (and a main()), consult the edit history.)

(b*Phi³ coincidentally can be computed with just two summands (and no other power up to 2³² can).)






share|improve this answer























  • (Disclaimer: I haven't used C++ in earnest for over a decade, I never was up to speed with "modern C++", even C++03. Feel invited to improve (especially) the code above.)
    – greybeard
    Jan 15 at 1:15










  • I think I would move fib and luc into the scope of triFib() and triLuc() respectively (as static constants) - no need for them to be globally visible.
    – Toby Speight
    Jan 15 at 8:40






  • 1




    Woah... Never expected this old question to be answered! Thank you very much.
    – Dannyu NDos
    Jan 16 at 0:23










  • (For the curious: multipliers and step sizes for three summands: 3/2, (7/4((x<<3)-x, shift&mask instead of divmod)), 18/6; four summands: (7/4, shift&mask), 11/5, (47/8((x<<5)+(x<<4)-x, s&m)), 76/9, 322/12, 521/13)
    – greybeard
    Jan 17 at 8:04













up vote
3
down vote



accepted







up vote
3
down vote



accepted






(Uh-oh: better - better define a quality measure!)




  • Your code doesn't tell what it's about.


  • constexpr looks good - "my" environment complains with C++11.

  • "The array&index manipulation" where "simultaneous assignment" is wanted is hard to read (could be worse: the elements of result could be non-interchangeable).

    Alas, what I found for "modern C++" is ghastly compared to python's a, b = b, a + b. I appreciate the attempt to avoid avoidable assignments; I'm mildly curious if it makes any difference in the code generated by an optimising compiler.


  • Is there any better? Well, with output size limited by a constant, there's a tighter limit:

    the runtime of your code is in O(1), just as any other.

    In a comment, you express concern about the complexity of multiplication. If you accept ("bit-wise") "shift" as a (very) cheap operation, you can take three steps in the Fibonacci sequence at once without an increase in "logic gate complexity":



#include <cstdlib>

#include <tuple>

#include <iostream>



/// Iterates an a,b = b,a+b sequence in steps of three.

//constexpr

static unsigned long tri(int previous, int current, const unsigned int n) {

    if (n < 2)

        return n ? current : previous;

    std::div_t split = std::div(n-2, 3);

    while (0 <= --split.rem)

        std::tie(previous, current)

            = std::make_tuple(current, current+previous);

    unsigned long

        a = current - previous,

        b = current + previous;      

    while (0 <= --split.quot)

        std::tie(a, b) = std::make_tuple(b, (b<<2)+a);



    return b;

}

/// Iterates the Fibonacci sequence in steps of three.

unsigned long fibonacci(const unsigned int n) {

    return tri(0, 1, n);

}

/// Iterates the Lucas numbers in steps of three.

unsigned long lucas(const unsigned int n) {

    return tri(2, 1, n);

}


(For variants using arrays of precomputed elements in stead of "the setup-loop" (and a main()), consult the edit history.)

(b*Phi³ coincidentally can be computed with just two summands (and no other power up to 2³² can).)






share|improve this answer














(Uh-oh: better - better define a quality measure!)




  • Your code doesn't tell what it's about.


  • constexpr looks good - "my" environment complains with C++11.

  • "The array&index manipulation" where "simultaneous assignment" is wanted is hard to read (could be worse: the elements of result could be non-interchangeable).

    Alas, what I found for "modern C++" is ghastly compared to python's a, b = b, a + b. I appreciate the attempt to avoid avoidable assignments; I'm mildly curious if it makes any difference in the code generated by an optimising compiler.


  • Is there any better? Well, with output size limited by a constant, there's a tighter limit:

    the runtime of your code is in O(1), just as any other.

    In a comment, you express concern about the complexity of multiplication. If you accept ("bit-wise") "shift" as a (very) cheap operation, you can take three steps in the Fibonacci sequence at once without an increase in "logic gate complexity":



#include <cstdlib>

#include <tuple>

#include <iostream>



/// Iterates an a,b = b,a+b sequence in steps of three.

//constexpr

static unsigned long tri(int previous, int current, const unsigned int n) {

    if (n < 2)

        return n ? current : previous;

    std::div_t split = std::div(n-2, 3);

    while (0 <= --split.rem)

        std::tie(previous, current)

            = std::make_tuple(current, current+previous);

    unsigned long

        a = current - previous,

        b = current + previous;      

    while (0 <= --split.quot)

        std::tie(a, b) = std::make_tuple(b, (b<<2)+a);



    return b;

}

/// Iterates the Fibonacci sequence in steps of three.

unsigned long fibonacci(const unsigned int n) {

    return tri(0, 1, n);

}

/// Iterates the Lucas numbers in steps of three.

unsigned long lucas(const unsigned int n) {

    return tri(2, 1, n);

}


(For variants using arrays of precomputed elements in stead of "the setup-loop" (and a main()), consult the edit history.)

(b*Phi³ coincidentally can be computed with just two summands (and no other power up to 2³² can).)







share|improve this answer














share|improve this answer



share|improve this answer








edited 12 mins ago









albert

1071




1071










answered Jan 15 at 1:14









greybeard

1,3491521




1,3491521












  • (Disclaimer: I haven't used C++ in earnest for over a decade, I never was up to speed with "modern C++", even C++03. Feel invited to improve (especially) the code above.)
    – greybeard
    Jan 15 at 1:15










  • I think I would move fib and luc into the scope of triFib() and triLuc() respectively (as static constants) - no need for them to be globally visible.
    – Toby Speight
    Jan 15 at 8:40






  • 1




    Woah... Never expected this old question to be answered! Thank you very much.
    – Dannyu NDos
    Jan 16 at 0:23










  • (For the curious: multipliers and step sizes for three summands: 3/2, (7/4((x<<3)-x, shift&mask instead of divmod)), 18/6; four summands: (7/4, shift&mask), 11/5, (47/8((x<<5)+(x<<4)-x, s&m)), 76/9, 322/12, 521/13)
    – greybeard
    Jan 17 at 8:04


















  • (Disclaimer: I haven't used C++ in earnest for over a decade, I never was up to speed with "modern C++", even C++03. Feel invited to improve (especially) the code above.)
    – greybeard
    Jan 15 at 1:15










  • I think I would move fib and luc into the scope of triFib() and triLuc() respectively (as static constants) - no need for them to be globally visible.
    – Toby Speight
    Jan 15 at 8:40






  • 1




    Woah... Never expected this old question to be answered! Thank you very much.
    – Dannyu NDos
    Jan 16 at 0:23










  • (For the curious: multipliers and step sizes for three summands: 3/2, (7/4((x<<3)-x, shift&mask instead of divmod)), 18/6; four summands: (7/4, shift&mask), 11/5, (47/8((x<<5)+(x<<4)-x, s&m)), 76/9, 322/12, 521/13)
    – greybeard
    Jan 17 at 8:04
















(Disclaimer: I haven't used C++ in earnest for over a decade, I never was up to speed with "modern C++", even C++03. Feel invited to improve (especially) the code above.)
– greybeard
Jan 15 at 1:15




(Disclaimer: I haven't used C++ in earnest for over a decade, I never was up to speed with "modern C++", even C++03. Feel invited to improve (especially) the code above.)
– greybeard
Jan 15 at 1:15












I think I would move fib and luc into the scope of triFib() and triLuc() respectively (as static constants) - no need for them to be globally visible.
– Toby Speight
Jan 15 at 8:40




I think I would move fib and luc into the scope of triFib() and triLuc() respectively (as static constants) - no need for them to be globally visible.
– Toby Speight
Jan 15 at 8:40




1




1




Woah... Never expected this old question to be answered! Thank you very much.
– Dannyu NDos
Jan 16 at 0:23




Woah... Never expected this old question to be answered! Thank you very much.
– Dannyu NDos
Jan 16 at 0:23












(For the curious: multipliers and step sizes for three summands: 3/2, (7/4((x<<3)-x, shift&mask instead of divmod)), 18/6; four summands: (7/4, shift&mask), 11/5, (47/8((x<<5)+(x<<4)-x, s&m)), 76/9, 322/12, 521/13)
– greybeard
Jan 17 at 8:04




(For the curious: multipliers and step sizes for three summands: 3/2, (7/4((x<<3)-x, shift&mask instead of divmod)), 18/6; four summands: (7/4, shift&mask), 11/5, (47/8((x<<5)+(x<<4)-x, s&m)), 76/9, 322/12, 521/13)
– greybeard
Jan 17 at 8:04


















draft saved

draft discarded




















































Thanks for contributing an answer to Code Review Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f163132%2fbetter-fibonacci-sequence-calculation%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Quarter-circle Tiles

Image
up vote 0 down vote favorite I have $99$ identical square tiles, each with a quarter-circle drawn on it like this: [asy] size(1.5cm); draw(Arc((2,0),1,90,180),red+1); draw((0,0)--(2,0)--(2,2)--(0,2)--(0,0)); [/asy] When I arrange the tiles in a $9times 11$ rectangular grid, each with a random orientation, what is the expected value of the number of full circles I form? I think this problem has to do with finding the chance any given 2x2 square has a circle, but I can't find it. expected-value share | cite | improve this question asked Nov 20 at 15:03 6minecraftninja 1 2
Read more

build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

Image
0 I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $epsilon$ -transition from the start state to the actual finite states of the given automaton. The start state of the given automaton will be my accepting(finite) state of my new one. All transitions will be reversed of course to recognize the reversed word. But how do I have to change the stack of the pushdown automaton? That's tricky. formal-languages automata context-free-grammar share | cite | improve this question edited Nov 29 '18 at 14:20 joee
Read more

Mont Emei

Image
Mont Emei.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Vue du sommet Wanfo du mont Emei Géographie Altitude 3 099  m , Wanfo Coordonnées 29° 31′ 11″ nord, 103° 19′ 57″ est Administration Pays   Chine Province Sichuan Ville-préfecture Leshan Géolocalisation sur la carte : Sichuan Mont Emei Géolocalisation sur la carte : Chine Mont Emei modifier   Paysage panoramique du mont Emei, incluant le paysage panoramique du grand Bouddha de Leshan *   Patrimoine mondial de l'UNESCO Passerelle en bois sur le versant ouest Pays   Chine Subdivision Sichuan Type Mixte Critères (iv) (vi) (x) Superficie 15 400 ha Numéro d’identification 779 Zone géographique Asie et Pacifique  ** Année d’inscription 1996 (20 e session) * Descriptif officiel UNESCO ** Classification géog
Read more