Additional interesting questions is: how the compiler was able to compute the fib(45) in the compile time much faster (literally no increase of the compile time comparing to all other examples) than the runtime example using "the same" recursive algorithm?
For a tail recursive one, you could do something like: include int fibimpl(const int i, const int i1, const int i2) { if (i == 0) return i2; if (i == 1) return i1; return fibimpl(i-1, i1+i2, i1); } int fib(const int i) { return fibimpl(i, 1, 0); } int main() { std::cout
The main issue is that the Fibonacci sequence is not to be implemented recursively since here the values are computed again and again, when done as follows: int fib(int i) { if (i==0) return 0; if (i==1) return 1; return fib(i-2)+fib(i-1); } So, assuming evaluation from left to right, a call to fib(4) will lead to the following calls: fib(2), fib(0), fib(1), fib(3), fib(2), fib(0), fib(1), fib(1) and a call to fib(5) will call fib(3), fib(2), fib(0), fib(1), fib(1), fib(4), fib(2), fib(0), fib(1), fib(3), fib(2), fib(0), fib(1), fib(1) So values are computed again and again, which leads to exponential complexity! Not so for templates: After a template has been instanciated for a particular parameter, it is fixed. It cannot be instanciated a second time. So, the whole story is about caching. We could do the same at runtime: int fib(int i) { std::vector data; data.reserve(i); for (int j=0;j
Here's yet another way to compute Fibonacci numbers: If you treat the Fibonacci sequence as a recurrence relation, you can use matrix multiplication and the power algorithm to compute Fibonacci numbers in logarithmic time. In the range supported by a 32-bit (or probably even 64-bit) int, the additional constant factor would, I'm sure, overwhelm the order of growth savings compared to the linear algorithm, but if you're using an extended precision integer type of some sort, it may be worth it.
@@xinpingzhang4506 Yes, both can use fast exponentation. But for Binet's formula you can have rounding errors: When calculating Fib(71) using double precision the error is already larger than 0.5 so that it would give a wrong result. For calculating fibonacci for some larger values (using some library for large integers) i see an advantage of the matrix approach.
If I missed it in the comments below, my apologies, but I would replace 'std::pow(2, i) * sqrt_5' with 'std::scalbn(sqrt_5, i)'. The latter should be much faster because it only has to adjust the exponent field for the floating point value sqrt_5. That is, it's much faster for the case that one uses the function to compute the Fibonacci number at runtime. I also suspect it's less prone to rounding errors. I know, I know, that's contrary to what Mr. Turner is demonstrating in this video. 🙂 But I find that scalbn is useful in lots of different places so I thought it was worth pointing out as an option.
I guess using std::sqrt and std::pow in a constexpr function is a gcc-specific trick. They are not marked constexpr in the standard, and the code, naturally, doesn't work with msvc.
By default gcc has maximum stack depth of ~1000 for compile time computation and a limited amout of computational steps. Kept that in mind when writing recursive folds, try to use variadic expansion when possible. The limits can be increased with -fconstexpr-steps=N and -fconstexpr-depth=N.
Thank you very much jason about constexpr and variadic templates. Please, Jason, could you make a new episode to explain how variadic templates work ? Thank you
I definitely like the lessons taught here about template magic, and although I love constant time expressions, it creates some precision errors for larger numbers, as others have already pointed out. What I was more wondering about is why not opt for the rather simplistic and C-like linear time dynamic solution. It's going to be 45 additions, which honestly is really fast and doesn't introduce complex formulas or floating point errors. For larger numbers to operate fibonacci on, the integer types are going to overflow regardless, and 45 additions don't seem that bad, especially given the simplicity of the algorithm and implementation.
__uint128_t fib(int n) { __uint128_t a=0, b=1, c=1; while((n-=3) >= 0) { a=c+b; b=a+c; c=a+b; } return n==-3 ? a : n==-2 ? b : c; } Accurate and quite fast up to fib(186)= 332825110087067562321196029789634457848 Congratulation for your work Mr Turner !
Tail recursion is unlikelly to happen reliably as it (almost) requires the function call to happen exactly once per recursion as the very last expression of the recursion. Tail recursion relies on reusing the same stack frame for each recursive call, which implies forgetting the entire context of the previous calls. The compiler can opperate certain transformations to convert a non-tail recursive function into one though but it needs to prove difficult equivalences between the original recursion stack unwinding process and the accumulator based version (associativity of the combination operation being a desirable property). Then, it needs to figure out how to statically allocate the accumulator, which is usually done by the programmer through an explicit function parameter of a tail recusive function. In the case of fibonacci, linearizing the double recursion is a non-trivial task as the accumulator must be at least a pair of values. Latest versions of clang and gcc at the time of writing this do not optimize fibonacci to tail recursion but they do optimize factorial. Clang will actually refuse to compile when forced to perform tail recusion in both cases with the following error: error: 'musttail' attribute requires that the return value is the result of a function call
Another technique would be to use an accumulator template. In the recursive case, you take advantage of the compiler caching the template instantiations, which gives a dynamic programming optimisation for free. #include template struct FibAcc { static const long val = FibAcc::val; }; template struct FibAcc { static const long val = ThisVal; }; template struct Fib { static const long val = FibAcc::val; }; int main() { std::cout
The only issue is that if you try to calculate a fibonacci number over 70, the Binet's Formula for Fibonacci numbers starts to give bad results and you need to start rounding the value using the Newton’s Method to have a better accuracy of the result and the code gets pretty large..
Actually using the matrix form yields better results within the bounds of the integer types or one can use an arbitrary precision integer library with the same approach.
Just wanted to say that you have your arguments in the the wrong place in your recursive call. It should be fib = (n, x = 0, y = 1) => { return n == 0 ? x : fib(n-1, y, x+y); } I ran it in the console window just to make sure.
Question: What's the point of doing this via a struct with a static value rather than a function which returns the value? What are the tradeoffs between these two things?
There is also another solution which uses 2x2 matrix and fast power algorithm to get result in O(log n) time. Quite useful if precise result is needed for larger values (with big ints) .
It is of course also possible to write it as a non-recursive function (even w/o knowing that there is a closed-form formula available). Implement the 0 and 1 case as usual, but for any higher number simply initialize a fib[2] with {0,1}, and in a loop alternately replace the values (starting with fib[0]) with the sum of fib[0] and fib[1] n-1 times. At the end of the loop, return the last replaced value. Lesson: most recursive functions can be replaced with a loop, and the if you find yourself doing a recursive call more than once (like in this example) become very aware, as you are doing the same work an exponential number of times... It would have been instructive to show the number of calls to the recursive fib implementation...
True but (tail recursion == loop solution) anyway. Once, you know that you have a reasonably performing solution the choice becomes how expressive (readable) you want to make it.
The last presented method with the formula is very badly written as the integer result stored in double is converted back to the integer by retyping, never do that. The numerical error can be positive or negative, one never knows and the negative one gives the wrong result, for example, static_cast(5 - 1e-15) = 4. The correct way to convert is to use round function.
This is a less wrong method but the error quickly gets much bigger than 0.5, making rounding also incorrect. Double cannot represent all integer values in their range. Most "big" integers actually cannot be represented by a double.
Better yet: copy and paste the values from the web site you showed, and use those as the initializers for a static array. I'm also willing to bet that a simple loop would be faster than the 3 calls to std::pow() for values up through the max that fits in an int. Also, the closed form solution would no longer work if you wanted to return a 64-bit int, since a double doesn't have 64 bits of precision.
The closed form is nice, but it's in my opinion not the best way. Without floating point numbers it can be done in O(log n) using matrix exponentiation. The simple linear method is this: a = 0, b = 1 repeat(n) { a -> prev_b b -> prev_a+prev_b } And the return value should be a. This transformation be encoded in a 2x2 matrix: m= [[0, 1], [1, 1]] And the starting values can be represented by the vector s = [0, 1] The transformation is done by multiplying the vector by the matrix. Multiplying n times is the same as multiplying by the matrix raised to the nth power since matrix multiplication is commutative. Therefore fib(n) = s*m^n. This looks linear, but matrix exponentiation can be done in O(s^2*log n) time where s is the with and height of the matrix using this method: pow(base, exp) { If exp is 0: return identity; If exp is odd: return pow(base, exp-1)*base If exp is even: return pow(base*base, exp/2) } Width and height of the matrix is constant in this example, so the complexity is O(log n). This can also be extended to use bignums or use modular arithmetic to support big n. With really big numbers the complexity is multiplied by the complexity of multiplication, which is O(d log d) where d is the number of digits in the numbers being multiplied
Nice work! I really enjoy your videos. But speaking of searching for the maths, there is an even faster solution : The ratio between two consecutive Fibonacci numbers is Phi (aka the Golden ratio, ie: (1+sqrt(5)) / 2) Hence, you can get a Fibonacci number this way: int fib(const unsigned int idx) { static const auto kSqrt5 = std::sqrt(5); static const auto kPhi = (1 + kSqrt5) / 2.; return (idx < 2) ? idx : round(std::pow(kPhi, idx) / kSqr5); } It saves you 2 pow ;)
I just measured the time taken and the difference between the two is extra short: with 100,000 fib(46) yours: 6.5e-08 s mine: 4e-08 s lol, this is overkill: the time I spent on it is pure waste compared to the result
The first one uses recursion. It computes the same functiom call lots of times, that's why it's slow. If it wants to calculate fib(10), it will call fib(8) twice for example. Once for fib(10) directly and once to calculate fib(9). The number of function calls will grow in an exponential manner.
Hello, I wanted to ask, I have read few books, but in none of these was any type of program you did right now made nor explained, now I understand it, but I would want to know a little more of cpp, did I read wrong books or is it you just having better resources? Thanks.
You should benchmark this in a loop, getting a random sequence of fibonacci numbers. I'd be surprised if multiple calls to pow were faster than hot array lookups.
Here's a benchmark. Happy to hear feedback. Best thing to do, performance wise, is to use the template version that uses a lookup table. Both it and a constexpr linear loop get fully evaluated when given a constant, but the array lookup is faster than the loop in this case. Hard to test when the caches are cold. quick-bench.com/Nzg7754mpOJnjpa1Q0YNhcvnhnw
For the Binet formula, technically you don't even need the special cases for 0 and 1, they are just optimizations in this case. The formula would give the correct results for those also: For 0: anything to the power 0 is always 1, so you get (1-1)/(1*sqrt(5) = 0/sqrt(5), which is 0 For 1: the nominator: (1+sqrt(5))-(1-sqrt(5)) = 1+sqrt(5)-1+sqrt(5)=2*sqrt(5), which is the same as the denominator, therefore, the formula yields 1
Awesome videos!! I have one question. Instead of structs I used a template function like this: template int Fib() { return Fib() + Fib(); }; template int Fib() { return 0; } template int Fib() { return 1; } Executing Fib takes about 4 or 5 seconds, like your "constexpr" version. I guess the compiler is doing something similar in both cases? thanks!
This should be instantaneous! My understanding is that the compiler needs to know what is a compile time constant. See how I need to evaluate the result as a constant expression before passing it to std::cout? It is because the compiler doesn't know it is a compile time constant when it passes the computation to std::cout as it is simply an operator overload and that argument is not constexpr. #include template constexpr int fib() { return fib() + fib(); } template constexpr int fib() { return 0; } template constexpr int fib() { return 1; } int main() { constexpr int result = fib(); std::cout
Indeed, you are right. I think this is because the calls to Fib() + Fib() are still actually made/computed inside every template function instantiated by SomeT. So it's in practice the same as the runtime version. In the meanwhile, the template version in the video works, I believe, because, there, static const member is computed as Fib() + Fib(), and the value is like constexpr. I.e., it is really computed at compile-time rather than once at the very beginning of a program like it might be for a non-const static member.
It does memoization (It does not Compute the same Number twice), while the other does a Double recursion. The First runs in O(n) the last is exponential
@@mocloun3709 because it was not programmed to do memoization? It's unrealistic to expect your compiler to switch to completely another algorithm when generating code.
I learn something from those episodes, but not exactly on what the author is focused. Fibonacci formula is given in rosetta in the best way, moreover, usings std::pow is not very fast thing..better multiply twice
In fact all this methods are wrong, there easier and faster methods using Dynamic programming, and even one where all you need is tree variables and swap their values in each iteration: Un+1=Un + Un-1; Un= Un+1; Un-1=Un; While n != to the number you're looking for the benet formula can give a faster result using fast exponentiation in log(n) but of course the result won't be precice
a nonrecursive and simple solution with a precalculation and without Binet-formula: struct fib { fib() { results[0] = 0; results[1] = 1; for (int i = 2; i < 50; i++) results[i] = results[i - 1] + results[i - 2]; } size_t results[50]; }; int main() { std::cout
He made a video about it, basically std::endl is a call to std::flush + a ' ', the std::flush is in most case completely useless and is also very time consuming
+Freezee I absolutely did not know this at all (i.e. that std::endl invoked flush on the stream)... thanks for answering and teaching me something new!
Yes, it is not understandable. The compiler can calculate it much faster than the direct c++ program. This is impossible! I think something is made wrong.
@@chris_tzikas Yes, now I understand, the recursive formula Jason used is wrong because he is not reusing the values calculated before. If you just build a consecutive list and add the two numbers before to the get the next value, you are also extremely fast and don't need his complex headstands. But if you recalculate the numbers before again and again then it becomes awful slow.
Trivial answer, compiler calculates it iteratively. Fib is a typical first year computer science lesson. Just do a loop from 1 to 45 and add two numbers in each step. He startet to explain fib in this way 1+2=3, 2+3=5, 3+5=8, 5+8=13, ... very simple to program that way, easy to understand and what the compiler does. By the way it then takes linear time, the formular takes constant time and the recursive version takes exponential time.
int main () needs a return value, otherwise it should be void main (). Interesting video. A bit difficult to follow and stay awake, but very interesting.
void main() is not ISO C/C++ and should not (never) be used. Actually, in C++ when not returning a value from main(), std::exit() is implicitly called anyway when the main function terminates, returning 0 by default.
Additional interesting questions is: how the compiler was able to compute the fib(45) in the compile time much faster (literally no increase of the compile time comparing to all other examples) than the runtime example using "the same" recursive algorithm?
@@cppweekly Does that mean that the compiler remembers instantiations within one compilation or even for multiple calls of g++?
Yes, template instantiations are memoised, that’s pretty much the definition of how template instantiations work.
I think at 18:28 you meant to use "
For a tail recursive one, you could do something like:
include
int fibimpl(const int i, const int i1, const int i2)
{
if (i == 0) return i2;
if (i == 1) return i1;
return fibimpl(i-1, i1+i2, i1);
}
int fib(const int i) { return fibimpl(i, 1, 0); }
int main()
{
std::cout
The main issue is that the Fibonacci sequence is not to be implemented recursively since here the values are computed again and again, when done as follows:
int fib(int i) {
if (i==0) return 0;
if (i==1) return 1;
return fib(i-2)+fib(i-1);
}
So, assuming evaluation from left to right, a call to fib(4) will lead to the following calls:
fib(2), fib(0), fib(1), fib(3), fib(2), fib(0), fib(1), fib(1)
and a call to fib(5) will call
fib(3), fib(2), fib(0), fib(1), fib(1), fib(4), fib(2), fib(0), fib(1), fib(3), fib(2), fib(0), fib(1), fib(1)
So values are computed again and again, which leads to exponential complexity!
Not so for templates: After a template has been instanciated for a particular parameter, it is fixed. It cannot be instanciated a second time.
So, the whole story is about caching. We could do the same at runtime:
int fib(int i) {
std::vector data;
data.reserve(i);
for (int j=0;j
This series of videos is excellent, and I learn something with every episode. Great work!
such a use case for std::exchange wasted :D
@@cppweekly main() returns int, fib returns long long.
constexpr long long fib(const int i) {...}
int main { return fib(46); }
./a.out; echo $?
95
You didn't mention the iterative version which is pretty fast.
Here's yet another way to compute Fibonacci numbers: If you treat the Fibonacci sequence as a recurrence relation, you can use matrix multiplication and the power algorithm to compute Fibonacci numbers in logarithmic time. In the range supported by a 32-bit (or probably even 64-bit) int, the additional constant factor would, I'm sure, overwhelm the order of growth savings compared to the linear algorithm, but if you're using an extended precision integer type of some sort, it may be worth it.
The formula can be evaluated in log time as well, using fast exponentiation.
@@xinpingzhang4506 Yes, both can use fast exponentation. But for Binet's formula you can have rounding errors: When calculating Fib(71) using double precision the error is already larger than 0.5 so that it would give a wrong result. For calculating fibonacci for some larger values (using some library for large integers) i see an advantage of the matrix approach.
If I missed it in the comments below, my apologies, but I would replace 'std::pow(2, i) * sqrt_5' with 'std::scalbn(sqrt_5, i)'. The latter should be much faster because it only has to adjust the exponent field for the floating point value sqrt_5. That is, it's much faster for the case that one uses the function to compute the Fibonacci number at runtime. I also suspect it's less prone to rounding errors.
I know, I know, that's contrary to what Mr. Turner is demonstrating in this video. 🙂 But I find that scalbn is useful in lots of different places so I thought it was worth pointing out as an option.
I had no idea it was a thing!
@@cppweekly Just glad I could give back a little. 😁
I guess using std::sqrt and std::pow in a constexpr function is a gcc-specific trick. They are not marked constexpr in the standard, and the code, naturally, doesn't work with msvc.
By default gcc has maximum stack depth of ~1000 for compile time computation and a limited amout of computational steps. Kept that in mind when writing recursive folds, try to use variadic expansion when possible. The limits can be increased with -fconstexpr-steps=N and -fconstexpr-depth=N.
Thank you very much jason about constexpr and variadic templates. Please, Jason, could you make a new episode to explain how variadic templates work ? Thank you
Wow. That template usage expanded my understanding of how generic templates can actually be.
I definitely like the lessons taught here about template magic, and although I love constant time expressions, it creates some precision errors for larger numbers, as others have already pointed out. What I was more wondering about is why not opt for the rather simplistic and C-like linear time dynamic solution. It's going to be 45 additions, which honestly is really fast and doesn't introduce complex formulas or floating point errors.
For larger numbers to operate fibonacci on, the integer types are going to overflow regardless, and 45 additions don't seem that bad, especially given the simplicity of the algorithm and implementation.
__uint128_t fib(int n) { __uint128_t a=0, b=1, c=1;
while((n-=3) >= 0) { a=c+b; b=a+c; c=a+b; }
return n==-3 ? a : n==-2 ? b : c;
} Accurate and quite fast up to fib(186)= 332825110087067562321196029789634457848
Congratulation for your work Mr Turner !
Tail recursion is unlikelly to happen reliably as it (almost) requires the function call to happen exactly once per recursion as the very last expression of the recursion. Tail recursion relies on reusing the same stack frame for each recursive call, which implies forgetting the entire context of the previous calls. The compiler can opperate certain transformations to convert a non-tail recursive function into one though but it needs to prove difficult equivalences between the original recursion stack unwinding process and the accumulator based version (associativity of the combination operation being a desirable property). Then, it needs to figure out how to statically allocate the accumulator, which is usually done by the programmer through an explicit function parameter of a tail recusive function. In the case of fibonacci, linearizing the double recursion is a non-trivial task as the accumulator must be at least a pair of values. Latest versions of clang and gcc at the time of writing this do not optimize fibonacci to tail recursion but they do optimize factorial.
Clang will actually refuse to compile when forced to perform tail recusion in both cases with the following error:
error: 'musttail' attribute requires that the return value is the result of a function call
what about a loop?
uint64_t fib(int f){
if(f == 0) return 0;
if(f == 1) return 0;
uint64_t r = 1;
uint64_t previous = 0;
for(int i = 2; i
Failed to mention memoization technique in the context of dynamic programming solution.
What about using memoization?
Just a note, at 19:36 instead of linear time, you can generate the result in constant time :)
complexity of pow(x,n) is O(log(2,n)), isn't it?
I love the takeaway from this video. Simple beats complex, always
Another technique would be to use an accumulator template. In the recursive case, you take advantage of the compiler caching the template instantiations, which gives a dynamic programming optimisation for free.
#include
template
struct FibAcc {
static const long val = FibAcc::val;
};
template
struct FibAcc {
static const long val = ThisVal;
};
template
struct Fib {
static const long val = FibAcc::val;
};
int main()
{
std::cout
Do you have some documentation (links) about this features: "accumulator template" please ?
The only issue is that if you try to calculate a fibonacci number over 70, the Binet's Formula for Fibonacci numbers starts to give bad results and you need to start rounding the value using the Newton’s Method to have a better accuracy of the result and the code gets pretty large..
Actually using the matrix form yields better results within the bounds of the integer types or one can use an arbitrary precision integer library with the same approach.
Why not just do as the functional programmers would:
int fib(int n, int x = 0, int y = 1) { return n == 0 ? x : fib(y, x+y, n-1); }
Just wanted to say that you have your arguments in the the wrong place in your recursive call. It should be
fib = (n, x = 0, y = 1) => { return n == 0 ? x : fib(n-1, y, x+y); }
I ran it in the console window just to make sure.
3:43 Are you saying that GCC can transform the non-tail recursion into tail recursion and then eliminate the tail call?
If reality changes will propagated constants still be valid?
(Or why ppl write stupid programs relying on compier optimization...)
Question: What's the point of doing this via a struct with a static value rather than a function which returns the value? What are the tradeoffs between these two things?
Line#6 is g++ special. std::sqrt isn't constexpr. Probably, for that reason, clang++ errs out.
You know you're not calling `fib()` in the index_sequence example, right?
There is also another solution which uses 2x2 matrix and fast power algorithm to get result in O(log n) time.
Quite useful if precise result is needed for larger values (with big ints) .
I wonder if I should do more follow-ups on this topic.
It is of course also possible to write it as a non-recursive function (even w/o knowing that there is a closed-form formula available). Implement the 0 and 1 case as usual, but for any higher number simply initialize a fib[2] with {0,1}, and in a loop alternately replace the values (starting with fib[0]) with the sum of fib[0] and fib[1] n-1 times. At the end of the loop, return the last replaced value. Lesson: most recursive functions can be replaced with a loop, and the if you find yourself doing a recursive call more than once (like in this example) become very aware, as you are doing the same work an exponential number of times... It would have been instructive to show the number of calls to the recursive fib implementation...
True but (tail recursion == loop solution) anyway. Once, you know that you have a reasonably performing solution the choice becomes how expressive (readable) you want to make it.
The last presented method with the formula is very badly written as the integer result stored in double is converted back to the integer by retyping, never do that.
The numerical error can be positive or negative, one never knows and the negative one gives the wrong result, for example,
static_cast(5 - 1e-15) = 4.
The correct way to convert is to use round function.
This is a less wrong method but the error quickly gets much bigger than 0.5, making rounding also incorrect. Double cannot represent all integer values in their range. Most "big" integers actually cannot be represented by a double.
Better yet: copy and paste the values from the web site you showed, and use those as the initializers for a static array.
I'm also willing to bet that a simple loop would be faster than the 3 calls to std::pow() for values up through the max that fits in an int. Also, the closed form solution would no longer work if you wanted to return a 64-bit int, since a double doesn't have 64 bits of precision.
The closed form is nice, but it's in my opinion not the best way. Without floating point numbers it can be done in O(log n) using matrix exponentiation.
The simple linear method is this:
a = 0, b = 1
repeat(n) {
a -> prev_b
b -> prev_a+prev_b
}
And the return value should be a.
This transformation be encoded in a 2x2 matrix:
m= [[0, 1],
[1, 1]]
And the starting values can be represented by the vector s = [0, 1]
The transformation is done by multiplying the vector by the matrix. Multiplying n times is the same as multiplying by the matrix raised to the nth power since matrix multiplication is commutative. Therefore fib(n) = s*m^n.
This looks linear, but matrix exponentiation can be done in O(s^2*log n) time where s is the with and height of the matrix using this method:
pow(base, exp) {
If exp is 0: return identity;
If exp is odd: return pow(base, exp-1)*base
If exp is even: return pow(base*base, exp/2)
}
Width and height of the matrix is constant in this example, so the complexity is O(log n).
This can also be extended to use bignums or use modular arithmetic to support big n.
With really big numbers the complexity is multiplied by the complexity of multiplication, which is O(d log d) where d is the number of digits in the numbers being multiplied
Just Don't do it recursively! What about a normal loop liket this?
int fib (int n)
{
if(n < 2) return n;
int a = 0;
int b = 1;
for (int i = 2; i
Nice work!
I really enjoy your videos.
But speaking of searching for the maths, there is an even faster solution :
The ratio between two consecutive Fibonacci numbers is Phi (aka the Golden ratio, ie: (1+sqrt(5)) / 2)
Hence, you can get a Fibonacci number this way:
int fib(const unsigned int idx)
{
static const auto kSqrt5 = std::sqrt(5);
static const auto kPhi = (1 + kSqrt5) / 2.;
return (idx < 2) ? idx : round(std::pow(kPhi, idx) / kSqr5);
}
It saves you 2 pow ;)
I just measured the time taken and the difference between the two is extra short:
with 100,000 fib(46)
yours: 6.5e-08 s
mine: 4e-08 s
lol, this is overkill:
the time I spent on it is pure waste compared to the result
Man I liked the way you used that TERNARY OPERATOR. You gave me Tons of new Ideas :), Thanks Man, Cheers
Why is the compiled version that slow? It only adds 45 times a number. This should get be done in nanoseconds.
The first one uses recursion. It computes the same functiom call lots of times, that's why it's slow. If it wants to calculate fib(10), it will call fib(8) twice for example. Once for fib(10) directly and once to calculate fib(9). The number of function calls will grow in an exponential manner.
Hello, I wanted to ask, I have read few books, but in none of these was any type of program you did right now made nor explained, now I understand it, but I would want to know a little more of cpp, did I read wrong books or is it you just having better resources? Thanks.
How to add whole channel in watch later?
You should benchmark this in a loop, getting a random sequence of fibonacci numbers. I'd be surprised if multiple calls to pow were faster than hot array lookups.
Here's a benchmark. Happy to hear feedback. Best thing to do, performance wise, is to use the template version that uses a lookup table. Both it and a constexpr linear loop get fully evaluated when given a constant, but the array lookup is faster than the loop in this case. Hard to test when the caches are cold.
quick-bench.com/Nzg7754mpOJnjpa1Q0YNhcvnhnw
So this basically dynamic programming at compile time? Why????????????
For the Binet formula, technically you don't even need the special cases for 0 and 1, they are just optimizations in this case. The formula would give the correct results for those also:
For 0: anything to the power 0 is always 1, so you get (1-1)/(1*sqrt(5) = 0/sqrt(5), which is 0
For 1: the nominator: (1+sqrt(5))-(1-sqrt(5)) = 1+sqrt(5)-1+sqrt(5)=2*sqrt(5), which is the same as the denominator, therefore, the formula yields 1
Awesome videos!!
I have one question. Instead of structs I used a template function like this:
template
int Fib()
{
return Fib() + Fib();
};
template
int Fib()
{
return 0;
}
template
int Fib()
{
return 1;
}
Executing Fib takes about 4 or 5 seconds, like your "constexpr" version. I guess the compiler is doing something similar in both cases? thanks!
This should be instantaneous! My understanding is that the compiler needs to know what is a compile time constant.
See how I need to evaluate the result as a constant expression before passing it to std::cout? It is because the compiler doesn't know it is a compile time constant when it passes the computation to std::cout as it is simply an operator overload and that argument is not constexpr.
#include
template constexpr int fib() { return fib() + fib(); }
template constexpr int fib() { return 0; }
template constexpr int fib() { return 1; }
int main() {
constexpr int result = fib();
std::cout
Well you don't even need to write the template in the full specializations! :-)
But anyway,great code👍
Indeed, you are right. I think this is because the calls to Fib() + Fib() are still actually made/computed inside every template function instantiated by SomeT. So it's in practice the same as the runtime version. In the meanwhile, the template version in the video works, I believe, because, there, static const member is computed as Fib() + Fib(), and the value is like constexpr. I.e., it is really computed at compile-time rather than once at the very beginning of a program like it might be for a non-const static member.
Have you tried if your constexpr function works like this?
template
T force_constexpr(constexpr T arg)
{
return arg;
}
why is the compiler faster than the runtime, it also has to make the same decisions, hasn't it? do I miss something?
It does memoization (It does not Compute the same Number twice), while the other does a Double recursion. The First runs in O(n) the last is exponential
@@benjaminlieser8148 And why is the c++ compiled version not doing it? If the compiler can do it, the optimization should do it anyway.
@@mocloun3709 because it was not programmed to do memoization? It's unrealistic to expect your compiler to switch to completely another algorithm when generating code.
@@mocloun3709 Compiler is not magic. What you wish is basically solving the halting problem.
I learn something from those episodes, but not exactly on what the author is focused. Fibonacci formula is given in rosetta in the best way, moreover, usings std::pow is not very fast thing..better multiply twice
In fact all this methods are wrong, there easier and faster methods using Dynamic programming, and even one where all you need is tree variables and swap their values in each iteration:
Un+1=Un + Un-1;
Un= Un+1;
Un-1=Un;
While n != to the number you're looking for
the benet formula can give a faster result using fast exponentiation in log(n) but of course the result won't be precice
It can be made precise enough using GMP and MPFR, at the cost of some speed though. At least up until the type sizes overflow machine memory.
can we use math function in constexpr?
a nonrecursive and simple solution with a precalculation and without Binet-formula:
struct fib
{
fib()
{
results[0] = 0;
results[1] = 1;
for (int i = 2; i < 50; i++)
results[i] = results[i - 1] + results[i - 2];
}
size_t results[50];
};
int main()
{
std::cout
Is there a reason why I see so many people using '
' instead of std::endl?
He made a video about it, basically std::endl is a call to std::flush + a '
', the std::flush is in most case completely useless and is also very time consuming
+Freezee
I absolutely did not know this at all (i.e. that std::endl invoked flush on the stream)... thanks for answering and teaching me something new!
Fascinating stuff
This was gold.
Is this black magic? How did the compiler compute Fib::val so fast? What the hell, my mind is blown.
Yes, it is not understandable. The compiler can calculate it much faster than the direct c++ program. This is impossible! I think something is made wrong.
@@mocloun3709 Jason answered that one somewhere here in the comments.
@@chris_tzikas Yes, now I understand, the recursive formula Jason used is wrong because he is not reusing the values calculated before. If you just build a consecutive list and add the two numbers before to the get the next value, you are also extremely fast and don't need his complex headstands. But if you recalculate the numbers before again and again then it becomes awful slow.
Trivial answer, compiler calculates it iteratively. Fib is a typical first year computer science lesson. Just do a loop from 1 to 45 and add two numbers in each step. He startet to explain fib in this way 1+2=3, 2+3=5, 3+5=8, 5+8=13, ... very simple to program that way, easy to understand and what the compiler does. By the way it then takes linear time, the formular takes constant time and the recursive version takes exponential time.
@@volkerbohm403 The formula uses `pow`, which is O(log n) at best.
How is colorscheme named?
gruvbox, probably.
bruh, my recursive powershell script smashes the non-binet programs
AAAAHH. I am waiting for somone to use an array of bytes with dangling pointers, it screeems at me.
Good one!
int main () needs a return value, otherwise it should be void main (). Interesting video. A bit difficult to follow and stay awake, but very interesting.
void main() is not ISO C/C++ and should not (never) be used. Actually, in C++ when not returning a value from main(), std::exit() is implicitly called anyway when the main function terminates, returning 0 by default.