serious stuff
www.cubbi.com
personal
programming
fibonacci numbers
forth examples
postscript examples
muf examples
joy examples
j examples
scheme examples
hope examples
ocaml examples
haskell examples
prolog examples
c++ examples
java examples
assembly language examples
fortran examples
c examples
sh examples
awk examples
perl examples
tcl examples
asmix
hacker test
resume
science
martial arts
fun stuff
www.cubbi.org
|
C++
Date: 1986 (Standards: ISO/IEC 14882:1998, ISO/IEC 14882:2003)
Type: Object-oriented language with excessive features
Usage: Wide variety of software. This is the language I use at work.
ALGORITHM 1A: NAIVE BINARY RECURSION |
#include <iostream>
#include <stdexcept>
#include <vector>
long fib(int n) {
return n<2 ? n : fib(n-1) + fib(n-2);
}
long f(int n) {
if(n<0)
return n%2 ? fib(-n) : -fib(-n);
else
return fib(n);
}
void fib_print(int n) {
std::cout << n << "th Fibonacci number is " << f(n) << '\n';
}
int main(int argc, char** argv) {
std::vector<std::string> args(argv, argv+argc);
try {
fib_print(stoi(args.at(1)));
} catch (std::exception& ) {
std::cout << "Usage: " << args[0] << " <n>\n";
}
}
|
ALGORITHM 1B: CACHED BINARY RECURSION / MEMOIZATION
|
---|
#include <iostream>
#include <stdexcept>
#include <unordered_map>
#include <gmpxx.h>
#include <vector>
typedef std::unordered_map<int, mpz_class> memo;
mpz_class frec(int n, memo& m) {
memo::iterator i = m.find(n);
if(i!=m.end()) return i->second;
return n<2 ? n : m[n] = frec(n-1, m) + frec(n-2, m);
}
mpz_class fib(int n) {
memo m;
return frec(n, m);
}
mpz_class f(int n) {
if(n<0)
return n%2 ? fib(-n) : 0-fib(-n);
else
return fib(n);
}
void fib_print(int n) {
std::cout << n << "th Fibonacci number is "
<< f(n).get_str(10) << '\n';
}
int main(int argc, char** argv) {
std::vector<std::string> args(argv, argv+argc);
try {
fib_print(stoi(args.at(1)));
} catch (std::exception& ) {
std::cout << "Usage: " << args[0] << " <n>\n";
}
}
|
ALGORITHM 2A: CACHED LINEAR RECURSION / RANDOM-ACCESS CONTAINER |
#include <iostream>
#include <algorithm>
#include <sstream>
#include <gmpxx.h>
#include <deque>
mpz_class flrec(std::deque<mpz_class>& fl, int n)
{
fl.push_front(fl[0] + fl[1]);
return n<1 ? fl.front() : flrec(fl, n-1);
}
mpz_class fib(int n) {
std::deque<mpz_class> fl = {1, 0};
return n<2 ? n : flrec(fl, n-2);
}
mpz_class f(int n) {
if(n<0)
return n%2 ? fib(-n) : 0-fib(-n);
else
return fib(n);
}
void fib_print(int n) {
std::cout << n << "th Fibonacci number is "
<< f(n).get_str(10) << '\n';
}
int main(int argc, char** argv) {
std::vector<std::string> args(argv, argv+argc);
try {
fib_print(stoi(args.at(1)));
} catch (std::exception& ) {
std::cout << "Usage: " << args[0] << " <n>\n";
}
}
|
ALGORITHM 2B: LINEAR RECURSION WITH ACCUMULATORS |
#include <iostream>
#include <sstream>
#include <gmpxx.h>
#include <vector>
mpz_class fib(int x, mpz_class x1 = 0, mpz_class x2 = 1) {
return x<1 ? x1 : fib(x-1, x2+x1, x1);
}
mpz_class f(int n) {
if(n<0)
return n%2 ? fib(-n) : 0-fib(-n);
else
return fib(n);
}
void fib_print(int n) {
std::cout << n << "th Fibonacci number is "
<< f(n).get_str(10) << '\n';
}
int main(int argc, char** argv) {
std::vector<std::string> args(argv, argv+argc);
try {
fib_print(stoi(args.at(1)));
} catch (std::exception& ) {
std::cout << "Usage: " << args[0] << " <n>\n";
}
}
|
ALGORITHM 2C: IMPERATIVE LOOP WITH MUTABLE VARIABLES |
#include <iostream>
#include <algorithm>
#include <sstream>
#include <gmpxx.h>
#include <vector>
#include <numeric>
#include <functional>
mpz_class fib(int x) {
if(x==0) return x;
std::vector<mpz_class> v(x, 1);
adjacent_difference(v.begin(), v.end()-1, v.begin()+1, std::plus<mpz_class>());
return v[x-1];
}
mpz_class f(int n) {
if(n<0)
return n%2 ? fib(-n) : 0-fib(-n);
else
return fib(n);
}
void fib_print(int n) {
std::cout << n << "th Fibonacci number is "
<< fib(n).get_str(10) << '\n';
}
int main(int argc, char** argv) {
std::vector<std::string> args(argv, argv+argc);
try {
fib_print(stoi(args.at(1)));
} catch (std::exception& ) {
std::cout << "Usage: " << args[0] << " <n>\n";
}
}
|
ALGORITHM 3A: MATRIX MULTIPLICATION |
#include <iostream>
#include <sstream>
#include <gmpxx.h>
#include <vector>
#include <boost/numeric/ublas/matrix.hpp>
typedef boost::numeric::ublas::matrix<mpz_class> matrix;
typedef boost::numeric::ublas::identity_matrix<mpz_class> identity_matrix;
matrix operator^(const matrix& a, int n) {
if(n<=0) return identity_matrix(a.size1(), a.size2());
matrix b(prod(a,a));
return n&1 ? prod(a,b^n>>1) : b^n>>1;
}
mpz_class fib(int x) {
matrix A(2,2);
A(0,0)=A(0,1)=A(1,0)=1; A(1,1)=0;
return x==0 ? 0 : (A^(x-1))(0,0);
}
mpz_class f(int n) {
if(n<0)
return n%2 ? fib(-n) : 0-fib(-n);
else
return fib(n);
}
void fib_print(int n) {
std::cout << n << "th Fibonacci number is "
<< f(n).get_str(10) << '\n';
}
int main(int argc, char** argv) {
std::vector<std::string> args(argv, argv+argc);
try {
fib_print(stoi(args.at(1)));
} catch (std::exception& ) {
std::cout << "Usage: " << args[0] << " <n>\n";
}
}
|
ALGORITHM 3B: FAST RECURSION |
#include <iostream>
#include <sstream>
#include <vector>
#include <gmpxx.h>
std::pair<mpz_class, mpz_class> fib_rec(int n) {
if(n<=0) return {0,0};
if(n==1) return {0,1};
auto k = fib_rec(n/2);
mpz_class f1 = k.first;
mpz_class f2 = k.second;
mpz_class f3 = f1+f2;
if (n%2) return { (f1+f3)*f2, f3*f3+f2*f2 };
else return { f1*f1+f2*f2, (f1+f3)*f2 };
}
mpz_class fib(int x) {
return fib_rec(x).second;
}
mpz_class f(int n) {
if(n<0)
return n%2 ? fib(-n) : 0-fib(-n);
else
return fib(n);
}
void fib_print(int n) {
std::cout << n << "th Fibonacci number is "
<< f(n).get_str(10) << '\n';
}
int main(int argc, char** argv) {
std::vector<std::string> args(argv, argv+argc);
try {
fib_print(stoi(args.at(1)));
} catch (std::exception& ) {
std::cout << "Usage: " << args[0] << " <n>\n";
}
}
|
ALGORITHM 3C: BINET'S FORMULA WITH ROUNDING |
#include <iostream>
#include <sstream>
#include <vector>
#include <gmpxx.h>
mpf_class operator^(const mpf_class& a, int n) {
if(n<=0) return 1;
mpf_class b = a*a;
b = b^n>>1;
return n&1 ? a*b : b;
}
mpz_class fib(int x) {
mpf_class five(5, 0.7*x);
mpf_class sqrt5 = sqrt(five);
mpf_class phi = (1+sqrt5)/2;
return floor((phi^x)/sqrt5 + 0.5);
}
mpz_class f(int n) {
if(n<0)
return n%2 ? fib(-n) : 0-fib(-n);
else
return fib(n);
}
void fib_print(int n) {
std::cout << n << "th Fibonacci number is "
<< f(n).get_str(10) << '\n';
}
int main(int argc, char** argv) {
std::vector<std::string> args(argv, argv+argc);
try {
fib_print(stoi(args.at(1)));
} catch (std::exception& ) {
std::cout << "Usage: " << args[0] << " <n>\n";
}
}
|
|