4 ms·
This can easily be optimized to use less memory, since pi is thankfully random. Do N passes over the data, and at each pass only put in your hashmap the values
by mihaic 2y ago
This can easily be optimized to use less memory, since pi is thankfully random.
Do N passes over the data, and at each pass only put in your hashmap the values that mod N equal the current iteration. If you take N~100, the runtime would probably be in the same ballpark, since the only thing that increase is streaming all the data N times. With a fast SSD, that's not that much.
- tfehring 2y agoIsn't this functionally the same thing that the author already did, just with N=10 and filtering on the first digit instead of the last?
- mihaic 2y agoSure, I did read it too quickly, but why didn't he simply extend the generalized implementation instead of saying at the end that he was limited by the amount of RAM he has? Those runtimes seem quite a lot slower than what I would have expected, and I'm pretty sure they could be optimized by a lot, especially since he sounds like he has enough RAM to hold the entire file. Not trying to be dismissive, but this doesn't sound like that great of an implementation.
- sponaugle 2y agoIndeed no worries about pointing that out! - there are lots of things that could optimize the RAM requirements, and especially reduce the runtime. Since the overall runtime is pretty quick to getting a single answer (3 hours) vs spending more time optimizing.. but absolutely there is a lot left on the table. I think with some good optimization you could reduce the runtime significantly, especially on modern hardware. As for RAM limitations - You are correct the only limitation is just that with the RAM I have I would need to do more iterations. It would be possible to do this in much less RAM with more iterations, or the reverse of course. I was fond of solving the problem in RAM just as a way to limit the scope of the problem... but SSDs are indeed pretty fast at streaming data like this.
- ForOldHack 2y agoHow odd. You have to read and copy the data from the web to your hard disk, to the SSD. Why not just run the program on the web copy, streaming. Tiny amount of ram for all the hash tables, and you do not need to move the data around. Multi threading would improve the runtime, but reading the table is the bottle neck. He makes a great optimization, by using hash tables, but I was wondering about optimizing about the evaluation of the Chi-Square Test for Equal Proportions. If the Chi-Square test diverges from the Chi-Square Test for e, then there is little likely hood for pi+e to ever converge on rationality. My hypothesis is that because Pi is cyclical, and e is exponentially transcendental, that their sum and product are not rational, and nether are their respective powers ( Pi^e and e^Pi ), but those will take a much larger homelab than I have access to.
- sponaugle 2y agoI have a local copy of 10 trillion digits of Pi on the math cluster, so no web access needed.
- altruios 2y agoPedantic point here. PI isn't random. It is exactly the ratio of a radius and the circumference of the circle. Incommutability is not the same thing as 'random'. PI does not follow any sort of probability or statistical algorithm to be generated. Nothing inside PI is random... Now... if you take a random number (introducing randomness in the first place) representing the position and another random number to represent the length. From PI those two random numbers will generated a random sequence. But the 'randomness' is not IN PI, the random elements are only in the 2 chosen numbers. I understand this is colloquially what people mean when they say PI is 'random'... Randomness can only come about from choice, and the digits of PI have no choice as to what they will be. You can not read out a deterministic sequence of numbers in order and expect randomness. The randomness must come from some choice interacting with that defined sequence of numbers.
- flir 2y agoNot taking issue with you, slightly different question: Do the digits of Pi pass statistical tests for randomness? Uniform distribution, etc?
- p4bl0 2y agoThis reminds me of Chaitin's work on the nature of randomness and his halting probability constant: https://en.wikipedia.org/wiki/Chaitin's_constant https://en.wikipedia.org/wiki/Chaitin's_constant