2 ms·

How do you "count trailing zeroes of n" without branching?

• pclmulqdq 4y ago
  I don't know how you formulate it mathematically for unbounded numbers without branching. On a computer, there are a variety of ways (including a single assembly instruction), but pretty much all of them rely on n being bounded. If you're trying to feed a SAT solver, you can bound the size of the numbers at some level, and then pass one of the closed-form formulas into the solver.
  • leereeves 4y ago
    Yeah, it seems important that the formula support unbounded numbers, because the numbers can grow inside the sequence. Naively, it seems like any starting value (except those for which you already know the full sequence) might lead to values that exceed any arbitrary bound.
    • pclmulqdq 4y ago
      From a theoretical standpoint, I think you could also attempt to approach this by thinking about a field where the "remove trailing zeros" step is built in. It may be a very weird field to do math on, and we may be unprepared for the math that is required, but it's a way to remove branching from the operations required for a proof. There's nothing inherently special about the branchiness of "remove trailing zeros" as an operation if you drill down into it: addition, for example, also needs conditional execution (based on the carry in to each section of a number). Otherwise, if you're searching for a counterexample, bound n by some ridiculous number of bits (whatever your supercomputer supports) and run your solver with a simple closed form.
• eru 4y ago
  Here's how you can do a 'branchless' one, using Python syntax: f = lambda n: (n & 1) * n + ((n + 1) >> 1) No need to count any trailing zeros. Of course, the multiplication sort-of acts as a branch.