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

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

1. BartCGuest

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
above.

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

2. James KuyperGuest

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)
{
...
if(FibCounter)
*FibCounter++;
...
i = Fib(num-1, FibCounter) + Fib(num-2, FibCounter);
...
}

James Kuyper, Jun 16, 2014

3. Tim RentschGuest

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

Tim Rentsch, Jun 16, 2014
4. Tim RentschGuest

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. James KuyperGuest

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
constant.
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:

{
A;
beginning:
if(B)
{
D // D is a complete statement - no ';' is needed
C;
goto beginning;
}
}

Note that, in particular, this means that B is evaluated every time the
if() is checked.

James Kuyper, Jun 16, 2014
6. Tim RentschGuest

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. Tim RentschGuest

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 );

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

U64
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. BartCGuest

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. James KuyperGuest

What kind of timing do you get from the python example given in
<http://en.wikipedia.org/wiki/Corecursion#Fibonacci_sequence>?

James Kuyper, Jun 16, 2014
10. BartCGuest

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. BartCGuest

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. James KuyperGuest

Of course, you're right. :-(

James Kuyper, Jun 16, 2014
13. BartCGuest

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