Comment Re:Small programming exercises (Score 1) 102
Do you try to teach your grandmother to suck eggs also?
>Have you ever coded anything in assembly?
I design the silicon on which the machine code runs.
You make a lot of assumptions.
Do you try to teach your grandmother to suck eggs also?
>Have you ever coded anything in assembly?
I design the silicon on which the machine code runs.
You make a lot of assumptions.
Nope. It would be a fault if the nondeterministic instructions were in fact deterministic. The security of your communications depends on those instructions being nondeterministic. Otherwise your adversary could guess your key.
>If you think that stack size depends on the algorithm
I said stack size depends on the data. Data dependent timing and memory use are gifts to the side channel people.
Not always, but you know that.
>Besides, tail calls are not the only form of recursion that can be optimised.
Yeah yeah, I did the algorithms course 35 years ago on recursion optimization in functional languages (Pre Haskell - We had standard ML and similar stuff back then).
You are arguing for correctness of code over side channel cleanliness. Correctness can be got at many ways. Data-runtime independence is not achieved with a recursion everywhere approach. You have to consider every case. Blanket "recursion everywhere" rules makes you sound like an FP zealot.
>your for-loops end up being compiled to recursive code,
Is your compiler drunk?
I've spent the past 16 years deep in the tarpit of RNG design. The book in my sig is one of the results, along with the RNGs that are common in today's CPUs.
I can't complain - it's kept me gainfully employed. But I'd really like to work on something else for a change.
"going deeper, i would surmise that even that instruction's internal process is fully deterministic too,"
Nope. The noise source is (subject to quantum physics) nondeterministic. Data from this source goes through a cryptographic entropy extractor. For RdRand there is a DRBG that follows, to give you fast, secure random numbers and for RdSeed you get full entropy random numbers, which are limited by the speed of the source and so isn't as fast as RdRand.
Quantum physics does not answer to question as to whether or not the universe is nondeterministic. It certainly look nondeterministic but we don't know if they is actual nondeterminism or ignorance of a deeper process.
For more stuff on this, maybe check out the book in my sig.
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
As Avi pointed out, Von Neumann did not follow his own advice.
No, components in your computer are subject to forces that are non deterministic, but the entire *purpose* of a processor is to be deterministic. To perform all instructions consistently, and repeatably, and to return the "correct" to an instruction every time.
Remember the Pentium Floating Point fiasco? THAT's what happens when your processor behaves non-deterministically!
You are wrong. The purpose of a computer is to compute and be useful. To that purpose, computers have nondeterministic instructions. In X86 CPUs they are RdRand and RdSeed. RISC-V has equivalent instructions. ARM is a bit of a mess, but various ARM providers have various RNG solutions on chip. If your computer was deterministic, it would never be able to perform a secure Diffie Hellman key setup, or generate a secure private key.
The i810 RNG was a slower noisy VCO sampling a fast oscillator. This is fine, albeit slow. However it did not scale well to modern small feature size silicon. We replaced it with a differential feedback metastable source which is fast and reliable and has been all Intel CPUs since 2011. This is the noise source behind the RdRand and RdSeed instructions that have an SP800-90A,B,C based design generating the random numbers.
Avi does awesome work. His papers, particularly on multiple input entropy extractors have solved fundamental problems in RNG design (and my job is RNG design, so I care).
Here is a very good and accessible talk he gave that covers some essential aspects of his research : https://www.youtube.com/watch?...
His work covers both domains you mentioned. On randomized algorithms, he established important principles about what is possible. On cryptographically secure sources of nondeterministic randomness, his BIW paper is seminal - solving the 50% problem for extractors.
"Your computer has nondeterministic instructions by design."
Okay, I'll bite. I'm working on a laptop with an Intel i7 processors. Please elaborate what machine language instructions it has that are nondeterministic.
RdRand and RdSeed.
From TFA:
"While computers are fundamentally deterministic systems,"
When you start with a wrong premise, the rest that follows is suspect.
Your computer has nondeterministic instructions by design. It is not in any way "fundamentally deterministic". It's made of electronics. Electronics has noise. Electrical noise is nondeterministic.
If all you do is tail recursion that gets optimized away, why bother?
>But recursion is fundamental to good code,
If you think that having a data dependent stack depth is ok.
The rest of us have to write secure and reliable code.
>Your Amazon service center must be better than mine
If the thing is in one of the local amazon warehouses, it will sometimes arrive the same day it was ordered. If not, you wait.
Why would someone mod this down? Sympathy for the imposter?
Composter Syndrome.
The only possible interpretation of any research whatever in the `social sciences' is: some do, some don't. -- Ernest Rutherford
