Why does strcat mess up the tokens in strtok (and strtok_r)?

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

  1. DFS

    BartC Guest

    With signed int64, you can get up to fib(92), but with unsigned int64 as I
    used, you can go one step further with fib(93), which is shown correctly

    For bigger Fibonacci numbers, you need to use some extended precision
    library. (So using my own home-made library, it calculated Fib(1000000),
    which took 6 minutes to get an exact result (with some 200000 digits). A
    proper library will be faster. But neither would use recursion, as the
    universe will not last that long.)
    BartC, Jun 16, 2014
    1. Advertisements

  2. DFS

    James Kuyper Guest

    On 06/16/2014 12:45 AM, DFS wrote:
    Here's how to do it with a counter passed in as an argument:

    int Fib(int num, unsigned long* FibCounter)
    i = Fib(num-1, FibCounter) + Fib(num-2, FibCounter);
    James Kuyper, Jun 16, 2014
    1. Advertisements

  3. DFS

    Tim Rentsch Guest

    The Standard specifies them as restrict-qualified (for strcat,
    among others), and an implementation may choose to define
    strcat() so that they are restrict-qualified, but it isn't
    required to. Leaving off the 'restrict' qualifiers here still
    produces a valid implementation of strcat() (and having nothing
    to do with whether the parameters for strncat() are qualified
    in this way).

    (Someone may want to remind JK of this since he does not
    read my postings.)
    Tim Rentsch, Jun 16, 2014
  4. DFS

    Tim Rentsch Guest

    But that's a different algorithm. The recursive algorithm
    corresponding to the iterative version is also O(N).
    And there is a different recursive algorithm that
    is O( log N ), and IMO much easier to program recursively
    than iteratively.
    Tim Rentsch, Jun 16, 2014
  5. DFS

    James Kuyper Guest

    You've already been told that this is not the case, but it just occurred
    to me that the above question might reflect a misconception about the
    meaning of a for() loop, and I don't think anyone had directly addressed
    that possibility. If you already understand all of following, I
    apologize for thinking that you might not have.

    There are four basic parts of any for() loop, I'll call them A, B, C, and D:

    for(A; B; C) D

    A and C are optional. If B is missing, it gets replaced by a nonzero
    A can either be an expression, or a declaration.
    B and C are simply expressions.
    D can be any type of statement, most commonly a compound statement,
    which is why some people get the mistaken impression that '{' and '}'
    are port of the for-loop syntax.

    In terms of the most basic C statement types, such a for loop is
    essentially equivalent to:

    D // D is a complete statement - no ';' is needed
    goto beginning;

    Note that, in particular, this means that B is evaluated every time the
    if() is checked.
    James Kuyper, Jun 16, 2014
  6. DFS

    Tim Rentsch Guest

    You mean neither would use a naive recursive algorithm.
    A recursive definition based on a different algorithm
    is just fine. I wrote a recursive fibonacci program
    in python, about five lines of code, and it calculated
    fibonacci( 1000000 ) in a second or two (my subjective
    impression between hitting the return key and when the
    result started printing).
    Tim Rentsch, Jun 16, 2014
  7. DFS

    Tim Rentsch Guest

    Oftentimes when using a recursive formulation there needs to be a
    helper function that has an extra parameter or two where the real
    work is done (disclaimer: not compiled or tested):

    typedef unsigned long long U64;

    static U64 fibber( U64 a, U64 b, unsigned i, unsigned n );

    fibonacci( unsigned n ){
    return fibber( 1, 0, 0, n );

    fibber( U64 a, U64 b, unsigned i, unsigned n ){
    return i == n ? b : fibber( b, a+b, i+1, n );

    Can you see the relationship between this recursive definition
    and your iterative one? Incidentally, notice how the recursive
    call means we don't need the temporary variable F.

    Probably you can revise this code so the helper function takes
    only three parameters rather than four. Try it!

    Here is the basic outline. From d'Ocagne we know

    f( 2n ) == ( f(n-1) + f(n+1) ) * f(n)
    f( 2(n-1) ) == ( f(n-2) + f(n) ) * f(n-1)

    If you play around with these, and keeping in mind the
    identity that f(k-1) + f(k) == f(k+1), you should find that
    values for f( 2n-1 ), f( 2n ), and f( 2n+1 ) can be
    expressed in terms of just f(n-1) and f(n)

    f( 2n-1 ) == ... something in terms of f(n-1) and f(n) ...
    f( 2n ) == ... something in terms of f(n-1) and f(n) ...
    f( 2n+1 ) == ... something in terms of f(n-1) and f(n) ...

    This means if we know f(k-1) and f(k), we can calculate either of
    the pairs { f(2k-1), f(2k) } or { f(2k), f(2k+1) } using a small
    number of additions and multiplications. That in turn suggests
    we can use the binary decomposition of n to ascend a chain where
    at each step we either "double" or "double and add one", ie,
    choose either the first pair or the second pair. Starting off
    with f(-1) == 1 and f(0) == 0, and looking at the bits of n
    starting at the high-order bit, this method will calculate
    fibonacci(n) in only O( log n ) steps.
    Tim Rentsch, Jun 16, 2014
  8. DFS

    BartC Guest

    Yes I meant the usual Fibonacci routine.
    It must use a highly optimised way of doing it, some way that avoids the
    million or so big-integer additions that are normally needed.

    Using a simple iterative loop in Python, it took 3 1/2 minutes to calculate
    fib(1000000) on my machine.
    BartC, Jun 16, 2014
  9. DFS

    James Kuyper Guest

    What kind of timing do you get from the python example given in
    James Kuyper, Jun 16, 2014
  10. DFS

    BartC Guest

    I've found what is touted as a faster algorithm, and it managed fib(1000000)
    in about 8 seconds (needing Python 3, which also executed the iterative
    version in some 30 seconds).

    I'm amazed, if it doesn't actually do all one million additions, that it
    manages to get every digit of the result spot-on (although I didn't look at
    each one, only the last few...).
    BartC, Jun 16, 2014
  11. DFS

    BartC Guest

    I couldn't that one to work. I just get a generator object returned instead
    of value. But I'd guess it would be similar to the iterative method, plus
    the overheads of the generator mechanism (which involves having to call it
    999999 times before you can get the millionth).
    BartC, Jun 16, 2014
  12. DFS

    James Kuyper Guest

    Of course, you're right. :-(
    James Kuyper, Jun 16, 2014
  13. DFS

    BartC Guest

    20% or 20x? Doing a bit of optimising (which the compiler will do anyway -
    apparently) will not get you a 20x speed improvement. Getting a faster
    machine, yes, if it's 10x faster!

    Using the method requiring a million adds of some biggish numbers (the
    result has 200,000 digits), took (C)Python 2.5 210 seconds, and Python 3.1
    30 seconds, but they will use an underlying C library to do the actual work.
    I can't see the overheads of invoking it from Python accounting for 90% or
    more of execution time.

    I think however that to get it down to 1 second, some cleverer code is
    needed than calculating all 1000000 terms. The faster method I found was not
    recursive (so I don't know what algorithm Tim was talking about), (but I
    applied it anyway to my slow library, and it was twice as fast as the simple
    method. But it uses multiplies, which doesn't sound good).
    BartC, Jun 17, 2014
    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.