Coverage for /usr/lib/python3/dist-packages/sympy/polys/densearith.py: 11%

1"""Arithmetics for dense recursive polynomials in ``K[x]`` or ``K[X]``. """

4from sympy.polys.densebasic import (

5 dup_slice,

6 dup_LC, dmp_LC,

7 dup_degree, dmp_degree,

8 dup_strip, dmp_strip,

9 dmp_zero_p, dmp_zero,

10 dmp_one_p, dmp_one,

11 dmp_ground, dmp_zeros)

12from sympy.polys.polyerrors import (ExactQuotientFailed, PolynomialDivisionFailed)

14def dup_add_term(f, c, i, K):

15 """

16 Add ``c*x**i`` to ``f`` in ``K[x]``.

18 Examples

19 ========

21 >>> from sympy.polys import ring, ZZ

22 >>> R, x = ring("x", ZZ)

24 >>> R.dup_add_term(x**2 - 1, ZZ(2), 4)

25 2*x**4 + x**2 - 1

27 """

28 if not c:

29 return f

31 n = len(f)

32 m = n - i - 1

34 if i == n - 1:

35 return dup_strip([f[0] + c] + f[1:])

36 else:

37 if i >= n:

38 return [c] + [K.zero]*(i - n) + f

39 else:

40 return f[:m] + [f[m] + c] + f[m + 1:]

43def dmp_add_term(f, c, i, u, K):

44 """

45 Add ``c(x_2..x_u)*x_0**i`` to ``f`` in ``K[X]``.

47 Examples

48 ========

50 >>> from sympy.polys import ring, ZZ

51 >>> R, x,y = ring("x,y", ZZ)

53 >>> R.dmp_add_term(x*y + 1, 2, 2)

54 2*x**2 + x*y + 1

56 """

57 if not u:

58 return dup_add_term(f, c, i, K)

60 v = u - 1

62 if dmp_zero_p(c, v):

63 return f

65 n = len(f)

66 m = n - i - 1

68 if i == n - 1:

69 return dmp_strip([dmp_add(f[0], c, v, K)] + f[1:], u)

70 else:

71 if i >= n:

72 return [c] + dmp_zeros(i - n, v, K) + f

73 else:

74 return f[:m] + [dmp_add(f[m], c, v, K)] + f[m + 1:]

77def dup_sub_term(f, c, i, K):

78 """

79 Subtract ``c*x**i`` from ``f`` in ``K[x]``.

81 Examples

82 ========

84 >>> from sympy.polys import ring, ZZ

85 >>> R, x = ring("x", ZZ)

87 >>> R.dup_sub_term(2*x**4 + x**2 - 1, ZZ(2), 4)

88 x**2 - 1

90 """

91 if not c:

92 return f

94 n = len(f)

95 m = n - i - 1

97 if i == n - 1:

98 return dup_strip([f[0] - c] + f[1:])

99 else:

100 if i >= n:

101 return [-c] + [K.zero]*(i - n) + f

102 else:

103 return f[:m] + [f[m] - c] + f[m + 1:]

104

105

106def dmp_sub_term(f, c, i, u, K):

107 """

108 Subtract ``c(x_2..x_u)*x_0**i`` from ``f`` in ``K[X]``.

109

110 Examples

111 ========

112

113 >>> from sympy.polys import ring, ZZ

114 >>> R, x,y = ring("x,y", ZZ)

115

116 >>> R.dmp_sub_term(2*x**2 + x*y + 1, 2, 2)

117 x*y + 1

118

119 """

120 if not u:

121 return dup_add_term(f, -c, i, K)

122

123 v = u - 1

124

125 if dmp_zero_p(c, v):

126 return f

127

128 n = len(f)

129 m = n - i - 1

130

131 if i == n - 1:

132 return dmp_strip([dmp_sub(f[0], c, v, K)] + f[1:], u)

133 else:

134 if i >= n:

135 return [dmp_neg(c, v, K)] + dmp_zeros(i - n, v, K) + f

136 else:

137 return f[:m] + [dmp_sub(f[m], c, v, K)] + f[m + 1:]

138

139

140def dup_mul_term(f, c, i, K):

141 """

142 Multiply ``f`` by ``c*x**i`` in ``K[x]``.

143

144 Examples

145 ========

146

147 >>> from sympy.polys import ring, ZZ

148 >>> R, x = ring("x", ZZ)

149

150 >>> R.dup_mul_term(x**2 - 1, ZZ(3), 2)

151 3*x**4 - 3*x**2

152

153 """

154 if not c or not f:

155 return []

156 else:

157 return [ cf * c for cf in f ] + [K.zero]*i

158

159

160def dmp_mul_term(f, c, i, u, K):

161 """

162 Multiply ``f`` by ``c(x_2..x_u)*x_0**i`` in ``K[X]``.

163

164 Examples

165 ========

166

167 >>> from sympy.polys import ring, ZZ

168 >>> R, x,y = ring("x,y", ZZ)

169

170 >>> R.dmp_mul_term(x**2*y + x, 3*y, 2)

171 3*x**4*y**2 + 3*x**3*y

172

173 """

174 if not u:

175 return dup_mul_term(f, c, i, K)

176

177 v = u - 1

178

179 if dmp_zero_p(f, u):

180 return f

181 if dmp_zero_p(c, v):

182 return dmp_zero(u)

183 else:

184 return [ dmp_mul(cf, c, v, K) for cf in f ] + dmp_zeros(i, v, K)

185

186

187def dup_add_ground(f, c, K):

188 """

189 Add an element of the ground domain to ``f``.

190

191 Examples

192 ========

193

194 >>> from sympy.polys import ring, ZZ

195 >>> R, x = ring("x", ZZ)

196

197 >>> R.dup_add_ground(x**3 + 2*x**2 + 3*x + 4, ZZ(4))

198 x**3 + 2*x**2 + 3*x + 8

199

200 """

201 return dup_add_term(f, c, 0, K)

202

203

204def dmp_add_ground(f, c, u, K):

205 """

206 Add an element of the ground domain to ``f``.

207

208 Examples

209 ========

210

211 >>> from sympy.polys import ring, ZZ

212 >>> R, x,y = ring("x,y", ZZ)

213

214 >>> R.dmp_add_ground(x**3 + 2*x**2 + 3*x + 4, ZZ(4))

215 x**3 + 2*x**2 + 3*x + 8

216

217 """

218 return dmp_add_term(f, dmp_ground(c, u - 1), 0, u, K)

219

220

221def dup_sub_ground(f, c, K):

222 """

223 Subtract an element of the ground domain from ``f``.

224

225 Examples

226 ========

227

228 >>> from sympy.polys import ring, ZZ

229 >>> R, x = ring("x", ZZ)

230

231 >>> R.dup_sub_ground(x**3 + 2*x**2 + 3*x + 4, ZZ(4))

232 x**3 + 2*x**2 + 3*x

233

234 """

235 return dup_sub_term(f, c, 0, K)

236

237

238def dmp_sub_ground(f, c, u, K):

239 """

240 Subtract an element of the ground domain from ``f``.

241

242 Examples

243 ========

244

245 >>> from sympy.polys import ring, ZZ

246 >>> R, x,y = ring("x,y", ZZ)

247

248 >>> R.dmp_sub_ground(x**3 + 2*x**2 + 3*x + 4, ZZ(4))

249 x**3 + 2*x**2 + 3*x

250

251 """

252 return dmp_sub_term(f, dmp_ground(c, u - 1), 0, u, K)

253

254

255def dup_mul_ground(f, c, K):

256 """

257 Multiply ``f`` by a constant value in ``K[x]``.

258

259 Examples

260 ========

261

262 >>> from sympy.polys import ring, ZZ

263 >>> R, x = ring("x", ZZ)

264

265 >>> R.dup_mul_ground(x**2 + 2*x - 1, ZZ(3))

266 3*x**2 + 6*x - 3

267

268 """

269 if not c or not f:

270 return []

271 else:

272 return [ cf * c for cf in f ]

273

274

275def dmp_mul_ground(f, c, u, K):

276 """

277 Multiply ``f`` by a constant value in ``K[X]``.

278

279 Examples

280 ========

281

282 >>> from sympy.polys import ring, ZZ

283 >>> R, x,y = ring("x,y", ZZ)

284

285 >>> R.dmp_mul_ground(2*x + 2*y, ZZ(3))

286 6*x + 6*y

287

288 """

289 if not u:

290 return dup_mul_ground(f, c, K)

291

292 v = u - 1

293

294 return [ dmp_mul_ground(cf, c, v, K) for cf in f ]

295

296

297def dup_quo_ground(f, c, K):

298 """

299 Quotient by a constant in ``K[x]``.

300

301 Examples

302 ========

303

304 >>> from sympy.polys import ring, ZZ, QQ

305

306 >>> R, x = ring("x", ZZ)

307 >>> R.dup_quo_ground(3*x**2 + 2, ZZ(2))

308 x**2 + 1

309

310 >>> R, x = ring("x", QQ)

311 >>> R.dup_quo_ground(3*x**2 + 2, QQ(2))

312 3/2*x**2 + 1

313

314 """

315 if not c:

316 raise ZeroDivisionError('polynomial division')

317 if not f:

318 return f

319

320 if K.is_Field:

321 return [ K.quo(cf, c) for cf in f ]

322 else:

323 return [ cf // c for cf in f ]

324

325

326def dmp_quo_ground(f, c, u, K):

327 """

328 Quotient by a constant in ``K[X]``.

329

330 Examples

331 ========

332

333 >>> from sympy.polys import ring, ZZ, QQ

334

335 >>> R, x,y = ring("x,y", ZZ)

336 >>> R.dmp_quo_ground(2*x**2*y + 3*x, ZZ(2))

337 x**2*y + x

338

339 >>> R, x,y = ring("x,y", QQ)

340 >>> R.dmp_quo_ground(2*x**2*y + 3*x, QQ(2))

341 x**2*y + 3/2*x

342

343 """

344 if not u:

345 return dup_quo_ground(f, c, K)

346

347 v = u - 1

348

349 return [ dmp_quo_ground(cf, c, v, K) for cf in f ]

350

351

352def dup_exquo_ground(f, c, K):

353 """

354 Exact quotient by a constant in ``K[x]``.

355

356 Examples

357 ========

358

359 >>> from sympy.polys import ring, QQ

360 >>> R, x = ring("x", QQ)

361

362 >>> R.dup_exquo_ground(x**2 + 2, QQ(2))

363 1/2*x**2 + 1

364

365 """

366 if not c:

367 raise ZeroDivisionError('polynomial division')

368 if not f:

369 return f

370

371 return [ K.exquo(cf, c) for cf in f ]

372

373

374def dmp_exquo_ground(f, c, u, K):

375 """

376 Exact quotient by a constant in ``K[X]``.

377

378 Examples

379 ========

380

381 >>> from sympy.polys import ring, QQ

382 >>> R, x,y = ring("x,y", QQ)

383

384 >>> R.dmp_exquo_ground(x**2*y + 2*x, QQ(2))

385 1/2*x**2*y + x

386

387 """

388 if not u:

389 return dup_exquo_ground(f, c, K)

390

391 v = u - 1

392

393 return [ dmp_exquo_ground(cf, c, v, K) for cf in f ]

394

395

396def dup_lshift(f, n, K):

397 """

398 Efficiently multiply ``f`` by ``x**n`` in ``K[x]``.

399

400 Examples

401 ========

402

403 >>> from sympy.polys import ring, ZZ

404 >>> R, x = ring("x", ZZ)

405

406 >>> R.dup_lshift(x**2 + 1, 2)

407 x**4 + x**2

408

409 """

410 if not f:

411 return f

412 else:

413 return f + [K.zero]*n

414

415

416def dup_rshift(f, n, K):

417 """

418 Efficiently divide ``f`` by ``x**n`` in ``K[x]``.

419

420 Examples

421 ========

422

423 >>> from sympy.polys import ring, ZZ

424 >>> R, x = ring("x", ZZ)

425

426 >>> R.dup_rshift(x**4 + x**2, 2)

427 x**2 + 1

428 >>> R.dup_rshift(x**4 + x**2 + 2, 2)

429 x**2 + 1

430

431 """

432 return f[:-n]

433

434

435def dup_abs(f, K):

436 """

437 Make all coefficients positive in ``K[x]``.

438

439 Examples

440 ========

441

442 >>> from sympy.polys import ring, ZZ

443 >>> R, x = ring("x", ZZ)

444

445 >>> R.dup_abs(x**2 - 1)

446 x**2 + 1

447

448 """

449 return [ K.abs(coeff) for coeff in f ]

450

451

452def dmp_abs(f, u, K):

453 """

454 Make all coefficients positive in ``K[X]``.

455

456 Examples

457 ========

458

459 >>> from sympy.polys import ring, ZZ

460 >>> R, x,y = ring("x,y", ZZ)

461

462 >>> R.dmp_abs(x**2*y - x)

463 x**2*y + x

464

465 """

466 if not u:

467 return dup_abs(f, K)

468

469 v = u - 1

470

471 return [ dmp_abs(cf, v, K) for cf in f ]

472

473

474def dup_neg(f, K):

475 """

476 Negate a polynomial in ``K[x]``.

477

478 Examples

479 ========

480

481 >>> from sympy.polys import ring, ZZ

482 >>> R, x = ring("x", ZZ)

483

484 >>> R.dup_neg(x**2 - 1)

485 -x**2 + 1

486

487 """

488 return [ -coeff for coeff in f ]

489

490

491def dmp_neg(f, u, K):

492 """

493 Negate a polynomial in ``K[X]``.

494

495 Examples

496 ========

497

498 >>> from sympy.polys import ring, ZZ

499 >>> R, x,y = ring("x,y", ZZ)

500

501 >>> R.dmp_neg(x**2*y - x)

502 -x**2*y + x

503

504 """

505 if not u:

506 return dup_neg(f, K)

507

508 v = u - 1

509

510 return [ dmp_neg(cf, v, K) for cf in f ]

511

512

513def dup_add(f, g, K):

514 """

515 Add dense polynomials in ``K[x]``.

516

517 Examples

518 ========

519

520 >>> from sympy.polys import ring, ZZ

521 >>> R, x = ring("x", ZZ)

522

523 >>> R.dup_add(x**2 - 1, x - 2)

524 x**2 + x - 3

525

526 """

527 if not f:

528 return g

529 if not g:

530 return f

531

532 df = dup_degree(f)

533 dg = dup_degree(g)

534

535 if df == dg:

536 return dup_strip([ a + b for a, b in zip(f, g) ])

537 else:

538 k = abs(df - dg)

539

540 if df > dg:

541 h, f = f[:k], f[k:]

542 else:

543 h, g = g[:k], g[k:]

544

545 return h + [ a + b for a, b in zip(f, g) ]

546

547

548def dmp_add(f, g, u, K):

549 """

550 Add dense polynomials in ``K[X]``.

551

552 Examples

553 ========

554

555 >>> from sympy.polys import ring, ZZ

556 >>> R, x,y = ring("x,y", ZZ)

557

558 >>> R.dmp_add(x**2 + y, x**2*y + x)

559 x**2*y + x**2 + x + y

560

561 """

562 if not u:

563 return dup_add(f, g, K)

564

565 df = dmp_degree(f, u)

566

567 if df < 0:

568 return g

569

570 dg = dmp_degree(g, u)

571

572 if dg < 0:

573 return f

574

575 v = u - 1

576

577 if df == dg:

578 return dmp_strip([ dmp_add(a, b, v, K) for a, b in zip(f, g) ], u)

579 else:

580 k = abs(df - dg)

581

582 if df > dg:

583 h, f = f[:k], f[k:]

584 else:

585 h, g = g[:k], g[k:]

586

587 return h + [ dmp_add(a, b, v, K) for a, b in zip(f, g) ]

588

589

590def dup_sub(f, g, K):

591 """

592 Subtract dense polynomials in ``K[x]``.

593

594 Examples

595 ========

596

597 >>> from sympy.polys import ring, ZZ

598 >>> R, x = ring("x", ZZ)

599

600 >>> R.dup_sub(x**2 - 1, x - 2)

601 x**2 - x + 1

602

603 """

604 if not f:

605 return dup_neg(g, K)

606 if not g:

607 return f

608

609 df = dup_degree(f)

610 dg = dup_degree(g)

611

612 if df == dg:

613 return dup_strip([ a - b for a, b in zip(f, g) ])

614 else:

615 k = abs(df - dg)

616

617 if df > dg:

618 h, f = f[:k], f[k:]

619 else:

620 h, g = dup_neg(g[:k], K), g[k:]

621

622 return h + [ a - b for a, b in zip(f, g) ]

623

624

625def dmp_sub(f, g, u, K):

626 """

627 Subtract dense polynomials in ``K[X]``.

628

629 Examples

630 ========

631

632 >>> from sympy.polys import ring, ZZ

633 >>> R, x,y = ring("x,y", ZZ)

634

635 >>> R.dmp_sub(x**2 + y, x**2*y + x)

636 -x**2*y + x**2 - x + y

637

638 """

639 if not u:

640 return dup_sub(f, g, K)

641

642 df = dmp_degree(f, u)

643

644 if df < 0:

645 return dmp_neg(g, u, K)

646

647 dg = dmp_degree(g, u)

648

649 if dg < 0:

650 return f

651

652 v = u - 1

653

654 if df == dg:

655 return dmp_strip([ dmp_sub(a, b, v, K) for a, b in zip(f, g) ], u)

656 else:

657 k = abs(df - dg)

658

659 if df > dg:

660 h, f = f[:k], f[k:]

661 else:

662 h, g = dmp_neg(g[:k], u, K), g[k:]

663

664 return h + [ dmp_sub(a, b, v, K) for a, b in zip(f, g) ]

665

666

667def dup_add_mul(f, g, h, K):

668 """

669 Returns ``f + g*h`` where ``f, g, h`` are in ``K[x]``.

670

671 Examples

672 ========

673

674 >>> from sympy.polys import ring, ZZ

675 >>> R, x = ring("x", ZZ)

676

677 >>> R.dup_add_mul(x**2 - 1, x - 2, x + 2)

678 2*x**2 - 5

679

680 """

681 return dup_add(f, dup_mul(g, h, K), K)

682

683

684def dmp_add_mul(f, g, h, u, K):

685 """

686 Returns ``f + g*h`` where ``f, g, h`` are in ``K[X]``.

687

688 Examples

689 ========

690

691 >>> from sympy.polys import ring, ZZ

692 >>> R, x,y = ring("x,y", ZZ)

693

694 >>> R.dmp_add_mul(x**2 + y, x, x + 2)

695 2*x**2 + 2*x + y

696

697 """

698 return dmp_add(f, dmp_mul(g, h, u, K), u, K)

699

700

701def dup_sub_mul(f, g, h, K):

702 """

703 Returns ``f - g*h`` where ``f, g, h`` are in ``K[x]``.

704

705 Examples

706 ========

707

708 >>> from sympy.polys import ring, ZZ

709 >>> R, x = ring("x", ZZ)

710

711 >>> R.dup_sub_mul(x**2 - 1, x - 2, x + 2)

712 3

713

714 """

715 return dup_sub(f, dup_mul(g, h, K), K)

716

717

718def dmp_sub_mul(f, g, h, u, K):

719 """

720 Returns ``f - g*h`` where ``f, g, h`` are in ``K[X]``.

721

722 Examples

723 ========

724

725 >>> from sympy.polys import ring, ZZ

726 >>> R, x,y = ring("x,y", ZZ)

727

728 >>> R.dmp_sub_mul(x**2 + y, x, x + 2)

729 -2*x + y

730

731 """

732 return dmp_sub(f, dmp_mul(g, h, u, K), u, K)

733

734

735def dup_mul(f, g, K):

736 """

737 Multiply dense polynomials in ``K[x]``.

738

739 Examples

740 ========

741

742 >>> from sympy.polys import ring, ZZ

743 >>> R, x = ring("x", ZZ)

744

745 >>> R.dup_mul(x - 2, x + 2)

746 x**2 - 4

747

748 """

749 if f == g:

750 return dup_sqr(f, K)

751

752 if not (f and g):

753 return []

754

755 df = dup_degree(f)

756 dg = dup_degree(g)

757

758 n = max(df, dg) + 1

759

760 if n < 100:

761 h = []

762

763 for i in range(0, df + dg + 1):

764 coeff = K.zero

765

766 for j in range(max(0, i - dg), min(df, i) + 1):

767 coeff += f[j]*g[i - j]

768

769 h.append(coeff)

770

771 return dup_strip(h)

772 else:

773 # Use Karatsuba's algorithm (divide and conquer), see e.g.:

774 # Joris van der Hoeven, Relax But Don't Be Too Lazy,

775 # J. Symbolic Computation, 11 (2002), section 3.1.1.

776 n2 = n//2

777

778 fl, gl = dup_slice(f, 0, n2, K), dup_slice(g, 0, n2, K)

779

780 fh = dup_rshift(dup_slice(f, n2, n, K), n2, K)

781 gh = dup_rshift(dup_slice(g, n2, n, K), n2, K)

782

783 lo, hi = dup_mul(fl, gl, K), dup_mul(fh, gh, K)

784

785 mid = dup_mul(dup_add(fl, fh, K), dup_add(gl, gh, K), K)

786 mid = dup_sub(mid, dup_add(lo, hi, K), K)

787

788 return dup_add(dup_add(lo, dup_lshift(mid, n2, K), K),

789 dup_lshift(hi, 2*n2, K), K)

790

791

792def dmp_mul(f, g, u, K):

793 """

794 Multiply dense polynomials in ``K[X]``.

795

796 Examples

797 ========

798

799 >>> from sympy.polys import ring, ZZ

800 >>> R, x,y = ring("x,y", ZZ)

801

802 >>> R.dmp_mul(x*y + 1, x)

803 x**2*y + x

804

805 """

806 if not u:

807 return dup_mul(f, g, K)

808

809 if f == g:

810 return dmp_sqr(f, u, K)

811

812 df = dmp_degree(f, u)

813

814 if df < 0:

815 return f

816

817 dg = dmp_degree(g, u)

818

819 if dg < 0:

820 return g

821

822 h, v = [], u - 1

823

824 for i in range(0, df + dg + 1):

825 coeff = dmp_zero(v)

826

827 for j in range(max(0, i - dg), min(df, i) + 1):

828 coeff = dmp_add(coeff, dmp_mul(f[j], g[i - j], v, K), v, K)

829

830 h.append(coeff)

831

832 return dmp_strip(h, u)

833

834

835def dup_sqr(f, K):

836 """

837 Square dense polynomials in ``K[x]``.

838

839 Examples

840 ========

841

842 >>> from sympy.polys import ring, ZZ

843 >>> R, x = ring("x", ZZ)

844

845 >>> R.dup_sqr(x**2 + 1)

846 x**4 + 2*x**2 + 1

847

848 """

849 df, h = len(f) - 1, []

850

851 for i in range(0, 2*df + 1):

852 c = K.zero

853

854 jmin = max(0, i - df)

855 jmax = min(i, df)

856

857 n = jmax - jmin + 1

858

859 jmax = jmin + n // 2 - 1

860

861 for j in range(jmin, jmax + 1):

862 c += f[j]*f[i - j]

863

864 c += c

865

866 if n & 1:

867 elem = f[jmax + 1]

868 c += elem**2

869

870 h.append(c)

871

872 return dup_strip(h)

873

874

875def dmp_sqr(f, u, K):

876 """

877 Square dense polynomials in ``K[X]``.

878

879 Examples

880 ========

881

882 >>> from sympy.polys import ring, ZZ

883 >>> R, x,y = ring("x,y", ZZ)

884

885 >>> R.dmp_sqr(x**2 + x*y + y**2)

886 x**4 + 2*x**3*y + 3*x**2*y**2 + 2*x*y**3 + y**4

887

888 """

889 if not u:

890 return dup_sqr(f, K)

891

892 df = dmp_degree(f, u)

893

894 if df < 0:

895 return f

896

897 h, v = [], u - 1

898

899 for i in range(0, 2*df + 1):

900 c = dmp_zero(v)

901

902 jmin = max(0, i - df)

903 jmax = min(i, df)

904

905 n = jmax - jmin + 1

906

907 jmax = jmin + n // 2 - 1

908

909 for j in range(jmin, jmax + 1):

910 c = dmp_add(c, dmp_mul(f[j], f[i - j], v, K), v, K)

911

912 c = dmp_mul_ground(c, K(2), v, K)

913

914 if n & 1:

915 elem = dmp_sqr(f[jmax + 1], v, K)

916 c = dmp_add(c, elem, v, K)

917

918 h.append(c)

919

920 return dmp_strip(h, u)

921

922

923def dup_pow(f, n, K):

924 """

925 Raise ``f`` to the ``n``-th power in ``K[x]``.

926

927 Examples

928 ========

929

930 >>> from sympy.polys import ring, ZZ

931 >>> R, x = ring("x", ZZ)

932

933 >>> R.dup_pow(x - 2, 3)

934 x**3 - 6*x**2 + 12*x - 8

935

936 """

937 if not n:

938 return [K.one]

939 if n < 0:

940 raise ValueError("Cannot raise polynomial to a negative power")

941 if n == 1 or not f or f == [K.one]:

942 return f

943

944 g = [K.one]

945

946 while True:

947 n, m = n//2, n

948

949 if m % 2:

950 g = dup_mul(g, f, K)

951

952 if not n:

953 break

954

955 f = dup_sqr(f, K)

956

957 return g

958

959

960def dmp_pow(f, n, u, K):

961 """

962 Raise ``f`` to the ``n``-th power in ``K[X]``.

963

964 Examples

965 ========

966

967 >>> from sympy.polys import ring, ZZ

968 >>> R, x,y = ring("x,y", ZZ)

969

970 >>> R.dmp_pow(x*y + 1, 3)

971 x**3*y**3 + 3*x**2*y**2 + 3*x*y + 1

972

973 """

974 if not u:

975 return dup_pow(f, n, K)

976

977 if not n:

978 return dmp_one(u, K)

979 if n < 0:

980 raise ValueError("Cannot raise polynomial to a negative power")

981 if n == 1 or dmp_zero_p(f, u) or dmp_one_p(f, u, K):

982 return f

983

984 g = dmp_one(u, K)

985

986 while True:

987 n, m = n//2, n

988

989 if m & 1:

990 g = dmp_mul(g, f, u, K)

991

992 if not n:

993 break

994

995 f = dmp_sqr(f, u, K)

996

997 return g

998

999

1000def dup_pdiv(f, g, K):

1001 """

1002 Polynomial pseudo-division in ``K[x]``.

1003

1004 Examples

1005 ========

1006

1007 >>> from sympy.polys import ring, ZZ

1008 >>> R, x = ring("x", ZZ)

1009

1010 >>> R.dup_pdiv(x**2 + 1, 2*x - 4)

1011 (2*x + 4, 20)

1012

1013 """

1014 df = dup_degree(f)

1015 dg = dup_degree(g)

1016

1017 q, r, dr = [], f, df

1018

1019 if not g:

1020 raise ZeroDivisionError("polynomial division")

1021 elif df < dg:

1022 return q, r

1023

1024 N = df - dg + 1

1025 lc_g = dup_LC(g, K)

1026

1027 while True:

1028 lc_r = dup_LC(r, K)

1029 j, N = dr - dg, N - 1

1030

1031 Q = dup_mul_ground(q, lc_g, K)

1032 q = dup_add_term(Q, lc_r, j, K)

1033

1034 R = dup_mul_ground(r, lc_g, K)

1035 G = dup_mul_term(g, lc_r, j, K)

1036 r = dup_sub(R, G, K)

1037

1038 _dr, dr = dr, dup_degree(r)

1039

1040 if dr < dg:

1041 break

1042 elif not (dr < _dr):

1043 raise PolynomialDivisionFailed(f, g, K)

1044

1045 c = lc_g**N

1046

1047 q = dup_mul_ground(q, c, K)

1048 r = dup_mul_ground(r, c, K)

1049

1050 return q, r

1051

1052

1053def dup_prem(f, g, K):

1054 """

1055 Polynomial pseudo-remainder in ``K[x]``.

1056

1057 Examples

1058 ========

1059

1060 >>> from sympy.polys import ring, ZZ

1061 >>> R, x = ring("x", ZZ)

1062

1063 >>> R.dup_prem(x**2 + 1, 2*x - 4)

1064 20

1065

1066 """

1067 df = dup_degree(f)

1068 dg = dup_degree(g)

1069

1070 r, dr = f, df

1071

1072 if not g:

1073 raise ZeroDivisionError("polynomial division")

1074 elif df < dg:

1075 return r

1076

1077 N = df - dg + 1

1078 lc_g = dup_LC(g, K)

1079

1080 while True:

1081 lc_r = dup_LC(r, K)

1082 j, N = dr - dg, N - 1

1083

1084 R = dup_mul_ground(r, lc_g, K)

1085 G = dup_mul_term(g, lc_r, j, K)

1086 r = dup_sub(R, G, K)

1087

1088 _dr, dr = dr, dup_degree(r)

1089

1090 if dr < dg:

1091 break

1092 elif not (dr < _dr):

1093 raise PolynomialDivisionFailed(f, g, K)

1094

1095 return dup_mul_ground(r, lc_g**N, K)

1096

1097

1098def dup_pquo(f, g, K):

1099 """

1100 Polynomial exact pseudo-quotient in ``K[X]``.

1101

1102 Examples

1103 ========

1104

1105 >>> from sympy.polys import ring, ZZ

1106 >>> R, x = ring("x", ZZ)

1107

1108 >>> R.dup_pquo(x**2 - 1, 2*x - 2)

1109 2*x + 2

1110

1111 >>> R.dup_pquo(x**2 + 1, 2*x - 4)

1112 2*x + 4

1113

1114 """

1115 return dup_pdiv(f, g, K)[0]

1116

1117

1118def dup_pexquo(f, g, K):

1119 """

1120 Polynomial pseudo-quotient in ``K[x]``.

1121

1122 Examples

1123 ========

1124

1125 >>> from sympy.polys import ring, ZZ

1126 >>> R, x = ring("x", ZZ)

1127

1128 >>> R.dup_pexquo(x**2 - 1, 2*x - 2)

1129 2*x + 2

1130

1131 >>> R.dup_pexquo(x**2 + 1, 2*x - 4)

1132 Traceback (most recent call last):

1133 ...

1134 ExactQuotientFailed: [2, -4] does not divide [1, 0, 1]

1135

1136 """

1137 q, r = dup_pdiv(f, g, K)

1138

1139 if not r:

1140 return q

1141 else:

1142 raise ExactQuotientFailed(f, g)

1143

1144

1145def dmp_pdiv(f, g, u, K):

1146 """

1147 Polynomial pseudo-division in ``K[X]``.

1148

1149 Examples

1150 ========

1151

1152 >>> from sympy.polys import ring, ZZ

1153 >>> R, x,y = ring("x,y", ZZ)

1154

1155 >>> R.dmp_pdiv(x**2 + x*y, 2*x + 2)

1156 (2*x + 2*y - 2, -4*y + 4)

1157

1158 """

1159 if not u:

1160 return dup_pdiv(f, g, K)

1161

1162 df = dmp_degree(f, u)

1163 dg = dmp_degree(g, u)

1164

1165 if dg < 0:

1166 raise ZeroDivisionError("polynomial division")

1167

1168 q, r, dr = dmp_zero(u), f, df

1169

1170 if df < dg:

1171 return q, r

1172

1173 N = df - dg + 1

1174 lc_g = dmp_LC(g, K)

1175

1176 while True:

1177 lc_r = dmp_LC(r, K)

1178 j, N = dr - dg, N - 1

1179

1180 Q = dmp_mul_term(q, lc_g, 0, u, K)

1181 q = dmp_add_term(Q, lc_r, j, u, K)

1182

1183 R = dmp_mul_term(r, lc_g, 0, u, K)

1184 G = dmp_mul_term(g, lc_r, j, u, K)

1185 r = dmp_sub(R, G, u, K)

1186

1187 _dr, dr = dr, dmp_degree(r, u)

1188

1189 if dr < dg:

1190 break

1191 elif not (dr < _dr):

1192 raise PolynomialDivisionFailed(f, g, K)

1193

1194 c = dmp_pow(lc_g, N, u - 1, K)

1195

1196 q = dmp_mul_term(q, c, 0, u, K)

1197 r = dmp_mul_term(r, c, 0, u, K)

1198

1199 return q, r

1200

1201

1202def dmp_prem(f, g, u, K):

1203 """

1204 Polynomial pseudo-remainder in ``K[X]``.

1205

1206 Examples

1207 ========

1208

1209 >>> from sympy.polys import ring, ZZ

1210 >>> R, x,y = ring("x,y", ZZ)

1211

1212 >>> R.dmp_prem(x**2 + x*y, 2*x + 2)

1213 -4*y + 4

1214

1215 """

1216 if not u:

1217 return dup_prem(f, g, K)

1218

1219 df = dmp_degree(f, u)

1220 dg = dmp_degree(g, u)

1221

1222 if dg < 0:

1223 raise ZeroDivisionError("polynomial division")

1224

1225 r, dr = f, df

1226

1227 if df < dg:

1228 return r

1229

1230 N = df - dg + 1

1231 lc_g = dmp_LC(g, K)

1232

1233 while True:

1234 lc_r = dmp_LC(r, K)

1235 j, N = dr - dg, N - 1

1236

1237 R = dmp_mul_term(r, lc_g, 0, u, K)

1238 G = dmp_mul_term(g, lc_r, j, u, K)

1239 r = dmp_sub(R, G, u, K)

1240

1241 _dr, dr = dr, dmp_degree(r, u)

1242

1243 if dr < dg:

1244 break

1245 elif not (dr < _dr):

1246 raise PolynomialDivisionFailed(f, g, K)

1247

1248 c = dmp_pow(lc_g, N, u - 1, K)

1249

1250 return dmp_mul_term(r, c, 0, u, K)

1251

1252

1253def dmp_pquo(f, g, u, K):

1254 """

1255 Polynomial exact pseudo-quotient in ``K[X]``.

1256

1257 Examples

1258 ========

1259

1260 >>> from sympy.polys import ring, ZZ

1261 >>> R, x,y = ring("x,y", ZZ)

1262

1263 >>> f = x**2 + x*y

1264 >>> g = 2*x + 2*y

1265 >>> h = 2*x + 2

1266

1267 >>> R.dmp_pquo(f, g)

1268 2*x

1269

1270 >>> R.dmp_pquo(f, h)

1271 2*x + 2*y - 2

1272

1273 """

1274 return dmp_pdiv(f, g, u, K)[0]

1275

1276

1277def dmp_pexquo(f, g, u, K):

1278 """

1279 Polynomial pseudo-quotient in ``K[X]``.

1280

1281 Examples

1282 ========

1283

1284 >>> from sympy.polys import ring, ZZ

1285 >>> R, x,y = ring("x,y", ZZ)

1286

1287 >>> f = x**2 + x*y

1288 >>> g = 2*x + 2*y

1289 >>> h = 2*x + 2

1290

1291 >>> R.dmp_pexquo(f, g)

1292 2*x

1293

1294 >>> R.dmp_pexquo(f, h)

1295 Traceback (most recent call last):

1296 ...

1297 ExactQuotientFailed: [[2], [2]] does not divide [[1], [1, 0], []]

1298

1299 """

1300 q, r = dmp_pdiv(f, g, u, K)

1301

1302 if dmp_zero_p(r, u):

1303 return q

1304 else:

1305 raise ExactQuotientFailed(f, g)

1306

1307

1308def dup_rr_div(f, g, K):

1309 """

1310 Univariate division with remainder over a ring.

1311

1312 Examples

1313 ========

1314

1315 >>> from sympy.polys import ring, ZZ

1316 >>> R, x = ring("x", ZZ)

1317

1318 >>> R.dup_rr_div(x**2 + 1, 2*x - 4)

1319 (0, x**2 + 1)

1320

1321 """

1322 df = dup_degree(f)

1323 dg = dup_degree(g)

1324

1325 q, r, dr = [], f, df

1326

1327 if not g:

1328 raise ZeroDivisionError("polynomial division")

1329 elif df < dg:

1330 return q, r

1331

1332 lc_g = dup_LC(g, K)

1333

1334 while True:

1335 lc_r = dup_LC(r, K)

1336

1337 if lc_r % lc_g:

1338 break

1339

1340 c = K.exquo(lc_r, lc_g)

1341 j = dr - dg

1342

1343 q = dup_add_term(q, c, j, K)

1344 h = dup_mul_term(g, c, j, K)

1345 r = dup_sub(r, h, K)

1346

1347 _dr, dr = dr, dup_degree(r)

1348

1349 if dr < dg:

1350 break

1351 elif not (dr < _dr):

1352 raise PolynomialDivisionFailed(f, g, K)

1353

1354 return q, r

1355

1356

1357def dmp_rr_div(f, g, u, K):

1358 """

1359 Multivariate division with remainder over a ring.

1360

1361 Examples

1362 ========

1363

1364 >>> from sympy.polys import ring, ZZ

1365 >>> R, x,y = ring("x,y", ZZ)

1366

1367 >>> R.dmp_rr_div(x**2 + x*y, 2*x + 2)

1368 (0, x**2 + x*y)

1369

1370 """

1371 if not u:

1372 return dup_rr_div(f, g, K)

1373

1374 df = dmp_degree(f, u)

1375 dg = dmp_degree(g, u)

1376

1377 if dg < 0:

1378 raise ZeroDivisionError("polynomial division")

1379

1380 q, r, dr = dmp_zero(u), f, df

1381

1382 if df < dg:

1383 return q, r

1384

1385 lc_g, v = dmp_LC(g, K), u - 1

1386

1387 while True:

1388 lc_r = dmp_LC(r, K)

1389 c, R = dmp_rr_div(lc_r, lc_g, v, K)

1390

1391 if not dmp_zero_p(R, v):

1392 break

1393

1394 j = dr - dg

1395

1396 q = dmp_add_term(q, c, j, u, K)

1397 h = dmp_mul_term(g, c, j, u, K)

1398 r = dmp_sub(r, h, u, K)

1399

1400 _dr, dr = dr, dmp_degree(r, u)

1401

1402 if dr < dg:

1403 break

1404 elif not (dr < _dr):

1405 raise PolynomialDivisionFailed(f, g, K)

1406

1407 return q, r

1408

1409

1410def dup_ff_div(f, g, K):

1411 """

1412 Polynomial division with remainder over a field.

1413

1414 Examples

1415 ========

1416

1417 >>> from sympy.polys import ring, QQ

1418 >>> R, x = ring("x", QQ)

1419

1420 >>> R.dup_ff_div(x**2 + 1, 2*x - 4)

1421 (1/2*x + 1, 5)

1422

1423 """

1424 df = dup_degree(f)

1425 dg = dup_degree(g)

1426

1427 q, r, dr = [], f, df

1428

1429 if not g:

1430 raise ZeroDivisionError("polynomial division")

1431 elif df < dg:

1432 return q, r

1433

1434 lc_g = dup_LC(g, K)

1435

1436 while True:

1437 lc_r = dup_LC(r, K)

1438

1439 c = K.exquo(lc_r, lc_g)

1440 j = dr - dg

1441

1442 q = dup_add_term(q, c, j, K)

1443 h = dup_mul_term(g, c, j, K)

1444 r = dup_sub(r, h, K)

1445

1446 _dr, dr = dr, dup_degree(r)

1447

1448 if dr < dg:

1449 break

1450 elif dr == _dr and not K.is_Exact:

1451 # remove leading term created by rounding error

1452 r = dup_strip(r[1:])

1453 dr = dup_degree(r)

1454 if dr < dg:

1455 break

1456 elif not (dr < _dr):

1457 raise PolynomialDivisionFailed(f, g, K)

1458

1459 return q, r

1460

1461

1462def dmp_ff_div(f, g, u, K):

1463 """

1464 Polynomial division with remainder over a field.

1465

1466 Examples

1467 ========

1468

1469 >>> from sympy.polys import ring, QQ

1470 >>> R, x,y = ring("x,y", QQ)

1471

1472 >>> R.dmp_ff_div(x**2 + x*y, 2*x + 2)

1473 (1/2*x + 1/2*y - 1/2, -y + 1)

1474

1475 """

1476 if not u:

1477 return dup_ff_div(f, g, K)

1478

1479 df = dmp_degree(f, u)

1480 dg = dmp_degree(g, u)

1481

1482 if dg < 0:

1483 raise ZeroDivisionError("polynomial division")

1484

1485 q, r, dr = dmp_zero(u), f, df

1486

1487 if df < dg:

1488 return q, r

1489

1490 lc_g, v = dmp_LC(g, K), u - 1

1491

1492 while True:

1493 lc_r = dmp_LC(r, K)

1494 c, R = dmp_ff_div(lc_r, lc_g, v, K)

1495

1496 if not dmp_zero_p(R, v):

1497 break

1498

1499 j = dr - dg

1500

1501 q = dmp_add_term(q, c, j, u, K)

1502 h = dmp_mul_term(g, c, j, u, K)

1503 r = dmp_sub(r, h, u, K)

1504

1505 _dr, dr = dr, dmp_degree(r, u)

1506

1507 if dr < dg:

1508 break

1509 elif not (dr < _dr):

1510 raise PolynomialDivisionFailed(f, g, K)

1511

1512 return q, r

1513

1514

1515def dup_div(f, g, K):

1516 """

1517 Polynomial division with remainder in ``K[x]``.

1518

1519 Examples

1520 ========

1521

1522 >>> from sympy.polys import ring, ZZ, QQ

1523

1524 >>> R, x = ring("x", ZZ)

1525 >>> R.dup_div(x**2 + 1, 2*x - 4)

1526 (0, x**2 + 1)

1527

1528 >>> R, x = ring("x", QQ)

1529 >>> R.dup_div(x**2 + 1, 2*x - 4)

1530 (1/2*x + 1, 5)

1531

1532 """

1533 if K.is_Field:

1534 return dup_ff_div(f, g, K)

1535 else:

1536 return dup_rr_div(f, g, K)

1537

1538

1539def dup_rem(f, g, K):

1540 """

1541 Returns polynomial remainder in ``K[x]``.

1542

1543 Examples

1544 ========

1545

1546 >>> from sympy.polys import ring, ZZ, QQ

1547

1548 >>> R, x = ring("x", ZZ)

1549 >>> R.dup_rem(x**2 + 1, 2*x - 4)

1550 x**2 + 1

1551

1552 >>> R, x = ring("x", QQ)

1553 >>> R.dup_rem(x**2 + 1, 2*x - 4)

1554 5

1555

1556 """

1557 return dup_div(f, g, K)[1]

1558

1559

1560def dup_quo(f, g, K):

1561 """

1562 Returns exact polynomial quotient in ``K[x]``.

1563

1564 Examples

1565 ========

1566

1567 >>> from sympy.polys import ring, ZZ, QQ

1568

1569 >>> R, x = ring("x", ZZ)

1570 >>> R.dup_quo(x**2 + 1, 2*x - 4)

1571 0

1572

1573 >>> R, x = ring("x", QQ)

1574 >>> R.dup_quo(x**2 + 1, 2*x - 4)

1575 1/2*x + 1

1576

1577 """

1578 return dup_div(f, g, K)[0]

1579

1580

1581def dup_exquo(f, g, K):

1582 """

1583 Returns polynomial quotient in ``K[x]``.

1584

1585 Examples

1586 ========

1587

1588 >>> from sympy.polys import ring, ZZ

1589 >>> R, x = ring("x", ZZ)

1590

1591 >>> R.dup_exquo(x**2 - 1, x - 1)

1592 x + 1

1593

1594 >>> R.dup_exquo(x**2 + 1, 2*x - 4)

1595 Traceback (most recent call last):

1596 ...

1597 ExactQuotientFailed: [2, -4] does not divide [1, 0, 1]

1598

1599 """

1600 q, r = dup_div(f, g, K)

1601

1602 if not r:

1603 return q

1604 else:

1605 raise ExactQuotientFailed(f, g)

1606

1607

1608def dmp_div(f, g, u, K):

1609 """

1610 Polynomial division with remainder in ``K[X]``.

1611

1612 Examples

1613 ========

1614

1615 >>> from sympy.polys import ring, ZZ, QQ

1616

1617 >>> R, x,y = ring("x,y", ZZ)

1618 >>> R.dmp_div(x**2 + x*y, 2*x + 2)

1619 (0, x**2 + x*y)

1620

1621 >>> R, x,y = ring("x,y", QQ)

1622 >>> R.dmp_div(x**2 + x*y, 2*x + 2)

1623 (1/2*x + 1/2*y - 1/2, -y + 1)

1624

1625 """

1626 if K.is_Field:

1627 return dmp_ff_div(f, g, u, K)

1628 else:

1629 return dmp_rr_div(f, g, u, K)

1630

1631

1632def dmp_rem(f, g, u, K):

1633 """

1634 Returns polynomial remainder in ``K[X]``.

1635

1636 Examples

1637 ========

1638

1639 >>> from sympy.polys import ring, ZZ, QQ

1640

1641 >>> R, x,y = ring("x,y", ZZ)

1642 >>> R.dmp_rem(x**2 + x*y, 2*x + 2)

1643 x**2 + x*y

1644

1645 >>> R, x,y = ring("x,y", QQ)

1646 >>> R.dmp_rem(x**2 + x*y, 2*x + 2)

1647 -y + 1

1648

1649 """

1650 return dmp_div(f, g, u, K)[1]

1651

1652

1653def dmp_quo(f, g, u, K):

1654 """

1655 Returns exact polynomial quotient in ``K[X]``.

1656

1657 Examples

1658 ========

1659

1660 >>> from sympy.polys import ring, ZZ, QQ

1661

1662 >>> R, x,y = ring("x,y", ZZ)

1663 >>> R.dmp_quo(x**2 + x*y, 2*x + 2)

1664 0

1665

1666 >>> R, x,y = ring("x,y", QQ)

1667 >>> R.dmp_quo(x**2 + x*y, 2*x + 2)

1668 1/2*x + 1/2*y - 1/2

1669

1670 """

1671 return dmp_div(f, g, u, K)[0]

1672

1673

1674def dmp_exquo(f, g, u, K):

1675 """

1676 Returns polynomial quotient in ``K[X]``.

1677

1678 Examples

1679 ========

1680

1681 >>> from sympy.polys import ring, ZZ

1682 >>> R, x,y = ring("x,y", ZZ)

1683

1684 >>> f = x**2 + x*y

1685 >>> g = x + y

1686 >>> h = 2*x + 2

1687

1688 >>> R.dmp_exquo(f, g)

1689 x

1690

1691 >>> R.dmp_exquo(f, h)

1692 Traceback (most recent call last):

1693 ...

1694 ExactQuotientFailed: [[2], [2]] does not divide [[1], [1, 0], []]

1695

1696 """

1697 q, r = dmp_div(f, g, u, K)

1698

1699 if dmp_zero_p(r, u):

1700 return q

1701 else:

1702 raise ExactQuotientFailed(f, g)

1703

1704

1705def dup_max_norm(f, K):

1706 """

1707 Returns maximum norm of a polynomial in ``K[x]``.

1708

1709 Examples

1710 ========

1711

1712 >>> from sympy.polys import ring, ZZ

1713 >>> R, x = ring("x", ZZ)

1714

1715 >>> R.dup_max_norm(-x**2 + 2*x - 3)

1716 3

1717

1718 """

1719 if not f:

1720 return K.zero

1721 else:

1722 return max(dup_abs(f, K))

1723

1724

1725def dmp_max_norm(f, u, K):

1726 """

1727 Returns maximum norm of a polynomial in ``K[X]``.

1728

1729 Examples

1730 ========

1731

1732 >>> from sympy.polys import ring, ZZ

1733 >>> R, x,y = ring("x,y", ZZ)

1734

1735 >>> R.dmp_max_norm(2*x*y - x - 3)

1736 3

1737

1738 """

1739 if not u:

1740 return dup_max_norm(f, K)

1741

1742 v = u - 1

1743

1744 return max([ dmp_max_norm(c, v, K) for c in f ])

1745

1746

1747def dup_l1_norm(f, K):

1748 """

1749 Returns l1 norm of a polynomial in ``K[x]``.

1750

1751 Examples

1752 ========

1753

1754 >>> from sympy.polys import ring, ZZ

1755 >>> R, x = ring("x", ZZ)

1756

1757 >>> R.dup_l1_norm(2*x**3 - 3*x**2 + 1)

1758 6

1759

1760 """

1761 if not f:

1762 return K.zero

1763 else:

1764 return sum(dup_abs(f, K))

1765

1766

1767def dmp_l1_norm(f, u, K):

1768 """

1769 Returns l1 norm of a polynomial in ``K[X]``.

1770

1771 Examples

1772 ========

1773

1774 >>> from sympy.polys import ring, ZZ

1775 >>> R, x,y = ring("x,y", ZZ)

1776

1777 >>> R.dmp_l1_norm(2*x*y - x - 3)

1778 6

1779

1780 """

1781 if not u:

1782 return dup_l1_norm(f, K)

1783

1784 v = u - 1

1785

1786 return sum([ dmp_l1_norm(c, v, K) for c in f ])

1787

1788

1789def dup_l2_norm_squared(f, K):

1790 """

1791 Returns squared l2 norm of a polynomial in ``K[x]``.

1792

1793 Examples

1794 ========

1795

1796 >>> from sympy.polys import ring, ZZ

1797 >>> R, x = ring("x", ZZ)

1798

1799 >>> R.dup_l2_norm_squared(2*x**3 - 3*x**2 + 1)

1800 14

1801

1802 """

1803 return sum([coeff**2 for coeff in f], K.zero)

1804

1805

1806def dmp_l2_norm_squared(f, u, K):

1807 """

1808 Returns squared l2 norm of a polynomial in ``K[X]``.

1809

1810 Examples

1811 ========

1812

1813 >>> from sympy.polys import ring, ZZ

1814 >>> R, x,y = ring("x,y", ZZ)

1815

1816 >>> R.dmp_l2_norm_squared(2*x*y - x - 3)

1817 14

1818

1819 """

1820 if not u:

1821 return dup_l2_norm_squared(f, K)

1822

1823 v = u - 1

1824

1825 return sum([ dmp_l2_norm_squared(c, v, K) for c in f ])

1826

1827

1828def dup_expand(polys, K):

1829 """

1830 Multiply together several polynomials in ``K[x]``.

1831

1832 Examples

1833 ========

1834

1835 >>> from sympy.polys import ring, ZZ

1836 >>> R, x = ring("x", ZZ)

1837

1838 >>> R.dup_expand([x**2 - 1, x, 2])

1839 2*x**3 - 2*x

1840

1841 """

1842 if not polys:

1843 return [K.one]

1844

1845 f = polys[0]

1846

1847 for g in polys[1:]:

1848 f = dup_mul(f, g, K)

1849

1850 return f

1851

1852

1853def dmp_expand(polys, u, K):

1854 """

1855 Multiply together several polynomials in ``K[X]``.

1856

1857 Examples

1858 ========

1859

1860 >>> from sympy.polys import ring, ZZ

1861 >>> R, x,y = ring("x,y", ZZ)

1862

1863 >>> R.dmp_expand([x**2 + y**2, x + 1])

1864 x**3 + x**2 + x*y**2 + y**2

1865

1866 """

1867 if not polys:

1868 return dmp_one(u, K)

1869

1870 f = polys[0]

1871

1872 for g in polys[1:]:

1873 f = dmp_mul(f, g, u, K)

1874

1875 return f