How Noise Improves Computing
Вставка
- Опубліковано 12 кві 2024
- Check out courses in coding, math, science, and more on Brilliant. First 30 days are free and 20% off the annual premium subscription when you use our link ➜ brilliant.org/sabine.
It sounds weird, but randomness can actually improve computer calculations, in certain circumstances. After some digging into the reasons why, I’ve uncovered three different ways this can happen. The first one is noisy computation, then there’s stochastic computation, and then there’s probabilistic computation. What exactly are the differences and how do they help computation? Let’s have a look.
🤓 Check out my new quiz app ➜ quizwithit.com/
💌 Support me on Donatebox ➜ donorbox.org/swtg
📝 Transcripts and written news on Substack ➜ sciencewtg.substack.com/
👉 Transcript with links to references on Patreon ➜ / sabine
📩 Free weekly science newsletter ➜ sabinehossenfelder.com/newsle...
👂 Audio only podcast ➜ open.spotify.com/show/0MkNfXl...
🔗 Join this channel to get access to perks ➜
/ @sabinehossenfelder
🖼️ On instagram ➜ / sciencewtg
#science #sciencenews #technews #technology - Наука та технологія
As a heavy metal fan I'm glad that noise is finally getting the attention and respect it deserves.
I am gonna blast my speakers with speedcore, gonna scare that CPU into overdrive
Perhaps you mean _"grindcore_ fan".
Thanks Mr clever
Not the admission I’d expect from a fan
I have calculated that moving to renewables it is much cheaper to 100% finance Greek families acquiring zero cost renewable energy(sun,air, battery), than the Government giving subsidies, tax breaks and costs of improvement of the electric grid.
This finding changes the present approach to funding , and promotes the transfer from fossil to renewables.
I have been writing letters to the President of the European Commission, to the Greek Prime Minister and others , arguing and presenting the savings with numbers and data.
Additionally, the management, resilience and security of the electric grid will be much better with this approach
The social impact of financing the citizens for acquiring renewable energy (sun,air, battery) will be enormous in the abundant production of goods and freedom of the citizens.
Could I kindly ask you to, please consider, explore and present this approach.
😊
I built a hardware random number generator in the 70s by reverse biasing a germanium transistor to it's breakdown voltage. I used the resulting white noise to make random 1s and 0s that were constantly flowing through a shift register. When you pressed a button, it would use the random bits in the shift register and a bit of logic to present a number on a 7-segment display. The random number would be between 1 and 6. A true random die. Got an A+ in my 9th grade science class for designing and building it. That was a lot more than ten years ago.
I don't know if you still have any of the schematics or pictures, but I recently started dabbling in electronics and designing circuits myself so I'm thinking about wanting to try building something similar.
Sounds like a great time :)
@@maverick9708 I wish I did, I don't have the die anymore either. Sold it in desperate times. But I pretty much have what I did in my head. It's on my list of things to recreate from the past for my other channel (which would be rude of me to mention here).
@@maverick9708 There are a lot of schematics and partial schematics for analog synthesizers available online (electronic musical instruments, in case the context is unclear).
There are two main types of noise generator circuit that have been used. One uses a simple device like a transistor as the main element, making a true random source (but subject to electromagnetic interference). The other uses a shift register starting from a known state, but producing a usefully long pseudo random sequence, by feeding the output back to different stages of the shift register - for example look at the circuit for the TR-909’s noise generator.
Both types are meant to produce audio noise, but they can just as easily be used to produce a random or pseudo random one bit number. You might need a comparator circuit (e.g. op amp based), to get a binary value from the transistor based one, which you can also use to change the probability of getting a 1 or a 0, by changing the threshold voltage.
That's way kool. P.S. I was doing that wiz kid stuff back in the day too. Had way heaps of fun, except for the beatings for being a geek, that wasn't fun.
There is no use of random generation in computer science except to generate unique id / key. Generating random values in all other applications is because of lack of real data. There is no other use of randomization in science or technology. If we depend on, or reference to randomization, we are faking since it will not be reproducible.
As a computer engineer at IBM (1977-1983) we used "simulated annealing" techniques on our next flagship mainframe for chip/circuit placement at many packaging levels to minimize power requirements, eliminate wiring bottlenecks and to maximize processor speed.
I wish you lot would stop using stupid prentious names for these things....enough already begorrah.
I experimented with that too for placing. You still have to define a cost, potential function, not easy.
I never got useful results.
I've used it to find and optimize nonstandard kinds of filters for sound processing. It worked very well. Note that if the filter had been based on common form then I could have used an already known formula to make it instead of using an optimizer.
Something very much like the "truth probabilities" trick, which I hadn't heard of, is widely used in computational linear algebra, where it is often possible to approximate difficult matrix computations with the help of random vectors.
Yeah aerodynamics calculations use that, the solutions are too large to directly calculate so a psuedo random Jacobian iteration is used
There is no use of random generation in computer science except to generate unique id / key. Generating random values in all other applications is because of lack of real data. There is no other use of randomization in science or technology. If we depend on, or reference to randomization, we are faking since it will not be reproducible.
Not to mention that mini-batch gradient descent, a variant of stochastic gradient descent, is the current standard for training artificial neural networks. Just to nitpick: according to the Tokyo university paper, the annealing processor system used roughly 100 seconds rather than 1000 (8:37). The caption is correct.
There's an idea percolating in the neuroscience for years that stochastic resonance also exists in neuronal processing. Claims suggest that internal (brain) noise enhances a sensory target detection among environmental noise. Interesting idea that captured my attention for a while, difficult to capture though.
Efficiency from chaos. I love the irony. That’s the excuse I’ll use the next time my wife complains about my messy desk.
You need to keep a variety of tools in level 1 cache.
It's not irony. It's a higher and more general level of efficiency. Would there be e. g. life on earth without it?
BTW: Be careful not to create life on your desk 😉
@@imho4556
Definition of irony: An outcome that is opposite of what you would expect. Chaos is not generally associated with the idea of efficiency. It provides efficiency in this context when developing a program that needs random numbers since there is no formula for generating random numbers which is why lottery numbers are generated by numbered ping pong balls. Chaos is a component of nature and economics and is therefore necessary when modeling natural systems.
It doesn’t matter if the irony has a rational explanation, all irony does, it just has to be counter intuitive like a criminal who has been in and out of jail and ends up becoming a prosecutor or the chief of police. It’s possible, but contrary to conventional expectation.
@@kurtiserikson7334autism vs autism
Tim Palmer's excellent book, "The Primacy of Doubt," gives several examples of chaos geometry that shows how randomness actually enhances computational results for Lorentz systems. BTW Sabine reviewed this book and gave it a nice accolade on the backside of the dust sleeve.
2:44: Sarcastic computing
I think you can easily add sarcastic physics to that.
One big application of randomness is in Monte-Carlo simulations. This is used to ascertain effects of parameter uncertainties in highly complex systems. E.g. spacecraft algorithms are frequently validated using Monte-Carlo sims where the various spacecraft parameters are randomly scattered based on the uncertainty in their values.
3:50 Even ChatGPT isn't safe from Sabine 🤣
I think a Turing test between ChatGPT and Sabine would be fascinating.
@@tarmaque ChatGPT would start questioning its free will.
@@Kenjuudo According to Sabine, free will is an illusion. So... Yeah.
I have two favorite uses of randomness.
The first is in down sampling an image. Say you want to reduce the resolution by a factor of 64. You would normally go through the source image in blocs of 64x64 and average them to compute a pixel on the destination image. However you can just randomly sample a few pixels in the source region and average those for a much faster process, that does not suffer from bad aliasing.
The other is in trying to digitize a weak analog signal. Say you have an analog sine wave that fluctuates between 1 and 2. The digital signal will be a simple square wave that is 1 for half the time and 2 for the other half of the time. But by injecting randomness into the source signal, you end up with a signal that randomly goes from 1 to 2 based roughly on the gain of the source signal. You end up capturing the signal with more fidelity as a pulse code modulated output.
3:42 Video error: Should be "50%: either 01 or 10".
Which proves: I watched it :D
i was wondering why nobody else pointed it out lol
@@Irondragon1945 Believe me, I was wondering the same since that video was a few hours up when I watched it.
I would be less afraid of this machine wanting to be called Hal than if it told me, "I'm sorry Dave, I'm afraid I can't do that."
I used noise for years in Photoshop filters. Often it's just the right je ne sais quoi to help sharpen OR blur a specific part of an image just right, and for MANY other uses.
I've also been long fascinated by the phenomenon of undertones and overtones caused by resonances between two different tones.
Back in the old days, we would get pseudorandom numbers by arbitrarily sampling a timer or sound generator.
It can be quite difficult to come up with truly random numbers because there seems to be some sort of pattern to almost any source of data you choose.
This method has been in use for much longer than 10 years. Back in the 80s, my Amiga had such a device. It worked like this. The scan line on the monitor was faster than the device measuring it, leading to an error that was exploited. This error was used as a random seed to generate genuine random numbers. Even my ZX81 uses something similar and it was made in 1981 (hence the name).
Back in the 90s, a company called NOMOS used simulated annealing to plan radiation treatment.
Agree. I built a hardware random number generator in the 70s by reverse biasing a germanium transistor to produce white noise that I used to make a constant stream of random bits.
@@imiklasome Intel processors (and probably others) have this built in as “true” random number generators.
@@imikla The funny thing is, when trying to get ordered output, we sometimes end up accidently creating random noise. 🤷♂
Wish I could remember the details better. I wanted to get a pair of random 0s or 1s on the ZX81, so 00, 01, 10, or 11. I found that the probabilities were not exactly 1/4 for each, but if I ran it a large number of times, there was always a very slight bias for the numbers to be the same, 00 or 11. It wasn't by much.
Really enjoyed the Timex Sinclair version of BASIC, though.
Fun current use to me - stable diffusion image AI starts from a random noise image, it reduces the number of generations needed to get a "good" image.
I worked for a company (Nanoteq, SA) in 1998 that made a computer card that used white noise from an antenna to generate random number when it does hardware encryption of transactional data on the fly. It was very successful and even Commerce Bank (DE) used it back then.
IMO, perhaps Sabine's best video to date. Incredibly important concepts presented here. If you watch it once, watch it three times. Keep in mind anything humans have done, nature did a long time ago, so these concepts have value to all disciplines of science. Also, any video that mentions stochastic in the proper context (ie, without being stupid as hell), is a good thing, a very good thing indeed.
Thanks, Sabine. Your talk took me down the winding memory lane of collaborative research efforts of UBC/Dr John A. Wheeler's Exxon tech memo on Random walk(2D Markov chain process)/ University of Calgary Geophysics dept PhD thesis on 3 D random walk/ University of Alberta, and of course D:Wave.
Sabine, you forgot one more class of computation: 4. Noise-driven computation, which uses noise to drive computation. An example is "Brownian circuits", which use Brownian motion to make signals search their way through a circuit so that a deterministic outcome is obtained. Another example is circuits in which the signals are noise sources or superpositions thereof like in quantum computing. There have been research on implementing Brownian circuits by Single Electron Tunneling circuits, as well as by spintronics based on skyrmions.
Proud researcher on applied Chaos theory. This video directly enters in my golden archive. Sabine is amazing, as always.
Many recent CPUs support the RDRAND and RDSEED instructions for returning random numbers from an on-chip hardware random number generator.
Also, many SoCs that contain ARM CPU cores contain a HWRNG peripheral (/dev/hw_random).
Thank you for accepting random numbers. In neural networks they actually kill certain nodes at random to avoid overfitting. 🎉They told us that radioactivity was random in which we do not know what atom decays. The word noise implies that humans cannot make out the signal as per one interpretation if you look at things lile SETI. I often got the police walkie talkie on the noise in the TV as a kid.
---
ChatGPT Verified
Yes, dropout regularization randomly turns off nodes during training to prevent overfitting.
I actually worked on a project for my networking course last year which involved using randomness for optimisation, but you might be well aware that it was all for research paper publishing rather than actually improving humanity. (Like 99% of research papers)
Sometimes, when an algorithm needs to make a choice but doesn't know how to make the most optimal one, making it at random is usually better, but the reason is unknown.
A correction on pseudo-random number generators (PRNGs): They don't have to be very computationally intensive at all. The only requirement is that they algorithm be uncorrelated with how the output will be used. Their main problem is actually that they need to be "seeded" with an initial random number, and that's not feasible in some applications (such as in a computer on its first startup.) That's where true RNGs come in-a bit of hardware that is guaranteed to give a random value each time even though it can't keep notes about its internal state. (And generally you only use it to seed the PRNG.)
I assume that stochastic and sarchastic mean similar things.
That's why stochastic climate models are so super dee duper accurate.
You can generate a random number with some math function and taking the decimal part.
for example , you can take square root of the product of date time in msec and a random number generated by the computer, and then take the decimal parts , if you plot the results graphically , you will find that it looks liked a white noise.
Cheers bud, gonna save that idea for later
Still predetermined
Hey, I'm an expert (kinda) in neural computation! Noise as computational strategy is super interesting. You'd think evolution would push us to strict logic, but brains are statistics machines and on a neural population level noise gives a much better representation of signal encoding than anything strict. Neat stuff
Is this noise our perception of free choice?
I'm working with some CA RC techniques right now.
@@user-vc5zt9ci12 I would say the perception of free choice as well as sense of self breaks down upon examination techniques for example mindful meditation. Ironically, the sense of self isn't even subjectively real.
Evolution depends on noise. Without noise it would fail to improve. You need population of members who are varying. And then apply fitness function to find the ones who are better than others. Without noise they would all be the same. All genetic algorithms, regardless whether applied by nature or a computer, require random noise. It also includes the decisions, not just biological functions. You want some people to go north while some others go south. You need some to fight, others to run. Etc.
@@user-vc5zt9ci12 your statement itself is the truth. "Perception of". You don't really have it as the "decision tree" is already in place, you're just running the "data" through it and getting a result. And it changes itself, so you don't even know what the result of running the same "data" again through it will be...
Thanks, I have long wondered if such things could be done!
Really enjoyed this analysis of the topic. Thank you, Sabine and team.
So interesting - appreciate your insight!
I watched a video that explained how an electric current 'knew' which path was open and which shorted. If you then described a maze with electrical paths, it would solve it 'instantly'. I feel like this is along those lines.
From a computer science vantage, stochastic theory is in many ways the foundation of probability theory and simulated annealing. We also use it in some neural networks and genetic algorithms. What you present as stochastic computation, a simple stochastic matrix, is a very limited example of how varied the field is, and many of the later examples are still essentially stochastic computations behind the scenes. One of the other areas stochastic theory creates is the Markov process (and Markov chains) and Monte Carlo analysis.
An area of research I am interested in relates to discerning the entropy of apparent noise. Any noise over a finite time has entropy and can be described with finite generators. There are interesting use cases from not only being able to create the generators, but also the processes that create the generators. This can lead to higher speed networks, higher quality processes, better cryptographic algorithms, and techniques to uncover counterfeit information, such as that generated by AI.
That metal plate solution made me think of the Simulated Annealing algorithm, with volume as a stand in for the 'temperature'.
Wow! My first draft of this note was very badly written. I’ll try again:
Great video here. I’m trying to catch up to what we know in physical chemistry (or maybe quantum chemistry) about how to bond CO2 in the reverse Krebs cycle. A long the way, I think I understand that molecular bonds are more than just the sum of the pairs of atoms. Somebody referred me to ‘supramolecular’ chemistry, for example. I gotta be honest: it’s starting to run together… But intuitively, I feel like this survey of random numbers being useful is kinda reminding me of the ways people describe electrons. In the video, there’s a comparison of sand finding stable points on a sheet of metal with vibrations running through it. That’s quite a good illustration. I immediately thought of how electrons work. I’m trying to find the current state of thinking about how chemistry works in mitochondria, but I don’t think I’ve got the right search terms yet. Please feel free to suggest. I’ll read anything at this point. I’m particularly interested in how we might replace haber-bosch for fertilizer production, or at least stop using methane for it.
So the big shift that will help you is to abandon the idea that the electrons are within the bonds or being bonded. ❌
@@philipm3173 Thanks! This will sound a bit elementary but I’ve found “crash course” video channel on UA-cam.
@@blinkingmanchannel Check out the video "How atoms REALLY make molecules."
@@blinkingmanchannel and as for the Krebs cycle I recommend "the bumbling biochemist", I think I saw they just uploaded a video on TCA
@@philipm3173Thanks! I'll comment further once I've had a chance to see those.
In the meantime: 😂 UA-cam decided I'd like to see videos related to "Breaking Bad" 😮😂 So I watched some. I see why it was so popular. And I'm glad we're done with the "shaky handheld" shot.
Randomness is highly used for games as well, Sabine. For card games, for example. 😊
Stay safe there with your family! 🖖😊
The thing is, for most applications of "random" numbers, pseudo-random numbers are good enough, and computers are VERY good at producing those, in extremely large quantities. They're not "truly" random, because they are generated by algorithms, and repeating the algorithm with the same inputs will always produce exactly the same stream. But they do pass the primary standard tests for randomness in a sequence, so they can get the job done. For most simulation purposes I'd expect them to be fine.
Loved those mysterious ChatGPT 'higher math' probability calcs. Here's a fun homework project: implement a spreadsheet to run on top of ChatGPT. Using the super-smart AI Chatbot mathematical powers, the results are sure to be unpredictable and entertaining for all! 🙃
Back in the day, we used noise to improve the accuracy of A/D converters. It was called "dithering"
Thank you for the video.
If we have some gas confined by a piston inside a cylinder, then we observe at once that the piston is heavier than the Planck mass. Model it with a bit of classical Brownian motion on the scale of the Heisenberg Uncertainty Principle, but replace this with the Fuerth Uncertainty Principle. Model gas molecules with a bit of Lucretian motion, which means random changes in direction but no change in kinetic energy. Any tendency to a Poincare cycle in the gas will be rapidly disrupted by all this randomness, and our model does not have any arrow of time issue.
As a software engineer, my primary use for randomness is security. Outside of that, I usually want pseudorandomness. Usually for things that are intended to be entertaining.
Thanks!
Thanks in return from the entire team!
PRNGs - Strongly preferred!
Easier to debug; Test can be seeded to be reproducible. They produce more even distributions for crypto work. Their security is testable and quantifiable. (See Yarrow, Fortuna, etc.) Much higher throughput with no pool exhaustion. That said, great vid! Cool to see options on the horizon.
But for cryptographic applications you generally want to seed your cryptographic PRNG with a true RNG.
@@__christopher__ Agreed!
The Texas Instruments TI-58 was considered “powerful” at introduction in the 1980’s. The random number generator would repeat after ~1000 iterations. Not very random. But it would generate a solution if one recognized the RNG’s limitations. The tools have definitely gotten better.
Hardware RNG cards have existed for 25+ years, not 10. I remember reading about them in the late 1990s and it seemed an established industry, just small and niche. FYI, "noise" algorithms can also be seeded by this RNG and generate 2D maps that can be interpreted as topographical information used in the procedural generation of video-game world terrain. I'm not sure how to utilize such techniques to generate randomness such as caves and spires or plateaus, though I suppose it's possible. Randomness helps keeps humans entertained as they jog on digital hamster wheels.
Caves can be done with cellular automata on noise iteratively to create a sort of "surface tension" type effect joining neighbors & smoothing them out.
Plateaus could be done with perlin noise & fractal perlin noise with a max() function to chop the tops of hills off.
Spires could be done with weighted perlin noise, exaggerating the peaks & flattening the rest.
Gradual steps & layers on any of the 3 could be done with an effect similar to cel shading, where you bias generated data points near certain ranges to clamp to a certain value, or be weighted to approach it faster.
Each randomness generation has its implicit bias(no bias is itself a bias). I believe the closest we can get to a truely random must be an aggregate of all the techniques(the technique used for a specific problem would itself be chosen randomly which proposes a derivative regression problem but I digress). Its also worth considering if we are even asking the right question. Many physics data manifests as cyclical, it could be that chaotic dynamic systems are just a huge number of cyclical patterns laid over top each other, and true random is a ghost we've imagined to exist
There are also algorithms that use some randomness for problems that aren't exactly optimization problems. For instance there are some linear problems whose solutions can be found much more efficiently with algorithms that use some randomness and converge on a solution rather than compute that solution directly.
Another point is that simulated annealing is a useful kind of algorithm even on conventional computers using pseudo randomness rather than hardware random sources
If you are using simulated annealing for optimization problems then you are at least 80 years old and you have stopped reading the literature over 40 years ago. There are much, much better modern algorithms for most such problems.
@@schmetterling4477 well, I was using the library of routines from "Numerical Recipes in C".
However I just saw an article mention linear solutions that can be found hundreds of times faster with an algorithm that has a little bit of randomness in it.
That might be related to Avi Wigderson getting the 2023 Turing Award, I'm not sure. I guess that was 80 years ago.
thank you for the video, noise is a very interesting subject for me. I wonder if my tinnitus is stochastic.
When I first proposed using random noise to do computing in 2020, especially for AI hardware acceleration, many people thought it wouldn't work because it defies modern computing logic. Then, the 2024 Abel Prize (Nobel Prize in mathematics) and the 2023 Turing Award (Nobel Prize in computing) go to recognise the importance of randomness. Sometimes, you have to see ahead to make decisions, not because it is irrelevant for now, but because it will be relevant in the future.
This a theme of influence showing up in countless avenues. Inspiring models on this basis.
Reminds me of movie & music where to much quality & clearity makes it hard for us to zone out or dive into movies that are to clear.
The distortion in sound can even distinctively stand alone as an era or genre we have created.
This definitely deserves some sycho anylisis by anyone that studys our relationship with maths, science and the world around us.
This simple fact its the point between dualism that we are full of historically is very interesting side note. I hear new orgin of life trying to use this and maybe something like grass, or things we miss diagnosis as life can be allocated some modeling value on this.
But i would think its a more precise and accurate foundational architecture to be found non the less
It could be the " Rugitus principia mathematica " -
Methods Of Bosonic Path Integrals Representations: Random System On Classical Physics UK ed. Edition
by Luiz C. L. Botelho (Author)
Pseudo random noise is also placed on idle channels in code division multiplexing RF mobile communications instead of the “silence” encoding as it improved the overall signal error rate.
You mean to tell me my over-paid ECC ram, the LC filters in my speakers, the carefully calibrated diaphragm in cars pressure sensors, the laser cut resistors in passive EC's and ICs, and so on and so forth are holding us down from scientific enlighten? Truly entertaining, miss YTber.
Noise allows to upsample AD converters form eg from 10 to 12 bits because the noise is not randomly distributed
Never stop your work, millions of people like you and value your knowledge. Also, not all those are kid but expert in many domains.
My experience is that Monte Carlo and ruining frequency in encryption need random numbers. However, being the heir of fuzzy logic and the founder of post-science fuzzy logic, I believe that fuzzy convergence will avoid dead loop in exact convergence scheme. One of the way to produce fuzziness is random numbers. I also speculate that nothing can exist if it does not compute, and fuzzy logic should be the foundation of knowledge with random number playing a vaulted role in knowledge. The recent Turing Award is given for randomness; I just hope that the recipient knows fuzzy logic, since my nomination on fuzzy logic, robot touch, and complete automation have all been rejected.
We also use noise in signal processing to boost weak analog signals (stochastic resonance).
I have long believe that two technologies are the near future of superpowered computing: analog chips and probabilistic computing. I think I saw the analog chips on a Veritasium video or another similar channel. Really fascinating stuff.
In a way, I am comforted by the idea of imperfect computing. Most Skynet scenarios rely on the machines being smarter or somehow "more perfect" than human minds, therefore the machines know what's in our own best interests better than we do. I'm a world of imperfect computing, that doesn't happen. Instead, the machines aren't any more "perfect" than their human constructors, they're just faster. This sort of dynamic could foster a cooperative environment where humans and machines work together for the betterment of everyone.
Idealistic and naive, probably, but it sounds nice anyway.
There is a government run lottery system in the UK called Premium Bonds, and the device at the core of that, ERNIE, for Electronic Random Number Indicating equipment had a true hardware random number generator at its core, and that was devised back in 1957, by a certain Tommy Flowers. Who is he you may ask? Well, he just happened to be the designer and builder of the top secret Colossus machine at Bletchley Park, the first fully electronic, programmable (albeit not Turing complete) computer, which automated the cracking of encoded messages using the Nazi Lorenz machine (a completely different type of machine to the Enigma one, using a different cryptographic machine.
In any event, the idea that hardware random number generators have only been used for about 10 years is not the case. They have been used for at least 67 years.
ERNIE 1 used the signal noise from neon tubes, was the size of a van and produced 2,000 random winners an hour. The latest incarnation, ERNIE 5, uses quantum effects to generate numbers and produces 3 million winning numbers in just 12 minutes.
Of course the key to simulated annealing is the simulated cooling profile. You turn up the 'heat' to get large jumps (say in the position of wiring in a PCB) and then as you cool it the changes become more and more localized until the system 'crystalizes' into its satisficed optimum state.
I remember the ATARI 8-bit systems had a wild random number generator at the circuit level, I believe it was. I made some fractal graphics stuff back then and it made a perfect 48-bit float randomizer.
Dithering is used in digital audio to give more headroom
Source of creativity.
The best encryption is that which you can not differentiate from randomness or noise.
What do you mean? Noise is random.
@@giannismentz3570 Yeah, noise, true randomness, same thing. And yes, the best encyption is unbreakable (without the key). For example One Time Pad. Generate secret key (truly random) with the same length as message you want to send, distribute it securely to final receivers, XOR your message with that key, destroy original message. Now result of XORing is also truly random and without the key is useless. But with the secret key you can retriever the message by XORing it with scrambled message. In other words you encode original message in difference between two sequences of random numbers. So message become non local in some sense ;)
I Got 0.99 Problems, But the Noise Ain't 1.00
Kindergartens should be ideal grounds for supercomputing😂
More and more companies offer kindergartens for their employees with children, maybe they are more interested in the noisy chaos that the children produce than in the productivity of their parents...
Probabilistic computing is indeed fascinating, but also theoretically rather taxing. BPP (bounded-error probabilistic polynomial) class of problems contain many highly practical ones. Their solutions analysis (algorithm correctness and complexity) is in sharp contrast with their perceived simplicity. I remember that back at the uni, we did analyse a simple BPP algorithm for hypercube routing (this is used in supercomputers with hypercube architecture to efficiently pass information between CPUs). The algorithm can be implemented in ~10 lines of code. The analysis took half of the semester. :-)
"That's amazing!" I agree. 08:42
Great Stufff!!
@sabine. Listen to Feynman's talk about reversible computation (in tokyo when I remember correctly) to find a 4th way in which noise can drive extremely power efficient calculations. (Ah maybe I should have listened to your talk first ;) . You are talking about it indirectly. ). Thanks for all the great content.
Perhaps not just a coincidence you're treating this topic this week: The ACM just awarded this year's Turing Award ("Nobel of computer science") to Avi Wigderson, a leading computer science researcher working on randomness in computing. The main work cited for the award is about *derandomization*, i.e., showing that, when randomness helps a computation, there's a deterministic algorithm that works as well. Here's the text from the announcement: "Computer scientists have discovered a remarkable connection between randomness and computational difficulty (i.e., identifying natural problems that have no efficient algorithms). Working with colleagues, Wigderson authored a highly influential series of works on trading hardness for randomness. They proved that, under standard and widely believed computational assumptions, every probabilistic polynomial time algorithm can be efficiently derandomized (namely, made fully deterministic). In other words, randomness is not necessary for efficient computation. This sequence of works revolutionized our understanding of the role of randomness in computation, and the way we think about randomness." -Tom
I'd be looking at an analogue solution to the random generator problem. Perhaps the Brownian motion in an on-board liquid or it might be more practical to use a gas.
randomness is super powerful! The classical best-known maxcut algorithm by goemans-williamson also uses randomness in a brilliant way and works pretty well in practice (87% of optimal solution in worst case but typically more like 95%). Also, maxcut is not that difficult on planar/euclidean graph layouts as you can lump clusters of neighboring nodes together and just assume that they belong to the same side of the cut. You can then bruteforce the solution for the (much fewer) clusters. The result can be made arbitrarily efficient in polynomial time (though it takes longer to get better solutions as you need more small clusters).
This is fine because we can just wear ear plugs all our life (I have to for bicycling anyway). Anything for the machines (I'm just sucking up to them in case they take over, they'll need whipmasters). In 1966 one of our programs (not mine) for seismic oil exploration blew a gasket whenever a "dead trace" (all 0s recorded) happened & printed "Floating Point Underflow - 100% White Noise Added" (it was dividing by zero) repeatedly (Jack Nicholson Shining all work and no play) as fast as the huge IBM line printer could run the 11x17 continuous paper through & the operators scrambled to kill it before it had wasted a box of printer paper. I used pseudorandom rectangular deviates sequences for randomizing with the seed based on the obvious date and time including how thousandths of seconds had passed in the second when the CPU randomly was at seed selection. I used it for iterative process minimum RMS error fit geophone line calculation seismic oil exploration in ~1970, for computer simulation modeling in 1973 and 2002, and for controlling 5 elevators to answer the calls fast in KOIN Centre, Columbia & Clay, Portland, Oregon in 1990 (upgrade to state-of-the-art Prestige Building security & monitoring system I wrote in 1984-85). Prototype computer control of elevators. Building Engineer said it worked real good, fast service. Torn out soon later because technology advanced fast, computers cheapened since our IBM PCs (new computers they invented, even smaller than 2 wardrobes). I tried devising Regular Logic for 5 days to assign elevators faultlessly, wasted 50 hours of frustration and made an Executive Decision to switch to Fuzzy Logic, random numbers generated to point into a Table of values statistically corresponding to the required ratios so that any one pick was random unpredictable but large quantities of picks were guaranteed to group in the required ratios, the Magic of Large Statistics averaging out, similar to quantum mechanics on a simpler level. I did something similar but less in 1975 on a Fairchild F8 with PROM or EPROM, I added closed-loop-feedback to an open-loop elevator, improved service.
So, I'm going off topic, Sabina. I was doing some listening to a program, and I was listening to the physics dude and his way of thinking. And it occurred to me that his way of thinking reminded me of my son at 5 years old. And it shocked me at first. Then, as I was lying, there I thought how could I have a conversation with someone that thinks like that seriously. I'm still wondering if this way of thinking has become normal in the field. To be quite honest, I find listening to you, Sabina, to be more adult like. Are they so hardwired to this way of thinking, I wonder. Could they ever really understand if it slapped them right in the face. Anyway, another great video,Sabina. Thanks for being the adult of the field. Peace ✌️ 😎. I'm still baffled about this. I would have to explain it like to my 5 year old. Incredible. Thanks, kid. He will be 29.
I remember years ago we set up a microphone in the server room and fed its input to the random number generator in the OS to give it truly random noise root.
Did it change anything about the result of what you were doing? Probably not, right?
@@schmetterling4477 It did produce a more random number, especially at that time
@@rrmackay Yes, but did that change anything about the result of what you were doing with that random number?
Yep, I was also perplexed when started working with radio signals, that you can increase signal/noise ratio (SNR) by ADDING noise. :-) (not always with any signal and any noise)
And adding many amplifiers in parallel *decreases* the output noise.
True random number generation is still one of software engineering's unsolved problems. Sure we can generate pseudo random numbers, but given enough values patterns soon start to emerge.
Right. I got to admit did not understand many things, and I design hardware and embedded software for a living. In general, noise is a pain for electronic circuits and we want to avoid it, just like the quantum computer. However, sometimes noise or randomness is needed :
- when doing analog to digital conversion and we are averaging the output. Without noise, we could average all we want and get the same result, with noise we can average and increase resolution. This is very commonly done.
- For programming games. If we want the next move of our opponents to be unexpected, it better be random.
- For testing noise canceling algorithms. Hard to test those without noise.
- For certain AI algorithms. If an AI never tries a random thing when learning, how is it to learn something new.
As for random number generation in a computer, a common source used is the program code in a computer program itself. These are instructions and operand codes and if you just retrieve those from memory, it is more or less random.
Another source is human input. The moment a human pushes a button on a keyboard is pretty random. When a high resolution timer is present it is a good source of randomness.
9:55 -- this is the premise behind "reconfigurable computing"
Simplest / most readily available source of hardware noise: your soundcard!
Just use the an ADC with nothing hooked up and you get hardware random noise.
Pesky problem: the samples tend to be correlated, 50Hz and such.
Yeah we have also chips for grafic, ai accelerators, fpgas etc.
It gets more specialized.
Just 2 days ago I was writing a program that would make a random selection but avoid the previous item. That is, it would loop and compare.
So my first thought was to use the computer's date and time function as nanoseconds as a seed and then keep calling the languages built-in pseudorandom number generator.
BUT... the time of the call to the date function is uncertain because the operating system is running processes and check for breaks and so on in background. Nanoseconds from date and time can never be precise.
So I just put the nanosecond function in the loop and use it as the random number.
This is closer to true random than the pseudorandom function.
No additonal hardware needed.
Instead of looping and comparing (which rarely but inevitably requires many loops to settle) you could just rand (n-1) and add 1 when the result is >= the id of the previous item. One shot and no bias.
As for calling from the clock for each rand, there's reasons people don't do this. Often, when you need theoretic/cryptographic randomness, you need more than just uncertainty, you need independence which your method likely lacks, especially if it's called very frequently.
And if you don't need strong randomness, then PRNGs are just more convenient for getting uniform numbers.
For many, many purposes, pretty much any sort of randomness are fine, so if you like your method, keep it.
Sabine, keep being awesome!
I trust the "conventional computer" used in the annealing comparison was a bit more modern than the one shown ;)
That chatgpt burn was hilarious.
Im wondering if that will lead us to the first infinite improbability drive.
i thought annealing was a way of always having the right amount of noise to jump between solutions on a given scale. In annealing you gradually cool down and so you first make large scale choices (high noise level) and as you cool down (lower noise) you make smaller and smaller scale choices until you end up at the optimal solution. So i didn't understand that part about not knowing how much noise is needed.
This seems analogous to how analog (see what I did there?) amplifiers require small oscillations to work. End goal is a large increase with 0 oscillations, but with 0 oscillation it wouldn't work in the first place.
Very INTERESTING 🧐 now tell us about the latest chemistry news in German chemistry publications?
Lava lamps as a source of randomness: ua-cam.com/video/1cUUfMeOijg/v-deo.html
Digital audio sounded awful until dithering was added. It took the sharp edges off the digits, I suppose. But isn’t a preexisting optimal state Teleological? What determines such a state?
Hardware random number generators have been available for longer than 10 years! One of the early 1980s home computers (was it Atari or Texas Instruments?) had a random number generator that used electrical noise - it was marketed as being the only PC that had a true RN generator bult in and available from BASIC.
Also to be known, is that noise degrades digital signals, and that, all our modern cpu's are based upon. It is also what necessiates radiation hardening of the components exposed to cosmic rays outside our atmosphere. This is also the reason for the need of analog frontends with high noise floor, since the extent of digital processing is limited by noise. Just some 💭
How can I get some reading material on it? btw, I've heard about annealing and Ising model.
Next they'll be making add on hardware dedicated to graphics!
I like that Sabine refuses to say that "the first 100 people that sign up for (*sponsor*) will get 20% off."