Re:Can LLMs write better code if you keep asking them to "wr...
by ryao on Friday January 03, 2025 @07:48PM
(#42591129)
It turns out that there is no modular multiplicative inverse for this, so that trick cannot be used to avoid the modulus and division when getting the base 10 digits:
https://extendedeuclideanalgorithm.com/calculator.php?mode=2...
Re:Can LLMs write better code if you keep asking them to "wr...
by thequux on Friday January 03, 2025 @08:10PM
(#42591287)
Indeed there isn't; 10 is not relatively prime to 2^32. However, 5 is (and therefore has a multiplicative inverse), so you can right shift and then multiply by the inverse.
Re:Can LLMs write better code if you keep asking them to "wr...
by zahlman on Saturday January 04, 2025 @07:59AM
(#42594441)
All of this is missing the point that doing basic arithmetic like this in Python drowns in the overhead of manipulating objects (at least with the reference C implementation).
For that matter, the naive "convert to string and convert each digit to int" approach becomes faster in pure Python than using explicit div/mod arithmetic for very large numbers. This is in part thanks to algorithmic improvements implemented at least partially in Python (https://github.com/python/cpython/blob/main/Lib/_pylong.py#L...). But I can also see improved performance even for only a couple hundred digits (i.e. less than DIGLIM for the recursion) which I think comes from being able to do the div/mod loop in C (although my initial idea about the details doesn't make much sense if I keep thinking about it).
Note that the conversion of numbers to base 10 to check the digits typically involves doing division and modulus operations, so you are already doing those even if you remove the modulus operation from this check. That is unless you find a clever way of extracting the digits using the modular multiplicative inverse to calculate x/10^k.