nt/jacobi.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <cassert> | ||
| 4 | #include <utility> | ||
| 5 | |||
| 6 | namespace wala { | ||
| 7 | |||
| 8 | // Computes (n on m) == 1 using the binary-gcd method | ||
| 9 | // m must be positive and odd, and n must be relatively prime | ||
| 10 | ✗ | template <typename T> bool is_qr_jacobi(T n, T m) { | |
| 11 | ✗ | bool r = true; | |
| 12 | ✗ | assert(m & 1); | |
| 13 | ✗ | assert(m > 0); | |
| 14 | ✗ | if (n < 0) { | |
| 15 | ✗ | if (m & 2) r = !r; | |
| 16 | ✗ | n = -n; | |
| 17 | } | ||
| 18 | ✗ | while (m > 1) { | |
| 19 | ✗ | assert(n > 0); | |
| 20 | ✗ | int t = __builtin_ctzll(n); | |
| 21 | ✗ | n >>= t; | |
| 22 | ✗ | if ((t & 1) && (((m & 7) == 3) || ((m & 7) == 5))) { | |
| 23 | ✗ | r = !r; | |
| 24 | } | ||
| 25 | // n and m both odd | ||
| 26 | ✗ | if (n < m) { | |
| 27 | ✗ | if ((n & 2) && (m & 2)) { | |
| 28 | ✗ | r = !r; | |
| 29 | } | ||
| 30 | using std::swap; | ||
| 31 | ✗ | swap(n, m); | |
| 32 | } | ||
| 33 | ✗ | n -= m; | |
| 34 | } | ||
| 35 | ✗ | return r; | |
| 36 | } | ||
| 37 | |||
| 38 | } // namespace wala | ||
| 39 |