getMaxWordLength().... Ben Bacarisse wins!

Discussion in 'C Programming' started by DFS, Jun 14, 2014.

  1. Some quibbles (none of which are meant to detract from the main point):

    Surely upower(1, -1) should be 1, not 0. upower(0, -1) (or with any
    negative exponent) is an error; it's not clear how that should be
    handled. You might make n an unsigned int, since negative exponents
    aren't particularly useful for an integer power function.

    In the last return statement, (n-1)/2 could be written as n/2, since n
    is odd and integer division truncates anyway. I might put the
    multiplication by a at the beginning of the expression, just to make it
    stand out more:

    return a * upower(a*a, n/2);
     
    Keith Thompson, Jun 16, 2014
    #21
    1. Advertisements

  2. DFS

    Jorgen Grahn Guest

    I studied functional programming for 1--2 years, but I never quite got
    the answer to that first question (and I was one of the rather few
    students who liked it).

    I now work with a real product where the big and important part is
    written in a functional language, and that doesn't really help either!
    The product is alive and well, but would it have been better off if
    written in C or C++? Impossible to tell.

    /Jorgen
     
    Jorgen Grahn, Jun 16, 2014
    #22
    1. Advertisements

  3. DFS

    jacob navia Guest

    Le 16/06/2014 15:26, DFS a écrit :
    Well I have a version in C that is faster than any of those recursive
    calls in ANY language, even pure assembly.

    It will beat any recursive function in C, asm, fortran, APL, basic,
    java, C# C++... It will beat the memoizing half solutions, all table
    based stuff...

    It will beat ANYTHING.

    Interested?

    jacob
     
    jacob navia, Jun 17, 2014
    #23
  4. DFS

    DFS Guest


    Something that great should be locked in a vault forever.
     
    DFS, Jun 17, 2014
    #24
  5. DFS

    jacob navia Guest

    Le 17/06/2014 01:59, DFS a écrit :
    :)

    Here is the test program:
    14 int main(int argc,char *argv[])
    15 {
    16 int i,limit;
    17
    18 if (argc > 1) limit = atoi(argv[1]);
    19 else limit = 50;
    20 if (limit > 70) {
    21 printf("Warning: Results beyond fib(70) are not accurate in
    the last digits\n");
    22 if (limit > MAXFIB) {
    23 printf("Error, max is %d. Results beyond that are
    wrong\n",MAXFIB);
    24 limit = MAXFIB;
    25 }
    26 }
    27 for (i=0; i<limit; i++) {
    28 printf("Fib(%d)=%llu\n",i,fib(i));
    29 }
    30 return 0;
    31 }

    This executes in 1 ms for input of 70. It calculates each fib from
    scratch AGAIN!
     
    jacob navia, Jun 17, 2014
    #25
  6. DFS

    jacob navia Guest

    1 #include <math.h>
    2 #include <stdio.h>
    3 #include <stdlib.h>
    4 #define SQRT5 2.236067977499789696409173L
    5 #define MAXFIB 93
    6 static unsigned long long fib(int n)
    7 {
    8 long double phi = (1+SQRT5)/2.0;
    9 long double phi_n = pow(phi,(long double)n);
    10 long double result = phi_n/SQRT5;
    11 return round(result);
    12 }
    13
    14 int main(int argc,char *argv[])
    15 {
    16 unsigned int i, limit;
    17
    18 if (argc > 1) limit = atoi(argv[1]);
    19 else limit = 50;
    20 if (limit > 70) {
    21 printf("Warning: Results beyond fib(70) are not accurate in
    the last digits\n");
    22 if (limit > MAXFIB) {
    23 printf("Error, max is %d. Results beyond that are
    wrong\n",MAXFIB);
    24 limit = MAXFIB;
    25 }
    26 }
    27 for (i=0; i<limit; i++) {
    28 printf("Fib(%d)=%llu\n",i,fib(i));
    29 }
    30 return 0;
    31 }
     
    jacob navia, Jun 17, 2014
    #26
  7. DFS

    Stefan Ram Guest

    »RAM usage«
     
    Stefan Ram, Jun 17, 2014
    #27
  8. DFS

    jacob navia Guest

    Le 17/06/2014 02:32, jacob navia a écrit :
    BUG!

    That is
    Ram usage: 2*sizeof(unsigned) +3*sizeof(long double).
     
    jacob navia, Jun 17, 2014
    #28
  9. DFS

    jacob navia Guest

    Le 17/06/2014 02:34, Stefan Ram a écrit :
    Sorry Mr Ram :)
     
    jacob navia, Jun 17, 2014
    #29
  10. DFS

    jacob navia Guest

    Le 17/06/2014 02:32, jacob navia a écrit :
    Much too clear!

    I should have written:

    return (pow((1+SQRT5)/2.0,(long double)n))/SQRT5;

    That looks better for the uninitiated.
     
    jacob navia, Jun 17, 2014
    #30
  11. DFS

    jacob navia Guest

    Le 17/06/2014 03:05, Robert Wessel a écrit :
    Never.

    Just reproduce my program in Haskell: print the list of all fibs from
    zero to n (n being an input of the program). Each time the fib is
    recalculated from scratch.

    Do it in 1ms if possible.
     
    jacob navia, Jun 17, 2014
    #31
  12. DFS

    DFS Guest


    You saying it calculates them all in 1ms, or it calculates and prints
    them all in 1ms?
     
    DFS, Jun 17, 2014
    #32
  13. DFS

    Ian Collins Guest

    Except a crude C++ version that does the grunt work at compile time?

    #include <stdio.h>
    #include <stdint.h>
    #include <stdlib.h>

    template <unsigned N>
    struct Fibonacci
    {
    static const uint64_t value = Fibonacci<N-1>::value +
    Fibonacci<N-2>::value;
    };

    template <>
    struct Fibonacci<1> { static const uint64_t value = 1; };

    template <>
    struct Fibonacci<0> { static const uint64_t value = 0; };

    const size_t maxFib = 93;

    uint64_t fibs[maxFib];

    template <unsigned N> uint64_t loadFib()
    {
    fibs[N] = Fibonacci<N>::value;
    loadFib<N-1>();
    return fibs[N];
    }

    template <> uint64_t loadFib<0>()
    {
    fibs[0] = Fibonacci<0>::value;
    return 0;
    }

    const uint64_t big = loadFib<maxFib>();

    int main(int argc,char *argv[])
    {
    unsigned limit = 50;

    if( argc > 1 ) limit = atoi(argv[1]);

    for( unsigned i=0; i<limit; i++)
    {
    printf("Fib(%d)=%llu\n",i,fibs);
    }

    return 0;
    }
     
    Ian Collins, Jun 17, 2014
    #33
  14. DFS

    jacob navia Guest

    Le 17/06/2014 04:52, Ian Collins a écrit :
    Small bug. It is

    uint64_t fibs[maxFib+1];

    according to g++. (Mac OS X)

    Your proposition is trivial to replicate in C. Just make a table of the
    first 93 values of fib and be done with it. No templates necessary!
     
    jacob navia, Jun 17, 2014
    #34
  15. DFS

    jacob navia Guest

    Le 17/06/2014 04:24, DFS a écrit :
    Yes. Less than 1ms actually.
     
    jacob navia, Jun 17, 2014
    #35
  16. DFS

    jacob navia Guest

    Le 17/06/2014 05:39, Robert Wessel a écrit :
    [snip]

    Nice, you were faster by 25%.

    Your advantage disappears however if instead of calling the general
    pow() function we use:

    8 static long double ipow(long double base, int exp)
    9 {
    10 long double result = 1;
    11 while (exp)
    12 {
    13 if (exp & 1)
    14 result *= base;
    15 exp >>= 1;
    16 base *= base;
    17 }
    18
    19 return result;
    20 }

    This makes my algorithm accelerate to just under 25% of the time needed
    by yours!

    Just 1/4 of your time. Nice isn't it?
     
    jacob navia, Jun 17, 2014
    #36
  17. DFS

    Ian Collins Guest

    The template is a convenient way to get the compiler to use compile time
    recursion to generate tables. Trivial in this case, but more fun with
    more complex examples. I think the code meets your requirements with no
    outside intervention!
     
    Ian Collins, Jun 17, 2014
    #37
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.