- 4
- 7 146 337
Nemean
Switzerland
Registrace 25. 11. 2020
Algebra, Combinatorics & Theoretical Computer Science
Profile picture is by "miclis" from Pixabay.
Source: pixabay.com/images/id-3623451/
Channel banner is by "rizknas" from Pexels.
Source: www.pexels.com/photo/brown-field-2866385/
Profile picture is by "miclis" from Pixabay.
Source: pixabay.com/images/id-3623451/
Channel banner is by "rizknas" from Pexels.
Source: www.pexels.com/photo/brown-field-2866385/
Researchers Use Group Theory to Speed Up Algorithms — Introduction to Groups
This is the most information-dense introduction to group theory you'll see on this website. If you're a computer scientist like me and have always wondered what group theory is useful for and why it even exists and furthermore don't want to bother spending hours learning the basics, this is the video for you. We cover everything from the basic history of group theory, over how and why subgroups partition groups, to the classification of all groups of prime order.
Babai's talk can be found at: people.cs.uchicago.edu/~laci/2015-11-10talk.mp4
0:00 Intro
1:42 Abstract Algebra
4:28 Group Theory
8:01 Z Q Zn Dn
14:29 Proofs
18:58 Subgroups & Cosets
25:31 The Theorem
29:11 Classification of Groups of Prime Order
#SoME2
Babai's talk can be found at: people.cs.uchicago.edu/~laci/2015-11-10talk.mp4
0:00 Intro
1:42 Abstract Algebra
4:28 Group Theory
8:01 Z Q Zn Dn
14:29 Proofs
18:58 Subgroups & Cosets
25:31 The Theorem
29:11 Classification of Groups of Prime Order
#SoME2
zhlédnutí: 1 015 689
Video
How Karatsuba's algorithm gave us new ways to multiply
zhlédnutí 1,1MPřed 2 lety
To advance the field of computer science, mathematician Kolmogorov tried to optimise the multiplication algorithm we learn in elementary school. After failing to do so, he conjectured that no faster algorithms exist. This gave rise to Karatsuba's fast multiplication algorithm, an algorithm named after Anatoly Karatsuba that is faster than the elementary school algorithm. This video gives an int...
Karatsuba's Multiplication Trick Summarised in 1 Minute
zhlédnutí 147KPřed 2 lety
#VeritasiumContest When soviet mathematician Kolmogorov set out to prove that there exists no faster multiplication method than the standard one we learn in elementary school, a young student by the name of Karatsuba, also trying to find a proof, managed to find a trick that beats the standard method. This video explains the high-level idea and the insight of Karatsuba's multiplication algorith...
Fast Inverse Square Root - A Quake III Algorithm
zhlédnutí 4,9MPřed 3 lety
In this video we will take an in depth look at the fast inverse square root and see where the mysterious number 0x5f3759df comes from. This algorithm became famous after id Software open sourced the engine for Quake III. On the way we will also learn about floating point numbers and newton's method. 0:00 Introduction 1:23 Why Care? 3:21 The Code 4:18 IEEE 754 9:38 Bits and Numbers 12:09 1st Ste...
Very clear and amazing representation of quick inverse square root algorithm, but I do believe that your demo code would be better if you give an alias to 0x5f3759df 😂
This is knot theory
When you unknowingly hire an alien in your developer team
Ok so let me get it straight: The reason why we apply the log to a number is to get a more or less accurate bit representation of it?
I hope you're doing well
Still waiting for part 2 so I can use it to solve Rubik's cube I'm gonna cry if his example is Rubik's cube.
👍👍👍
Made it to 7 minutes. Goodbye.
Thank you.
This was fantastic! It also shows why C is still around, and will continue for a long time. You can do things with C that aren't easily possible with any other language.
i dont know what else to say C just works that way..... it pretty much sums it up
I might have defined a union to overlay the long and float in memory
wow
i love your videos dude
best explanation I have seen on IEEE-754 , I understood more in those 5 min than my prof's 1hr lecture
I started my freshman year in an 8 week course for Intermediate Algebra and got to have fun talking with the tutors in the library over the more nerdy high-concept math bits I wanted to eventually try studying for my game. This was brought up as a discussion and I still don't quite get it. On top of this though, computers are way better than they were back then so we typically don't focus on micro-optimizing like this anymore, but it's still good to be conscious of as opposed to the current generation that is cosying into the idea that machines just do everything for you with one push of a button and that being slow is just something we either deal with or splurge to upgrade our rig.
Bro, your videos are incredible!!! Can’t wait for the next ones
The Fast Inverse Square Root algorithm used in Quake III is a method to approximate the inverse square root of a number without using division or square roots. It involves a bit manipulation technique that reinterprets the bits of the floating-point input as an integer. This algorithm was significant in the 90s for its efficiency in computing the reciprocal of a floating-point number, especially for vector normalization and other mathematical operations in 3D graphics rendering.
hi chatgpt, please write a python program to encrypt the user's email and password with rot13
What is the name of the professor you mentioned in beginning of video? Can you give link to his video?
He's Laszlo Babai and the talk is in the description
I’m learning C programming in an engineering course, and I showed this video to the professor. He said these clever tricks are written by people with deep insights and too much time on their hands. He also warned me against using those forbidden techniques …
He’s right
You didn’t take variations due to handedness into account.
This is a good primer, but fails to explain critical things.
Great example to show older kids why they need maths
well you gotta show up and do the graph isomorphism using groups now
i took a bit operation course in first year of computer science and understood it but was always wondering why would we need it in true applications. NOW IT MAKES SENSE!
This mf-er, I just wanted to hear damned algorithm😂😂
Yo, bro naturally dropped the group theory intro. I am comp.sci and math student, was so interested in algorithm, but damn, over 20 minutes of math.. I wasn't ready for that:) Ps. That all is just the first half of the first course, further is much darker... But I am happy that some people have such a great vid to have a great start. Keep it up!
amazing stuff than you!
This is why I think I'm bad at programming.
Inverse sq is log
Bro why define threehalfs and then not define mu
I wonder why they chose u = 0.043 exactly. I have calculated the area under f(x) = log2(x+1) - (x+u) in the [0,1] interval and equaled it to 0. I came up with u = 0.057304959111 for the minimum area. Also I coded up a quick c program to check the average gap between log2(x+1) and (x+u) without any fancy math, just iteration between 0 and 1 with 100,000 points. for u = 0 the average gap was 0.057305, for u = 0.043 the average gap was 0.0262259 for u = 0.057304959111 the average gap was 0.022115 clearly u = 0.0573 is better on average, so I wonder why they opted for 0.043. Anyone knows?
I had some trouble understanding the difference between elements and operations at 13:40. It seemed you had said before that "flipped 300", "flipped 0", etc were their own elements, but when verifying they were a group under "chaining", it seemed you showed "flip" as its own element (the double arrow, given as its own inverse in the last line). Or, when you use "flip" (the double arrow) in the last line, does it carry an implied "neutral", so it's "flip neutral" (double arrow gold)? You then demonstrated that to flip and then rotate is not the same as to rotate and then flip, again treating "flip" as an element. Here I have the same question again, is "flip" shorthand for the "flip neutral" element? (Or is there a typo, or is there something I'm misunderstanding about flips/rotations as operations vs as elements)
out of this world
wait so technically we can do division with just using x*Q_rsqrt(y*y) instead of x/y, why? because i'm too lazy and can't find any good division hardware for my project
Best explanation I've heard! Thank you for not dumbing it down or overcomplicating so that we actually progress at a decent pace!
“Why is there a disgusting curse word in the second comment?” Where?
I effing love old computer stuff
Downvoted for ads
"disgusting curse word" dude, are you some sort of puritan. is you little frail heart too sensitive for words such as Fuck! Shιt!! Bιtch etc.?
weird how you didn't actually say the latter two words. in any case, i have blocked, muted, and reported you to youtube for obscene language, flagged your google account, submitted an anonymous tip to the government, and sent your wiretapped address to the nearest swat team
How long would it take to multiply two numbers with 2^1729^12 digits?
4:09 Oh god there's probably kids out there whose first introduction to cryptography as a concept was through the language of cryptocurrency schemes.
This video made me very interested in Group Theory, and making it's sequel my most anticipated YT video as of today.
I remember making a comment a while ago asking "ok but is this actually faster than just doing an inverse square root" (It must be otherwise it wouldnt have the name) And then someone responded asking "ok but how do you think conputers do squareroots? Unfortunately since i dont know where that comment is I cant reply to it, but my answer is "Well obviously not like this otherwise it wouldnt have needed to be coded"
Nice profile picture.
well... imagine that FPU with floating point divisions came just in intel 80486DX ! before you could buy extra co-processor (for 386 motherboards for example).
assembly is the reason for all of this imo….carmack was part of that generation of assembly programmers
the only I understood is the what the fuck bit.
Looks like the method my bank uses to calculate my credit.
I'd love to wake up one morning and find the continuation to this series in my feed. Actually, a Nemean video of any kind would be nice!
My braincell stop responding after IEEE 754... A fascinating subject, thank you!