getMaxWordLength().... Ben Bacarisse wins!

[Keith Thompson]

A simple example which is related (in being numeric) but better (as it is
genuinely useful) is the following code to calculate the integer power of a
integer:

#include <stdint.h>

uint64_t upower(uint64_t a, int n) {

if (n<=0)
return 0; /* use 0 for fractional results */
else if (n==0)
return 1;
else if (n==1)
return a;
else if ((n & 1)==0)
return upower(a*a, n/2);
else
return upower(a*a, (n-1)/2)*a;
}

An iterative version (which doesn't just do n-1 multiplications) is not
impossible, but the recursive method is more natural.

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

 

[Jorgen Grahn]

You can always cherry-pick cases.

The question is how the language scales up to real problems which programmers
are trying to solve, not how elegantly you can write small functions which
execute well-studied and known algorithms.

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

 

[jacob navia]

Le 16/06/2014 15:26, DFS a écrit :

I saw something cool written in a few lines of Haskell:

http://projects.haskell.org/diagrams/gallery/FibCalls.html

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

 

[DFS]

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

Something that great should be locked in a vault forever.

 

[jacob navia]

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

Something that great should be locked in a vault forever.

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]

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 }

 

[Stefan Ram]

Ram usage

»RAM usage«

 

[jacob navia]

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

Ram usage: 2*sizeof(unsigned) +2*sizeof(long double)+sizeof(long long).

BUG!

That is
Ram usage: 2*sizeof(unsigned) +3*sizeof(long double).

 

[jacob navia]

Le 17/06/2014 02:34, Stefan Ram a écrit :

»RAM usage«

Sorry Mr Ram

 

[jacob navia]

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

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 }

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]

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

Never mind, you used the power function. But that's still likely
slower than the iterative version for fib(70).

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.

 

[DFS]

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.

You saying it calculates them all in 1ms, or it calculates and prints
them all in 1ms?

 

[Ian Collins]

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.

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

 

[jacob navia]

Le 17/06/2014 04:52, Ian Collins a écrit :

uint64_t fibs[maxFib];

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]

Le 17/06/2014 04:24, DFS a écrit :

You saying it calculates them all in 1ms, or it calculates and prints
them all in 1ms?

Yes. Less than 1ms actually.

 

[jacob navia]

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?

 

[Ian Collins]

Le 17/06/2014 04:52, Ian Collins a écrit :

uint64_t fibs[maxFib];

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!

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!