test_densetools.py 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668
  1. """Tests for dense recursive polynomials' tools. """
  2. from sympy.polys.densebasic import (
  3. dup_normal, dmp_normal,
  4. dup_from_raw_dict,
  5. dmp_convert, dmp_swap,
  6. )
  7. from sympy.polys.densearith import dmp_mul_ground
  8. from sympy.polys.densetools import (
  9. dup_clear_denoms, dmp_clear_denoms,
  10. dup_integrate, dmp_integrate, dmp_integrate_in,
  11. dup_diff, dmp_diff, dmp_diff_in,
  12. dup_eval, dmp_eval, dmp_eval_in,
  13. dmp_eval_tail, dmp_diff_eval_in,
  14. dup_trunc, dmp_trunc, dmp_ground_trunc,
  15. dup_monic, dmp_ground_monic,
  16. dup_content, dmp_ground_content,
  17. dup_primitive, dmp_ground_primitive,
  18. dup_extract, dmp_ground_extract,
  19. dup_real_imag,
  20. dup_mirror, dup_scale, dup_shift,
  21. dup_transform,
  22. dup_compose, dmp_compose,
  23. dup_decompose,
  24. dmp_lift,
  25. dup_sign_variations,
  26. dup_revert, dmp_revert,
  27. )
  28. from sympy.polys.polyclasses import ANP
  29. from sympy.polys.polyerrors import (
  30. MultivariatePolynomialError,
  31. ExactQuotientFailed,
  32. NotReversible,
  33. DomainError,
  34. )
  35. from sympy.polys.specialpolys import f_polys
  36. from sympy.polys.domains import FF, ZZ, QQ, EX
  37. from sympy.polys.rings import ring
  38. from sympy.core.numbers import I
  39. from sympy.core.singleton import S
  40. from sympy.functions.elementary.trigonometric import sin
  41. from sympy.abc import x
  42. from sympy.testing.pytest import raises
  43. f_0, f_1, f_2, f_3, f_4, f_5, f_6 = [ f.to_dense() for f in f_polys() ]
  44. def test_dup_integrate():
  45. assert dup_integrate([], 1, QQ) == []
  46. assert dup_integrate([], 2, QQ) == []
  47. assert dup_integrate([QQ(1)], 1, QQ) == [QQ(1), QQ(0)]
  48. assert dup_integrate([QQ(1)], 2, QQ) == [QQ(1, 2), QQ(0), QQ(0)]
  49. assert dup_integrate([QQ(1), QQ(2), QQ(3)], 0, QQ) == \
  50. [QQ(1), QQ(2), QQ(3)]
  51. assert dup_integrate([QQ(1), QQ(2), QQ(3)], 1, QQ) == \
  52. [QQ(1, 3), QQ(1), QQ(3), QQ(0)]
  53. assert dup_integrate([QQ(1), QQ(2), QQ(3)], 2, QQ) == \
  54. [QQ(1, 12), QQ(1, 3), QQ(3, 2), QQ(0), QQ(0)]
  55. assert dup_integrate([QQ(1), QQ(2), QQ(3)], 3, QQ) == \
  56. [QQ(1, 60), QQ(1, 12), QQ(1, 2), QQ(0), QQ(0), QQ(0)]
  57. assert dup_integrate(dup_from_raw_dict({29: QQ(17)}, QQ), 3, QQ) == \
  58. dup_from_raw_dict({32: QQ(17, 29760)}, QQ)
  59. assert dup_integrate(dup_from_raw_dict({29: QQ(17), 5: QQ(1, 2)}, QQ), 3, QQ) == \
  60. dup_from_raw_dict({32: QQ(17, 29760), 8: QQ(1, 672)}, QQ)
  61. def test_dmp_integrate():
  62. assert dmp_integrate([[[]]], 1, 2, QQ) == [[[]]]
  63. assert dmp_integrate([[[]]], 2, 2, QQ) == [[[]]]
  64. assert dmp_integrate([[[QQ(1)]]], 1, 2, QQ) == [[[QQ(1)]], [[]]]
  65. assert dmp_integrate([[[QQ(1)]]], 2, 2, QQ) == [[[QQ(1, 2)]], [[]], [[]]]
  66. assert dmp_integrate([[QQ(1)], [QQ(2)], [QQ(3)]], 0, 1, QQ) == \
  67. [[QQ(1)], [QQ(2)], [QQ(3)]]
  68. assert dmp_integrate([[QQ(1)], [QQ(2)], [QQ(3)]], 1, 1, QQ) == \
  69. [[QQ(1, 3)], [QQ(1)], [QQ(3)], []]
  70. assert dmp_integrate([[QQ(1)], [QQ(2)], [QQ(3)]], 2, 1, QQ) == \
  71. [[QQ(1, 12)], [QQ(1, 3)], [QQ(3, 2)], [], []]
  72. assert dmp_integrate([[QQ(1)], [QQ(2)], [QQ(3)]], 3, 1, QQ) == \
  73. [[QQ(1, 60)], [QQ(1, 12)], [QQ(1, 2)], [], [], []]
  74. def test_dmp_integrate_in():
  75. f = dmp_convert(f_6, 3, ZZ, QQ)
  76. assert dmp_integrate_in(f, 2, 1, 3, QQ) == \
  77. dmp_swap(
  78. dmp_integrate(dmp_swap(f, 0, 1, 3, QQ), 2, 3, QQ), 0, 1, 3, QQ)
  79. assert dmp_integrate_in(f, 3, 1, 3, QQ) == \
  80. dmp_swap(
  81. dmp_integrate(dmp_swap(f, 0, 1, 3, QQ), 3, 3, QQ), 0, 1, 3, QQ)
  82. assert dmp_integrate_in(f, 2, 2, 3, QQ) == \
  83. dmp_swap(
  84. dmp_integrate(dmp_swap(f, 0, 2, 3, QQ), 2, 3, QQ), 0, 2, 3, QQ)
  85. assert dmp_integrate_in(f, 3, 2, 3, QQ) == \
  86. dmp_swap(
  87. dmp_integrate(dmp_swap(f, 0, 2, 3, QQ), 3, 3, QQ), 0, 2, 3, QQ)
  88. def test_dup_diff():
  89. assert dup_diff([], 1, ZZ) == []
  90. assert dup_diff([7], 1, ZZ) == []
  91. assert dup_diff([2, 7], 1, ZZ) == [2]
  92. assert dup_diff([1, 2, 1], 1, ZZ) == [2, 2]
  93. assert dup_diff([1, 2, 3, 4], 1, ZZ) == [3, 4, 3]
  94. assert dup_diff([1, -1, 0, 0, 2], 1, ZZ) == [4, -3, 0, 0]
  95. f = dup_normal([17, 34, 56, -345, 23, 76, 0, 0, 12, 3, 7], ZZ)
  96. assert dup_diff(f, 0, ZZ) == f
  97. assert dup_diff(f, 1, ZZ) == [170, 306, 448, -2415, 138, 380, 0, 0, 24, 3]
  98. assert dup_diff(f, 2, ZZ) == dup_diff(dup_diff(f, 1, ZZ), 1, ZZ)
  99. assert dup_diff(
  100. f, 3, ZZ) == dup_diff(dup_diff(dup_diff(f, 1, ZZ), 1, ZZ), 1, ZZ)
  101. K = FF(3)
  102. f = dup_normal([17, 34, 56, -345, 23, 76, 0, 0, 12, 3, 7], K)
  103. assert dup_diff(f, 1, K) == dup_normal([2, 0, 1, 0, 0, 2, 0, 0, 0, 0], K)
  104. assert dup_diff(f, 2, K) == dup_normal([1, 0, 0, 2, 0, 0, 0], K)
  105. assert dup_diff(f, 3, K) == dup_normal([], K)
  106. assert dup_diff(f, 0, K) == f
  107. assert dup_diff(f, 2, K) == dup_diff(dup_diff(f, 1, K), 1, K)
  108. assert dup_diff(
  109. f, 3, K) == dup_diff(dup_diff(dup_diff(f, 1, K), 1, K), 1, K)
  110. def test_dmp_diff():
  111. assert dmp_diff([], 1, 0, ZZ) == []
  112. assert dmp_diff([[]], 1, 1, ZZ) == [[]]
  113. assert dmp_diff([[[]]], 1, 2, ZZ) == [[[]]]
  114. assert dmp_diff([[[1], [2]]], 1, 2, ZZ) == [[[]]]
  115. assert dmp_diff([[[1]], [[]]], 1, 2, ZZ) == [[[1]]]
  116. assert dmp_diff([[[3]], [[1]], [[]]], 1, 2, ZZ) == [[[6]], [[1]]]
  117. assert dmp_diff([1, -1, 0, 0, 2], 1, 0, ZZ) == \
  118. dup_diff([1, -1, 0, 0, 2], 1, ZZ)
  119. assert dmp_diff(f_6, 0, 3, ZZ) == f_6
  120. assert dmp_diff(f_6, 1, 3, ZZ) == [[[[8460]], [[]]],
  121. [[[135, 0, 0], [], [], [-135, 0, 0]]],
  122. [[[]]],
  123. [[[-423]], [[-47]], [[]], [[141], [], [94, 0], []], [[]]]]
  124. assert dmp_diff(
  125. f_6, 2, 3, ZZ) == dmp_diff(dmp_diff(f_6, 1, 3, ZZ), 1, 3, ZZ)
  126. assert dmp_diff(f_6, 3, 3, ZZ) == dmp_diff(
  127. dmp_diff(dmp_diff(f_6, 1, 3, ZZ), 1, 3, ZZ), 1, 3, ZZ)
  128. K = FF(23)
  129. F_6 = dmp_normal(f_6, 3, K)
  130. assert dmp_diff(F_6, 0, 3, K) == F_6
  131. assert dmp_diff(F_6, 1, 3, K) == dmp_diff(F_6, 1, 3, K)
  132. assert dmp_diff(F_6, 2, 3, K) == dmp_diff(dmp_diff(F_6, 1, 3, K), 1, 3, K)
  133. assert dmp_diff(F_6, 3, 3, K) == dmp_diff(
  134. dmp_diff(dmp_diff(F_6, 1, 3, K), 1, 3, K), 1, 3, K)
  135. def test_dmp_diff_in():
  136. assert dmp_diff_in(f_6, 2, 1, 3, ZZ) == \
  137. dmp_swap(dmp_diff(dmp_swap(f_6, 0, 1, 3, ZZ), 2, 3, ZZ), 0, 1, 3, ZZ)
  138. assert dmp_diff_in(f_6, 3, 1, 3, ZZ) == \
  139. dmp_swap(dmp_diff(dmp_swap(f_6, 0, 1, 3, ZZ), 3, 3, ZZ), 0, 1, 3, ZZ)
  140. assert dmp_diff_in(f_6, 2, 2, 3, ZZ) == \
  141. dmp_swap(dmp_diff(dmp_swap(f_6, 0, 2, 3, ZZ), 2, 3, ZZ), 0, 2, 3, ZZ)
  142. assert dmp_diff_in(f_6, 3, 2, 3, ZZ) == \
  143. dmp_swap(dmp_diff(dmp_swap(f_6, 0, 2, 3, ZZ), 3, 3, ZZ), 0, 2, 3, ZZ)
  144. def test_dup_eval():
  145. assert dup_eval([], 7, ZZ) == 0
  146. assert dup_eval([1, 2], 0, ZZ) == 2
  147. assert dup_eval([1, 2, 3], 7, ZZ) == 66
  148. def test_dmp_eval():
  149. assert dmp_eval([], 3, 0, ZZ) == 0
  150. assert dmp_eval([[]], 3, 1, ZZ) == []
  151. assert dmp_eval([[[]]], 3, 2, ZZ) == [[]]
  152. assert dmp_eval([[1, 2]], 0, 1, ZZ) == [1, 2]
  153. assert dmp_eval([[[1]]], 3, 2, ZZ) == [[1]]
  154. assert dmp_eval([[[1, 2]]], 3, 2, ZZ) == [[1, 2]]
  155. assert dmp_eval([[3, 2], [1, 2]], 3, 1, ZZ) == [10, 8]
  156. assert dmp_eval([[[3, 2]], [[1, 2]]], 3, 2, ZZ) == [[10, 8]]
  157. def test_dmp_eval_in():
  158. assert dmp_eval_in(
  159. f_6, -2, 1, 3, ZZ) == dmp_eval(dmp_swap(f_6, 0, 1, 3, ZZ), -2, 3, ZZ)
  160. assert dmp_eval_in(
  161. f_6, 7, 1, 3, ZZ) == dmp_eval(dmp_swap(f_6, 0, 1, 3, ZZ), 7, 3, ZZ)
  162. assert dmp_eval_in(f_6, -2, 2, 3, ZZ) == dmp_swap(
  163. dmp_eval(dmp_swap(f_6, 0, 2, 3, ZZ), -2, 3, ZZ), 0, 1, 2, ZZ)
  164. assert dmp_eval_in(f_6, 7, 2, 3, ZZ) == dmp_swap(
  165. dmp_eval(dmp_swap(f_6, 0, 2, 3, ZZ), 7, 3, ZZ), 0, 1, 2, ZZ)
  166. f = [[[int(45)]], [[]], [[]], [[int(-9)], [-1], [], [int(3), int(0), int(10), int(0)]]]
  167. assert dmp_eval_in(f, -2, 2, 2, ZZ) == \
  168. [[45], [], [], [-9, -1, 0, -44]]
  169. def test_dmp_eval_tail():
  170. assert dmp_eval_tail([[]], [1], 1, ZZ) == []
  171. assert dmp_eval_tail([[[]]], [1], 2, ZZ) == [[]]
  172. assert dmp_eval_tail([[[]]], [1, 2], 2, ZZ) == []
  173. assert dmp_eval_tail(f_0, [], 2, ZZ) == f_0
  174. assert dmp_eval_tail(f_0, [1, -17, 8], 2, ZZ) == 84496
  175. assert dmp_eval_tail(f_0, [-17, 8], 2, ZZ) == [-1409, 3, 85902]
  176. assert dmp_eval_tail(f_0, [8], 2, ZZ) == [[83, 2], [3], [302, 81, 1]]
  177. assert dmp_eval_tail(f_1, [-17, 8], 2, ZZ) == [-136, 15699, 9166, -27144]
  178. assert dmp_eval_tail(
  179. f_2, [-12, 3], 2, ZZ) == [-1377, 0, -702, -1224, 0, -624]
  180. assert dmp_eval_tail(
  181. f_3, [-12, 3], 2, ZZ) == [144, 82, -5181, -28872, -14868, -540]
  182. assert dmp_eval_tail(
  183. f_4, [25, -1], 2, ZZ) == [152587890625, 9765625, -59605407714843750,
  184. -3839159765625, -1562475, 9536712644531250, 610349546750, -4, 24414375000, 1562520]
  185. assert dmp_eval_tail(f_5, [25, -1], 2, ZZ) == [-1, -78, -2028, -17576]
  186. assert dmp_eval_tail(f_6, [0, 2, 4], 3, ZZ) == [5040, 0, 0, 4480]
  187. def test_dmp_diff_eval_in():
  188. assert dmp_diff_eval_in(f_6, 2, 7, 1, 3, ZZ) == \
  189. dmp_eval(dmp_diff(dmp_swap(f_6, 0, 1, 3, ZZ), 2, 3, ZZ), 7, 3, ZZ)
  190. def test_dup_revert():
  191. f = [-QQ(1, 720), QQ(0), QQ(1, 24), QQ(0), -QQ(1, 2), QQ(0), QQ(1)]
  192. g = [QQ(61, 720), QQ(0), QQ(5, 24), QQ(0), QQ(1, 2), QQ(0), QQ(1)]
  193. assert dup_revert(f, 8, QQ) == g
  194. raises(NotReversible, lambda: dup_revert([QQ(1), QQ(0)], 3, QQ))
  195. def test_dmp_revert():
  196. f = [-QQ(1, 720), QQ(0), QQ(1, 24), QQ(0), -QQ(1, 2), QQ(0), QQ(1)]
  197. g = [QQ(61, 720), QQ(0), QQ(5, 24), QQ(0), QQ(1, 2), QQ(0), QQ(1)]
  198. assert dmp_revert(f, 8, 0, QQ) == g
  199. raises(MultivariatePolynomialError, lambda: dmp_revert([[1]], 2, 1, QQ))
  200. def test_dup_trunc():
  201. assert dup_trunc([1, 2, 3, 4, 5, 6], ZZ(3), ZZ) == [1, -1, 0, 1, -1, 0]
  202. assert dup_trunc([6, 5, 4, 3, 2, 1], ZZ(3), ZZ) == [-1, 1, 0, -1, 1]
  203. def test_dmp_trunc():
  204. assert dmp_trunc([[]], [1, 2], 2, ZZ) == [[]]
  205. assert dmp_trunc([[1, 2], [1, 4, 1], [1]], [1, 2], 1, ZZ) == [[-3], [1]]
  206. def test_dmp_ground_trunc():
  207. assert dmp_ground_trunc(f_0, ZZ(3), 2, ZZ) == \
  208. dmp_normal(
  209. [[[1, -1, 0], [-1]], [[]], [[1, -1, 0], [1, -1, 1], [1]]], 2, ZZ)
  210. def test_dup_monic():
  211. assert dup_monic([3, 6, 9], ZZ) == [1, 2, 3]
  212. raises(ExactQuotientFailed, lambda: dup_monic([3, 4, 5], ZZ))
  213. assert dup_monic([], QQ) == []
  214. assert dup_monic([QQ(1)], QQ) == [QQ(1)]
  215. assert dup_monic([QQ(7), QQ(1), QQ(21)], QQ) == [QQ(1), QQ(1, 7), QQ(3)]
  216. def test_dmp_ground_monic():
  217. assert dmp_ground_monic([[3], [6], [9]], 1, ZZ) == [[1], [2], [3]]
  218. raises(
  219. ExactQuotientFailed, lambda: dmp_ground_monic([[3], [4], [5]], 1, ZZ))
  220. assert dmp_ground_monic([[]], 1, QQ) == [[]]
  221. assert dmp_ground_monic([[QQ(1)]], 1, QQ) == [[QQ(1)]]
  222. assert dmp_ground_monic(
  223. [[QQ(7)], [QQ(1)], [QQ(21)]], 1, QQ) == [[QQ(1)], [QQ(1, 7)], [QQ(3)]]
  224. def test_dup_content():
  225. assert dup_content([], ZZ) == ZZ(0)
  226. assert dup_content([1], ZZ) == ZZ(1)
  227. assert dup_content([-1], ZZ) == ZZ(1)
  228. assert dup_content([1, 1], ZZ) == ZZ(1)
  229. assert dup_content([2, 2], ZZ) == ZZ(2)
  230. assert dup_content([1, 2, 1], ZZ) == ZZ(1)
  231. assert dup_content([2, 4, 2], ZZ) == ZZ(2)
  232. assert dup_content([QQ(2, 3), QQ(4, 9)], QQ) == QQ(2, 9)
  233. assert dup_content([QQ(2, 3), QQ(4, 5)], QQ) == QQ(2, 15)
  234. def test_dmp_ground_content():
  235. assert dmp_ground_content([[]], 1, ZZ) == ZZ(0)
  236. assert dmp_ground_content([[]], 1, QQ) == QQ(0)
  237. assert dmp_ground_content([[1]], 1, ZZ) == ZZ(1)
  238. assert dmp_ground_content([[-1]], 1, ZZ) == ZZ(1)
  239. assert dmp_ground_content([[1], [1]], 1, ZZ) == ZZ(1)
  240. assert dmp_ground_content([[2], [2]], 1, ZZ) == ZZ(2)
  241. assert dmp_ground_content([[1], [2], [1]], 1, ZZ) == ZZ(1)
  242. assert dmp_ground_content([[2], [4], [2]], 1, ZZ) == ZZ(2)
  243. assert dmp_ground_content([[QQ(2, 3)], [QQ(4, 9)]], 1, QQ) == QQ(2, 9)
  244. assert dmp_ground_content([[QQ(2, 3)], [QQ(4, 5)]], 1, QQ) == QQ(2, 15)
  245. assert dmp_ground_content(f_0, 2, ZZ) == ZZ(1)
  246. assert dmp_ground_content(
  247. dmp_mul_ground(f_0, ZZ(2), 2, ZZ), 2, ZZ) == ZZ(2)
  248. assert dmp_ground_content(f_1, 2, ZZ) == ZZ(1)
  249. assert dmp_ground_content(
  250. dmp_mul_ground(f_1, ZZ(3), 2, ZZ), 2, ZZ) == ZZ(3)
  251. assert dmp_ground_content(f_2, 2, ZZ) == ZZ(1)
  252. assert dmp_ground_content(
  253. dmp_mul_ground(f_2, ZZ(4), 2, ZZ), 2, ZZ) == ZZ(4)
  254. assert dmp_ground_content(f_3, 2, ZZ) == ZZ(1)
  255. assert dmp_ground_content(
  256. dmp_mul_ground(f_3, ZZ(5), 2, ZZ), 2, ZZ) == ZZ(5)
  257. assert dmp_ground_content(f_4, 2, ZZ) == ZZ(1)
  258. assert dmp_ground_content(
  259. dmp_mul_ground(f_4, ZZ(6), 2, ZZ), 2, ZZ) == ZZ(6)
  260. assert dmp_ground_content(f_5, 2, ZZ) == ZZ(1)
  261. assert dmp_ground_content(
  262. dmp_mul_ground(f_5, ZZ(7), 2, ZZ), 2, ZZ) == ZZ(7)
  263. assert dmp_ground_content(f_6, 3, ZZ) == ZZ(1)
  264. assert dmp_ground_content(
  265. dmp_mul_ground(f_6, ZZ(8), 3, ZZ), 3, ZZ) == ZZ(8)
  266. def test_dup_primitive():
  267. assert dup_primitive([], ZZ) == (ZZ(0), [])
  268. assert dup_primitive([ZZ(1)], ZZ) == (ZZ(1), [ZZ(1)])
  269. assert dup_primitive([ZZ(1), ZZ(1)], ZZ) == (ZZ(1), [ZZ(1), ZZ(1)])
  270. assert dup_primitive([ZZ(2), ZZ(2)], ZZ) == (ZZ(2), [ZZ(1), ZZ(1)])
  271. assert dup_primitive(
  272. [ZZ(1), ZZ(2), ZZ(1)], ZZ) == (ZZ(1), [ZZ(1), ZZ(2), ZZ(1)])
  273. assert dup_primitive(
  274. [ZZ(2), ZZ(4), ZZ(2)], ZZ) == (ZZ(2), [ZZ(1), ZZ(2), ZZ(1)])
  275. assert dup_primitive([], QQ) == (QQ(0), [])
  276. assert dup_primitive([QQ(1)], QQ) == (QQ(1), [QQ(1)])
  277. assert dup_primitive([QQ(1), QQ(1)], QQ) == (QQ(1), [QQ(1), QQ(1)])
  278. assert dup_primitive([QQ(2), QQ(2)], QQ) == (QQ(2), [QQ(1), QQ(1)])
  279. assert dup_primitive(
  280. [QQ(1), QQ(2), QQ(1)], QQ) == (QQ(1), [QQ(1), QQ(2), QQ(1)])
  281. assert dup_primitive(
  282. [QQ(2), QQ(4), QQ(2)], QQ) == (QQ(2), [QQ(1), QQ(2), QQ(1)])
  283. assert dup_primitive(
  284. [QQ(2, 3), QQ(4, 9)], QQ) == (QQ(2, 9), [QQ(3), QQ(2)])
  285. assert dup_primitive(
  286. [QQ(2, 3), QQ(4, 5)], QQ) == (QQ(2, 15), [QQ(5), QQ(6)])
  287. def test_dmp_ground_primitive():
  288. assert dmp_ground_primitive([[]], 1, ZZ) == (ZZ(0), [[]])
  289. assert dmp_ground_primitive(f_0, 2, ZZ) == (ZZ(1), f_0)
  290. assert dmp_ground_primitive(
  291. dmp_mul_ground(f_0, ZZ(2), 2, ZZ), 2, ZZ) == (ZZ(2), f_0)
  292. assert dmp_ground_primitive(f_1, 2, ZZ) == (ZZ(1), f_1)
  293. assert dmp_ground_primitive(
  294. dmp_mul_ground(f_1, ZZ(3), 2, ZZ), 2, ZZ) == (ZZ(3), f_1)
  295. assert dmp_ground_primitive(f_2, 2, ZZ) == (ZZ(1), f_2)
  296. assert dmp_ground_primitive(
  297. dmp_mul_ground(f_2, ZZ(4), 2, ZZ), 2, ZZ) == (ZZ(4), f_2)
  298. assert dmp_ground_primitive(f_3, 2, ZZ) == (ZZ(1), f_3)
  299. assert dmp_ground_primitive(
  300. dmp_mul_ground(f_3, ZZ(5), 2, ZZ), 2, ZZ) == (ZZ(5), f_3)
  301. assert dmp_ground_primitive(f_4, 2, ZZ) == (ZZ(1), f_4)
  302. assert dmp_ground_primitive(
  303. dmp_mul_ground(f_4, ZZ(6), 2, ZZ), 2, ZZ) == (ZZ(6), f_4)
  304. assert dmp_ground_primitive(f_5, 2, ZZ) == (ZZ(1), f_5)
  305. assert dmp_ground_primitive(
  306. dmp_mul_ground(f_5, ZZ(7), 2, ZZ), 2, ZZ) == (ZZ(7), f_5)
  307. assert dmp_ground_primitive(f_6, 3, ZZ) == (ZZ(1), f_6)
  308. assert dmp_ground_primitive(
  309. dmp_mul_ground(f_6, ZZ(8), 3, ZZ), 3, ZZ) == (ZZ(8), f_6)
  310. assert dmp_ground_primitive([[ZZ(2)]], 1, ZZ) == (ZZ(2), [[ZZ(1)]])
  311. assert dmp_ground_primitive([[QQ(2)]], 1, QQ) == (QQ(2), [[QQ(1)]])
  312. assert dmp_ground_primitive(
  313. [[QQ(2, 3)], [QQ(4, 9)]], 1, QQ) == (QQ(2, 9), [[QQ(3)], [QQ(2)]])
  314. assert dmp_ground_primitive(
  315. [[QQ(2, 3)], [QQ(4, 5)]], 1, QQ) == (QQ(2, 15), [[QQ(5)], [QQ(6)]])
  316. def test_dup_extract():
  317. f = dup_normal([2930944, 0, 2198208, 0, 549552, 0, 45796], ZZ)
  318. g = dup_normal([17585664, 0, 8792832, 0, 1099104, 0], ZZ)
  319. F = dup_normal([64, 0, 48, 0, 12, 0, 1], ZZ)
  320. G = dup_normal([384, 0, 192, 0, 24, 0], ZZ)
  321. assert dup_extract(f, g, ZZ) == (45796, F, G)
  322. def test_dmp_ground_extract():
  323. f = dmp_normal(
  324. [[2930944], [], [2198208], [], [549552], [], [45796]], 1, ZZ)
  325. g = dmp_normal([[17585664], [], [8792832], [], [1099104], []], 1, ZZ)
  326. F = dmp_normal([[64], [], [48], [], [12], [], [1]], 1, ZZ)
  327. G = dmp_normal([[384], [], [192], [], [24], []], 1, ZZ)
  328. assert dmp_ground_extract(f, g, 1, ZZ) == (45796, F, G)
  329. def test_dup_real_imag():
  330. assert dup_real_imag([], ZZ) == ([[]], [[]])
  331. assert dup_real_imag([1], ZZ) == ([[1]], [[]])
  332. assert dup_real_imag([1, 1], ZZ) == ([[1], [1]], [[1, 0]])
  333. assert dup_real_imag([1, 2], ZZ) == ([[1], [2]], [[1, 0]])
  334. assert dup_real_imag(
  335. [1, 2, 3], ZZ) == ([[1], [2], [-1, 0, 3]], [[2, 0], [2, 0]])
  336. raises(DomainError, lambda: dup_real_imag([EX(1), EX(2)], EX))
  337. def test_dup_mirror():
  338. assert dup_mirror([], ZZ) == []
  339. assert dup_mirror([1], ZZ) == [1]
  340. assert dup_mirror([1, 2, 3, 4, 5], ZZ) == [1, -2, 3, -4, 5]
  341. assert dup_mirror([1, 2, 3, 4, 5, 6], ZZ) == [-1, 2, -3, 4, -5, 6]
  342. def test_dup_scale():
  343. assert dup_scale([], -1, ZZ) == []
  344. assert dup_scale([1], -1, ZZ) == [1]
  345. assert dup_scale([1, 2, 3, 4, 5], -1, ZZ) == [1, -2, 3, -4, 5]
  346. assert dup_scale([1, 2, 3, 4, 5], -7, ZZ) == [2401, -686, 147, -28, 5]
  347. def test_dup_shift():
  348. assert dup_shift([], 1, ZZ) == []
  349. assert dup_shift([1], 1, ZZ) == [1]
  350. assert dup_shift([1, 2, 3, 4, 5], 1, ZZ) == [1, 6, 15, 20, 15]
  351. assert dup_shift([1, 2, 3, 4, 5], 7, ZZ) == [1, 30, 339, 1712, 3267]
  352. def test_dup_transform():
  353. assert dup_transform([], [], [1, 1], ZZ) == []
  354. assert dup_transform([], [1], [1, 1], ZZ) == []
  355. assert dup_transform([], [1, 2], [1, 1], ZZ) == []
  356. assert dup_transform([6, -5, 4, -3, 17], [1, -3, 4], [2, -3], ZZ) == \
  357. [6, -82, 541, -2205, 6277, -12723, 17191, -13603, 4773]
  358. def test_dup_compose():
  359. assert dup_compose([], [], ZZ) == []
  360. assert dup_compose([], [1], ZZ) == []
  361. assert dup_compose([], [1, 2], ZZ) == []
  362. assert dup_compose([1], [], ZZ) == [1]
  363. assert dup_compose([1, 2, 0], [], ZZ) == []
  364. assert dup_compose([1, 2, 1], [], ZZ) == [1]
  365. assert dup_compose([1, 2, 1], [1], ZZ) == [4]
  366. assert dup_compose([1, 2, 1], [7], ZZ) == [64]
  367. assert dup_compose([1, 2, 1], [1, -1], ZZ) == [1, 0, 0]
  368. assert dup_compose([1, 2, 1], [1, 1], ZZ) == [1, 4, 4]
  369. assert dup_compose([1, 2, 1], [1, 2, 1], ZZ) == [1, 4, 8, 8, 4]
  370. def test_dmp_compose():
  371. assert dmp_compose([1, 2, 1], [1, 2, 1], 0, ZZ) == [1, 4, 8, 8, 4]
  372. assert dmp_compose([[[]]], [[[]]], 2, ZZ) == [[[]]]
  373. assert dmp_compose([[[]]], [[[1]]], 2, ZZ) == [[[]]]
  374. assert dmp_compose([[[]]], [[[1]], [[2]]], 2, ZZ) == [[[]]]
  375. assert dmp_compose([[[1]]], [], 2, ZZ) == [[[1]]]
  376. assert dmp_compose([[1], [2], [ ]], [[]], 1, ZZ) == [[]]
  377. assert dmp_compose([[1], [2], [1]], [[]], 1, ZZ) == [[1]]
  378. assert dmp_compose([[1], [2], [1]], [[1]], 1, ZZ) == [[4]]
  379. assert dmp_compose([[1], [2], [1]], [[7]], 1, ZZ) == [[64]]
  380. assert dmp_compose([[1], [2], [1]], [[1], [-1]], 1, ZZ) == [[1], [ ], [ ]]
  381. assert dmp_compose([[1], [2], [1]], [[1], [ 1]], 1, ZZ) == [[1], [4], [4]]
  382. assert dmp_compose(
  383. [[1], [2], [1]], [[1], [2], [1]], 1, ZZ) == [[1], [4], [8], [8], [4]]
  384. def test_dup_decompose():
  385. assert dup_decompose([1], ZZ) == [[1]]
  386. assert dup_decompose([1, 0], ZZ) == [[1, 0]]
  387. assert dup_decompose([1, 0, 0, 0], ZZ) == [[1, 0, 0, 0]]
  388. assert dup_decompose([1, 0, 0, 0, 0], ZZ) == [[1, 0, 0], [1, 0, 0]]
  389. assert dup_decompose(
  390. [1, 0, 0, 0, 0, 0, 0], ZZ) == [[1, 0, 0, 0], [1, 0, 0]]
  391. assert dup_decompose([7, 0, 0, 0, 1], ZZ) == [[7, 0, 1], [1, 0, 0]]
  392. assert dup_decompose([4, 0, 3, 0, 2], ZZ) == [[4, 3, 2], [1, 0, 0]]
  393. f = [1, 0, 20, 0, 150, 0, 500, 0, 625, -2, 0, -10, 9]
  394. assert dup_decompose(f, ZZ) == [[1, 0, 0, -2, 9], [1, 0, 5, 0]]
  395. f = [2, 0, 40, 0, 300, 0, 1000, 0, 1250, -4, 0, -20, 18]
  396. assert dup_decompose(f, ZZ) == [[2, 0, 0, -4, 18], [1, 0, 5, 0]]
  397. f = [1, 0, 20, -8, 150, -120, 524, -600, 865, -1034, 600, -170, 29]
  398. assert dup_decompose(f, ZZ) == [[1, -8, 24, -34, 29], [1, 0, 5, 0]]
  399. R, t = ring("t", ZZ)
  400. f = [6*t**2 - 42,
  401. 48*t**2 + 96,
  402. 144*t**2 + 648*t + 288,
  403. 624*t**2 + 864*t + 384,
  404. 108*t**3 + 312*t**2 + 432*t + 192]
  405. assert dup_decompose(f, R.to_domain()) == [f]
  406. def test_dmp_lift():
  407. q = [QQ(1, 1), QQ(0, 1), QQ(1, 1)]
  408. f = [ANP([QQ(1, 1)], q, QQ), ANP([], q, QQ), ANP([], q, QQ),
  409. ANP([QQ(1, 1), QQ(0, 1)], q, QQ), ANP([QQ(17, 1), QQ(0, 1)], q, QQ)]
  410. assert dmp_lift(f, 0, QQ.algebraic_field(I)) == \
  411. [QQ(1), QQ(0), QQ(0), QQ(0), QQ(0), QQ(0), QQ(2), QQ(0), QQ(578),
  412. QQ(0), QQ(0), QQ(0), QQ(1), QQ(0), QQ(-578), QQ(0), QQ(83521)]
  413. raises(DomainError, lambda: dmp_lift([EX(1), EX(2)], 0, EX))
  414. def test_dup_sign_variations():
  415. assert dup_sign_variations([], ZZ) == 0
  416. assert dup_sign_variations([1, 0], ZZ) == 0
  417. assert dup_sign_variations([1, 0, 2], ZZ) == 0
  418. assert dup_sign_variations([1, 0, 3, 0], ZZ) == 0
  419. assert dup_sign_variations([1, 0, 4, 0, 5], ZZ) == 0
  420. assert dup_sign_variations([-1, 0, 2], ZZ) == 1
  421. assert dup_sign_variations([-1, 0, 3, 0], ZZ) == 1
  422. assert dup_sign_variations([-1, 0, 4, 0, 5], ZZ) == 1
  423. assert dup_sign_variations([-1, -4, -5], ZZ) == 0
  424. assert dup_sign_variations([ 1, -4, -5], ZZ) == 1
  425. assert dup_sign_variations([ 1, 4, -5], ZZ) == 1
  426. assert dup_sign_variations([ 1, -4, 5], ZZ) == 2
  427. assert dup_sign_variations([-1, 4, -5], ZZ) == 2
  428. assert dup_sign_variations([-1, 4, 5], ZZ) == 1
  429. assert dup_sign_variations([-1, -4, 5], ZZ) == 1
  430. assert dup_sign_variations([ 1, 4, 5], ZZ) == 0
  431. assert dup_sign_variations([-1, 0, -4, 0, -5], ZZ) == 0
  432. assert dup_sign_variations([ 1, 0, -4, 0, -5], ZZ) == 1
  433. assert dup_sign_variations([ 1, 0, 4, 0, -5], ZZ) == 1
  434. assert dup_sign_variations([ 1, 0, -4, 0, 5], ZZ) == 2
  435. assert dup_sign_variations([-1, 0, 4, 0, -5], ZZ) == 2
  436. assert dup_sign_variations([-1, 0, 4, 0, 5], ZZ) == 1
  437. assert dup_sign_variations([-1, 0, -4, 0, 5], ZZ) == 1
  438. assert dup_sign_variations([ 1, 0, 4, 0, 5], ZZ) == 0
  439. def test_dup_clear_denoms():
  440. assert dup_clear_denoms([], QQ, ZZ) == (ZZ(1), [])
  441. assert dup_clear_denoms([QQ(1)], QQ, ZZ) == (ZZ(1), [QQ(1)])
  442. assert dup_clear_denoms([QQ(7)], QQ, ZZ) == (ZZ(1), [QQ(7)])
  443. assert dup_clear_denoms([QQ(7, 3)], QQ) == (ZZ(3), [QQ(7)])
  444. assert dup_clear_denoms([QQ(7, 3)], QQ, ZZ) == (ZZ(3), [QQ(7)])
  445. assert dup_clear_denoms(
  446. [QQ(3), QQ(1), QQ(0)], QQ, ZZ) == (ZZ(1), [QQ(3), QQ(1), QQ(0)])
  447. assert dup_clear_denoms(
  448. [QQ(1), QQ(1, 2), QQ(0)], QQ, ZZ) == (ZZ(2), [QQ(2), QQ(1), QQ(0)])
  449. assert dup_clear_denoms([QQ(3), QQ(
  450. 1), QQ(0)], QQ, ZZ, convert=True) == (ZZ(1), [ZZ(3), ZZ(1), ZZ(0)])
  451. assert dup_clear_denoms([QQ(1), QQ(
  452. 1, 2), QQ(0)], QQ, ZZ, convert=True) == (ZZ(2), [ZZ(2), ZZ(1), ZZ(0)])
  453. assert dup_clear_denoms(
  454. [EX(S(3)/2), EX(S(9)/4)], EX) == (EX(4), [EX(6), EX(9)])
  455. assert dup_clear_denoms([EX(7)], EX) == (EX(1), [EX(7)])
  456. assert dup_clear_denoms([EX(sin(x)/x), EX(0)], EX) == (EX(x), [EX(sin(x)), EX(0)])
  457. def test_dmp_clear_denoms():
  458. assert dmp_clear_denoms([[]], 1, QQ, ZZ) == (ZZ(1), [[]])
  459. assert dmp_clear_denoms([[QQ(1)]], 1, QQ, ZZ) == (ZZ(1), [[QQ(1)]])
  460. assert dmp_clear_denoms([[QQ(7)]], 1, QQ, ZZ) == (ZZ(1), [[QQ(7)]])
  461. assert dmp_clear_denoms([[QQ(7, 3)]], 1, QQ) == (ZZ(3), [[QQ(7)]])
  462. assert dmp_clear_denoms([[QQ(7, 3)]], 1, QQ, ZZ) == (ZZ(3), [[QQ(7)]])
  463. assert dmp_clear_denoms(
  464. [[QQ(3)], [QQ(1)], []], 1, QQ, ZZ) == (ZZ(1), [[QQ(3)], [QQ(1)], []])
  465. assert dmp_clear_denoms([[QQ(
  466. 1)], [QQ(1, 2)], []], 1, QQ, ZZ) == (ZZ(2), [[QQ(2)], [QQ(1)], []])
  467. assert dmp_clear_denoms([QQ(3), QQ(
  468. 1), QQ(0)], 0, QQ, ZZ, convert=True) == (ZZ(1), [ZZ(3), ZZ(1), ZZ(0)])
  469. assert dmp_clear_denoms([QQ(1), QQ(1, 2), QQ(
  470. 0)], 0, QQ, ZZ, convert=True) == (ZZ(2), [ZZ(2), ZZ(1), ZZ(0)])
  471. assert dmp_clear_denoms([[QQ(3)], [QQ(
  472. 1)], []], 1, QQ, ZZ, convert=True) == (ZZ(1), [[QQ(3)], [QQ(1)], []])
  473. assert dmp_clear_denoms([[QQ(1)], [QQ(1, 2)], []], 1, QQ, ZZ,
  474. convert=True) == (ZZ(2), [[QQ(2)], [QQ(1)], []])
  475. assert dmp_clear_denoms(
  476. [[EX(S(3)/2)], [EX(S(9)/4)]], 1, EX) == (EX(4), [[EX(6)], [EX(9)]])
  477. assert dmp_clear_denoms([[EX(7)]], 1, EX) == (EX(1), [[EX(7)]])
  478. assert dmp_clear_denoms([[EX(sin(x)/x), EX(0)]], 1, EX) == (EX(x), [[EX(sin(x)), EX(0)]])