fork download
copy 
  1. # Casting out nines.
  2.  
  3. import operator
  4.  
  5. def _residue(n: int) -> int:
  6.     """
  7.     Return residue modulo 9 in 0..8.
  8.     In Python, n % 9 always yields a non-negative result, even for negative n.
  9.     """
  10.     return n % 9
  11.  
  12. def _casting_out_nines(op, x: int, y: int) -> bool:
  13.     """
  14.     General casting out nines check for a binary operation.
  15.     Compares the residue of the true operation with the residue of the
  16.     operation applied to the operands' residues.
  17.     """
  18.     z = _residue(x)
  19.     w = _residue(y)
  20.     return _residue(op(x, y)) == _residue(op(z, w))
  21.  
  22. def casting_out_nines_add(x: int, y: int) -> bool:
  23.     """Check addition using casting out nines."""
  24.     return _casting_out_nines(operator.add, x, y)
  25.  
  26. def casting_out_nines_sub(x: int, y: int) -> bool:
  27.     """Check subtraction using casting out nines."""
  28.     return _casting_out_nines(operator.sub, x, y)
  29.  
  30. def casting_out_nines_mul(x: int, y: int) -> bool:
  31.     """Check multiplication using casting out nines."""
  32.     return _casting_out_nines(operator.mul, x, y)
  33.  
  34. def casting_out_nines_pow(x: int, y: int) -> bool:
  35.     """
  36.     Check exponentiation using casting out nines.
  37.     Uses modular exponentiation to respect cycles modulo 9.
  38.     """
  39.     return pow(x, y, 9) == pow(_residue(x), y, 9)
  40.  
  41. import random
  42.  
  43. def randomized_tests(num_trials=5000):
  44.     """
  45.     Run randomized tests for casting out nines utilities.
  46.     Validates congruence modulo 9 for add, sub, mul, pow.
  47.     """
  48.     for _ in range(num_trials):
  49.         x = random.randint(-10**6, 10**6)
  50.         y = random.randint(-10**6, 10**6)
  51.  
  52.         # Addition
  53.         assert casting_out_nines_add(x, y), f"Addition failed for {x}, {y}"
  54.  
  55.         # Subtraction
  56.         assert casting_out_nines_sub(x, y), f"Subtraction failed for {x}, {y}"
  57.  
  58.         # Multiplication
  59.         assert casting_out_nines_mul(x, y), f"Multiplication failed for {x}, {y}"
  60.  
  61.     for _ in range(num_trials):
  62.         x = random.randint(-10**6, 10**6)
  63.         y = random.randint(0, 19)
  64.  
  65.         # Exponentiation: restrict y to small non-negative values
  66.         assert casting_out_nines_pow(x, y), f"Exponentiation failed for {x}^{y}"
  67.  
  68.     print(f"All {num_trials} randomized tests passed!")
  69.  
  70. # Example run
  71. if __name__ == "__main__":
  72.     randomized_tests(5000)
Success #stdin #stdout 0.13s 14276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
All 5000 randomized tests passed!
https://ideone.com/pAQg43
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!