Sines and cosines of rational multiples of π
- Cost
- for the Chebyshev iteration, about square roots for the half-angle steps at .
The values are algebraic of degree at most , and at high precision it is cheaper to compute one as an algebraic number than to evaluate the cosine with the general kernels of Elementary functions. mp_real_sin_cos_pi_ui_div_ui (and mp_real_tan_pi_ui_div_ui) chooses by the denominator and the precision between closed forms with square roots, half-angle steps, a Chebyshev step whose order grows with the precision, and the general kernel on ; arb_sin_cos_pi_fmpq, arb_tan_pi_fmpq and the functions of at a dyadic with a small denominator use it where it is faster.
The Chebyshev step#
Theorem 1 (Chebyshev step). Let in lowest terms, , , and let with , . Put , , , and . Then
Proof. Since , , and , so with and , and . Then , and with (valid on the principal branch, ) the classical expansions and give the claim, becoming .
No division or square root enters: appears only through and . The pair is computed by a Montgomery ladder on , , , one squaring and one product per bit of . The coefficients of and decrease in magnitude from resp. 1, so for the tails after are below resp. ; in both have integer coefficients over common denominators, so the series cost a few products and one division by a word each. With correct to bits, , and summing to the target precision makes a step of any order from at about bits; the order used is 12. The recursion runs in ball arithmetic and checks the branch condition from the rigorous radius of the previous level. The cost is , against the of the general kernel; the iteration is used for denominators up to a bit length that grows with the precision (none below 48 limbs, 12 bits at 512 limbs, 48 at 65536 limbs, and all denominators beyond). Of and the one with the smaller denominator is iterated and the other is .
Square roots and half angles#
The denominators up to 6 have closed forms (, , , ), and quadratic ones. For with , the half-angle formulas
lead from a closed form at the denominator to in or fewer square roots. The second form cancels: , and the absolute error of the step grows by at most a factor , so each step costs at most guard bits. Of and , one value alone is its own chain (, one step more); for both, the larger is the chain and the other , which costs more guard bits for the cancellation. With , the chain beats the general kernel from about limbs ( from 16 limbs, from 24, from 128), and for it stays 10-20% faster than the Chebyshev step at any size; for larger it is used up to 1024 limbs, and beyond for the cosine alone (5-25% faster than the Chebyshev step there, which wins for the sine and for both).
Choosing the method#
_mp_real_sin_cos_pi_ui_div_ui takes, in this order, the exact values (), the closed forms (; from 12 limbs), the half-angle steps for where they win, the Chebyshev step for denominators up to the tuned bit length, and the kernel on (or its complement) otherwise; the tangent uses the closed forms , , , and the sine and cosine of the half-angle steps or the Chebyshev step divided, where they win, and the tangent kernel otherwise. _mp_real_sin_cos_pi_ui_div_ui_algebraic tells whether the choice is other than the kernel.
The callers use this predicate:
_mp_real_sin_cos_pi_fpand_mp_real_tan_pi_fp, the fixed-point kernels behindarb_sin_pi,arf_sin_pi,nfloat_sin_piand their relatives, reduce exactly to ; when with and the predicate holds, and (or ) come from the algebraic methods: is one square root at any precision, half-angle steps from about 24 limbs.arb_sin_cos_pi_fmpq,arb_sin_pi_fmpq,arb_cos_pi_fmpqandarb_tan_pi_fmpqreduce exactly to by symmetries. Below 12288 bits, square roots througharb_sqrtare faster than those of mp_real: the closed forms for , and the half-angle steps for from a precision growing with the number () of square roots (768 bits for to 3072 bits for for both values, 256 to 6144 bits up to for one of them; not for the tangent at , whose closed forms in mp_real are faster). Otherwise a word-size denominator goes tomp_real_sin_cos_pi_ui_div_uiresp.mp_real_tan_pi_ui_div_uiwhere the predicate holds, and the remaining cases evaluate the functions of an enclosure of , with full relative accuracy since the reduced argument is small or away from the zeros; the tangent is the quotient of the sine and cosine (or its inverse).
Use in FLINT#
void arb_sin_cos_pi_fmpq(arb_t s, arb_t c, const fmpq_t x, slong prec)void arb_tan_pi_fmpq(arb_t t, const fmpq_t x, slong prec)Referenced from#
The FLINT team, “Sines and cosines of rational multiples of π,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/special-functions/rational-sines.html (generated 2026-11-17).
@misc{flint-doc-algorithms-special-functions-rational-sines,
author = {{The FLINT team}},
title = {{Sines and cosines of rational multiples of π}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/special-functions/rational-sines.html},
note = {Generated 2026-11-17}
}