skills.rest
Arcadi4
Arcadi4COMMUNITY
Explore all skills by this author →
Website𝕏@_4rcadiaGitHub

polynomials-and-fft

Multiply polynomials via FFT with padding and root-of-unity handling.

7|Updated Apr 24, 2026
Search Tags:#convolution#fft#polynomials#algorithm-design#clrs#root-of-unity
One-click install
npx skills add https://github.com/Arcadi4/nerdy --skill polynomials-and-fft
Or copy as Structured Prompt for Agent▼
Please help me install this Agent Skill.
Skill: polynomials-and-fft
Source: https://github.com/Arcadi4/nerdy/tree/main/clrs/polynomials-and-fft
Command: npx skills add https://github.com/Arcadi4/nerdy --skill polynomials-and-fft

SYSTEM DOCUMENTATION & REQUIREMENTS

What problem does it solve?

Polynomial multiplication is expensive in coefficient form; converting to a point-value representation via DFT/FFT enables fast convolution, provided padding, root-of-unity structure, and exactness considerations are properly managed.

Core Features & Use Cases

  • Efficient polynomial multiplication using the FFT pipeline: padding to an appropriate transform length, forward DFT, pointwise multiplication, inverse DFT, and result trimming.
  • Two representations: switch between coefficient form and a point-value form with evaluation points, ensuring consistent ordering of points.
  • Guidance on degree-bounds, root-of-unity requirements, and when exact vs floating-point accuracy is appropriate.
  • Use case examples: multiplying two degree-n polynomials, performing many-labeled convolutions, and reasoning about interpolation from roots of unity.

Quick Start

Multiply polynomials using FFT with proper padding and root-of-unity handling.

Frequently Asked Questions about polynomials-and-fft

High-intent search queries and answers about installing and using this skill.

FAQPage Schema
How does FFT polynomial multiplication work?▼

FFT polynomial multiplication converts coefficient-form polynomials into point-value representations via the discrete Fourier transform, performs pointwise multiplication, and applies the inverse DFT to retrieve the convolved coefficients efficiently.

How do I multiply two polynomials using the DFT pipeline?▼

To multiply two polynomials, pad both inputs to an appropriate transform length, apply the forward DFT, multiply the resulting point values, and apply the inverse DFT before trimming the result.

What is the difference between coefficient and point-value representation for convolution?▼

Coefficient representation stores polynomial values directly, while point-value representation evaluates polynomials at specific roots of unity to enable fast O(n log n) convolution through pointwise multiplication rather than quadratic multiplication.

When should I use floating-point approximation vs exact arithmetic in FFT convolution?▼

Use floating-point approximation for general fast multiplication where minor precision loss is acceptable, but verify root-of-unity exactness requirements when your algorithm design demands precise integer convolution.

Why do I need padding when multiplying degree-n polynomials with FFT?▼

Padding is required because multiplying two degree-n polynomials yields a degree-2n result, so you must extend the transform length to prevent circular convolution from corrupting the output coefficients.

Related Skills

Explore More Software Engineering Skills→
0bserver070bserver07
3

polynomial-proof

Determine polynomial irreducibility and factorizations over specified rings.

Community
Advanced
mailhexumailhexu
101

TB2J

TB2J computes magnetic interaction parameters from DFT outputs for Wannier90, Siesta, and Abacus workflows.

Community
Intermediate
attentiondotnetattentiondotnet

calculator

Evaluate arithmetic expressions with arbitrary-precision decimal math using big.js.

Community
Intermediate
vicharanashalavicharanashala
6

Polynomial Multiplication

Generate and validate polynomial multiplication problems with dynamic coefficient prompts.

Official
Intermediate