Відео

727 wysi

You sound like you're talking through clenched teeth.

The reason I opened this video is to check my understanding on limits after graduating from university. And the reason I finished this video is I understand none of it but enjoy the show

5:54 but limit of something like {5+1, 5+2, 5+3, .......} is same as limit of {1, 2, 3, 4, ......}.

Yea, I understood none of this, I watched it though…

I want to see how efficiently I can make the algorithm by writing it as optimised as physically possible in x86-64 assembly.

haha, 128 bits integer go brrr

I learned about while watching a guide for "Please, Don't Touch Anything" of all places lmao

i saw it

Coming next: Kan't Academy where we discuss the Spectral theorem for Commutative C* algebras

cool

yours is the only channel that doesn't come to my feed still i intentionally search it up regularly just so i don't miss a video.

My immediate guess at how you would optimise the bad recursive version was to use a tail recursive algorithm.

Using closed form of fibonacci recurrence was my first thought and you implemented it using benet's formula which was well done. Upon doing some research i came across the doubling recurrence relationship which would be O(logN) time and space complexity, have you tested that in 1 second time?

watching videos like these makes me realise how bad I truly am with comp sci/algorithms :D time to hit the books as my brain promptly exploded when the moon runes were shown.

Really interesting topic. I would prefer if the color coding on the graph remained consistent between runs.

after learning a bunch of mathematical logic and getting into haskell and lambda caluclus and type theory, this whole thing now makes a lot of sense. (i was an expert c++ programmer, so i'm familier with impure functions or functions that obfuscate their state).

5:29 😭🙏☠️

I fucking love watching videos that delve into topics that I clearly don't/shouldn't understand I don't even know how this crept into my recommended. But I love this

Mhmm, you hit a spot in my soul I never knew existed. All I have is this sub and this like. The love I give you freely. This was a wonderful experience.

I watched this about when it came out and was thinking about it for a while. In English class one day, I drew a chart that had a few low Fibonacci numbers each arranged diagonally to the previous and above the one two before it. I realized that each F(n) is equal to the sum of two lesser consecutive Fibonacci numbers each multiplied by another set of consecutive Fibonacci numbers, where the larger two are grouped and the lesser two are grouped. In the context of this video, if F(0) = 0, (F(n))^2 + (F(n-1))^2 = F(2n-1). 8^2 + 13^2 = 233. From the matrix point of the video on, I didn't have a good idea of what math all of those symbols actually signifies, so if its this then okay I guess. But I would think that this algorithm would run faster than O(n log n), and if its not necessary to compute all of the numbers along the way, i would expect it to be very efficient. In pseudocode: OldSmall = 0 OldMedium = 1 OldBig = 1 StartTime = time TimeAlotted = 1000 loop( NewSmall = OldSmall^2 + OldMedium^2 NewBig = OldMedium^2 + OldBig^2 NewMedium = NewBig - NewSmall if( time - StartTime > TimeAlotted ){ output( OldBig ) } OldSmall = NewSmall OldMedium = NewMedium OldBig = NewBig ) Looking at it, the computation for computing F(n) would be approximately 8x (4/1 + 4/2 + 4/4 ...) squaring a ~((n log phi)/2) digit number, assuming addition and moving around are numbers are trivial operations compared to multiplication. Wikipedia says that multiplying 2 n-digit numbers is O(n log n), so I guess it didn't get anywhere. Watching back, I think i understand the matrix section of the video more. He was doing something similar to this, but with a matrix instead of integers (which i still dont understand), and then just optimising the multiplication (until it becomes O(n log n))(Which i also dont understand!). Since both ways have the same rough complexity, which one is actually faster? Right before I comment this, that 8x can be improved to 6x since OldMedium^2 is computed twice.

I never understand anything but still watch these vids, makes me feel smart 😂

Are you calculating fibonacci numbers up to or just the highest value in a second?

One thing I’m still a bit confused on is how this all plays with the law of excluded middle. If we take it as axiom, then these statements have truth value. Should be think of them being simultaneously true and false (until we create a model where we have chosen a specific value)?

Law of naming: Mathematical discoveries are named after the first person AFTER Gauss to have discovered them 😂

Ofc my ignorance watching a video on computer science and not expecting the Fourier Transform

Why is the X axis not the time? Just curious

incredible work. watched it unpaused

hi :3 UwU

Can’t you use 64 bit integers to store just the mantissa? Alternatively why not use Kahan Summation Algorithms? Both of those should allow you to traverse many more orders of magnitude with the gold medalist.

As a physicist (person who can't math or program), this is lovely. I understood like 75% of each part

6th category 16 yo, idk what I'm doing here, never even heard of a monad, might be able to waste some time

Idk man ill just write backend code in c# wfh and earn six figs but you have fun with this alright

Brah rhis linear algebra thing is too hard i immediately thought of Binet and thats it

I have this small (but prob very improvable) function in Haskell that calculated a 10^(300,000) number in 3 seconds. Might be interesting still because this uses tail recursion (+ compiler optimization) and is O(n) as far as I'm aware. fibTail n = aux n 0 1 where aux n !a !b | n == 1 = b | otherwise = aux (n-1) b (a+b)

The last proof only works because of well-ordering of ordinals, which prohibits infinite descending sequences. Without that, this kind of induction can loop back on itself to infinite depth, and while it would still prove the existence of an expansion, it would not prove its finiteness.

The “linear” Fibonacci’s runtime should really be N*log(N) and not N^2. Adding two integers is O(log(N)) as the number of digits is of the order log N, not N.

good content

Great video, but wouldnt it be better to do the fft on the complex numbers symbolickly, instead of doing aproximations?

got to fib iteration 530000 personally

This video had me smiling from the math and references all the way through, loved it :^)

Appreciate the joke where life lesson numbering starts at 0 :D

25:05 I just love when sentences suddenly begin consisting of very cromulent words.

Wysi

Let's consider a vector space of all sequences satisfying Fibonacci recurrence(which obviously has dimension 2), and operator V of left shift by 1 (forgetting the first element). This is obviously a linear operator, satisfying charpoly equation V^2 - V - 1. So computing n-th Fibonacci number reduced to computing V^n and applying it to vector (F_0, F_1) to get (F_n, F_(n+1)), and all you need to do is to compute x^n modulo x^2 - x - 1, if it is represented by class ax + b, then a = F_n is your answer. It may not give performance boost for Fibonacci sequence, but it is really important on higher degree recurrences. For example, if you have recurrence degree d, and you want to compute n-th term, assuming all arithmetic takes constant time (i.e over finite field) then matrix approach with fast powering gives O(d^3 log n) and surely no better than O(d^2 log n), while this approach(computing x^n modulo charpoly) gives O(d log d log n) using fast polynomial multiplication. Moral: don't represent linear operators in coordinates, unless you really need it. Choosing basis is bad option.

17:27 did you seriously fucking put wysi in the tag because of the 727? I can't escape osu even when I'm trying to learn about algorithms??

University course class recording as UA-cam content Gen z might be the most educated generation

5:30 say that again

Now run it in parallel bc that makes *everything* faster. No exceptions.