Native reverse-order paths for InterpolationSearch, ExpFromLeft, SIMDLinearScan, BitInterpolationSearch

[ChrisRackauckas-Claude]

Background

In FFF 2.0 the strategies all accept an order::Base.Order.Ordering keyword, but
several of them only have a fast path for Base.Order.Forward. When a caller
passes Base.Order.Reverse (or any non-Forward ordering), these strategies
fall back to BinaryBracket() — which is correct but throws away the
hint-based speedup the caller was expecting.

Specifically:

• InterpolationSearch falls back to BinaryBracket for non-Forward
  orderings. The linear-extrapolation guess is direction-aware in principle
  but currently only implemented for the forward polarity.
• ExpFromLeft falls back to Base.searchsorted{first,last} (bounded
  binary) for non-Forward orderings — same direction-aware reasoning.
• SIMDLinearScan falls back to scalar LinearScan for non-Forward
  orderings. The LLVM IR is hardcoded to the forward comparison polarity
  (icmp sgt / fcmp ogt / etc.).
• BitInterpolationSearch falls back to BinaryBracket for non-Forward
  orderings.

BracketGallop, LinearScan, and the various BinaryBracket paths already
work natively under any ordering — they pass order through to
Base.Order.lt for every compare.

What would change

For each affected strategy, add a backward-direction implementation that
mirrors the forward one with the comparison polarity flipped. The
algorithm doesn't change — only the comparison.

For SIMDLinearScan specifically, this would mean two more IR templates
(icmp slt/sle for Int64, fcmp olt/ole for Float64) generated by the
existing _simd_scan_ir(t, pred) helper. The dispatch would branch on
order === Forward vs order === Reverse (with Reverse going through the
new IR).

For InterpolationSearch / ExpFromLeft / BitInterpolationSearch, the
guess-and-refine arithmetic flips sign in the right places — short patches
per strategy, ~20-30 lines each.

Why not in 2.0

Reverse-ordering workflows are niche (Base.Order.Reverse is rarely the right
shape for sorted-search workloads — most callers reverse the vector itself
instead). The current fallback paths are correct, just slower than necessary.

Filing this as a 2.x followup rather than blocking the 2.0 release.

Acceptance

For each affected strategy:

• Native reverse-ordering implementation
• Test parity against Base.searchsorted{first,last} under Reverse
  ordering across the same fuzz harness used for the forward path

Bonus:

• Generalize beyond Reverse to any user-supplied Base.Order.Ordering
  whose lt function can be flipped. (Currently Reverse is the only
  non-Forward ordering with a well-defined inverse comparison.)

[ChrisRackauckas-Claude]

Implemented in PR #65 (commit 7c407b1). All four strategies now have native Reverse paths:

• InterpolationSearch: the existing _interp_guess math already handles vhi - vlo < 0 correctly; dropping the Forward-only guard was enough.
• ExpFromLeft: parameterised searchsortedfirstexp on order and added a sibling searchsortedlastexp using the strict comparison (the old post-processing returned the first occurrence when duplicates were present; the duplicates bug was pre-existing under Forward but not exercised by tests).
• SIMDLinearScan: four new LLVM IR predicates (slt/sle for Int64, olt/ole for Float64) via the existing _simd_scan_ir template, with _simdscan_*_specialized branching on order at runtime (compiles away when order is statically known). Non-Forward / non-Reverse orderings fall back to scalar LinearScan.
• BitInterpolationSearch: _bit_interp_guess_f64 mirrors its unsigned arithmetic for the descending-bit-pattern case.

Tests: 15421 new parity comparisons against Base.searchsorted{first,last}(v, x, Reverse) across all strategies on random Int64 / Float64 inputs with duplicates, plus log-spaced positive Float64 for BitInterp. All 100047 tests pass.

The bonus item (generalize beyond Reverse to arbitrary user-supplied orderings) is deliberately not done: SIMDLinearScan and BitInterpolationSearch use raw machine compares (icmp/fcmp) that aren't aware of Base.Order, so custom By / Lt orderings continue to fall back to scalar LinearScan (which is order-agnostic by construction).