Ad
  • Default User Avatar

    'alr approved some time ago'

  • Custom User Avatar

    I still don't get where the (b - 1) * fib(n + 2) = (b - 1) * fib(n) + (b - 1) * fib(n + 1) comes from and why should I add this to the original equation. Please, explain in details or give me link to a book or some article where it is well-explained.

  • Custom User Avatar

    @Technetium_Phenol Oh, C'mon :D It's 21st century, forget Fortran and come to Scala :D

  • Default User Avatar

    The description is not correct.
    they have fib(0) = 1
    and there code doesn't calculate the fibonnaci series.

    Here is my alternative expansion.

    The function is recursively defined by:

    0.    fib(0) = 0
    1.    fib(1) = 1
    2.    fib(2) = 1
    3.    fib(n + 2) = fib(n) + fib(n + 1), if n + 2 > 1
    If one translates the above definition directly into a recursive function, the result is not very efficient. One can try memoization, but that requires lots of space and is not necessary. So, first step is to try and find a tail recursive definition. In order to do that we try to write both sides of equation 3) on the same form. Currently, the left side of the equation contains a single term, whereas the right side is the sum of two terms. A first attempt is to add fib(n + 1) to both sides of the equation:

    3.    fib(n + 1) + fib(n + 2) = fib(n) + 2 * fib(n + 1)

    The two sides of the equation look much more alike, but there is still an essential difference, which is the coefficient of the second term of each side. On the left side of the equation, it is 1 and, on the right, it is 2. To remedy this, we can introduce a variable b:

    3.     b * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (b + b) * fib(n + 1)

    We then subtract both sides by b * fib(n+1)

    3.     b * fib(n + 2) = b * fib(n) + (b + b)

    To try and return the tail to the function we add both sides by a * fib(n+1) to each side:

    3.     a * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (a + b) * fib(n + 1)

    Now the two sides have the same form (call it F), this function has the form:

    3.     F(c, d, e) = F(a, b, n+1) = F(a, a+b, n) = c * fib(e) + d * fib(e + 1)

    (Note if your confused by the above equation substitute the values into the furthest right function and you get)

    3.     a * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (a + b) * fib(n + 1) = c * fib(n) + d * fib(n + 1)

    Which we can simplify to:

    3.     F(a, b, n + 1) = F(b, a + b, n)

    We also have, by definition of F and fib:

    4.     F(a, b, 0) = a * fib(0) + b * fib(1) = b

    (Proove this with general equation)
    F(a, b, n + 1) with n = 0
    c * fib(n) + d * fib(n + 1)
    a * fib(0) + b * fib(0 + 1) as fib(0) = 0, fib(1) = 1
    b
    Also, by definition of F:
    5\.     fib(n) = F(1, 0, n) with a = 1, b = 0
    (Proove this with general equation)
    c * fib(e) + d * fib(e + 1)
    1 * fib(n) + 0 * fib(n + 1)
    1 * fib(n)
    6\.     F(a, b, 1) = a * fib(1) + b * fib(2) = a + b
    (Proove this with general equation)
    F(a, b, n + 1) with n = 1
    c * fib(n) + d * fib(n + 1)
    a * fib(1) + b * fib(1 + 1) as fib(1) = fib(2) = 1
    a + b
    The next step is to translate the above into code:
    def fib(n):
        if n == 0: return 0    # see 6. above
        def F(a, b, n):
            if n == 1: return a + b    # see 6. above
            return F(b, a + b, n - 1)  # see 3. above (F(a, b, n + 1) = F(b, a + b, n)) use n = n - 1
        return F(1, 0, n)              # see 5. above
    

    The final step (optional for languages that support tail call optimization) is to replace the tail recursive function F with a loop:

    def fib(n):
        if n == 0: return 0            # see 4. above
        a, b = 1, 0                    # see 5. above
        while n > 1:		
            a, b, n = b, a + b, n - 1  # see 3. above
        # n = 1 at this point
        return a + b<>                   # see 6. above 
    
  • Custom User Avatar

    (1) that each golfer plays "exactly once every day"
    That means same set of players everyday.

  • Custom User Avatar

    Thanks, approved. I don't know a thing about Fortran, so hopefully it's ok... :)

  • Custom User Avatar

    Thank you, if someone raises an issue I'll post the comment in here so that you get a notification, if thats OK.

    Thanks once again for the translation.

  • Custom User Avatar

    Thank you so much for the translation. Please could you keep an eye on it for a few weeks, in case anybody raises an issue as I have little exposure with Go.

  • Custom User Avatar
  • Custom User Avatar

    What version of gfortran are you using?

    5.4.0 https://packages.ubuntu.com/xenial/gfortran-5

    I would not use the -std=f2008 compiler directive. That actually makes the compiler more restrictive and probably would reject more code than accept.

    We can support multiple versions. So -std=f95, -std=f2003, -std=f2008, and -std=f2018 can be supported and the version can be enabled for the kata based on if the reference solution and the tests compiles with the version. Other languages works like this.

    Without -std=, it seems to default to -std=gnu which specifies

    a superset of the latest Fortran standard that includes all of the extensions supported by GNU Fortran, although warnings will be given for obsolete extensions not recommended for use in new code.

    https://gcc.gnu.org/onlinedocs/gfortran/Fortran-Dialect-Options.html

    What "the latest Fortran standard" means depends on the specific version of gfortran and I'd like to avoid that so we have better idea what exactly is supported.

    I'll update gfortran to the latest and experiment with options.

  • Custom User Avatar

    How did you find this super old post? :/

    You can open an issue to request to add those Fortran versions on runner repository. There's an issue template for that.

    It currently just does gfortran -o test solution.f95 tests.f95 && exec ./test. I'm assuming we can add variations by using -std=f2008. We can discuss what needs to be done to add support once you open the issue.

  • Custom User Avatar
  • Default User Avatar

    The explanation does not say to add b, but to introduce a variable b. You have fib(n + 1) + fib(n + 2) = fib(n) + 2 * fib(n + 1). Add this equation to the equation (b - 1) * fib(n + 2) = (b - 1) * fib(n) + (b - 1) * fib(n + 1) and you get: fib(n + 1) + b * fib(n + 2) = b * fib(n) + (b + 1) * fib(n + 1). For the next step, add (a - 1) * fib(n + 1) to both sides of the last equation.