Yeah, this example produced a sequence with double the frequency of the Fibonacci sequence. You could use this trick with other numbers though (including complex numbers).
@@pihedronyea that's how i thought you were going to solve it..why didn't you do this way just curious? And wpuld you agree most ppl will not think to write 1 as x^0. Thanks for sharing.
I'm not sure how you expected me to solve it. The way you solve powers of phi is using this same technique, but I realised this can be used for other binomials as well. It just happened that the expression I chose for this video was phi squared. I agree writing 1 as x ^ 0 is uncommon but for me it made sense because from a programming perspective, polynomials are just a list of coefficients for x ^ 0 + x ^ 1 + x ^ n and so on. This view helped quite a bit with calculus.
Calculators "get it wrong" because of floating point arithmetic... e-15 is high accuracy, no? Wolframalpha got the precise answer because it is made for dealing with radicals. Ordinary calculators aren't.
Yeah, computers work with limited precision, so some values will get rounded during calculations. Adding first and multiplying second may not give exactly the same result as multiplying first and adding second. Imagine if you only had one digit of precision. We know that 1.4 + 1.4 should equal 2.8 and therefore round to 3, but if the inputs are rounded to 1 ahead of time the result becomes 2. Rounding errors are inevitable unless you do completely symbolic calculations.
Even Wolfram didn't get it "precise", just more precise than Google's calculator. It's still has to approximate at some point, because the answer is irrational.
@jursamaj If you paid close attention to the alternate forms, you can see that Wolfram gives a precise answer in symbolic form. Computers aren't limited to just FP approximations. Rational data types do exist. Wolfram has the tools necessary to do algebra.
There is actually a way to solve these with computers. It works the same ways as a complex number : instead of storing a + b√5 as a float in memory, store it as two integers (a, b). Multiplication is as follows (a, b) * (c, d) = (ac + 5bd, ad + bc). Now just do 7 repeated multiplications (or implement fastexp), and print the result (m, n) as m + n√5. No precision loss ! As a bonus, this can compute fib(n) with O(lg n) complexity. It's very useful.
Yeah, I recently wrote an algorithm that can generate the nth Fibonacci and Lucas number in O(log n). So, it's possible to do phi^n in O(log n) without loss of precision. It's on GitHub if you're curious.
@alphazero339 You can probably ask chatGPT for an explanation or lookup in wikipedia. In general, the complexity is determined by the number of iterations you have to do in the main loop. Operations such as addition and exponentiation are done in one CPU cycle so their complexity is O(1). A naive implementation of exponentiation will be to repeatedly multiply the number by itself, n times. It requires n iterations of the multiplication loop so the complexity would be O(n). Fast exponentiation (look it up) needs log_2(n) operations, so it has a complexity of O(log n). There are some floating point multiplication algorithms that can compute the exponential with O(1) complexity but they lose precision. You always take the biggest complexity, so if for example the algorithm has n + n^2 iterations, you say it has a complexity of O(n^2). An algorithm in 3n iterations has a complexity of O(n). log(n) + 4n^3 has a complexity of O(n^3). It just gives an order of magnitude for the computational complexity. That's about it, it's not an exact value, it just gives some sort of reference for the efficiency of an algorithm. Some O(n) algorithms are better than other O(n) algorithms. For example, in my original comment I said that multiplication is the following : (a, b) * (c, d) = (ac + 5bd, ad + bc). While we assume that it's computed with O(1) complexity, multiplication does take more time than addition. Instead of computing the 4 following products : ac, bd, ad, bc we actually only need 3. Here is a little trick : compute ac, bd and (a+b)(c+d). Notice that ad + bc = (a+b)(c+d) - ac - bd. So computing the fast exponential the way I described using only 3 multiplications instead of 4 will be about 25% faster, even though both their complexities are O(lg n). By the way, this is called Karatsuba's multiplication algorithm.
Yes, powers of phi in algebraic form can be computed in O(log n) time due to the identities of the Fibonacci and Lucas sequences. The github.com/pihedron/fib repo contains a function which can compute both the nth Fibonacci and Lucas numbers in O(log n) steps which is O(n log n) time for big integers. Therefore, we can get the nth power of phi as (L + F * sqrt(5))/2.
Fast algorithm I used: Note the (a+b√5)^2=(a^2+5b^2)+2ab√5. Perform this calculation 3 times, recursively, to get x^8. Now put x over x^8. Multiply numerator and denominator by the "conjugate" of x^8 (that is, flip the '+' in x^8 to a '-'). The denominator simplifies to an integer, while the numerator becomes another number in the form a+b√5. If you really don't want to do that division, you can use the simple (a+b√5)(c+d√5)=(ac+5db)+(ad+bc)√5 to calculate x^2, the x^3, then x^4, then multiple those 3 together to get x^7. Then simplify "conjugate" of x over (x times "conjugate" of x).
Shouldn't that be fib(13) in the last line, not fib(15) ? As someone familiar with the golden ratio, your explanation makes a lot more sense than the video, though it's situational on the presence of phi
So I had a different approach before seeing your solution and please correct me if I am wrong!!so (3+√5/2)^-7 can be written as (2/3+√5)^7 and i rationalised the denominator my multiplying and dividing by 3-√5 and so I got {2(3-√5)/1)^7 and 2^7 is 128 and we can use binomial expansion There's also another faster way from the start i took 1/2^-7 out which is just 128 and then took 3 common from (3+√5)^-7 getting 3^-7 which is 1/2187 and then we have (1+√5/3)^-7 which can be approximated as 1-7√5/3 and soo on the further we go the better
You could use binomial expansion, but you would have to make 7 rows of Pascal's triangle. From an algorithm perspective, this is too slow because it's O(n^2) whereas recursion is O(n). It's faster to multiply and add subtract 7 times each than it is to add 21 times, multiply 6 times, and exponentiate 14 times. The speed difference becomes more obvious when you raise binomials to the power of large prime numbers.
4:46 Calculators don't get it "wrong", they just operate with a given precision. Changing the order of operations can get a slightly different result. That -2e-15 is a difference in the last 2 out of 53 bits of precision. Neither of the 2 terms you subtracted are precise beyond that point, so it's not like one is "right" and the other is "wrong". They're both approximations of the real result.
I'm glad you understand FPA, but that wasn't the point of the video. I cut that part of the video because it was boring. If the result is not accurate, it's still considered wrong. The point of the video is to devise a method for getting the EXACT answer and bring awareness to the limitations of calculators.
@@pihedron It's not even a limitation of calculators themselves, unless you include *any* method of calculating a numeric result, including pencil & paper. *Any* answer not in the symbolic form of a+b√5 will have to be rounded off it some point. Of course, you can't do anything in the real world with √5. You *have* to turn it into an approximate number for it to be any use. Also, accuracy is not a binary, but a measure of *how* accurate it is. In approximating π, 3 is not very accurate. 22/7 is more accurate, and 3.1415926536 more accurate yet.
"Any answer not in the symbolic form of a+b√5 will have to be rounded off it some point." This is exactly the limitation associated with some calculators. They are approximating. Plus there's no denying that the symbolic answer given in the video is better or more "right" than the answer given by the calculator. When I said "not accurate", I meant "not 100% accurate" or "not accurate enough". It's perfectly reasonable to reject an approximation as an answer no matter how good it is. 4:46 is a warning for people who may blindly use a calculator to verify their answer and get surprised. The explanation as to why this error happens is left as an exercise for the viewer. I hope this clarifies anything you misunderstood.
I just calculated x^-1=2/(3+√5)=2*(3-√5)/(9-5)=(3-√5)/2, then x^-2=(x^-1)^2, then x^-4=(x^-2)^2, then x^-3=x^-1*x^-2, then x^-7=x^-3*x^-4. Pretty easy.
It would definitely be slower due to you having to create the triangle in the first place. Pascal's triangle grows at a rate of O(n^2). Plus there's lots of multiplication involved.
For real advice this is poorly explained and for me to understand this need to do your work for myself So recommend making the video longer yet explain each bit thoroughly I still understand it myself ( mainly because I understand the concept which you did great in explaining)
tbh, these videos are not made for ppl who don't understand or havnt acquired these methods and ideas beforehand even if he thouroughly explained each step it would still be hard to follow for some ie:this solution is very intuitive only if u know the concepts behind it
2:48 Because WolframAlpha is an extremely powerful AI calculator and Google's calculator is just a regular calculator. You're basically comparing apples and oranges at this point 😐.
As this is my best video so far, if you want to see me do a cursed version of this (complex numbers), make sure to like this comment.
i saw the thumbnail and realised it was φ squared cause I fool around on the calculator all the time... no wonder f(n) were all fibonacci numbers
Yeah, this example produced a sequence with double the frequency of the Fibonacci sequence. You could use this trick with other numbers though (including complex numbers).
@@pihedronyea that's how i thought you were going to solve it..why didn't you do this way just curious? And wpuld you agree most ppl will not think to write 1 as x^0. Thanks for sharing.
I'm not sure how you expected me to solve it. The way you solve powers of phi is using this same technique, but I realised this can be used for other binomials as well. It just happened that the expression I chose for this video was phi squared. I agree writing 1 as x ^ 0 is uncommon but for me it made sense because from a programming perspective, polynomials are just a list of coefficients for x ^ 0 + x ^ 1 + x ^ n and so on. This view helped quite a bit with calculus.
"Put the table on the food."💀
Calculators "get it wrong" because of floating point arithmetic... e-15 is high accuracy, no?
Wolframalpha got the precise answer because it is made for dealing with radicals. Ordinary calculators aren't.
Yeah, computers work with limited precision, so some values will get rounded during calculations. Adding first and multiplying second may not give exactly the same result as multiplying first and adding second.
Imagine if you only had one digit of precision. We know that 1.4 + 1.4 should equal 2.8 and therefore round to 3, but if the inputs are rounded to 1 ahead of time the result becomes 2. Rounding errors are inevitable unless you do completely symbolic calculations.
Even Wolfram didn't get it "precise", just more precise than Google's calculator. It's still has to approximate at some point, because the answer is irrational.
@jursamaj If you paid close attention to the alternate forms, you can see that Wolfram gives a precise answer in symbolic form. Computers aren't limited to just FP approximations. Rational data types do exist. Wolfram has the tools necessary to do algebra.
@@pihedron I was referring to the value it printed with dozens of digits.
HiPER scientific calculator for android gets this right
There is actually a way to solve these with computers. It works the same ways as a complex number :
instead of storing a + b√5 as a float in memory, store it as two integers (a, b). Multiplication is as follows (a, b) * (c, d) = (ac + 5bd, ad + bc).
Now just do 7 repeated multiplications (or implement fastexp), and print the result (m, n) as m + n√5. No precision loss !
As a bonus, this can compute fib(n) with O(lg n) complexity. It's very useful.
Yeah, I recently wrote an algorithm that can generate the nth Fibonacci and Lucas number in O(log n). So, it's possible to do phi^n in O(log n) without loss of precision. It's on GitHub if you're curious.
How does the big o work for example what do O(1) or O(n) represent
@alphazero339 You can probably ask chatGPT for an explanation or lookup in wikipedia.
In general, the complexity is determined by the number of iterations you have to do in the main loop.
Operations such as addition and exponentiation are done in one CPU cycle so their complexity is O(1).
A naive implementation of exponentiation will be to repeatedly multiply the number by itself, n times. It requires n iterations of the multiplication loop so the complexity would be O(n).
Fast exponentiation (look it up) needs log_2(n) operations, so it has a complexity of O(log n).
There are some floating point multiplication algorithms that can compute the exponential with O(1) complexity but they lose precision.
You always take the biggest complexity, so if for example the algorithm has n + n^2 iterations, you say it has a complexity of O(n^2). An algorithm in 3n iterations has a complexity of O(n). log(n) + 4n^3 has a complexity of O(n^3). It just gives an order of magnitude for the computational complexity.
That's about it, it's not an exact value, it just gives some sort of reference for the efficiency of an algorithm. Some O(n) algorithms are better than other O(n) algorithms.
For example, in my original comment I said that multiplication is the following : (a, b) * (c, d) = (ac + 5bd, ad + bc). While we assume that it's computed with O(1) complexity, multiplication does take more time than addition. Instead of computing the 4 following products : ac, bd, ad, bc we actually only need 3.
Here is a little trick : compute ac, bd and (a+b)(c+d). Notice that ad + bc = (a+b)(c+d) - ac - bd. So computing the fast exponential the way I described using only 3 multiplications instead of 4 will be about 25% faster, even though both their complexities are O(lg n).
By the way, this is called Karatsuba's multiplication algorithm.
Yes, powers of phi in algebraic form can be computed in O(log n) time due to the identities of the Fibonacci and Lucas sequences. The github.com/pihedron/fib repo contains a function which can compute both the nth Fibonacci and Lucas numbers in O(log n) steps which is O(n log n) time for big integers. Therefore, we can get the nth power of phi as (L + F * sqrt(5))/2.
I don’t understand now but hopefully someday I get better at this
Don't worry, you will.
Fast algorithm I used: Note the (a+b√5)^2=(a^2+5b^2)+2ab√5. Perform this calculation 3 times, recursively, to get x^8. Now put x over x^8. Multiply numerator and denominator by the "conjugate" of x^8 (that is, flip the '+' in x^8 to a '-'). The denominator simplifies to an integer, while the numerator becomes another number in the form a+b√5.
If you really don't want to do that division, you can use the simple (a+b√5)(c+d√5)=(ac+5db)+(ad+bc)√5 to calculate x^2, the x^3, then x^4, then multiple those 3 together to get x^7. Then simplify "conjugate" of x over (x times "conjugate" of x).
or just use the binomial theorem?
Firstly i will solve that √5 is an irrational number😂
stop putting tables on your food!
this is just (φ + 1)^-7. Since φ^2 = φ + 1, this is asking for φ^-14.
You get φ^3 = φφ^2 = φ(φ + 1) = φ^2 + φ = φ + 1 + φ = 2φ + 1.
So φ^4 = φφ^3 = φ(2φ + 1) = 2φ^2 + φ = 2 (φ + 1) + φ = 3φ+ 2. Therefore
φ^5 = φ(3φ + 2) = 5φ+ 3
φ^6 = 8φ+ 5
φ^7 = 13φ+ 8
and continuing this way the coefficients will be the Fibonacci numbers, of course:
φ^n = fib(n)φ+ fib(n - 1).
This means the answer is:
1/φ^14 = 1/(fib(14)φ + fib(13)) = 1/(377φ + 233).
Shouldn't that be fib(13) in the last line, not fib(15) ? As someone familiar with the golden ratio, your explanation makes a lot more sense than the video, though it's situational on the presence of phi
@thegreatguardian1 Yes, you are right. It was a typo! I corrected it now :)
So I had a different approach before seeing your solution and please correct me if I am wrong!!so (3+√5/2)^-7 can be written as (2/3+√5)^7 and i rationalised the denominator my multiplying and dividing by 3-√5 and so I got {2(3-√5)/1)^7 and 2^7 is 128 and we can use binomial expansion
There's also another faster way from the start i took 1/2^-7 out which is just 128 and then took 3 common from (3+√5)^-7 getting 3^-7 which is 1/2187 and then we have (1+√5/3)^-7 which can be approximated as 1-7√5/3 and soo on the further we go the better
While you need better notation , it is technically correct answer but is inefficient
You could use binomial expansion, but you would have to make 7 rows of Pascal's triangle. From an algorithm perspective, this is too slow because it's O(n^2) whereas recursion is O(n). It's faster to multiply and add subtract 7 times each than it is to add 21 times, multiply 6 times, and exponentiate 14 times. The speed difference becomes more obvious when you raise binomials to the power of large prime numbers.
Clear as mud. No idea what's going on.
4:46 Calculators don't get it "wrong", they just operate with a given precision. Changing the order of operations can get a slightly different result. That -2e-15 is a difference in the last 2 out of 53 bits of precision. Neither of the 2 terms you subtracted are precise beyond that point, so it's not like one is "right" and the other is "wrong". They're both approximations of the real result.
I'm glad you understand FPA, but that wasn't the point of the video. I cut that part of the video because it was boring. If the result is not accurate, it's still considered wrong. The point of the video is to devise a method for getting the EXACT answer and bring awareness to the limitations of calculators.
@@pihedron It's not even a limitation of calculators themselves, unless you include *any* method of calculating a numeric result, including pencil & paper. *Any* answer not in the symbolic form of a+b√5 will have to be rounded off it some point.
Of course, you can't do anything in the real world with √5. You *have* to turn it into an approximate number for it to be any use.
Also, accuracy is not a binary, but a measure of *how* accurate it is. In approximating π, 3 is not very accurate. 22/7 is more accurate, and 3.1415926536 more accurate yet.
"Any answer not in the symbolic form of a+b√5 will have to be rounded off it some point."
This is exactly the limitation associated with some calculators. They are approximating. Plus there's no denying that the symbolic answer given in the video is better or more "right" than the answer given by the calculator. When I said "not accurate", I meant "not 100% accurate" or "not accurate enough". It's perfectly reasonable to reject an approximation as an answer no matter how good it is. 4:46 is a warning for people who may blindly use a calculator to verify their answer and get surprised. The explanation as to why this error happens is left as an exercise for the viewer. I hope this clarifies anything you misunderstood.
Great Video! Very nice animations
Thanks!
Cool video! Did you use pack that 3b1b uses? The python library that name I forgot?
Yeah, it's called Manim.
Great video! I think I'll use the calculator for this one. Me is dumb
this channel is so underrated! it deserves more reconization!
I just calculated x^-1=2/(3+√5)=2*(3-√5)/(9-5)=(3-√5)/2, then x^-2=(x^-1)^2, then x^-4=(x^-2)^2, then x^-3=x^-1*x^-2, then x^-7=x^-3*x^-4. Pretty easy.
i can see the answer immediately xD
powers with phi are fun to play with.
I feel like just using pascals triangle would have been way faster, its like 3 steps😭
It would definitely be slower due to you having to create the triangle in the first place. Pascal's triangle grows at a rate of O(n^2). Plus there's lots of multiplication involved.
Perhaps using combinations would be pretty fast
1 ÷ by (3+√5)/2 for 7 times
Wow!
Subscribed ❤
how you do your maths edit plz
I use Manim.
hidden gem fr
Great everything expect the last last
For real advice this is poorly explained and for me to understand this need to do your work for myself
So recommend making the video longer yet explain each bit thoroughly
I still understand it myself ( mainly because I understand the concept which you did great in explaining)
tbh, these videos are not made for ppl who don't understand or havnt acquired these methods and ideas beforehand
even if he thouroughly explained each step it would still be hard to follow for some
ie:this solution is very intuitive only if u know the concepts behind it
Great channel ❤
1brown3blue ahh video
I'm 0blue4brown.
1 / (1 + golden ratio) ^ 7
you're not wrong but you can further simplify this to be 1/(golden ratio)^14
I subscribed and liked , now I want more food.😐
I'm in the process of making a potentially longer video but I also have my SAT exam coming up soon. I'll try my best to release a video next week.
WTF💀💀💀💀💀💀💀
W channel #make contents on other stuff as well
2:48 Because WolframAlpha is an extremely powerful AI calculator and Google's calculator is just a regular calculator. You're basically comparing apples and oranges at this point 😐.
Okay
Instantly knew it, φ^2.
It also applies to numbers besides the powers of phi by the way.
{21+35}/14=56/14=4 (x ➖ 4x+4).