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

[DFS]

On 06/11/2014 10:45 PM, Ben Bacarisse wrote:

//GET LENGTH OF LONGEST WORD IN STRING

[snip]

I was thinking of using existing functions that are better
behaved that strtok:

int getMaxWordLength(const char *str, const char *delim)
{
size_t max = 0;
while (*str) {
size_t l = strcspn(str, delim);
if (l > max) max = l;
str += l + strspn(str, delim);
}
return max;
}

Programming interview test question - What is wrong
with this code, and why does it not matter?

The only thing I would change is moving the initialization of l out of
the while loop. And for my own style, add some brackets to the str += line:


int getMaxWordLength(const char *str, const char *delim)
{
size_t max = 0, l;
while (*str) {
l = strcspn(str, delim);
if (l > max) max = l;
str += (l + strspn(str, delim));
}
return max;
}


I doubt that's the right answer, though. My guess is it has something
to do with strcspn and strspn.

 

[DFS]

Regardless, I rewrote it without strtok, and to handle at most 3
delimiters. Seems to work well.

int getMaxWordLength(char *str, char *delim) {
int i=0,j=0,maxWordLen=0;

for(i=0;i<=strlen(str);i++) {
if(str==delim[0] || str==delim[1] || str==delim[2] ||
str=='\0') {

Here lurks a subtle bug:
1) if delim has less than three elements, the behaviour is undefined if
e.g. delim[2] is ever accessed.

Looks more than subtle to me!

2) if delim does have at least three elements but strlen(delim) < 2, the
conditional expression will reference characters that appear after
delim's null terminator, which may lead to surprising results.

Here's an example:

char words[] = "BACH:LISZT:CAGE";
char delimiters[3];
strcpy(delimiters, ":");
int length = getMaxWordLength(words, delimiters);
/* expecting length=5 i.e. length of longest word in {BACH,LISZT,CAGE} */

but what might actually happen:

char words[] = "BACH:LISZT:CAGE";
char delimiters[3];
/* delimiters[] contains three indeterminate values, say {'X','Y','Z'}
strcpy(delimiters, ":");
/* delimiters[] contains {':','\0','Z');
int length = getMaxWordLength(words, delimiters);
/* finding length=4 i.e. length of longest word in {BACH,LIS,T,CAGE} */

That's worrisome.

I may not have posted it, but in my example main() from which I called
the routine I always set char delim[N] = "space and/or some characters"

 

[DFS]

On 06/11/2014 10:45 PM, Ben Bacarisse wrote:

//GET LENGTH OF LONGEST WORD IN STRING
[snip]

I was thinking of using existing functions that are better
behaved that strtok:

int getMaxWordLength(const char *str, const char *delim)
{
size_t max = 0;
while (*str) {
size_t l = strcspn(str, delim);
if (l > max) max = l;
str += l + strspn(str, delim);
}
return max;
}

Programming interview test question - What is wrong
with this code, and why does it not matter?

What's wrong: that it doesn't do str += l + strspn(str + l, delim);

Why it doesn't matter: l will be zero at the top of the next iteration, which
doesn't affect the correctness of the value of max, and allows the strspn to
proceed from the new current str location.

And here's a visual display of why it doesn't matter:

[dfs@home files]$ ./temp
String: The titanosaur remains were eaten up.
Delimiter(s): | |
word lengths: 3,0,10,0,7,0,4,0,5,0,3, (max 10)

 

[DFS]

On 06/13/2014 01:59 PM, DFS wrote:
On 06/11/2014 10:45 PM, Ben Bacarisse wrote:
...
char longestWords[2] = "";

You have 2 bytes (one taken with a null) and you write the whole output
string to it. That scribbles on goodness know what other objects. Make
this array big enough for the intended use (or pass its size to
getLongestWords and use snprintf).

This kind of string-handling and memory mgmt stuff make C less "fun"
than it could be.

True - but for precisely that reason, it (or C++, which makes memory
management only slightly easier) is often the language used to implement
many of the more "fun" languages.

I never understood how C was used to write a C compiler, or in fact how
one computer language is developed using a different language.

I always thought you wrote the higher-level language in a lower-level
language.

I assume VB was developed with C, and C was developed with assembler?

The compiler bootstrapping thing much beloved in CS textbooks is
vanishing rare in the real world. Yes, there have been a few examples
(early C, is a notable one), but it almost never happens today. Cross
platform tools are far too available to go through the pain of a
bootstrapping cycle.

Further, the vast majority of compilers (and interpreters) implement
languages not particularly suited to implementing compilers (or
interpreters).

A compiler is just a program. It typically (and there are exceptions)
takes some sort of text file (or several) as input, chews on it for a
while, and then emits some sort of assembler-ish or machine-code-ish
object file. Again, a compiler is just a program that mostly does
some textual manipulation. Certainly fairly sophisticated textual
manipulation in many cases, but really not much more. Ultimately a
compiler (or a assembler, or a linker) is just a translator of a
source language into a target language.

That's a good way of thinking about it.

On most systems compilers are
not special programs*** at all, the inputs and output just being
ordinary files.

I don't get you. Isn't it 'special' (ie powerful, intelligent) to
generate a machine-ish object file from C code?

Compilers, like any program, should be written in languages that are
convenient for implementing them. That, rather mundanely, includes
many practical constraints, which pretty often trump the more
"interesting" technical consideration. Frankly if I were given the
task (without other constraints), of implementing a C compiler, I'd
almost certainly use Haskell.

I've seen a few people online praise Haskell.

Unfortunately practical considerations
would almost certainly prevent it. Issues of availability (limited
platforms), portability (Haskell actually does OK on that front,
except on the platform issue), support (really not that much out
there), skills base (not a lot of programmers), and whatnot, would
almost certainly drive me (and any rational manager) to C++ instead.
C++, of course, exists on almost every platform you'd likely actually
want to run a compiler on, has huge support, a massive tool base, is
reasonably portable, and has a massive skill base to draw from. I
wouldn't be likely to implement a C compiler in C. OTOH, 20 years ago
it would have been C as the first choice (and 20 years before that,
Fortran).

Which doesn't mean that unexpected languages haven't been used to
implement compilers. I'm aware of compilers written in Cobol*,
Basic** and Fortran, for example. Fortran used to actually be a
fairly popular choice, as it was by far the most widespread and
portable language (those annoying practical issues again), although
Fortran is not really very well suited to implementing a compiler.


*Realia Cobol, now a CA product, was originally written in Cobol (I
assume much of it still is, but I don't know), but it was originally
written on a mainframe platform using the (long) existing mainframe
compiler. As it was intended to be largely source compatible with the
mainframe language, that worked fairly well, although that's more an
example of cross-platform development, not bootstrapping.

**There were at least two Basic compilers for the Apple II that were
written in Basic. You could consider that to be an example of
bootstrapping, since MS and Apple wrote the interpreter first, and
that interpreter then hosted the (third party) compiler.

***On some systems, especially for the final executable programs,
there is some degree of specialness to the final output. On *nix, for
example, you need to set the proper attributes. On zOS, the
executable format is not really a "normal" file type, although there
are certainly system facilities for writing one.

Nice post. Thanks for the good info.

 

[Ben Bacarisse]

On 06/14/2014 10:18 AM, Kaz Kylheku wrote:

Yes, I intended the "str + l" to be in the strspn call but having written
something a bit like "str + l" I probably forgot that I hadn't (if you
see what I mean).

<snip>

 

[James Kuyper]

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

What I mean is you can define strcat as
char* strcat(char *tgt, const char *src)
{
return strncat(tgt, src, strlen(src));
}

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

 

[James Kuyper]

On 06/14/2014 11:03 AM, DFS wrote:
....

The only thing I would change is moving the initialization of l out of
the while loop. And for my own style, add some brackets to the str += line:


int getMaxWordLength(const char *str, const char *delim)
{
size_t max = 0, l;

You haven't moved the initialization of 'l' out of the loop; 'l' is
still uninitialized at this point.

This code makes no use of 'l' anywhere except inside the body of the
while() loop, and the value at the end of a given pass through the loop
gets overwritten at the start of the very next pass. Why give 'l' a
wider scope than necessary?

while (*str) {

'l' doesn't become initialized until the first time the following line
gets executed:

 

[DFS]

[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;
}

I want to try those exercises you talk about below, but you snipped my
post (all of main()), so I can't tell what you're talking about:

A few comments...

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

Are you referring to the elapsed time calculations in main()?


int main(void) {
int i,j;
struct timespec start, end;
double et;

for (i = 30; i <= 44; i++) {
clock_gettime(CLOCK_MONOTONIC_RAW, &start);
j = Fib(i);
clock_gettime(CLOCK_MONOTONIC_RAW, &end);
et = (end.tv_sec-start.tv_sec) + ((end.tv_nsec-start.tv_nsec) /
BILLION);
printf("Fibonacci %d = %d (%.2f seconds)\n", i, j, et);
}
}

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.

4. Using d'Ocagne's identity, an integer four parameter
recursive version can be written that is both 64-bit
exact and runs faster than the floating point version.

Integer versions of what?

 

[BartC]

On 06/14/2014 01:26 AM, Tim Rentsch wrote:

Are you referring to the elapsed time calculations in main()?

I think this is about FibBinet() function which might not give an exact
result (and that it can't represent every whole number which needs 52 to 64
bits or thereabouts, whereas a 64-bit int type can).

Integer versions of what?

Presumably of a Fibonacci function. For example, this simple iterative
version:

unsigned long long int myfib(int num) {
unsigned long long int a,b,t;
int i;
a=0;
b=1;
for (i=0; i<num; ++i){
t=a+b;
a=b;
b=t;
}
return a;
}

calculates myfib(44) more than 10 times faster than FibBinet(), and handles
values up 64 bits exactly, despite using a loop.

 

[Jorgen Grahn]

I thought gcc would if str where declared const,

Perhaps I'm missing some contect (the declaration of 'str' isn't shown
above) but if the compiler cannot prove that the 'const char* str'
isn't modified inside the loop through some alias, the 'const' doesn't
help.

but it doesn't which
just goes to show you can't rely on these things! Sun Studio cc inlines
strlen, but again, it doesn't optimise to a single call.

/Jorgen

 

[DFS]

[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;
}

A few comments...

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
and add them together.

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


But I notice Fib(72) and up are slightly different from the FibBinet()
results

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


int main(void) {
long long a,b;
for (int i=0;i<=100;i++) {
a = Fib(i);
b = FibBinet(i);
if(a != b) {
printf("Fib(%d) = %-*llu Binet = %llu\n", i,22,a,b);
}
}
}


[dfs@home misc]$ ./Fibonacci
Fib(72) = 498454011879264 Binet = 498454011879265
Fib(73) = 806515533049393 Binet = 806515533049395
Fib(74) = 1304969544928657 Binet = 1304969544928660
Fib(75) = 2111485077978050 Binet = 2111485077978055
Fib(76) = 3416454622906707 Binet = 3416454622906715
Fib(77) = 5527939700884757 Binet = 5527939700884771
Fib(78) = 8944394323791464 Binet = 8944394323791488
Fib(79) = 14472334024676221 Binet = 14472334024676260
Fib(80) = 23416728348467685 Binet = 23416728348467744
Fib(81) = 37889062373143906 Binet = 37889062373144008
Fib(82) = 61305790721611591 Binet = 61305790721611752
Fib(83) = 99194853094755497 Binet = 99194853094755776
Fib(84) = 160500643816367088 Binet = 160500643816367552
Fib(85) = 259695496911122585 Binet = 259695496911123328
Fib(86) = 420196140727489673 Binet = 420196140727490880
Fib(87) = 679891637638612258 Binet = 679891637638614272
Fib(88) = 1100087778366101931 Binet = 1100087778366105088
Fib(89) = 1779979416004714189 Binet = 1779979416004719360
Fib(90) = 2880067194370816120 Binet = 2880067194370824704
Fib(91) = 4660046610375530309 Binet = 4660046610375544832
Fib(92) = 7540113804746346429 Binet = 7540113804746369024

Fib(93) = 12200160415121876738 Binet = 9223372036854775808
Fib(94) = 1293530146158671551 Binet = 9223372036854775808
Fib(95) = 13493690561280548289 Binet = 9223372036854775808
Fib(96) = 14787220707439219840 Binet = 9223372036854775808
Fib(97) = 9834167195010216513 Binet = 9223372036854775808
Fib(98) = 6174643828739884737 Binet = 9223372036854775808
Fib(99) = 16008811023750101250 Binet = 9223372036854775808
Fib(100) = 3736710778780434371 Binet = 9223372036854775808

Also, from (93) onward the Fib() results look random, while the
FibBinet() result is always 9223372036854775808 (highest 64-bit number+1).

4. Using d'Ocagne's identity, an integer four parameter
recursive version can be written that is both 64-bit
exact and runs faster than the floating point version.

I couldn't find much on the web about d'Ocagne's identity, other than a
description and this page.

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


int main(void) {
int a=-10,b=10;
printf("\nd'Ocagne identity =
(Fib(m)*Fib(n+1))-(Fib(n)*Fib(m+1))=(-1^n)*Fib(m-n)\n\n");
for (int i=a;i<=b;i++) {
for (int j=a;j<=b;j++) {
docagne(i,j);
}
}
}

I leave 3 and 4 as exercises (but feel free to ask for
help if you get stuck).

Cool exercises!

I'm stuck on using docagne to generate the Fib series, and on the
recursive stuff. I do like the idea of recursive functions - they seem
tidier or something.

 

[DFS]

On 06/14/2014 11:03 AM, DFS wrote:
...

You haven't moved the initialization of 'l' out of the loop; 'l' is
still uninitialized at this point.

I meant 'move the declaration'.

This code makes no use of 'l' anywhere except inside the body of the
while() loop, and the value at the end of a given pass through the loop
gets overwritten at the start of the very next pass. Why give 'l' a
wider scope than necessary?

So you recommend declaring and initializing it inside the loop?

I figured it used more resources that way, than declaring it outside and
initializing it inside.

 

[Kaz Kylheku]

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 it creates an opportunity to demonstrate memoization.

 

[BartC]

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.

Suppose you wanted to test how well a language implemention handled lots of
function calls. Fib(44) using the recursive method requires over two billion
calls. An iterative version requires at most one call. Which one is a better
test?

(And ultimately both are pointless for actually delivering a Fibonacci
number; there are so few that will fit into even 64-bits, that a function
might just as well use a pre-calculated lookup-table.)

 

[James Kuyper]

On 06/14/2014 12:13 PM, Robert Wessel wrote: ....

I don't get you. Isn't it 'special' (ie powerful, intelligent) to
generate a machine-ish object file from C code?

Not in the sense he meant. Object files are just ordinary files in a
tightly specified format. No special permissions or abilities are needed
to write them, just a sufficiently good understanding of that format.

 

[James Kuyper]

On 6/14/2014 4:19 PM, James Kuyper wrote: ....


So you recommend declaring and initializing it inside the loop?

I do, strongly. Other people disagree with me, equally strongly,
recommending that automatic variables should be declared only at the top
of each function. You'll have to read our arguments and make your own
decision. There's nothing horribly wrong with the other approach, I just
think mine is better.

I figured it used more resources that way, than declaring it outside and
initializing it inside.

I'm curious - why? It must be set to a value at the start of each pass
through the loop, regardless of whether it's declared inside the loop or
outside of it.

If anything, it might use less resources, in some cases. By declaring
the variable inside the loop, it's lifetime ends when the body of the
loop completes. That means that the memory it occupied could be
available for some other variable declared later in the same function.
This isn't a particularly significant effect - any such variable can be
trivially analyzed to determine it will never be in use at the same time
as the first variable, and the two variables can therefore both be given
the same location in memory (unless your program takes the address of
both variables while they are in scope, which might force it to give
them distinct addresses).

There are three main reasons why I prefer declaring each identifier with
the tightest possible scope. Firstly, it reduces the likelihood of two
things being accidentally being given the same name in overlapping
scopes. Secondly, it means that you don't have to search as far from the
point of use to find the definition. Finally, if you delay definition of
a variable long enough, it's often possible to give it the only value it
will ever have, as part of the initialization. That allows you to define
it to be 'const', which often can enable warnings that would not
otherwise occur, and optimizations that would otherwise not be permitted.
In C90, declarations can occur only at the start of a block; but in
later versions of C, they can be mixed in with statements. Since the
scope of a variable name starts at the point of declaration, "tightest
possible scope" implies taking advantage of that fact to delay
definition even further - unless C90 compatibility is important.

Note: in principle, "tightest possible scope" could be taken as implying
the creation of a separate compound-statement block for each variable.
That would be ridiculous - it's not what I mean. I create
compound-statement blocks only as needed for other purposes, and define
each variable in the innermost of those blocks that gives it sufficient
scope for it's intended use.

 

[DFS]

Actually you get more calls than that.

Fib(40) is called 1 time (by the orignial call)
Fib(39) is called 1 time (Fib(40))
Fib(38) is called 2 times (Fib(40) Fib(39))
Fib(37) is called 3 times (Fib(39), 2* Fib(38))
Fib(36) is called 5 times (2*Fib(38), 3*Fib(37))
Fib(35) is called 8 times (3*Fib(37), 5*Fib(36))

Recognize the pattern?

Interesting. And given that 'naive' code, the times to calculate
follows the same pattern:

Fibonacci 30 = 832040 (0.03 seconds)
Fibonacci 31 = 1346269 (0.05 seconds)
Fibonacci 32 = 2178309 (0.08 seconds)
Fibonacci 33 = 3524578 (0.12 seconds)
Fibonacci 34 = 5702887 (0.20 seconds)
Fibonacci 35 = 9227465 (0.32 seconds)
Fibonacci 36 = 14930352 (0.52 seconds)
Fibonacci 37 = 24157817 (0.84 seconds)
Fibonacci 38 = 39088169 (1.36 seconds)
Fibonacci 39 = 63245986 (2.19 seconds)
Fibonacci 40 = 102334155 (3.55 seconds)
Fibonacci 41 = 165580141 (5.75 seconds)
Fibonacci 42 = 267914296 (9.30 seconds)
Fibonacci 43 = 433494437 (15.04 seconds)
Fibonacci 44 = 701408733 (24.34 seconds)


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

The # of calls Fib(0) thru Fib(40) is 866,988,831.

 

[DFS]

I think this is about FibBinet() function which might not give an exact
result (and that it can't represent every whole number which needs 52 to
64 bits or thereabouts, whereas a 64-bit int type can).


Presumably of a Fibonacci function. For example, this simple iterative
version:

unsigned long long int myfib(int num) {
unsigned long long int a,b,t;
int i;
a=0;
b=1;
for (i=0; i<num; ++i){
t=a+b;
a=b;
b=t;
}
return a;
}

calculates myfib(44) more than 10 times faster than FibBinet(), and
handles values up 64 bits exactly, despite using a loop.

I get strange numbers above Fib(92)


Fib(84) = 160500643816367088
Fib(85) = 259695496911122585
Fib(86) = 420196140727489673
Fib(87) = 679891637638612258
Fib(88) = 1100087778366101931
Fib(89) = 1779979416004714189
Fib(90) = 2880067194370816120
Fib(91) = 4660046610375530309
Fib(92) = 7540113804746346429

Fib(93) = 12200160415121876738
Fib(94) = 1293530146158671551
Fib(95) = 13493690561280548289
Fib(96) = 14787220707439219840
Fib(97) = 9834167195010216513
Fib(98) = 6174643828739884737
Fib(99) = 16008811023750101250
Fib(100) = 3736710778780434371




unsigned long long int myfib(int num) {
unsigned long long int a,b,t;
int i;
a=0;
b=1;
for (i=0; i<num; ++i){
t=a+b;
a=b;
b=t;
}
return a;
}



int main(void) {
for (int i=0;i<=100;i++) {
unsigned long long int j = myfib(i);
printf("Fib(%d) = %llu\n",i,j);
}
}

 

[Ike Naar]

A compiler is just a program. It typically (and there are exceptions)
takes some sort of text file (or several) as input, chews on it for a
while, and then emits some sort of assembler-ish or machine-code-ish
object file. Again, a compiler is just a program that mostly does
some textual manipulation. Certainly fairly sophisticated textual
manipulation in many cases, but really not much more. Ultimately a
compiler (or a assembler, or a linker) is just a translator of a
source language into a target language. On most systems compilers are
not special programs*** at all, the inputs and output just being
ordinary files.

One type of system where compilers *were* (or still are?) special
programs is the Burroughs large system series (later Unisys).
Executables were not ordinary files but has a special bit that
marked them as such, this bit could only be set by a program that
was declared a "compiler" by the system operator (I believe the
console command to achieve this was "MC" for "make compiler").

 

[Ike Naar]

Presumably of a Fibonacci function. For example, this simple iterative
version:

unsigned long long int myfib(int num) {
unsigned long long int a,b,t;
int i;
a=0;
b=1;
for (i=0; i<num; ++i){
t=a+b;
a=b;
b=t;
}
return a;
}

calculates myfib(44) more than 10 times faster than FibBinet(), and
handles values up 64 bits exactly, despite using a loop.

I get strange numbers above Fib(92)
[...]
Fib(93) = 12200160415121876738
Fib(94) = 1293530146158671551
Fib(95) = 13493690561280548289
Fib(96) = 14787220707439219840
Fib(97) = 9834167195010216513
Fib(98) = 6174643828739884737
Fib(99) = 16008811023750101250
Fib(100) = 3736710778780434371

Apparently unsigned long long int is a 64-bit type on your computer,
so it cannot store numbers larger than 18446744073709551615.