#include "jacobi.hpp"

View this file on GitHub · Last update: 2023-06-17 16:25:59-04:00

Code

	Coverage	Exec / Excl / Total
Lines	0.0%	0 / 0 / 19
Full report

#pragma once

#include <cassert>
#include <utility>

// Computes (n on m) == 1 using the binary-gcd method
// m must be positive and odd, and n must be relatively prime
template <typename T> bool is_qr_jacobi(T n, T m) {
	bool r = true;
	assert(m & 1);
	assert(m > 0);
	if (n < 0) {
		if (m & 2) r = !r;
		n = -n;
	}
	while (m > 1) {
		assert(n > 0);
		int t = __builtin_ctzll(n);
		n >>= t;
		if ((t & 1) && (((m & 7) == 3) || ((m & 7) == 5))) {
			r = !r;
		}
		// n and m both odd
		if (n < m) {
			if ((n & 2) && (m & 2)) {
				r = !r;
			}
			using std::swap;
			swap(n, m);
		}
		n -= m;
	}
	return r;
}

#include <cassert>
#include <utility>
#line 2 "src/jacobi.hpp"

#line 5 "src/jacobi.hpp"

// Computes (n on m) == 1 using the binary-gcd method
// m must be positive and odd, and n must be relatively prime
template <typename T> bool is_qr_jacobi(T n, T m) {
	bool r = true;
	assert(m & 1);
	assert(m > 0);
	if (n < 0) {
		if (m & 2) r = !r;
		n = -n;
	}
	while (m > 1) {
		assert(n > 0);
		int t = __builtin_ctzll(n);
		n >>= t;
		if ((t & 1) && (((m & 7) == 3) || ((m & 7) == 5))) {
			r = !r;
		}
		// n and m both odd
		if (n < m) {
			if ((n & 2) && (m & 2)) {
				r = !r;
			}
			using std::swap;
			swap(n, m);
		}
		n -= m;
	}
	return r;
}

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
#include <cassert>
// src/jacobi.hpp
template<typename T>bool is_qr_jacobi(T n,T m){
bool r=true;
assert(m&1);
assert(m>0);
if(n<0){
if(m&2)r=!r;
n=-n;
}
while(m>1){
assert(n>0);
int t=__builtin_ctzll(n);
n>>=t;
if((t&1)&&(((m&7)==3)||((m&7)==5))){
r=!r;
}
if(n<m){
if((n&2)&&(m&2)){
r=!r;
}
using std::swap;
swap(n,m);
}
n-=m;
}
return r;
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

#pragma once

#include <cassert>
#include <utility>

// Computes (n on m) == 1 using the binary-gcd method
// m must be positive and odd, and n must be relatively prime
template <typename T> bool is_qr_jacobi(T n, T m) {
	bool r = true;
	assert(m & 1);
	assert(m > 0);
	if (n < 0) {
		if (m & 2) r = !r;
		n = -n;
	}
	while (m > 1) {
		assert(n > 0);
		int t = __builtin_ctzll(n);
		n >>= t;
		if ((t & 1) && (((m & 7) == 3) || ((m & 7) == 5))) {
			r = !r;
		}
		// n and m both odd
		if (n < m) {
			if ((n & 2) && (m & 2)) {
				r = !r;
			}
			using std::swap;
			swap(n, m);
		}
		n -= m;
	}
	return r;
}

Back to top page