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

B

#### BartC

DFS said:
On 06/15/2014 04:46 AM, BartC wrote:

I get strange numbers above Fib(92)
Fib(92) = 7540113804746346429

Fib(93) = 12200160415121876738
unsigned long long int myfib(int num) {
unsigned long long int a,b,t;

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

J

#### James Kuyper

On 06/16/2014 12:45 AM, DFS wrote:
....
I used a global variable (I don't know any other way) to keep track of
how many calls to Fib() were made:

int Fib(int num) {
int i=0;
FibCounter++; //global
if(num==0) {i = 0;}
else if(num==1) {i = 1;}
else if(num>=2) {i = Fib(num-1) + Fib(num-2);}
return i;
}

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

T

#### Tim Rentsch

James Kuyper said:
On 06/14/2014 01:30 AM, Barry Schwarz wrote:
...

'tgt' and 'src' are supposed to be restrict-qualified (C99 and later).

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

T

#### Tim Rentsch

Robert Wessel said:
[snip]
Fast is good!

I wrote this last night:

======================================================================

//FIBONACCI SERIES
//0,1,1,2,3,5,8,13,21,34,55,89...

[...]

int Fib(int num) {
int i;
if(num==0) {i = 0;}
else if(num==1) {i = 1;}
else if(num>=2) {i = Fib(num-1) + Fib(num-2);}
return i;
}

[...]

// Then I found Binet's formula:
// http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

int FibBinet(int num) {
int i = (pow(1+sqrt(5),num) - pow(1-sqrt(5),num)) / (pow(2,num) *
sqrt(5));
return i;
}

1. Using floating point may give problems with rounding
behavior.

2. Using double probably limits the results to 50-ish bits
(ie, on common processors).

3. It's easy to write an integer version that gives results
exact to 64 bits, and fairly quickly, by simple iteration, or
three parameter recursion.

I think I got it (simple iteration)! I took another look at my orig
code/output and noticed you don't have to calculate Fib(N) recursively
each iteration, you just have to keep track of the previous 2 numbers

No wonder it was so slow: by the time it got to Fib(40) it had done
Fib(1) through Fib(39) up to thirty-nine times each.

It's far worse than that. The Fibonacci algorithm commonly used to
demonstrate recursion is perhaps one of the stupidest implementations
of an algorithm ever. The naive recursive version is O(2**N) whereas
the straightforward iterative version is O(N).

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.

J

#### James Kuyper

On 06/13/2014 03:58 PM, Keith Thompson wrote: ....

Doesn't the compiler calculate strlen(str) just once, when the for loop
is initialized?

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.

T

#### Tim Rentsch

BartC said:
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.)

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

T

#### Tim Rentsch

DFS said:
[snip]
Fast is good!

I wrote this last night:

=======================================================================

//FIBONACCI SERIES
//0,1,1,2,3,5,8,13,21,34,55,89...

[...]

int Fib(int num) {
int i;
if(num==0) {i = 0;}
else if(num==1) {i = 1;}
else if(num>=2) {i = Fib(num-1) + Fib(num-2);}
return i;
}

[...]

// Then I found Binet's formula:
// http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

int FibBinet(int num) {
int i = (pow(1+sqrt(5),num) - pow(1-sqrt(5),num)) / (pow(2,num) *
sqrt(5));
return i;
}

1. Using floating point may give problems with rounding
behavior.

2. Using double probably limits the results to 50-ish bits
(ie, on common processors).

3. It's easy to write an integer version that gives results
exact to 64 bits, and fairly quickly, by simple iteration, or
three parameter recursion.

I think I got it (simple iteration)! I took another look at my orig
code/output and noticed you don't have to calculate Fib(N) recursively
each iteration, you just have to keep track of the previous 2 numbers

No wonder it was so slow: by the time it got to Fib(40) it had done
Fib(1) through Fib(39) up to thirty-nine times each.

New version:

long long Fib(int num) {
long long a=0,b=1,F;int i=0;
while(i<=num){
if(i<2){F=i;}else{F=a+b;a=b;b=F;}
i++;
}
return F;
}

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!

I couldn't find much on the web about d'Ocagne's identity, other than

http://2000clicks.com/mathhelp/BasicRecurrenceRelationsFibonacci.aspx

So far all I've been able to do is prove the identity holds (sometimes
- it seems to hold where m>=n for integers >=0):

int docagne(int m, int n) {
printf("docagne %d,%d: ", m,n);
if((Fib(m)*Fib(n+1))-(Fib(n)*Fib(m+1))==pow(-1,n)*Fib(m-n)) {
printf("identity holds\n");
} else {
printf("identity (or DFS) fails\n");
}
return 0;
}

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.

B

#### BartC

Tim Rentsch said:
You mean neither would use a naive recursive algorithm.

Yes I meant the usual Fibonacci routine.
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).

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.

J

#### James Kuyper

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.

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

B

#### BartC

BartC said:
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.

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

B

#### BartC

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

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

J

#### James Kuyper

James Kuyper schrieb:

ITYM
(*FibCounter)++

Of course, you're right. :-(

B

#### BartC

Robert Wessel said:
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.

A second is probably not that far off. I was able to get a 32-bit
pure C version to compute fib(1000000) in about 36 seconds on a
3.16GHZ Core2 Duo. This used long longs to avoid conditional code and
cause the compiler to generate ADCs (IOW, the inner loops looked
like:

carry = 0;
for (i=0; i<cx->size; i++)
{
t1 = (unsigned long long)bx->v + (unsigned long
long)cx->v + carry;
carry = t1 >> 32;
a->v = t1 & 0xffffffff;
}

This still generated a 19 instruction loop for what should have been a
mov/adc loop. The code was also a sloppy with copies (did far too
many: three for each Fibonacci iteration, when you could do it without
any).

Convert to 64 bits, and you get twice as much done per add, get rid of
the copies, unroll a bit, get a faster machine - I could see an

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

C
Replies
7
Views
782
Keith Thompson
K
S
Replies
6
Views
516
Ben Bacarisse
B
?
Replies
16
Views
3K
=?ISO-8859-1?Q?Une_b=E9vue?=
?
T
Replies
2
Views
743
Moi
M
K
Replies
2
Views
662
Kelly B
K
D
Replies
2
Views
679
Lawrence Kirby
L
D
Replies
4
Views
611
default
D
B
Replies
15
Views
985
Keith Thompson
K