Random Numbers with LFSR (Linear Feedback Shift Register) - Computerphile
HTML-код
- Опубликовано: 9 сен 2021
- A simple bit-shift operation can generate amazing random strings of numbers. Dr Mike Pound explains then codes it in Python.
If you want to know more about how XOR works: • XOR & the Half Adder -...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
It’s cool that you guys talk about something random from time to time
_ba-dum tsssss_
*pseudo-random
> pseudo make me a sandwich ;)
' Achtsekundenfurz' is not in the sudoers file. This incident will be reported.
No presents for you this Christmas
I see what you did there
Due to their simplicity and ease of implementing in hardware, LFSRs were used as noise generators in a lot of early synths. Notably, the percussion sounds in NES games come from one of these. The shift register in NES APU is 15 bits long and can be tapped from either the two low bits, just like the 4-bit example in the video, or from bits 0 and 6. Otherwise, it works exactly as described, and because the signal is periodic, by changing how frequently you sample from LFSR, you can adjust the pitch of the simulated percussion. Add an envelope, and you can have pretty cool sound FX from a handful of transistors.
This comment is incredible. Thanks.
this is very cool to know, thank you!
They were used to generate "starfields" in the arcade shoot-em-ups like Galaga as well.
Also, digital noise is, due its nature, great for using as a quasi random clock/trigger source for other components of a synth. For example, in an analog modular synth, you could patch a digital noise source (like the Doepfer A-117, which is a LFSR) into the gate input of an amplitude envelope generator, which would result in musical notes being heard at random intervals.
Further / My favorite example regarding synths and LFSRs:
As before, DigiNoise / LSFR, but this time with a very low clock rate (less than 10-15 Hz) into the gate/trig in of an envelope, patch the env (with extremely short time constants, basically a quick impulse) directly into the audio input of a resonant filter (low or band pass, preferably), with the resonance setting being high, but shortly before self-oscillation, gently modulate the filter cutoff frequency with low-frequency analog noise (or heavily LP-filtered white noise) and you've got a simulation of falling raindrops, a dripping water tap or, if you add tons of delay and reverb effects on top, a dripstone cave soundscape.
That moment when you found something about sound design hardware in an unexpected place 👀
I love how around 7:42 the command history goes "cls" followed by "clear". It makes me feel comfortable knowing that the legend Dr. Mike Pound himself also still types clear on Windows
fwiw, if you use msys on Windows, then you can type clear and it will work just the same as cls.
@@Tahgtahv Powershell accepts "clear" too. I think it's an alias to the actual command though.
The exact moment is at 7:37
Yeah, I think everyone who switches between OSes has at some point typed "ls" into the Windows terminal ^^
@@jl_woodworks and ls too, I believe it even understands the -l and -A flags
Did a lot of this 40 years ago in device drivers on PDP11s to create Cyclic Redundancy Checks (CRCs) for communications protocols, to protect data in transmission. Every vendor had proprietary systems with different seed values, taps, and which bytes of the message headers to include or ignore! PDP11 assembler language made the ‘bit twiddling’ easy! Happy memories…
I approve this comment :)
RSTS/E
@@Wombbatts RSX-11M actually
@@Richardincancale I used RSTS/E for bank accounting and general ledger in '83.
Dear lord when i was busy not being born yet, my father was busy repairing CRT TVs in Polish People Republic you were busy doing this. Incredible.
I’m going to need a video on that math.
Yes
Pretty sure the valid numbers that repeat are always prime numbers within the width. In this case he used bits 2,3 to update 0 so b1101=13. The LFSR represents some generating polynomial which is prime. I could have that backwards but been a while since I did the math in college. I think it comes down to using a GF field of the length of the LFSR and when you generate these numbers once you exceed that width you divide by the generating polynomial to get within that field, and dividing by prime number will replicate all possible values
@@wesrichards6349 Yes you're correct on the GF field, (it's a GF(2) field), and if the polynomial which has exponents corresponding to the taps is primitive in the field (so for length 4, we had taps at positions 1 and 4, giving the polynomial x^4 + x + 1), the LFSR cycle length is maximal
If I remember my crypto course correctly lol
@you- tube Check out the videos and extra bits on the AES encryption videos.
At this point a video about the math is like an encore, he's just waiting for us to ask for it.
@you- tube not necessarily, he’s done math videos on Computerphile as well.
Well I'd be down!!
Sorry, but I have to ask: WHO? ... needs to ask for "the math" on this subject/video? Did they fast forward through some of it? Why not just watch it over one more time???
"The math" [sic] is not readily presentable even in a Numberphile video. There's too much of it. You'd first have to define Galois fields, then show how to do polynomial arithmetic in them, and then introduce primitive polynomials in GF(2). There's also spectral analysis, auto- and cross-correlation properties, Hadamard transforms etc.. A non-trivial chunk of my MSc. research was getting to grips with LFSRs.
@@davidgillies620 That would be a fantastic addendum. Especially since he could build off of the math already done when he explained how Galois fields are used for AES encryption.
Love all of this, but it's really time for Dr Mike to use f-strings in python!
I guess it's not possible to format a number as binary using an f-string
@@ramidaouas4933 print(f"{state:04b}")
@@MattRose30000 Thanks, I didn't know this
I once had to write a UUID4 generator and had to look into this stuff. It would be really interesting to see an episode talking about how RNG's can be classified and evaluated, because it really affects what you need them for. For example, different RNG's have different:
- memory requirements
- performance characteristics
- periodicity
- probability of collision within the period.
- seeding requirements (and sensitivity to seed)
- entropy at different points in the period
And so on. And it's really interesting how these requirements can conflict, e.g. you can't avoid collisions without reducing entropy. My UUID generator was for a big data system so it had to have exceedingly high period and low probability of collision, but I could use as much system resources as I wanted, didn't need high entropy, and it didn't have to be cryptographically strong. Whereas an RNG for a game can usually be pretty crap, because all that matters is it's fast.
RNG in games can be fascinating. In Doom, the RNG was a counter and a table of 256 values, the same in every copy of Doom. I suppose they thought it was worth the memory over the CPU time. Plus it makes it very easy to synchronize RNG in demos and multiplayer.
The predictable RNG is important for demo playback. The demo doesn't contain anything about AI actions; those are precisely recreated by running the RNG from the start of the table (starting a recording restarts the RNG, too). And 256 bytes isn't that much overhead for a game like Doom, which needed XMS (didn't fit 640k). Don't forget that part of those 256 bytes would be used for RNG purposes anyway, e.g. the code for the calculations and an internal state that's more complex than a simple 8-bit index.
"What's the actual use for this series?"
>> Hacking montages in 99% of movies.
I would love a video that dives deep into the math of finding optimal taps.
Dr Mike Pound, man I miss your cryptography teaching. Best lecturer I ever had.
I missed this lovely English voice, it definitely makes it easier to understand pretty much anything, loved your Data analysis course Dr Mike Pound, always a pleasure.
Yeah this dude and prof brailsford are my fav computerphile guys
Useless trivia: The "SID" sound chip in the Commodore 64 used LFSRs to approximate the logarithmic ramp of the ADSRs and filters.
Also used on the Game Boy to generate noise sounds (although probably not as exciting as the SID).
Also used in Pitfall on the Atari 2600 to generate the screen layouts.
Also used in the UK to generate government policy....
Also used in River Raid to generate screen layouts.
@@deviljelly3 lol
I could listen to this man for hours, all of his computerphile videos are pure gold.
I remember trying to look up LFSR last year and there were no good videos online. I had missed that day of my cryptology class and I struggled to figure it out for a few hours before finally getting it. And now this super good video is going to be helping future students for a long time
Julian Ilett did a series on hardware LFSRs 4 years ago... I thought it was fun but your mileage may vary
There is a great treatment of them in TAoCP. It’s somewhere around page 20 in one of the volumes.
The condition for maximal length is that the polynomial formed by the taps be primitive in GF(2). The first LFSR in the video has polynomial x^4 + x + 1. A sequence of maximal length generated by a given LFSR is an m-sequence.
How nostalgic. In a Dilbert cartoon, a demon was charged with creating random numbers. These were 9, 9, 9, 9, 9, .... Which is 1001 in binary! Now we know what program he was using!!!
I learn so much with Dr. Pound! Thank you for the videos! I wish his courses were available online
Wow! This is your first video I've seen a live demo in... I love it!
Finally a video on random numbers, i love this, last time it was like 9 years ago when -phile channels made video on RNG (using radiation)
The Atari 2600 game "Pitfall" is probably the most famous example of an LFSR, it used the bits from a random byte, to build 256 different rooms!
Not bad, when the whole game ROM was limited to 4KB!
Speaking of games. How about the strangest use of an LFSR in games.
A lot of LCD handheld games (like the Tiger games) used a Sharp SM510 (or variant) processor. The Program Counter was confusingly made up of 3 registers (Pu, Pm, and Pl) with Pl being a 5-bit LFSR with taps on bits 0 and 1 but with a twist -- it always included a 1, so on each iteration, bit 5 was bit1^bit0^1. This had the effect of including 0 in the sequence!
For the curious, the PC incremented in a weird way, first Pl was advanced to the next iteration: Pl = (Pl>>1) | (((bit1^bit0)^1)
That's a 6 bit LFSR ... d'oh! ... I'll bet that had a few heads scratching! Also, I should probably point out, as you've noticed that Pu and Pm don't change when PC is incremented. Those needed to be set separately. You can think of them as setting the memory "page". It's a very strange processor.
Imagine having classes with these guys, it would be amazingly exciting to learn!
Thank you for this great video! As an engineer I am often confronted with people using "only" random numbers to test their algorithms. E.g. communication through a channel and measure the bit error ratio. Often they underestimate the randomness of "randomness" and gather different results in different runs of the same test. And I always need to explain them to use LFSR (or more basic "pseudo-random binary sequences"), which pseudo-randomly output every possible bit combination exactly a single time.
This video, dear Computerphile, helps me a lot to explain the need for this sequences!
I used LFSRs over finite fields in my PhD thesis to generate a family of combinatorial designs for prime powers using primitive polynomials that gave much better bounds on their sizes than the previously known bounds. That was nearly 10 years ago and it's fascinating to see how people have taken my idea and adapted it to other related or completely unrelated combinatorial designs, but still, our records remain unbeaten in the online catalogue of these designs.
Great video, as usual! Brings up fond memories of working on signal processing algorithms using pseudo noise signals based on M-sequences. 🙂
I remember LFSR from my hardware course work. It would have been nice to see the math for choosing the taps because I've forgotten that part.
Thanks for yet another clear, engaging, and interesting talk and video!
I love when Dr. Pound explains stuff!
What an amazing video with great and clear explanations.
Keep it up and way to go !
the general quality of the video has improved! congrats!!
This is awesome, I have just started with my master's program in Cyber Security and we had to learn this for the basics in cryptography!
Remarkable coincidence. We just went over LFSRs in my class today and you guys released a video to help me understand better. Are you guys spying on me? Lol
I designed a hardware cryptography module using LFSRs in 1972, the year the first 8-bit microprocessor, the Intel 8008, was released.
Pls give us a 2nd inteveriew with the math behind this! And i could listen to Dr. Mike Pound for hours and hours. To bad i'm not living in the uk, so i can't study in Nottingham :D
7:30 Python conveniently offers fstrings by going print(f"{state:b}") you could have done the same thing. They are both easier to use and faster to execute!
Dont put “fast” and “python” together?
@@truestopguardatruestop164 of course using C or something would no doubt be faster. This still is faster *by python standards* though. "faster" != "fast"
There are some cool properties of the output of these LFSRs that were not mentioned. For example, if you skip one bit every time, you will still get the same bit-sequence in the end(but at a different "start" location). Also, if you XOR any number of bit-streams for an LFSR, the result will still be the same bit-sequence. The self-synchronizing property is also very useful. You can imagine that after receiving 4 bits into your receiving LFSR, you can calculate the next bit and hence use it as a bit-error-checker.
I've been researching these on and off for nearly a decade! I'm trying to add more randomness to the register as a whole. I've made a little progress by shifting normally for a set number of times and then "subshifting" where I shift only half of the register. I have animations and write ups but RUclips isn't letting me post links.
Dr. Mike, thank you as always! Could Computerphile revisit this topic in terms of cellular automata? I've been experimenting with using CAs as a PRNG/stream cipher components. I've been dying to see more attention to them for encryption or compression. Like LFSRs, they can be implemented extremely efficiently on hardware.
LFSRs were often used in place of counters for very large terminal counts in the days of PALs or PLAs. Simply preload a specific value and wait for the terminal count of all 1s. Or detect the proper bit patterns to generate precision sync pulses and reset count. LFSRs can run very fast without having to worry about complex counter logic or fast carry logic.
These are used in radio as well. GPS uses many 10 bit LFSRs. Funny thing is at 10 bits, there are quite a few tap patterns which will produce an M-sequence. And each bit sequence is seemingly uncorrelated with one another. What GPS does, is each satellite transmits on the same frequency, but uses a unique tap pattern with the repeat aligned exactly with an atomic clock. So not only can you differentiate which satellite you are picking up by it's code (multiple at a time) but you can also determine the time delay based on when the code starts.
welcome back my favourite professor
A pleasure to watch…
As it always is
In hardware we use these as the basis for communications testing, where they are sometimes referred to as a PRBS generator (psuedo-random binary sequence). The advantage of them is that you only need n bits in a row to determine the remaining outputs of a n shift-register PRBS. The feedback taps are standardized for different protocols, and with that you can use different brands of test equipment to do bit-error-rate testing over the link, because they all use the same PRBS to do so.
If I recall correctly, this is used in the noise generator for gen 1 pokemon roars. The more metallic noises also fudges with a bit in the middle of the register.
These are really handy.
Very simple, but you do have to check for the "ALL ZERO" state when you first power up.
Two key quotes from this video that sun up all of computer science 1) “that’s all just 0s and 1s” and 2) “let’s make this more complicated”
I think the period might be the maximum entropy or order - something like that - for a 4 bit shift register without the all 0's i.e. 15! Really nice example.
Thank you once again, Mike!
"We won't dwell on some maths". That's a shame because the maths behind LFSR is very interesting.
Numberphile don't like their territory being being encroached upon.... they send round the heavies ...
It could be a thrilling crossover!
@@heaslyben it could... just don't tell the physicists or the chemists
I took a cryptography course ages ago meant for math majors, where we delved into the mathematics of finite fields which underpins how LFSRs work. I was looking forward to a nice review/refresher of that material. It's a shame this video didn't go into that. Definitely a topic for Numberphile.
@@cybisz2883 Ben Eater made a fantastic series on error correction in which he delves to CRC to do polynomial divisions in GF(2) and its use of LFSR's in hardware to achieve that
Fun fact: another popular use of LFSRs is in GPS (rather, GNSS). They use a form of Gold Codes to generate psuedo-random identifiers for every satellite so that receivers (i.e. your phone) can identify, lock on, and track the signals to compute a position
this was one of my favourite parts of the digital electronics units I did
Computerphile should totally do a video on holomorphic encryption. Definitely worth the go at it given it is posed to rise to commonality soon.
Playing around with using this for a dissolve screen effect. Since it hits every combination between 1 and 15 you just blank out pixels in a 15 pixel shape each loop- no memory needed to keep track. This has been done before but what I'm doing is using a equilateral right triangle of pixels, 5,4,3,2,1 with pixel ids numbered randomly and blanked by an offset based upon the xy location of the triangle (two triangles actually in a 6x5 rectangle). The reason for the triangles is 1: They are 15 pixels, and 2: They move the blanking into an area of the screen as opposed to the easy way which would be a horizontal line of pixels and that would leave more artifacts on the screen.
You should mention that software implementations can be accelerated by generating multiple bits in one iteration using a lookup table. For example, if you need pseudorandom 8-bit values, you might use a 32-bit generator, but shift out 8 bits and look up the next value for the xor in a 256-word table.
Just what I've been waiting for😍
5:44 There are ways... that is an extremely interesting statement and I would very much enjoy hearing about those ways.
The easiest way is to get a table of primitive polynomials that is published in an academic journal. That’s what I did, long ago, but I’ve forgotten where it came from. I might have a reference to it somewhere in my poorly organized files.
Both Type 1 and Type 2 LFSRs can use the same polynomial and shift either left or right so your coding example could be simplified by changing from right to left shifting. It can also be helpful to use the carry bit as rotate through carry instructions are fast and efficient.
Fun fact: Wolfenstein 3D used a 17-bit Galois LFSR (more efficient to implement in software) to produce its famous fade to red effect when you died or defeated a boss. It could guarantee a linear time psuedo random fade with no memory needed to keep track of which pixels were already set to red.
Thanks a lot. I'm rather picky about random number generators. This is a great low-cost approach.
Was once involved with making a hardware RNG for a gambling service.
The gambling company used insurance against the risk of too many big prize wins, which meant the insurer had to audit their stuff. Having passed the audit before implmenting our hardware RNG, they were not allowed to make any changes without repeating the audit, so the gambling company chose to never use the hardware RNG. Instead they went back to using their dev tool's built in LSFR RNG.
As the video mentions, despite the long sequence, if you know a part of the sequence you can predict where you are along that sequence and therefore know every number that will be generated, this meant they would go live with a RNG that had a deterministic repeatable pattern, and knowing recent winning numbers anyone who knew or guessed the RNG could predict future winning numbers.
Luckily for the insurer, the company failed for other reasons before it was ever live! I would've been interested to follow the results had it gone live in that form.
I wish I had teachers like you in my computer class
I would imagine tap originates from beer or wine production (tapping a barrel or keg) which is pretty much what these taps are doing. The faucet in a sink is that same kind of tap into a water main. So they're related by a common ancestor.
I love the fact that Mike is using Dell XPS. great machine.
Interesting talk. Decades ago I had a Maplin 3600 synth which used an LFSR as a white noise generator. After a short while your brain could hear it cycling. I also built one using TTL 32 bit to flash lights in a sculpture that never happened.
I had to write a random number generator and what I found was the random function wasn’t statistically random. It appeared to be linked to the clock and the time the program took to get to the function. I had to seed the generator with the clock (time since computer epoch) portion of the PSW (Program Status Word). The fun part is to read the PSW you have to get in to supervisor status.
The real fun began when application programming teams wanted to use the code, as it meant their code would also need to run in supervisor state (a huge no-no). I ended up putting this in part of the Control Program (for TPF), which was then called by a macro.
LFSRs are a great way to add uncorrelated noise to a signal. This lets you take advantage of a sigma delta ADC's inherent noise shaping abilities, where adding noise can actually produce less noisy converted data.
The frequency at which D.R Pound flicks his left hand sleeve would be a great seed for a random number generator
Very interesting ; I was looking for a way to quickly generate a big stream of random data (testing a framebuffer with random pixels) and I think this will do! :-)
Something these are very commonly used for is noise generation in arcade machines, home computers, and some game consoles.
You wouldn't need any flip flops, there are actual 74 series shift registers out there to use.
I suspect that the deterministic observation of how many iterations it takes to return back to your original state based on the number of xor gates you have within your circuitry might be related to the properties of the polynomial functions in regards to their even and odd properties. For example 1 & 3 xor gates will behavior similarly while producing different results in the same manner that 2 & 4 xor gates will where the odd amount of gates and even amount of gates will behavior quite differently or almost opposite of each other kind of like two vectors and how close they are being either orthogonal or perpendicular to each other are. The steps of the algorithm with in the hardware are shift by 1 bit, then apply xor to n-arbitrary gates. The first instruction is a physical movement as in a linear transformation as we are moving the bits along a line or a stream by some defined stride and here in this case by 1. The second instruction is an arithmetic logical operation. The reason I state arithmetic logical as opposed to just logical is that even though xor is still a comparison gate, it is closely related to addition in that xor is the building blocks of your adder circuitry due to the properties of its truth table, however for xor to be considered a proper half adder other required gates are missing from the circuitry yet xor two single bits is still applying binary arithmetic without any carry bits. So we aren't just comparing two bits based on their 0 and 1 state we are also adding them in a binary fashion and disregarding any carry over. So in truth I suspect that after an x amount of iterations to return back to the original state based on the seeded bit pattern is that for each time we reach that duplicate state it is a multiple of that original state. One way to test this is that every time we shift the bits and a bit falls off the register... push it into a different shift register to keep track of all of the values and when we reach repeated state combine both registers as a single bit pattern with the working register as the MSBs and the stored register as the LSBs. I haven't tested this so I could be wrong on some of the details, but mathematically speaking this algorithm appears to exhibit these properties and behaviors.
That’s the content i’m looking for
I think we can use this similar kind of idea in cracking passwords if they consist only of numbers but it become a little bit steep when the password has larger no of digits in this case we can use recursion which can be used as a side guy during the brute force.
I needed this video about 6 years ago i was implementing game of life on my tandy color computer in assembly. I needed random numbers to initialize the cells, eventually someone pointed me to LFSRs
I found that grabbing the last several digits off of the computer's clock was pretty reliable as a random seed. There's probably some obscure reason that it's not truly random, but it served.
Awww yiss I finally learned to implement an algorithm on my own *before* Computerphile had a video on it xD
We will love to see a video on APIs
I just love me some Dr Mike Pound
Great explanation!
For a more low-level implementation you can replace a bunch of taps & xor with a mask and bitcount:
I.e. for the 128-bit lfsr with taps at 0,1,2 & 7 you could have rdx:rax as the shift reg, then do
mov rbx,rax ; save bottom half
and rbx,128+7 ; taps mask
shrd eax,edx,1 ; shift bottom half down, fill from top
popcnt rbx,rbx ; how many taps were set?
shrd edx,ebx,1 ; shift top half and bring in the parity of the count
and get a new state in about 5-6 clock cycles
Had to implement this in System Verilog for an intro EE class!
This is very cool! I guess it's harder to use this in cryptographic applications because by listening to n consecutive output bits, you can determine the rest of the output.
One great use of LFSRs is random number generators in sandboxy games like minecraft. They're very easy to build from redstone or whatever system the game has.
“Tap” has everything to do with plumbing - you are tapping into the stream of bits just as a faucet taps into a stream of water.
@Michael Lorton No. A faucet may stop the stream and it never feeds back.
@@MrCuddlyable3 It doesn’t but it can, and in the animation in the video it does just that.
@@FlyNAA FAUCET n. a metal piece of equipment that you turn to control the flow of water or other liquid from a pipe, especially on a sink or bathtub. The British word is tap.
@@MrCuddlyable3 yes, agreed. So what's your disagreement with Michael Lorton's comment?
@@FlyNAA Come back when you can make an LFSR using a faucet.
I would love to understand the maths of getting the taps right for maximum period lengths!
From the video, I came to two insights: one tap must be at the units digit, or you're wasting length, and if the distances to the insertion point share a common factor (say, you put bit #0 XOR bit #2 into position #4), you produce two separate sequences which never mix. Both of these "insights" might be trivial, but they fix one tap and eliminate some choices for others. I'd also avoid stuff like "bit #0 XOR bit #1 XOR bit #3 XOR bit #4" -- because XOR is associative and "bit #0 XOR bit #1" is the same as "bit #3 XOR bit #4" three shifts ago. That eliminates #0 XOR #1 XOR #4 XOR #6, too, because that can be taken XOR bit #3 twice, and then you have #3 XOR #4 XOR #6 both now and 3 cycles ago.
You need a primitive irreducible polynomial of the right order for the number of bits.
This is very informative. Thanks. Is there any way you could cover Nonlinear FSRs?
1 min since upload, 13 min video, two downvotes. WTF
People jealous of him handsomeness, probably
It's a shift to the right
And a little xor
With your taps on your bits
You bring your loops in tight
Now forever called the LDBW algorithm (or sing it with me) "Let's do the bit warp, yeah!"
(Rocky Horror Picture Show reference in verse form? You rock, sir. Made my day)
@@jones1618 Thanks Stephen. Dr Pound made me think of Rocky Horror when he used the first two lines in the video at 04:12 , I felt like I should add the last lines. Press 3 when watching the video to get those lines.
Wooo coding examples! More!
2^128 is around 3.4*10^38
Yes, if you're watching the digits print on the screen you'll be there for a very long time, but I don't feel like 10^38 is big enough to be truly "secure". That's probably 256-bit encryption is more common.
"I'm going to initialize this at random." Hey look, you got your random number! I agree, the code was simple.
All PRNGs depend on a “seed”. If you are using it for non-adversarial purposes (simulations, games), use the current time. If you are using it for crypto (literally “hidden”) and are facing a potential attack, use a REAL random-number generator, like rolling dice, to generate the seed.
Two xor streams running at slightly different frequencies and then xor'd together is impressively random. Especially when the frequency offset is inherently unpredictable.
I’m not sure I’d trust this. Seems shifty
Don't worry, it's going to be more of the same
Very informative! Could you also do a video on MT19937 algorithm?
Mike Pound❤️❤️❤️❤️❤️
I implimented s 32-bit maximum LFSR for rand() in he 1970 C libfary for SDWTPc 6809 hobby omputer, and got roundly fritidised for not using a "proper" linear ongruential pseudorandom number generator. As you pointed out LFSR's are stati9sically excellent and more to he pointk very vey fast, particularly on s processor hat didn't have a hardware DIV iinstruction.
thank you that was so useful :)
I learn more from Computerphile than from my computer science degree. Funny thing is, I went to the University of Nottingham where all these lecturers are 🤣
that's pretty cool, thanks!
LFSRs are also useful when you need a counter or timer in hardware to count up to some fixed value, since LFSRs need much less hardware logic than a binary counter.
So by using a LFSR instead of a binary counter, you save silicon area, increase max operating frequency, and lower the power consumption.
How would it work as a counter? It goes through every arrangement of bits, but not in order obviously, so how does that work?
@@monkatraz if you need to count some event, and generate a signal when you have seen 10 events. For example.
Just reset the LFSR to a known state, execute the LFSR on every event, and generate the output signal when the LFSR has reached the 10th state.
Interesting video as usual :)
However, at one million bits per second it'd take much, much longer than "10 to 20 times the lifetime of the universe" to exaust 2^128. More like one million billion times.
Also, saying "the statistical randomness of these streams [LFSR] is really, really good", without further qualifications, seems very naive; I'm pretty sure the 128-bit generator he presented would fail all randomness test suites, such as TestU01 and PractRand. In the original 2007 TestU01 paper the authors tested some LFSR (more modern and sophisticated than the one in the video) and they failed randomness tests. Marsaglia tried with his xorshift generator but today we know they have relevant flaws. You can make good generator using this approach, such as the recent ones by Vigna (xoroshiro etc) but it's not so easy. It it were, we would have got good random number generators in 1965 and not in 1997 or so with the MT.
Maybe he meant to say 10 to 20 orders of magnitude.
Maybe (10 ^ 20) ???
closer to 10 to *the* 20 *th power* i guess
He literally did qualify it
I would like to hear more about grammars and making a language like before the pandemic