{-| module : Data.Number.Flint.Fmpq.FFI copyright : (c) 2022 Hartmut Monien license : GNU GPL, version 2 or above (see LICENSE) maintainer : hmonien@uni-bonn.de -} module Data.Number.Flint.Fmpq.FFI ( -- * Rational numbers @Fmpq@ Fmpq , CFmpq (..) -- * Constructors , newFmpq , withFmpq , withFmpqNum , withFmpqDen , withNewFmpq -- * Memory management , fmpq_init , fmpq_clear -- * Canonicalisation , fmpq_canonicalise , _fmpq_canonicalise , fmpq_is_canonical , _fmpq_is_canonical -- * Basic assignment , fmpq_set , fmpq_swap , fmpq_neg , fmpq_abs , fmpq_zero , fmpq_one -- * Comparison , fmpq_is_zero , fmpq_is_one , fmpq_is_pm1 , fmpq_equal , fmpq_sgn , fmpq_cmp , fmpq_cmp_fmpz , fmpq_cmp_si , fmpq_equal_ui , fmpq_equal_si , fmpq_height , fmpq_height_bits -- * Conversion , fmpq_set_fmpz_frac , fmpq_get_fmpz_frac , fmpq_get_mpz_frac , fmpq_set_si , _fmpq_set_si , fmpq_set_ui , _fmpq_set_ui , fmpq_set_mpq , fmpq_set_str , fmpq_init_set_mpz_frac_readonly , fmpq_get_d , fmpq_get_mpq , fmpq_get_mpfr , fmpq_get_str , _fmpq_get_str , flint_mpq_init_set_readonly , flint_mpq_clear_readonly , fmpq_init_set_readonly , fmpq_clear_readonly -- * Input and output , fmpq_fprint , _fmpq_fprint , fmpq_print , _fmpq_print -- * Random number generation , fmpq_randtest , _fmpq_randtest , fmpq_randtest_not_zero , fmpq_randbits , _fmpq_randbits -- * Arithmetic , fmpq_add , fmpq_sub , fmpq_mul , fmpq_div , _fmpq_add , _fmpq_sub , _fmpq_mul , _fmpq_div , _fmpq_add_si , _fmpq_sub_si , _fmpq_add_ui , _fmpq_sub_ui , _fmpq_add_fmpz , _fmpq_sub_fmpz , _fmpq_mul_si , fmpq_add_si , fmpq_sub_si , fmpq_add_ui , fmpq_sub_ui , fmpq_add_fmpz , fmpq_sub_fmpz , _fmpq_mul_ui , fmpq_mul_ui , fmpq_addmul , fmpq_submul , _fmpq_addmul , fmpq_inv , _fmpq_pow_si , fmpq_pow_si , fmpq_pow_fmpz , fmpq_mul_fmpz , fmpq_div_fmpz , fmpq_mul_2exp , fmpq_div_2exp , _fmpq_gcd , fmpq_gcd , _fmpq_gcd_cofactors , fmpq_gcd_cofactors , _fmpq_add_small , _fmpq_mul_small -- * Modular reduction and rational reconstruction , _fmpq_mod_fmpz , _fmpq_reconstruct_fmpz_2_naive , _fmpq_reconstruct_fmpz -- * Rational enumeration , _fmpq_next_minimal , _fmpq_next_signed_minimal , _fmpq_next_calkin_wilf , _fmpq_next_signed_calkin_wilf , fmpq_farey_neighbors , fmpq_mediant , fmpq_simplest_between -- * Continued fractions , fmpq_get_cfrac , fmpq_set_cfrac , fmpq_cfrac_bound , fmpq_get_cfrac_st , fmpq_set_cfrac_st -- * Special functions , _fmpq_harmonic_ui , fmpq_harmonic_ui -- * Dedekind sums , fmpq_dedekind_sum , fmpq_dedekind_sum_naive ) where -- rational numbers ------------------------------------------------------------ import System.IO.Unsafe import Control.Monad import Foreign.C.String import Foreign.C.Types import Foreign.ForeignPtr import Foreign.Ptr ( Ptr, FunPtr, plusPtr, nullPtr, castPtr ) import Foreign.Storable import Foreign.Marshal ( free ) import Foreign.Marshal.Array ( advancePtr ) import Data.Functor ((<&>)) import Data.Number.Flint.Flint import Data.Number.Flint.Fmpz import Data.Number.Flint.Quotient #include #include -- fmpq_t ---------------------------------------------------------------------- -- | Rational numbers (opaque pointer) data Fmpq = Fmpq {-# UNPACK #-} !(ForeignPtr CFmpq) data CFmpq = CFmpq (Ptr CFmpz) (Ptr CFmpz) instance Storable CFmpq where {-# INLINE sizeOf #-} sizeOf _ = #{size fmpq_t} {-# INLINE alignment #-} alignment _ = #{alignment fmpq_t} peek ptr = CFmpq <$> (return $ castPtr ptr) <*> (return $ castPtr ptr `advancePtr` 1) poke = error "CFmpz.poke: Not defined" -- Fmpq ------------------------------------------------------------------------ -- | /newFmpq/ -- -- Construct a `Fmpq`. newFmpq = do x <- mallocForeignPtr withForeignPtr x fmpq_init addForeignPtrFinalizer p_fmpq_clear x return $ Fmpq x -- | /withFmpq/ /x/ /f/ -- -- Execute /f/ with /x/. {-# INLINE withFmpq #-} withFmpq (Fmpq x) f = withForeignPtr x $ \xp -> f xp <&> (Fmpq x,) -- | /withNewFmpq/ /f/ -- -- Execture /f/ with a new `Fmpq`. {-# INLINE withNewFmpq #-} withNewFmpq f = newFmpq >>= flip withFmpq f -- | /withFmpqNum/ /x/ /f/ -- -- Execute /f/ on the numerator of /x/. withFmpqNum x f = do withFmpq x $ \x -> do f $ castPtr x -- | /withFmpqDen/ /x/ /f/ -- -- Execute /f/ on the denominator of /x/. withFmpqDen x f = do withFmpq x $ \x -> do f $ flip advancePtr 1 $ castPtr x -- Fmpz <-> Fmpq -------------------------------------------------------------- instance Quotient Fmpq Fmpz where (//) x y = unsafePerformIO $ do result <- newFmpq withFmpq result $ \result -> do withFmpz x $ \x -> do withFmpz y $ \y -> do fmpq_set_fmpz_frac result x y return result numerator x = unsafePerformIO $ do result <- newFmpz withFmpz result $ \result -> do withFmpq x $ \x -> do withNewFmpz $ \tmp -> do fmpq_get_fmpz_frac result tmp x return result denominator x = unsafePerformIO $ do result <- newFmpz withFmpz result $ \result -> do withFmpq x $ \x -> do withNewFmpz $ \tmp -> do fmpq_get_fmpz_frac tmp result x return result -- Memory management ----------------------------------------------------------- -- | /fmpq_init/ /x/ -- -- Initialises the @fmpq_t@ variable @x@ for use. Its value is set to 0. foreign import ccall "fmpq.h fmpq_init" fmpq_init :: Ptr CFmpq -> IO () -- | /fmpq_clear/ /x/ -- -- Clears the @fmpq_t@ variable @x@. To use the variable again, it must be -- re-initialised with @fmpq_init@. foreign import ccall "fmpq.h fmpq_clear" fmpq_clear :: Ptr CFmpq -> IO () foreign import ccall "fmpq.h &fmpq_clear" p_fmpq_clear :: FunPtr (Ptr CFmpq -> IO ()) -- Canonicalisation ------------------------------------------------------------ -- | /fmpq_canonicalise/ /res/ -- -- Puts @res@ in canonical form: the numerator and denominator are reduced -- to lowest terms, and the denominator is made positive. If the numerator -- is zero, the denominator is set to one. -- -- If the denominator is zero, the outcome of calling this function is -- undefined, regardless of the value of the numerator. foreign import ccall "fmpq.h fmpq_canonicalise" fmpq_canonicalise :: Ptr CFmpq -> IO () -- | /_fmpq_canonicalise/ /num/ /den/ -- -- Does the same thing as @fmpq_canonicalise@, but for numerator and -- denominator given explicitly as @fmpz_t@ variables. Aliasing of @num@ -- and @den@ is not allowed. foreign import ccall "fmpq.h _fmpq_canonicalise" _fmpq_canonicalise :: Ptr CFmpz -> Ptr CFmpz -> IO () -- | /fmpq_is_canonical/ /x/ -- -- Returns nonzero if @fmpq_t@ x is in canonical form (as produced by -- @fmpq_canonicalise@), and zero otherwise. foreign import ccall "fmpq.h fmpq_is_canonical" fmpq_is_canonical :: Ptr CFmpq -> IO CInt -- | /_fmpq_is_canonical/ /num/ /den/ -- -- Does the same thing as @fmpq_is_canonical@, but for numerator and -- denominator given explicitly as @fmpz_t@ variables. foreign import ccall "fmpq.h _fmpq_is_canonical" _fmpq_is_canonical :: Ptr CFmpz -> Ptr CFmpz -> IO CInt -- Basic assignment ------------------------------------------------------------ -- | /fmpq_set/ /dest/ /src/ -- -- Sets @dest@ to a copy of @src@. No canonicalisation is performed. foreign import ccall "fmpq.h fmpq_set" fmpq_set :: Ptr CFmpq -> Ptr CFmpq -> IO () -- | /fmpq_swap/ /op1/ /op2/ -- -- Swaps the two rational numbers @op1@ and @op2@. foreign import ccall "fmpq.h fmpq_swap" fmpq_swap :: Ptr CFmpq -> Ptr CFmpq -> IO () -- | /fmpq_neg/ /dest/ /src/ -- -- Sets @dest@ to the additive inverse of @src@. foreign import ccall "fmpq.h fmpq_neg" fmpq_neg :: Ptr CFmpq -> Ptr CFmpq -> IO () -- | /fmpq_abs/ /dest/ /src/ -- -- Sets @dest@ to the absolute value of @src@. foreign import ccall "fmpq.h fmpq_abs" fmpq_abs :: Ptr CFmpq -> Ptr CFmpq -> IO () -- | /fmpq_zero/ /res/ -- -- Sets the value of @res@ to 0. foreign import ccall "fmpq.h fmpq_zero" fmpq_zero :: Ptr CFmpq -> IO () -- | /fmpq_one/ /res/ -- -- Sets the value of @res@ to \(1\). foreign import ccall "fmpq.h fmpq_one" fmpq_one :: Ptr CFmpq -> IO () -- Comparison ------------------------------------------------------------------ -- | /fmpq_is_zero/ /res/ -- -- Returns nonzero if @res@ has value 0, and returns zero otherwise. foreign import ccall "fmpq.h fmpq_is_zero" fmpq_is_zero :: Ptr CFmpq -> IO CInt -- | /fmpq_is_one/ /res/ -- -- Returns nonzero if @res@ has value \(1\), and returns zero otherwise. foreign import ccall "fmpq.h fmpq_is_one" fmpq_is_one :: Ptr CFmpq -> IO CInt -- | /fmpq_is_pm1/ /res/ -- -- Returns nonzero if @res@ has value \(\pm{1}\) and zero otherwise. foreign import ccall "fmpq.h fmpq_is_pm1" fmpq_is_pm1 :: Ptr CFmpq -> IO CInt -- | /fmpq_equal/ /x/ /y/ -- -- Returns nonzero if @x@ and @y@ are equal, and zero otherwise. Assumes -- that @x@ and @y@ are both in canonical form. foreign import ccall "fmpq.h fmpq_equal" fmpq_equal :: Ptr CFmpq -> Ptr CFmpq -> IO CInt -- | /fmpq_sgn/ /x/ -- -- Returns the sign of the rational number \(x\). foreign import ccall "fmpq.h fmpq_sgn" fmpq_sgn :: Ptr CFmpq -> IO CInt -- | /fmpq_cmp/ /x/ /y/ -- -- Returns negative if \(x < y\), zero if \(x = y\), and positive if -- \(x > y\). foreign import ccall "fmpq.h fmpq_cmp" fmpq_cmp :: Ptr CFmpq -> Ptr CFmpq -> IO CInt foreign import ccall "fmpq.h fmpq_cmp_fmpz" fmpq_cmp_fmpz :: Ptr CFmpq -> Ptr CFmpz -> IO CInt foreign import ccall "fmpq.h fmpq_cmp_ui" fmpq_cmp_ui :: Ptr CFmpq -> Ptr CULong -> IO CInt -- | /fmpq_cmp_si/ /x/ /y/ -- -- Returns negative if \(x < y\), zero if \(x = y\), and positive if -- \(x > y\). foreign import ccall "fmpq.h fmpq_cmp_si" fmpq_cmp_si :: Ptr CFmpq -> CLong -> IO CInt -- | /fmpq_equal_ui/ /x/ /y/ -- -- Returns \(1\) if \(x = y\), otherwise returns \(0\). foreign import ccall "fmpq.h fmpq_equal_ui" fmpq_equal_ui :: Ptr CFmpq -> CULong -> IO CInt -- | /fmpq_equal_si/ /x/ /y/ -- -- Returns \(1\) if \(x = y\), otherwise returns \(0\). foreign import ccall "fmpq.h fmpq_equal_si" fmpq_equal_si :: Ptr CFmpq -> CLong -> IO CInt -- | /fmpq_height/ /height/ /x/ -- -- Sets @height@ to the height of \(x\), defined as the larger of the -- absolute values of the numerator and denominator of \(x\). foreign import ccall "fmpq.h fmpq_height" fmpq_height :: Ptr CFmpz -> Ptr CFmpq -> IO () -- | /fmpq_height_bits/ /x/ -- -- Returns the number of bits in the height of \(x\). foreign import ccall "fmpq.h fmpq_height_bits" fmpq_height_bits :: Ptr CFmpq -> IO CFBitCnt -- Conversion ------------------------------------------------------------------ -- | /fmpq_set_fmpz_frac/ /res/ /p/ /q/ -- -- Sets @res@ to the canonical form of the fraction @p \/ q@. This is -- equivalent to assigning the numerator and denominator separately and -- calling @fmpq_canonicalise@. foreign import ccall "fmpq.h fmpq_set_fmpz_frac" fmpq_set_fmpz_frac :: Ptr CFmpq -> Ptr CFmpz -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h fmpq_get_fmpz_frac" fmpq_get_fmpz_frac :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpq -> IO () -- | /fmpq_get_mpz_frac/ /a/ /b/ /c/ -- -- Sets @a@, @b@ to the numerator and denominator of @c@ respectively. foreign import ccall "fmpq.h fmpq_get_mpz_frac" fmpq_get_mpz_frac :: Ptr CMpz -> Ptr CMpz -> Ptr CFmpq -> IO () -- | /fmpq_set_si/ /res/ /p/ /q/ -- -- Sets @res@ to the canonical form of the fraction @p \/ q@. foreign import ccall "fmpq.h fmpq_set_si" fmpq_set_si :: Ptr CFmpq -> CLong -> CULong -> IO () -- | /_fmpq_set_si/ /rnum/ /rden/ /p/ /q/ -- -- Sets @(rnum, rden)@ to the canonical form of the fraction @p \/ q@. -- @rnum@ and @rden@ may not be aliased. foreign import ccall "fmpq.h _fmpq_set_si" _fmpq_set_si :: Ptr CFmpz -> Ptr CFmpz -> CLong -> CULong -> IO () -- | /fmpq_set_ui/ /res/ /p/ /q/ -- -- Sets @res@ to the canonical form of the fraction @p \/ q@. foreign import ccall "fmpq.h fmpq_set_ui" fmpq_set_ui :: Ptr CFmpq -> CULong -> CULong -> IO () -- | /_fmpq_set_ui/ /rnum/ /rden/ /p/ /q/ -- -- Sets @(rnum, rden)@ to the canonical form of the fraction @p \/ q@. -- @rnum@ and @rden@ may not be aliased. foreign import ccall "fmpq.h _fmpq_set_ui" _fmpq_set_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> CULong -> IO () -- | /fmpq_set_mpq/ /dest/ /src/ -- -- Sets the value of @dest@ to that of the @mpq_t@ variable @src@. foreign import ccall "fmpq.h fmpq_set_mpq" fmpq_set_mpq :: Ptr CFmpq -> Ptr CMpq -> IO () -- | /fmpq_set_str/ /dest/ /s/ /base/ -- -- Sets the value of @dest@ to the value represented in the string @s@ in -- base @base@. -- -- Returns 0 if no error occurs. Otherwise returns -1 and @dest@ is set to -- zero. foreign import ccall "fmpq.h fmpq_set_str" fmpq_set_str :: Ptr CFmpq -> CString -> CInt -> IO CInt -- | /fmpq_init_set_mpz_frac_readonly/ /z/ /p/ /q/ -- -- Assuming @z@ is an @fmpz_t@ which will not be cleaned up, this -- temporarily copies @p@ and @q@ into the numerator and denominator of @z@ -- for read only operations only. The user must not run @fmpq_clear@ on -- @z@. foreign import ccall "fmpq.h fmpq_init_set_mpz_frac_readonly" fmpq_init_set_mpz_frac_readonly :: Ptr CFmpq -> Ptr CMpz -> Ptr CMpz -> IO () -- | /fmpq_get_d/ /f/ -- -- Returns \(f\) as a @double@, rounding towards zero if @f@ cannot be -- represented exactly. The return is system dependent if @f@ is too large -- or too small to fit in a @double@. foreign import ccall "fmpq.h fmpq_get_d" fmpq_get_d :: Ptr CFmpq -> IO CDouble -- | /fmpq_get_mpq/ /dest/ /src/ -- -- Sets the value of @dest@ foreign import ccall "fmpq.h fmpq_get_mpq" fmpq_get_mpq :: Ptr CMpq -> Ptr CFmpq -> IO () -- | /fmpq_get_mpfr/ /dest/ /src/ /rnd/ -- -- Sets the MPFR variable @dest@ to the value of @src@, rounded to the -- nearest representable binary floating-point value in direction @rnd@. -- Returns the sign of the rounding, according to MPFR conventions. foreign import ccall "fmpq.h fmpq_get_mpfr" fmpq_get_mpfr :: Ptr CMpfr -> Ptr CFmpq -> CMpfrRnd -> IO CInt -- | /_fmpq_get_str/ /str/ /b/ /num/ /den/ -- -- Prints the string representation of \(x\) in base \(b \in [2, 36]\) to a -- suitable buffer. -- -- If @str@ is not @NULL@, this is used as the buffer and also the return -- value. If @str@ is @NULL@, allocates sufficient space and returns a -- pointer to the string. foreign import ccall "fmpq.h fmpq_get_str" fmpq_get_str :: CString -> CInt -> Ptr CFmpq -> IO CString foreign import ccall "fmpq.h _fmpq_get_str" _fmpq_get_str :: CString -> CInt -> Ptr CFmpz -> Ptr CFmpz -> IO CString -- | /flint_mpq_init_set_readonly/ /z/ /f/ -- -- Sets the uninitialised @mpq_t@ \(z\) to the value of the readonly -- @fmpq_t@ \(f\). -- -- Note that it is assumed that \(f\) does not change during the lifetime -- of \(z\). -- -- The rational \(z\) has to be cleared by a call to -- @flint_mpq_clear_readonly@. -- -- The suggested use of the two functions is as follows: -- -- > fmpq_t f; -- > ... -- > { -- > mpq_t z; -- > -- > flint_mpq_init_set_readonly(z, f); -- > foo(..., z); -- > flint_mpq_clear_readonly(z); -- > } -- -- This provides a convenient function for user code, only requiring to -- work with the types @fmpq_t@ and @mpq_t@. foreign import ccall "fmpq.h flint_mpq_init_set_readonly" flint_mpq_init_set_readonly :: Ptr CMpq -> Ptr CFmpq -> IO () -- | /flint_mpq_clear_readonly/ /z/ -- -- Clears the readonly @mpq_t@ \(z\). foreign import ccall "fmpq.h flint_mpq_clear_readonly" flint_mpq_clear_readonly :: Ptr CMpq -> IO () -- | /fmpq_init_set_readonly/ /f/ /z/ -- -- Sets the uninitialised @fmpq_t@ \(f\) to a readonly version of the -- rational \(z\). -- -- Note that the value of \(z\) is assumed to remain constant throughout -- the lifetime of \(f\). -- -- The @fmpq_t@ \(f\) has to be cleared by calling the function -- @fmpq_clear_readonly@. -- -- The suggested use of the two functions is as follows: -- -- > mpq_t z; -- > ... -- > { -- > fmpq_t f; -- > -- > fmpq_init_set_readonly(f, z); -- > foo(..., f); -- > fmpq_clear_readonly(f); -- > } foreign import ccall "fmpq.h fmpq_init_set_readonly" fmpq_init_set_readonly :: Ptr CFmpq -> Ptr CMpq -> IO () -- | /fmpq_clear_readonly/ /f/ -- -- Clears the readonly @fmpq_t@ \(f\). foreign import ccall "fmpq.h fmpq_clear_readonly" fmpq_clear_readonly :: Ptr CFmpq -> IO () -- Input and output ------------------------------------------------------------ -- | /fmpq_fprint/ /file/ /x/ -- -- Prints @x@ as a fraction to the stream @file@. The numerator and -- denominator are printed verbatim as integers, with a forward slash (\/) -- printed in between. -- -- In case of success, returns a positive number. In case of failure, -- returns a non-positive number. foreign import ccall "fmpq.h fmpq_fprint" fmpq_fprint :: Ptr CFile -> Ptr CFmpq -> IO CInt -- | /_fmpq_fprint/ /file/ /num/ /den/ -- -- Does the same thing as @fmpq_fprint@, but for numerator and denominator -- given explicitly as @fmpz_t@ variables. -- -- In case of success, returns a positive number. In case of failure, -- returns a non-positive number. foreign import ccall "fmpq.h _fmpq_fprint" _fmpq_fprint :: Ptr CFile -> Ptr CFmpz -> Ptr CFmpz -> IO CInt -- | /fmpq_print/ /x/ -- -- Prints @x@ as a fraction. The numerator and denominator are printed -- verbatim as integers, with a forward slash (\/) printed in between. -- -- In case of success, returns a positive number. In case of failure, -- returns a non-positive number. fmpq_print :: Ptr CFmpq -> IO CInt fmpq_print x = printCStr (fmpq_get_str nullPtr 10) x -- | /_fmpq_print/ /num/ /den/ -- -- Does the same thing as @fmpq_print@, but for numerator and denominator -- given explicitly as @fmpz_t@ variables. -- -- In case of success, returns a positive number. In case of failure, -- returns a non-positive number. foreign import ccall "fmpq.h _fmpq_print" _fmpq_print :: Ptr CFmpz -> Ptr CFmpz -> IO CInt -- Random number generation ---------------------------------------------------- -- | /fmpq_randtest/ /res/ /state/ /bits/ -- -- Sets @res@ to a random value, with numerator and denominator having up -- to @bits@ bits. The fraction will be in canonical form. This function -- has an increased probability of generating special values which are -- likely to trigger corner cases. foreign import ccall "fmpq.h fmpq_randtest" fmpq_randtest :: Ptr CFmpq -> Ptr CFRandState -> CFBitCnt -> IO () -- | /_fmpq_randtest/ /num/ /den/ /state/ /bits/ -- -- Does the same thing as @fmpq_randtest@, but for numerator and -- denominator given explicitly as @fmpz_t@ variables. Aliasing of @num@ -- and @den@ is not allowed. foreign import ccall "fmpq.h _fmpq_randtest" _fmpq_randtest :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFRandState -> CFBitCnt -> IO () -- | /fmpq_randtest_not_zero/ /res/ /state/ /bits/ -- -- As per @fmpq_randtest@, but the result will not be \(0\). If @bits@ is -- set to \(0\), an exception will result. foreign import ccall "fmpq.h fmpq_randtest_not_zero" fmpq_randtest_not_zero :: Ptr CFmpq -> Ptr CFRandState -> CFBitCnt -> IO () -- | /fmpq_randbits/ /res/ /state/ /bits/ -- -- Sets @res@ to a random value, with numerator and denominator both having -- exactly @bits@ bits before canonicalisation, and then puts @res@ in -- canonical form. Note that as a result of the canonicalisation, the -- resulting numerator and denominator can be slightly smaller than @bits@ -- bits. foreign import ccall "fmpq.h fmpq_randbits" fmpq_randbits :: Ptr CFmpq -> Ptr CFRandState -> CFBitCnt -> IO () -- | /_fmpq_randbits/ /num/ /den/ /state/ /bits/ -- -- Does the same thing as @fmpq_randbits@, but for numerator and -- denominator given explicitly as @fmpz_t@ variables. Aliasing of @num@ -- and @den@ is not allowed. foreign import ccall "fmpq.h _fmpq_randbits" _fmpq_randbits :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFRandState -> CFBitCnt -> IO () -- Arithmetic ------------------------------------------------------------------ -- | /fmpq_add/ /res/ /op1/ /op2/ -- -- Sets @res@ respectively to @op1 + op2@, @op1 - op2@, @op1 * op2@, or -- @op1 \/ op2@. Assumes that the inputs are in canonical form, and -- produces output in canonical form. Division by zero results in an error. -- Aliasing between any combination of the variables is allowed. foreign import ccall "fmpq.h fmpq_add" fmpq_add :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> IO () foreign import ccall "fmpq.h fmpq_sub" fmpq_sub :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> IO () foreign import ccall "fmpq.h fmpq_mul" fmpq_mul :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> IO () foreign import ccall "fmpq.h fmpq_div" fmpq_div :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> IO () -- | /_fmpq_add/ /rnum/ /rden/ /op1num/ /op1den/ /op2num/ /op2den/ -- -- Sets @(rnum, rden)@ to the canonical form of the sum, difference, -- product or quotient respectively of the fractions represented by -- @(op1num, op1den)@ and @(op2num, op2den)@. Aliasing between any -- combination of the variables is allowed, whilst no numerator is aliased -- with a denominator. foreign import ccall "fmpq.h _fmpq_add" _fmpq_add :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h _fmpq_sub" _fmpq_sub :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h _fmpq_mul" _fmpq_mul :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h _fmpq_div" _fmpq_div :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /_fmpq_add_si/ /rnum/ /rden/ /p/ /q/ /r/ -- -- Sets @(rnum, rden)@ to the canonical form of the sum or difference -- respectively of the fractions represented by @(p, q)@ and @(r, 1)@. -- Numerators may not be aliased with denominators. foreign import ccall "fmpq.h _fmpq_add_si" _fmpq_add_si :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CLong -> IO () foreign import ccall "fmpq.h _fmpq_sub_si" _fmpq_sub_si :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CLong -> IO () foreign import ccall "fmpq.h _fmpq_add_ui" _fmpq_add_ui :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CLong -> IO () foreign import ccall "fmpq.h _fmpq_sub_ui" _fmpq_sub_ui :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CLong -> IO () foreign import ccall "fmpq.h _fmpq_add_fmpz" _fmpq_add_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h _fmpq_sub_fmpz" _fmpq_sub_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /fmpq_add_si/ /res/ /op1/ /c/ -- -- Sets @res@ to the sum or difference respectively, of the fraction @op1@ -- and the integer \(c\). foreign import ccall "fmpq.h fmpq_add_si" fmpq_add_si :: Ptr CFmpq -> Ptr CFmpq -> CLong -> IO () foreign import ccall "fmpq.h fmpq_sub_si" fmpq_sub_si :: Ptr CFmpq -> Ptr CFmpq -> CLong -> IO () foreign import ccall "fmpq.h fmpq_add_ui" fmpq_add_ui :: Ptr CFmpq -> Ptr CFmpq -> CLong -> IO () foreign import ccall "fmpq.h fmpq_sub_ui" fmpq_sub_ui :: Ptr CFmpq -> Ptr CFmpq -> CLong -> IO () foreign import ccall "fmpq.h fmpq_sub_fmpz" fmpq_add_fmpz :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h fmpq_sub_fmpz" fmpq_sub_fmpz :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpz -> IO () -- | /_fmpq_mul_si/ /rnum/ /rden/ /p/ /q/ /r/ -- -- Sets @(rnum, rden)@ to the product of @(p, q)@ and the integer \(r\). foreign import ccall "fmpq.h _fmpq_mul_si" _fmpq_mul_si :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CLong -> IO () -- | /fmpq_mul_si/ /res/ /op1/ /c/ -- -- Sets @res@ to the product of @op1@ and the integer \(c\). foreign import ccall "fmpq.h fmpq_mul_si" fmpq_mul_si :: Ptr CFmpq -> Ptr CFmpq -> CLong -> IO () -- | /_fmpq_mul_ui/ /rnum/ /rden/ /p/ /q/ /r/ -- -- Sets @(rnum, rden)@ to the product of @(p, q)@ and the integer \(r\). foreign import ccall "fmpq.h _fmpq_mul_ui" _fmpq_mul_ui :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CULong -> IO () -- | /fmpq_mul_ui/ /res/ /op1/ /c/ -- -- Sets @res@ to the product of @op1@ and the integer \(c\). foreign import ccall "fmpq.h fmpq_mul_ui" fmpq_mul_ui :: Ptr CFmpq -> Ptr CFmpq -> CULong -> IO () -- | /fmpq_addmul/ /res/ /op1/ /op2/ -- -- Sets @res@ to @res + op1 * op2@ or @res - op1 * op2@ respectively, -- placing the result in canonical form. Aliasing between any combination -- of the variables is allowed. foreign import ccall "fmpq.h fmpq_addmul" fmpq_addmul :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> IO () foreign import ccall "fmpq.h fmpq_submul" fmpq_submul :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> IO () -- | /_fmpq_addmul/ /rnum/ /rden/ /op1num/ /op1den/ /op2num/ /op2den/ -- -- Sets @(rnum, rden)@ to the canonical form of the fraction @(rnum, rden)@ -- + @(op1num, op1den)@ * @(op2num, op2den)@ or @(rnum, rden)@ - -- @(op1num, op1den)@ * @(op2num, op2den)@ respectively. Aliasing between -- any combination of the variables is allowed, whilst no numerator is -- aliased with a denominator. foreign import ccall "fmpq.h _fmpq_addmul" _fmpq_addmul :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /fmpq_inv/ /dest/ /src/ -- -- Sets @dest@ to @1 \/ src@. The result is placed in canonical form, -- assuming that @src@ is already in canonical form. foreign import ccall "fmpq.h fmpq_inv" fmpq_inv :: Ptr CFmpq -> Ptr CFmpq -> IO () -- | /_fmpq_pow_si/ /rnum/ /rden/ /opnum/ /opden/ /e/ -- -- Sets @res@ to @op@ raised to the power~\`e\`, where~\`e\` is a @slong@. -- If \(e\) is \(0\) and @op@ is \(0\), then @res@ will be set to \(1\). foreign import ccall "fmpq.h _fmpq_pow_si" _fmpq_pow_si :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> CLong -> IO () foreign import ccall "fmpq.h fmpq_pow_si" fmpq_pow_si :: Ptr CFmpq -> Ptr CFmpq -> CLong -> IO () -- | /fmpq_pow_fmpz/ /a/ /b/ /e/ -- -- Set @res@ to @op@ raised to the power~\`e\`. Return \(1\) for success -- and \(0\) for failure. foreign import ccall "fmpq.h fmpq_pow_fmpz" fmpq_pow_fmpz :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpz -> IO CInt -- | /fmpq_mul_fmpz/ /res/ /op/ /x/ -- -- Sets @res@ to the product of the rational number @op@ and the integer -- @x@. foreign import ccall "fmpq.h fmpq_mul_fmpz" fmpq_mul_fmpz :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpz -> IO () -- | /fmpq_div_fmpz/ /res/ /op/ /x/ -- -- Sets @res@ to the quotient of the rational number @op@ and the integer -- @x@. foreign import ccall "fmpq.h fmpq_div_fmpz" fmpq_div_fmpz :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpz -> IO () -- | /fmpq_mul_2exp/ /res/ /x/ /exp/ -- -- Sets @res@ to @x@ multiplied by @2^exp@. foreign import ccall "fmpq.h fmpq_mul_2exp" fmpq_mul_2exp :: Ptr CFmpq -> Ptr CFmpq -> CFBitCnt -> IO () -- | /fmpq_div_2exp/ /res/ /x/ /exp/ -- -- Sets @res@ to @x@ divided by @2^exp@. foreign import ccall "fmpq.h fmpq_div_2exp" fmpq_div_2exp :: Ptr CFmpq -> Ptr CFmpq -> CFBitCnt -> IO () -- | /_fmpq_gcd/ /rnum/ /rden/ /p/ /q/ /r/ /s/ -- -- Set @(rnum, rden)@ to the gcd of @(p, q)@ and @(r, s)@ which we define -- to be the canonicalisation of gcd\`(ps, qr)\/(qs). (This is apparently -- Euclid\'s original definition and is stable under scaling of numerator -- and denominator. It also agrees with the gcd on the integers. Note that -- it does not agree with gcd as defined in fmpq_poly\`.) This definition -- agrees with the result as output by Sage and Pari\/GP. foreign import ccall "fmpq.h _fmpq_gcd" _fmpq_gcd :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /fmpq_gcd/ /res/ /op1/ /op2/ -- -- Set @res@ to the gcd of @op1@ and @op2@. See the low level function -- @_fmpq_gcd@ for our definition of gcd. foreign import ccall "fmpq.h fmpq_gcd" fmpq_gcd :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> IO () -- | /_fmpq_gcd_cofactors/ /gnum/ /gden/ /abar/ /bbar/ /anum/ /aden/ /bnum/ /bden/ -- -- Set \(g\) to \(\operatorname{gcd}(a,b)\) as per @fmpq_gcd@ and also -- compute \(\overline{a} = a/g\) and \(\overline{b} = b/g\). Unlike -- @fmpq_gcd@, this function requires canonical inputs. foreign import ccall "fmpq.h _fmpq_gcd_cofactors" _fmpq_gcd_cofactors :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h fmpq_gcd_cofactors" fmpq_gcd_cofactors :: Ptr CFmpq -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpq -> Ptr CFmpq -> IO () -- | /_fmpq_add_small/ /rnum/ /rden/ /p1/ /q1/ /p2/ /q2/ -- -- Sets @(rnum, rden)@ to the sum of @(p1, q1)@ and @(p2, q2)@. Assumes -- that @(p1, q1)@ and @(p2, q2)@ are in canonical form and that all inputs -- are between @COEFF_MIN@ and @COEFF_MAX@. foreign import ccall "fmpq.h _fmpq_add_small" _fmpq_add_small :: Ptr CFmpz -> Ptr CFmpz -> CLong -> CULong -> CLong -> CULong -> IO () -- | /_fmpq_mul_small/ /rnum/ /rden/ /p1/ /q1/ /p2/ /q2/ -- -- Sets @(rnum, rden)@ to the product of @(p1, q1)@ and @(p2, q2)@. Assumes -- that @(p1, q1)@ and @(p2, q2)@ are in canonical form and that all inputs -- are between @COEFF_MIN@ and @COEFF_MAX@. foreign import ccall "fmpq.h _fmpq_mul_small" _fmpq_mul_small :: Ptr CFmpz -> Ptr CFmpz -> CLong -> CULong -> CLong -> CULong -> IO () -- Modular reduction and rational reconstruction ------------------------------- -- | /_fmpq_mod_fmpz/ /res/ /num/ /den/ /mod/ -- -- Sets the integer @res@ to the residue \(a\) of \(x = n/d\) = -- @(num, den)@ modulo the positive integer \(m\) = @mod@, defined as the -- \(0 \le a < m\) satisfying \(n \equiv a d \pmod m\). If such an \(a\) -- exists, 1 will be returned, otherwise 0 will be returned. foreign import ccall "fmpq.h _fmpq_mod_fmpz" _fmpq_mod_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CInt foreign import ccall "fmpq.h fmpq_mod_fmpz" fmpq_mod_fmpz :: Ptr CFmpz -> Ptr CFmpq -> Ptr CFmpz -> IO CInt -- | /_fmpq_reconstruct_fmpz_2_naive/ /n/ /d/ /a/ /m/ /N/ /D/ -- -- Reconstructs a rational number from its residue \(a\) modulo \(m\). -- -- Given a modulus \(m > 2\), a residue \(0 \le a < m\), and positive -- \(N, D\) satisfying \(2ND < m\), this function attempts to find a -- fraction \(n/d\) with \(0 \le |n| \le N\) and \(0 < d \le D\) such that -- \(\gcd(n,d) = 1\) and \(n \equiv ad \pmod m\). If a solution exists, -- then it is also unique. The function returns 1 if successful, and 0 to -- indicate that no solution exists. foreign import ccall "fmpq.h _fmpq_reconstruct_fmpz_2_naive" _fmpq_reconstruct_fmpz_2_naive :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CInt foreign import ccall "fmpq.h _fmpq_reconstruct_fmpz_2" _fmpq_reconstruct_fmpz_2 :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h fmpq_reconstruct_fmpz_2" fmpq_reconstruct_fmpz_2 :: Ptr CFmpq -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /_fmpq_reconstruct_fmpz/ /n/ /d/ /a/ /m/ -- -- Reconstructs a rational number from its residue \(a\) modulo \(m\), -- returning 1 if successful and 0 if no solution exists. Uses the balanced -- bounds \(N = D = \lfloor\sqrt{\frac{m-1}{2}}\rfloor\). foreign import ccall "fmpq.h _fmpq_reconstruct_fmpz" _fmpq_reconstruct_fmpz :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO CInt foreign import ccall "fmpq fmpq_reconstruct_fmpz" fmpq_reconstruct_fmpz :: Ptr CFmpq -> Ptr CFmpz -> Ptr CFmpz -> IO () -- Rational enumeration -------------------------------------------------------- -- | /_fmpq_next_minimal/ /rnum/ /rden/ /num/ /den/ -- -- Given \(x\) which is assumed to be nonnegative and in canonical form, -- sets @res@ to the next rational number in the sequence obtained by -- enumerating all positive denominators \(q\), for each \(q\) enumerating -- the numerators \(1 \le p < q\) in order and generating both \(p/q\) and -- \(q/p\), but skipping all \(\gcd(p,q) \ne 1\). Starting with zero, this -- generates every nonnegative rational number once and only once, with the -- first few entries being: -- -- \(0, 1, 1/2, 2, 1/3, 3, 2/3, 3/2, 1/4, 4, 3/4, 4/3, 1/5, 5, 2/5, \ldots.\) -- -- This enumeration produces the rational numbers in order of minimal -- height. It has the disadvantage of being somewhat slower to compute than -- the Calkin-Wilf enumeration. foreign import ccall "fmpq.h _fmpq_next_minimal" _fmpq_next_minimal :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /_fmpq_next_signed_minimal/ /rnum/ /rden/ /num/ /den/ -- -- Given a signed rational number \(x\) assumed to be in canonical form, -- sets @res@ to the next element in the minimal-height sequence generated -- by @fmpq_next_minimal@ but with negative numbers interleaved: -- -- \(0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, \ldots.\) -- -- Starting with zero, this generates every rational number once and only -- once, in order of minimal height. foreign import ccall "fmpq.h _fmpq_next_signed_minimal" _fmpq_next_signed_minimal :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /_fmpq_next_calkin_wilf/ /rnum/ /rden/ /num/ /den/ -- -- Given \(x\) which is assumed to be nonnegative and in canonical form, -- sets @res@ to the next number in the breadth-first traversal of the -- Calkin-Wilf tree. Starting with zero, this generates every nonnegative -- rational number once and only once, with the first few entries being: -- -- \(0, 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, \ldots.\) -- -- Despite the appearance of the initial entries, the Calkin-Wilf -- enumeration does not produce the rational numbers in order of height: -- some small fractions will appear late in the sequence. This order has -- the advantage of being faster to produce than the minimal-height order. foreign import ccall "fmpq.h _fmpq_next_calkin_wilf" _fmpq_next_calkin_wilf :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /_fmpq_next_signed_calkin_wilf/ /rnum/ /rden/ /num/ /den/ -- -- Given a signed rational number \(x\) assumed to be in canonical form, -- sets @res@ to the next element in the Calkin-Wilf sequence with negative -- numbers interleaved: -- -- \(0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, \ldots.\) -- -- Starting with zero, this generates every rational number once and only -- once, but not in order of minimal height. foreign import ccall "fmpq.h _fmpq_next_signed_calkin_wilf" _fmpq_next_signed_calkin_wilf :: Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> Ptr CFmpz -> IO () -- | /fmpq_farey_neighbors/ /l/ /r/ /x/ /Q/ -- -- Set \(l\) and \(r\) to the fractions directly below and above \(x\) in -- the Farey sequence of order \(Q\). This function will throw if \(x\) is -- not canonical or \(Q\) is less than the denominator of \(x\). foreign import ccall "fmpq.h fmpq_farey_neighbors" fmpq_farey_neighbors :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpz -> IO () -- | /fmpq_farey_mediant/ /x/ /l/ /r/ -- -- Set \(x\) to the mediant of \(l\) and \(r\) foreign import ccall "fmpq.h fmpq_mediant" fmpq_mediant :: Ptr CFmpq -> Ptr CFmpq -> Ptr CFmpq -> IO () -- | /fmpq_simplest_between/ /x/ /l/ /r/ -- -- Set \(x\) to the simplest fraction in the closed interval \([l, r]\). -- The underscore version makes the additional assumption that \(l \le r\). -- The endpoints \(l\) and \(r\) do not need to be reduced, but their -- denominators do need to be positive. \(x\) will be always be returned in -- canonical form. A canonical fraction \(a_1/b_1\) is defined to be -- simpler than \(a_2/b_2\) iff \(b_1 Ptr CFmpq -> Ptr CFmpq -> IO () -- Continued fractions --------------------------------------------------------- -- | /fmpq_get_cfrac/ /c/ /rem/ /x/ /n/ -- -- Generates up to \(n\) terms of the (simple) continued fraction expansion -- of \(x\), writing the coefficients to the vector \(c\) and the remainder -- \(r\) to the @rem@ variable. The return value is the number \(k\) of -- generated terms. The output satisfies -- -- \[x = c_0 + \cfrac{1}{c_1 + \cfrac{1}{c_2 + -- \cfrac{1}{ \ddots + \cfrac{1}{c_{k-1} + r }}}}\] -- \] -- -- If \(r\) is zero, the continued fraction expansion is complete. If \(r\) -- is nonzero, \(1/r\) can be passed back as input to generate -- \(c_k, c_{k+1}, \ldots\). Calls to @fmpq_get_cfrac@ can therefore be -- chained to generate the continued fraction incrementally, extracting any -- desired number of coefficients at a time. -- -- In general, a rational number has exactly two continued fraction -- expansions. By convention, we generate the shorter one. The longer -- expansion can be obtained by replacing the last coefficient \(a_{k-1}\) -- by the pair of coefficients \(a_{k-1} - 1, 1\). -- -- [The behaviour of this function in corner cases is as follows:] -- - if \(x\) is infinite (anything over 0), @rem@ will be zero and -- the return is \(k=0\) regardless of \(n\). -- -- - [else (if \(x\) is finite),] -- - if \(n <= 0\), @rem@ will be \(1/x\) (allowing for -- infinite in the case \(x=0\)) and the return is \(k=0\) -- - else (if \(n > 0\)), @rem@ will finite and the return is -- \(0 < k \le n\). -- -- Essentially, if this function is called with canonical \(x\) and -- \(n > 0\), then @rem@ will be canonical. Therefore, applications relying -- on canonical @fmpq_t@\'s should not call this function with \(n <= 0\). foreign import ccall "fmpq.h fmpq_get_cfrac" fmpq_get_cfrac :: Ptr CFmpz -> Ptr CFmpq -> Ptr CFmpq -> CLong -> IO CLong -- | /fmpq_set_cfrac/ /x/ /c/ /n/ -- -- Sets \(x\) to the value of the continued fraction -- -- \[`\] -- \[x = c_0 + \cfrac{1}{c_1 + \cfrac{1}{c_2 + -- \cfrac{1}{ \ddots + \cfrac{1}{c_{n-1}}}}}\] -- -- where all \(c_i\) except \(c_0\) should be nonnegative. It is assumed -- that \(n > 0\). -- -- For large \(n\), this function implements a subquadratic algorithm. The -- convergents are given by a chain product of 2 by 2 matrices. This -- product is split in half recursively to balance the size of the -- coefficients. foreign import ccall "fmpq.h fmpq_set_cfrac" fmpq_set_cfrac :: Ptr CFmpq -> Ptr CFmpz -> CLong -> IO () -- | /fmpq_cfrac_bound/ /x/ -- -- Returns an upper bound for the number of terms in the continued fraction -- expansion of \(x\). The computed bound is not necessarily sharp. -- -- We use the fact that the smallest denominator that can give a continued -- fraction of length \(n\) is the Fibonacci number \(F_{n+1}\). foreign import ccall "fmpq.h fmpq_cfrac_bound" fmpq_cfrac_bound :: Ptr CFmpq -> IO CLong -- | /fmpq_get_cfrac_st/ /c/ /rem/ /x/ /n/ -- -- Generates up to \(n\) terms of the continued fraction expansion -- of \(x\), writing the coefficients to the vector \(c\) and the remainder -- \(r\) to the @rem@ variable. The return value is the number \(k\) of -- generated terms. The output satisfies -- -- \[ -- x = c_0 - \cfrac{1}{c_1 - \cfrac{1}{c_2 - -- \cfrac{1}{ \ddots - \cfrac{1}{c_{k-1} - r }}}} -- \] -- -- This expansion is closely related to the modular group. In terms of -- the generators of the modular group \(S\) and \(T\) the expandion -- of \(x=h/k\) satisfies: -- -- \[ -- T^{c_0} S T^{c_1} \cdots T^{c_{k-1}} S -- \begin{pmatrix} 1 \\ 0 \end{pmatrix} -- = \begin{pmatrix} h \\ k \end{pmatrix} -- \] foreign import ccall "fmpq.h fmpq_get_cfrac_st" fmpq_get_cfrac_st :: Ptr CFmpz -> Ptr CFmpq -> Ptr CFmpq -> CLong -> IO CLong -- | /fmpq_set_cfrac_st/ /x/ /c/ /n/ -- -- Returns the value \(x\) corresponding to the continued fraction \(c\). foreign import ccall "fmpq.h fmpq_set_cfrac_st" fmpq_set_cfrac_st :: Ptr CFmpq -> Ptr CFmpz -> CLong -> IO () -- Special functions ----------------------------------------------------------- -- | /_fmpq_harmonic_ui/ /num/ /den/ /n/ -- -- Computes the harmonic number \(H_n = 1 + 1/2 + 1/3 + \dotsb + 1/n\). -- Table lookup is used for \(H_n\) whose numerator and denominator fit in -- single limb. For larger \(n\), a divide and conquer strategy is used. foreign import ccall "fmpq.h _fmpq_harmonic_ui" _fmpq_harmonic_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO () foreign import ccall "fmpq.h fmpq_harmonic_ui" fmpq_harmonic_ui ::Ptr CFmpq -> CULong -> IO () -- Dedekind sums --------------------------------------------------------------- -- Most of the definitions and relations used in the following section are -- given by Apostol < [Apostol1997]>. The Dedekind sum \(s(h,k)\) is -- defined for all integers \(h\) and \(k\) as -- -- \[`\] -- \[s(h,k) = \sum_{i=1}^{k-1} \left(\left(\frac{i}{k}\right)\right) -- \left(\left(\frac{hi}{k}\right)\right)\] -- -- where -- -- \[`\] -- \[\begin{aligned} -- ((x))=\begin{cases} -- x-\lfloor x\rfloor-1/2 &\mbox{if } -- x\in\mathbf{Q}\setminus\mathbf{Z}\\ -- 0 &\mbox{if }x\in\mathbf{Z}. -- \end{cases} -- \end{aligned}\] -- -- If \(0 < h < k\) and \((h,k) = 1\), this reduces to -- -- \[`\] -- \[s(h,k) = \sum_{i=1}^{k-1} \frac{i}{k} -- \left(\frac{hi}{k}-\left\lfloor\frac{hi}{k}\right\rfloor -- -\frac{1}{2}\right).\] -- -- The main formula for evaluating the series above is the following. -- Letting \(r_0 = k\), \(r_1 = h\), \(r_2, r_3, \ldots, r_n, r_{n+1} = 1\) -- be the remainder sequence in the Euclidean algorithm for computing GCD -- of \(h\) and \(k\), -- -- \[` -- s(h,k) = \frac{1-(-1)^n}{8} - \frac{1}{12} \sum_{i=1}^{n+1} -- (-1)^i \left(\frac{1+r_i^2+r_{i-1}^2}{r_i r_{i-1}}\right).\] -- -- Writing \(s(h,k) = p/q\), some useful properties employed are |s| \< k -- \/ 12, \(q | 6k\) and \(2|p| < k^2\). -- -- | /fmpq_dedekind_sum/ /s/ /h/ /k/ -- -- Computes \(s(h,k)\) for arbitrary \(h\) and \(k\). The naive version -- uses a straightforward implementation of the defining sum using @fmpz@ -- arithmetic and is slow for large \(k\). foreign import ccall "fmpq.h fmpq_dedekind_sum" fmpq_dedekind_sum :: Ptr CFmpq -> Ptr CFmpz -> Ptr CFmpz -> IO () foreign import ccall "fmpq.h fmpq_dedekind_sum_naive" fmpq_dedekind_sum_naive :: Ptr CFmpq -> Ptr CFmpz -> Ptr CFmpz -> IO ()