Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
sagemath
GitHub Repository: sagemath/sagesmc
 Path: blob/master/src/sage/libs/flint/arith.pyx
8871 views
1
"""

2
FLINT Arithmetic Functions

3
"""

4
###########################################################################

5
#       Copyright (C) 2013 Fredrik Johansson <[email protected]>

6
#

7
#  Distributed under the terms of the GNU General Public License (GPL)

8
#                  http://www.gnu.org/licenses/

9
###########################################################################

10


11
include "../../ext/interrupt.pxi"

12
include "fmpz.pxi"

13


14
cdef extern from "flint/fmpq.h":

15
    ctypedef void * fmpq_t

16
    void fmpq_init(fmpq_t)

17
    void fmpq_clear(fmpq_t)

18
    void fmpq_get_mpq(mpq_t, fmpq_t)

19
    void fmpq_set_mpq(fmpq_t, mpq_t)

20


21
cdef extern from "flint/arith.h":

22
    void arith_number_of_partitions(fmpz_t x, unsigned long n)

23
    void arith_dedekind_sum(fmpq_t, fmpz_t, fmpz_t)

24


25
from sage.rings.integer cimport Integer

26
from sage.rings.rational cimport Rational

27


28
def number_of_partitions(unsigned long n):

29
    """

30
    Returns the number of partitions of the integer ``n``.

31


32
    EXAMPLES::

33


34
        sage: from sage.libs.flint.arith import number_of_partitions

35
        sage: number_of_partitions(3)

36
        3

37
        sage: number_of_partitions(10)

38
        42

39
        sage: number_of_partitions(40)

40
        37338

41
        sage: number_of_partitions(100)

42
        190569292

43
        sage: number_of_partitions(100000)

44
        27493510569775696512677516320986352688173429315980054758203125984302147328114964173055050741660736621590157844774296248940493063070200461792764493033510116079342457190155718943509725312466108452006369558934464248716828789832182345009262853831404597021307130674510624419227311238999702284408609370935531629697851569569892196108480158600569421098519

45


46
    TESTS::

47


48
        sage: n = 500 + randint(0,500)

49
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0

50
        True

51
        sage: n = 1500 + randint(0,1500)

52
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0

53
        True

54
        sage: n = 1000000 + randint(0,1000000)

55
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0

56
        True

57
        sage: n = 1000000 + randint(0,1000000)

58
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0

59
        True

60
        sage: n = 1000000 + randint(0,1000000)

61
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0

62
        True

63
        sage: n = 1000000 + randint(0,1000000)

64
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0

65
        True

66
        sage: n = 1000000 + randint(0,1000000)

67
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0

68
        True

69
        sage: n = 1000000 + randint(0,1000000)

70
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0

71
        True

72
        sage: n = 100000000 + randint(0,100000000)

73
        sage: number_of_partitions( n - (n % 385) + 369) % 385 == 0  # long time

74
        True

75
    """

76
    cdef fmpz_t ans_fmpz

77
    cdef Integer ans

78


79
    fmpz_init(ans_fmpz)

80


81
    if n > 1000:

82
        sig_on()

83


84
    arith_number_of_partitions(ans_fmpz, n)

85


86
    if n > 1000:

87
        sig_off()

88


89
    ans = Integer(0)

90
    fmpz_get_mpz(ans.value, ans_fmpz)

91
    fmpz_clear(ans_fmpz)

92
    return ans

93


94
def dedekind_sum(p, q):

95
    """

96
    Return the Dedekind sum `s(p, q)` where `p` and `q` are arbitrary integers.

97


98
    EXAMPLES::

99


100
        sage: from sage.libs.flint.arith import dedekind_sum

101
        sage: dedekind_sum(4, 5)

102
        -1/5

103
    """

104
    p = Integer(p)

105
    q = Integer(q)

106
    s = Rational(0)

107


108
    cdef fmpz_t p_fmpz, q_fmpz

109
    cdef fmpq_t s_fmpq

110


111
    fmpz_init(p_fmpz)

112
    fmpz_init(q_fmpz)

113
    fmpq_init(s_fmpq)

114


115
    fmpz_set_mpz(p_fmpz, (<Integer>p).value)

116
    fmpz_set_mpz(q_fmpz, (<Integer>q).value)

117


118
    arith_dedekind_sum(s_fmpq, p_fmpz, q_fmpz)

119


120
    fmpq_get_mpq((<Rational>s).value, s_fmpq)

121


122
    fmpz_clear(p_fmpz)

123
    fmpz_clear(q_fmpz)

124
    fmpq_clear(s_fmpq)

125


126
    return s

127


128


129