Fibonacci function or sequence

  • The Fibonacci sequence is a sequence of numbers, where every number in the sequence is the sum of the two numbers preceding it. The first two numbers in the sequence are both 1. Here are the first few terms:


    1 1 2 3 5 8 13 21 34 55 89 ...



    Write the shortest code that either:



    • Generates the Fibonacci sequence without end.



    • Given n calculates the nth term of the sequence. (Either 1 or zero indexed)




    You may use standard forms of input and output.


    (I gave both options in case one is easier to do in your chosen language than the other.)




    For the function that takes an n, a reasonably large return value (the largest Fibonacci number that fits your computer's normal word size, at a minimum) has to be supported.




    Leaderboard




    /* Configuration */

    var QUESTION_ID = 85; // Obtain this from the url
    // It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
    var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
    var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
    var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

    /* App */

    var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

    function answersUrl(index) {
    return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
    }

    function commentUrl(index, answers) {
    return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
    }

    function getAnswers() {
    jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
    answers.push.apply(answers, data.items);
    answers_hash = [];
    answer_ids = [];
    data.items.forEach(function(a) {
    a.comments = [];
    var id = +a.share_link.match(/\d+/);
    answer_ids.push(id);
    answers_hash[id] = a;
    });
    if (!data.has_more) more_answers = false;
    comment_page = 1;
    getComments();
    }
    });
    }

    function getComments() {
    jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
    data.items.forEach(function(c) {
    if (c.owner.user_id === OVERRIDE_USER)
    answers_hash[c.post_id].comments.push(c);
    });
    if (data.has_more) getComments();
    else if (more_answers) getAnswers();
    else process();
    }
    });
    }

    getAnswers();

    var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

    var OVERRIDE_REG = /^Override\s*header:\s*/i;

    function getAuthorName(a) {
    return a.owner.display_name;
    }

    function process() {
    var valid = [];

    answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
    if(OVERRIDE_REG.test(c.body))
    body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
    valid.push({
    user: getAuthorName(a),
    size: +match[2],
    language: match[1],
    link: a.share_link,
    });
    else console.log(body);
    });

    valid.sort(function (a, b) {
    var aB = a.size,
    bB = b.size;
    return aB - bB
    });

    var languages = {};
    var place = 1;
    var lastSize = null;
    var lastPlace = 1;
    valid.forEach(function (a) {
    if (a.size != lastSize)
    lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
    .replace("{{NAME}}", a.user)
    .replace("{{LANGUAGE}}", a.language)
    .replace("{{SIZE}}", a.size)
    .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
    });

    var langs = [];
    for (var lang in languages)
    if (languages.hasOwnProperty(lang))
    langs.push(languages[lang]);

    langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
    });

    for (var i = 0; i < langs.length; ++i)
    {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
    .replace("{{NAME}}", lang.user)
    .replace("{{SIZE}}", lang.size)
    .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
    }

    }

    body {
    text-align: left !important;
    display: block !important;
    }

    #answer-list {
    padding: 10px;
    width: 290px;
    float: left;
    }

    #language-list {
    padding: 10px;
    width: 290px;
    float: left;
    }

    table thead {
    font-weight: bold;
    }

    table td {
    padding: 5px;
    }

    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
    <link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
    <div id="language-list">
    <h2>Shortest Solution by Language</h2>
    <table class="language-list">
    <thead>
    <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
    </table>
    </div>
    <div id="answer-list">
    <h2>Leaderboard</h2>
    <table class="answer-list">
    <thead>
    <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
    </table>
    </div>
    <table style="display: none">
    <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
    </tbody>
    </table>
    <table style="display: none">
    <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
    </tbody>
    </table>




    I am sort of waiting for a response like "f", 1 byte, in my math based golf language.

  • Perl 6, 10 chars:



    Anonymous infinite fibonacci sequence list:



    ^2,*+*...*


    Same as:



    0, 1, -> $x, $y { $x + $y } ... Inf;


    So, you can assign it to an array:



    my @short-fibs = ^2, * + * ... *;


    or



    my @fibs = 0, 1, -> $x, $y { $x + $y } ... Inf;


    And get the first eleven values (from 0 to 10) with:



    say @short-fibs[^11];


    or with:



    say @fibs[^11];


    Wait, you can get too the first 50 numbers from anonymous list itself:



    say (^2,*+*...*)[^50]


    That returns:



    0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
    10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
    1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169
    63245986 102334155 165580141 267914296 433494437 701408733 1134903170
    1836311903 2971215073 4807526976 7778742049


    And some simple benchmark:



    real    0m0.966s
    user 0m0.842s
    sys 0m0.080s


    With:



    $ time perl6 -e 'say (^2, *+* ... *)[^50]'


    EOF


    I wouldn't even think of `^2` as replacement for `0,1`. +1

    This is no longer valid, you will have to write it as `|^2,*+*...*`, which is the same number of bytes as `0,1,*+*...*`.

    Perl is so weird.

    What version of Perl 6 was this answer written in?

    @CalculatorFeline There was a big change known as GLR (Great List Refactor) which happened shortly before the first official release which was on 2015-12-25. This code would have worked right up until that time.

    `time perl6 -e 'say (|^2, *+* ... *)[^50]'` now reports 0.224s user time with the current version.

    @BradGilbertb2gills maybe Marco should change the title to "Perl 6 release candidate 1.2.3", but if a spec and interpreter were ever published for it then it's a valid language for PPCG.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM