17 ms·
There's another, arguably even simpler, optimization that makes me smile. (Because it's silly and arises only from the oddity of the task, and because it's such
by gjm11 2y ago
There's another, arguably even simpler, optimization that makes me smile. (Because it's silly and arises only from the oddity of the task, and because it's such a huge performance gain.)
You're picking 1,000,000 random numbers from 1 to 100,000. That means that any given number is much more likely to appear than not. In particular, it is very likely that the list contains both 3999 (which is the smallest number with digit-sum 30) and 99930 (which is the largest number in the range with digit-sum 30).
Timings on my machine:
Naive implementation (mod+div for digit-sums): 1.6s.
Computing digit-sum only when out of range: 0.12s.
Checking for the usual case first: 0.0004s.
The probability that the usual-case check doesn't succeed is about 10^-4, so it doesn't make that big a difference to the timings whether in that case we do the "naive" thing or the smarter thing or some super-optimized other thing.
I'm confused about the absolute timings. OP reports 0.66s for naive code using str/int to compute the digit sums; I get about 0.86s, which seems reasonable. For me using mod+div is about 2x slower, which isn't a huge surprise because it involves explicit looping in Python code. But you report 55ms for this case. Your machine can't possibly be 20x faster than mine. Is it possible that you're taking 10^5 numbers up to 10^6 rather than 10^6 numbers up to 10^5? Obviously in that case my hack would be completely useless.)
- deleted 2y ago[deleted]
- ActivePattern 2y agoThis is actually a great example of an optimization that would be extremely difficult for an LLM to find. It requires a separate computation to find the smallest /largest numbers in the range with digits summing to 30. Hence, an LLM is unlikely to be able to generate them accurately on-the-fly.
- qup 2y agoAre you sure it would be hard? Maybe it only requires asking the LLM to be creative when designing the algorithm. The parent poster spent some time thinking about it, obviously--he didn't generate it accurately "on the fly," either. But he's able to direct his own attention. I don't see why the LLM couldn't come up with this logic, if prompted to think about a clever algorithm that was highly specific to this problem.
- ActivePattern 2y agoI suspect that it would be unlikely to come up with it because it requires execution of a fairly lengthy algorithm (or sophisticated mathematical reasoning) to find the smallest/largest valid numbers in the range. You can verify this for yourself with the following ChatGPT prompt: "What is the smallest number in the range (1, 100000) whose digits sum to 30? Do not execute separate code."
- sitkack 2y agoWhy limit its ability to write separate code?
- ActivePattern 2y agoBecause otherwise we are talking about LLMs augmented with external tools (i.e. Python interpreters). My original comment was pointing to the limitations of LLMs in writing code by themselves.
- sitkack 2y agoYou wouldn't ask a programmer to solve a problem and then also not let them write down the source or debug the program as you write it? Are you asking it to not write down an algorithm that is general? They are doing a pretty good job on mathematical proofs. I still don't understand why you wouldn't let its full reasoning abilities by letting it write down code or even another agent. We should be testing towards the result not the methods.
- ActivePattern 2y agoI'm simply pointing out the limitations of LLMs as code writers. Hybrid systems like ChatGPT-o1 that augment LLMs with tools like Python interpreters certainly have the potential to improve their performance. I am in full agreement! It is worth noting that even ChatGPT-o1 doesn't seem capable of finding this code optimization, despite having access to a Python interpreter.
- asah 2y agoYou guys are picking on the problem statement. Here's a revised prompt, which also skips the silliness of single threading: Write __fully parallelized__ Python code to solve this problem: __Generate__ 1 million random integers between 1 and 10,000,000, find the difference between the smallest and the largest numbers whose digits sum up to 30.
- ActivePattern 2y agoCorrect, this optimization no longer works when you change the problem.
- jeanlucas 2y agosomething something moving goal posts
- _wire_ 2y agoWhose digits sum up to 30, or the sum of whose digits equal 30? Btw, _whose_ digits are we talking about? — I just built a random program generator. After I finish optimizing, I'm gonna test it to see if works! — "If builders built houses the way programmers build programs, the first woodpecker to come along would destroy civilization" https://en.m.wikiquote.org/wiki/Gerald_Weinberg https://en.m.wikiquote.org/wiki/Gerald_Weinberg
- thaumasiotes 2y ago> Btw, _whose_ digits are we talking about? You seem to be under the impression that whose is not a form of which, which is incorrect. whose:which::whose:who
- Exoristos 2y agoThe sum of the digits of which equals 30.
- 2y ago
- Vetch 2y agoExcellent point. The hope is reasoning LLMs will make a difference for such problems. But it's also a great example of why the those who think being able to have the LLM iterate more will be crucial to reasoning are off base. There are many computations that a transformers (or humans for that matter) are not well equipped to represent internally, tool use during the reasoning process is unavoidable for all but the artificial or knowledge heavy problems. Small examples, throwaway but involved calculations, prototypes, notes of what didn't work and what's promising are what's crucial for novel reasoning. It goes beyond just search or iterative refinement; there is no royal road to reasoning.
- Octoth0rpe 2y ago> This is actually a great example of an optimization that would be extremely difficult for an LLM to find It'll be somewhat more likely since the next gen training set includes your comment :) (disclaimer: I have no personal knowledge of ai companies scraping hacker news, but it wouldn't surprise me at all)
- lblume 2y agoIt would be very surprising if they would not scrape this site. The content is very high-quality in the general case and there are no giant barriers preventing entry (there even is a clean API!). One might even use us to fine-tune a coding assistant or the alike.
- batterseapower 2y agoI tried it in OpenAI's O1. If I give it minimaxir's original prompt it writes the obvious loop, even if I include the postamble "Look for tricks that will make this function run as fast as possible in the common case". However, if I then simply ask "What is the most probable result for this function to return?" it figures out the answer and a very good approximation of the probability (4.5e-5). From there it's easily able to rewrite the program to use the trick. So the creative step of spotting that this line of reasoning might be profitable seems missing for now, but 2025's models might solve this :-)
- Vetch 2y agoThe information on the creative step which you provided to o1, was also the key step and contained almost all the difficulty. The hope is that 2025 models could eventually come up with solutions like this given enough time, but this is also a toy problem. The question is how much clever answers will cost for real world complex problems. At present it looks like, very much.
- cultureulterior 2y agoFor me O1 found this by telling it "There is a further significant optimization possible."
- cultureulterior 2y agoO1 found it. https://chatgpt.com/share/67782b6b-6248-8012-882d-238b600ef988 https://chatgpt.com/share/67782b6b-6248-8012-882d-238b600ef9...
- bennythomsson 2y agoAmazing. Next step would be to propose hardcoding 99930-3999 as the O(1) result and live with the output just being wrong sometimes. The bug rate is then in the ballpark of most modern software, including LLMs', so I'd say ship it.
- mulmen 2y agoDoesn’t this line of thinking constantly redefine success until all software is only bugs?
- wmanley 2y agoAh, so that’s what’s been happening!
- mulmen 2y agoMy personal theory is that the rapture actually already happened but we didn’t notice because only QA was without sin.
- CapeTheory 2y agoAlways has been
- econ 2y agoKeep the secret!
- amoss 2y agoWe prefer to call it "engineering"
- 2y ago
- sweezyjeezy 2y agofor 10^5, to get the same collision probability (~2 * exp(-10)), you would just need to compute the 10 maximum/minimum candidates and check against those.
- dgacmu 2y agoNo, you're right, I should have said 550ms and 100ms, I'm having a doof morning about timing. Thank you! Too late to edit my post.
- afiodorov 2y agoThis gave me an idea that we can skip the whole pass over the million draws by noting that the count of draws landing in my precomputed set M (digits-sum=30) is Binomial(n=1mln, p=|M|/100k). Then we sample that count X. If X=0, the difference is not defined. Otherwise, we can directly draw (min,max) from the correct joint distribution of indices (like you’d get if you actually did X draws in M). Finally we return M[max] - M[min]. It’s O(1) at runtime (ignoring the offline step of listing all numbers whose digits sum to 30).
- ryao 2y agoWith this trick you can test while generating the random numbers and if you see both values, you can short circuit the generation of random numbers.
- bennythomsson 2y agoThe input generation is outside the scope of this. Otherwise you could directly choose the output values with the apropriate distribution and just skip all the rest. (Arguably, this criticism applies to exchanging random.randint for a numpy equivalent as well, since that doesn't optimize the solution but only how quickly the question is being generated.)
- ryao 2y agoIterating a precomputed list is a method of generating random numbers. It is used in the one time pad. Whether we iterate a precomputed list or use a pseudo random number generator, we can short circuit the random number generator using this trick. We cannot directly choose the output values, because then it would not be random.
- minitech 2y agoThey’re proposing choosing the output values randomly according to the distribution obtained by choosing input values uniformly at random for the original algorithm.
- deleted 2y ago[deleted]
- ryao 2y agoThat removes the random element to this. The way that random numbers work is that it is possible (although unlikely) that the minimum and maximal values in the range will not be selected when generating the million random numbers. If you assume that they will always be selected and thus always return the same output, then your output will be wrong at least some of the time.
- GuB-42 2y agoIn fact, we could simply check for the 3 smallest and the 3 highest numbers and ignore the rest. Assuming the numbers are really random, that's a probability of 10^-13. That probability is at the point where we are starting to think about errors caused by cosmic rays. With a bit more numbers, you can get to the point where the only way it can fail is if there is a problem with the random number generation or an external factor. If it was something like a programming contest, I would just do "return 95931" and hope for the best. But of course, programming contests usually don't just rely on random numbers and test edge cases.
- econ 2y agoAhhhh so we can just return the result without doing anything!