gh-157742: Let compilers vectorize the int shift loops #157751

v_lshift() and v_rshift() pass a carry from one loop iteration to the next, which prevents vectorization. The carry into a digit is just the bits shifted out of its neighbour, so each output digit can be built from two input digits instead, with nothing carried.

These helpers do the normalization in x_divrem() (three passes that dominate
when the quotient is short) and the scaling in true division.

| Benchmark | main | PR |
|---|:---:|:---:|
| a << 7 (10 digits) | 35.2 ns | 31.9 ns: 1.10x faster |
| a << 7 (100 digits) | 87.3 ns | 42.8 ns: 2.04x faster |
| a >> 7 (100 digits) | 90.2 ns | 42.4 ns: 2.13x faster |
| a << 7 (1000 digits) | 639 ns | 213 ns: 2.99x faster |
| a >> 7 (1000 digits) | 631 ns | 209 ns: 3.02x faster |
| 10 // 2 digits | 160 ns | 149 ns: 1.08x faster |
| 1000 // 2 digits | 14.7 us | 13.9 us: 1.05x faster |
| 100 // 99 digits | 535 ns | 349 ns: 1.54x faster |
| 1000 // 999 digits | 4.51 us | 2.95 us: 1.53x faster |
| 1000 % 999 digits | 4.53 us | 2.94 us: 1.54x faster |
| divmod, 1000 by 999 digits | 4.55 us | 2.98 us: 1.52x faster |
| 1000 / 999 digits | 5.22 us | 3.18 us: 1.64x faster |
| pyperformance pidigits | 161 ms | 129 ms: 1.24x faster |

Benchmark script

```python
import pyperf

runner = pyperf.Runner()
def ints(na, nb=1):
return (f"import random; r = random.Random(1234); "
f"a = r.getrandbits({na*30-1}) | (1 << {na*30-2}); "
f"b = r.getrandbits({nb*30-3}) | (1 << {nb*30-4})")
for na in (2, 10, 100, 1000):
runner.timeit(f"a << 7 ({na} digits)", "a << 7", setup=ints(na))
runner.timeit(f"a >> 7 ({na} digits)", "a >> 7", setup=ints(na))
runner.timeit("-a >> 7 (1000 digits)", "a >> 7", setup=ints(1000) + "; a = -a")
for na, nb in [(2, 2), (10, 2), (1000, 2), (10, 9), (100, 99), (1000, 999)]:
runner.timeit(f"{na} // {nb} digits", "a // b", setup=ints(na, nb))
runner.timeit("1000 % 999 digits", "a % b", setup=ints(1000, 999))
runner.timeit("divmod, 1000 by 999 digits", "divmod(a, b)", setup=ints(1000, 999))
runner.timeit("1000 / 999 digits", "a / b", setup=ints(1000, 999))
```

Note: when disabling vectorization I get a 20% slowdown. I think that is ok, since modern cpu's/compilers can do this, if not we could modify the PR to gate the change behind some macro.

Generated with Claude Code

• Issue: gh-157742
  <!-- /gh-issue-number -->