6 ms·

Another speed-up is to skip the sum of digits check if n % 9 != 30 % 9. Sum of digits have the same remainder divided by 9 as the number. This rules out 8/9 = 8

Another speed-up is to skip the sum of digits check if n % 9 != 30 % 9. Sum of digits have the same remainder divided by 9 as the number. This rules out 8/9 = 88% candidates.

brabel 2y ago
Did you measure it? I would expect using % would ruin your performance as it's slow, even if it allows you to avoid doing a bunch of sums (which are fast).
- ryao 2y ago
  You can do this “without” using the modulus operation by storing the numbers in a boolean array. Start at 3999 and keep adding 9 to find the minimum. Then start at 99930 and keep subtracting 9 to find the maximum. You would need to check if the number is in the array and then if the number’s digits sum to 30. 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.
  - ryao 2y ago
    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&n=4294967296&b=10#num https://extendedeuclideanalgorithm.com/calculator.php?mode=2...
    - thequux 2y ago
      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.
      - zahlman 2y ago
        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#L178 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).
- deleted 2y ago
  [deleted]
- ActivePattern 2y ago
  Doing a single modulo 9 operation is much faster than summing a d-digit number, which requires d modulo 10s, d divide 10s, and d sums.
  - brabel 2y ago
    You can do the sum by looking directly at the digits in the string, no need for module at all.
    - Jensson 2y ago
      Number to string is even more expensive.
- zahlman 2y ago
  Each sum involves determining the digits to sum, which involves using % multiple times. Also, you don't have to use % in order to decide whether to perform the sum-of-digits check for a given value. You can just iterate over values to check in steps of 9.
ryao 2y ago
Would someone write a mathematical proof showing this is always true?
- afiodorov 2y ago
  a = [int(x) for x in str(n)][::-1] assert n == sum(d*(10**i) for i, d in enumerate(a)) Now when you're operating mod 9, 10 == 1 % 9, thus 10**i == 1 % 9 Comes from the fact that (a*b) % 9 == (a % 9) * (b % 9) Now using (a+b) % 9 == (a % 9) + (b % 9) We get that that sum(a) and n are same mod 9.
  - ryao 2y ago
    Thank you for that.

Another speed-up is to skip the sum of digits check if n % 9 != 30 % 9. Sum of digits have the same remainder divided by 9 as the number. This rules out 8/9 = 88% candidates.

brabel 2y ago

Did you measure it? I would expect using % would ruin your performance as it's slow, even if it allows you to avoid doing a bunch of sums (which are fast).

ryao 2y ago
You can do this “without” using the modulus operation by storing the numbers in a boolean array. Start at 3999 and keep adding 9 to find the minimum. Then start at 99930 and keep subtracting 9 to find the maximum. You would need to check if the number is in the array and then if the number’s digits sum to 30. 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.
- ryao 2y ago
  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&n=4294967296&b=10#num https://extendedeuclideanalgorithm.com/calculator.php?mode=2...
  - thequux 2y ago
    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.
    - zahlman 2y ago
      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#L178 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).
deleted 2y ago
[deleted]
ActivePattern 2y ago
Doing a single modulo 9 operation is much faster than summing a d-digit number, which requires d modulo 10s, d divide 10s, and d sums.
- brabel 2y ago
  You can do the sum by looking directly at the digits in the string, no need for module at all.
  - Jensson 2y ago
    Number to string is even more expensive.
zahlman 2y ago
Each sum involves determining the digits to sum, which involves using % multiple times. Also, you don't have to use % in order to decide whether to perform the sum-of-digits check for a given value. You can just iterate over values to check in steps of 9.

ryao 2y ago

Would someone write a mathematical proof showing this is always true?

afiodorov 2y ago
a = [int(x) for x in str(n)][::-1] assert n == sum(d*(10**i) for i, d in enumerate(a)) Now when you're operating mod 9, 10 == 1 % 9, thus 10**i == 1 % 9 Comes from the fact that (a*b) % 9 == (a % 9) * (b % 9) Now using (a+b) % 9 == (a % 9) + (b % 9) We get that that sum(a) and n are same mod 9.
- ryao 2y ago
  Thank you for that.