Divide and Conquer/Polynomial Multiplication - Revision history

Admin: /* Overview */

2017-08-15T23:19:50Z

Overview

← Older revision		Revision as of 23:19, 15 August 2017
Line 51:		Line 51:

	\|}		\|}

			==The Goal==

			Given that the roots representation contains an infinite cell, we'll ignore it in the search for practical solutions to our problem.

			Our goal is to implement a linear time algorithm for each operation. The table above shows we are almost there, but the last multiplication row causes some issues.

			Specifically, we would like to be able to get the best of both worlds. However, converting from a coefficients representation to a samples representation, or vice-versa, takes quadratic time (because you have N samples, and your overall algorithm performs N operations on each sample, so you end up with a quadratic algorithm.)

			Here, we will cover a way to go from a samples representation to a coefficients representation, or vice-versa, in O(N log N) time.


	[[Category:Math]]		[[Category:Math]]
	[[Category:Polynomials]]		[[Category:Polynomials]]

Admin: /* Overview */

2017-08-15T23:14:51Z

Overview

← Older revision		Revision as of 23:14, 15 August 2017
Line 34:		Line 34:
	\|O(n)		\|O(n)
	\|style="background-color: #700;"\|		\|style="background-color: #700;"\|
	\|O(n^2)		O(n^2)

	\|-		\|-
Line 40:		Line 40:
	\|O(n)		\|O(n)
	\|style="background-color: #700;"\|		\|style="background-color: #700;"\|
	\|Infinite time		Infinite time
	\|O(n)		\|O(n)

Line 46:		Line 46:
	\|Multiplication		\|Multiplication
	\|style="background-color: #700;"\|		\|style="background-color: #700;"\|
	\|O(n^2)		O(n^2)
	\|O(n)		\|O(n)
	\|O(n)		\|O(n)

Admin at 23:14, 15 August 2017

2017-08-15T23:14:13Z

← Older revision		Revision as of 23:14, 15 August 2017
Line 1:		Line 1:
			==Overview==

	Start with overview of what we've covered so far:		Start with overview of what we've covered so far:

Line 12:		Line 14:
	* Addition		* Addition
	* Multiplication		* Multiplication

			Making a table of what operations take what amounts of time, we get:

	{\| class="wikitable" cellpadding="100" width="66%"		{\| class="wikitable" cellpadding="100" width="66%"
Line 29:		Line 33:
	\|O(n)		\|O(n)
	\|O(n)		\|O(n)
			\|style="background-color: #700;"\|
	\|O(n^2)		\|O(n^2)

Line 34:		Line 39:
	\|Addition:		\|Addition:
	\|O(n)		\|O(n)
			\|style="background-color: #700;"\|
	\|Infinite time		\|Infinite time
	\|O(n)		\|O(n)
Line 39:		Line 45:
	\|-		\|-
	\|Multiplication		\|Multiplication
			\|style="background-color: #700;"\|
	\|O(n^2)		\|O(n^2)
	\|O(n)		\|O(n)
Line 44:		Line 51:

	\|}		\|}








	[[Category:Math]]		[[Category:Math]]
	[[Category:Polynomials]]		[[Category:Polynomials]]

Admin at 23:04, 15 August 2017

2017-08-15T23:04:05Z

← Older revision		Revision as of 23:04, 15 August 2017
Line 12:		Line 12:
	* Addition		* Addition
	* Multiplication		* Multiplication

			{\| class="wikitable" cellpadding="100" width="66%"
			!colspan="4"\|Big-O Complexity of Polynomial Operations
			\|-
			\|<br /><br />
			Operation
			\|<br /><br />
			Coefficient Representation
			\|<br /><br />
			Roots Representation
			\|<br /><br />
			Samples Representation

			\|-
			\|Evaluation:
			\|O(n)
			\|O(n)
			\|O(n^2)

			\|-
			\|Addition:
			\|O(n)
			\|Infinite time
			\|O(n)

			\|-
			\|Multiplication
			\|O(n^2)
			\|O(n)
			\|O(n)

			\|}

Admin at 22:48, 15 August 2017

2017-08-15T22:48:03Z

← Older revision		Revision as of 22:48, 15 August 2017
Line 5:		Line 5:
	We can represent them in three ways:		We can represent them in three ways:
	* Coefficients vector		* Coefficients vector
	* Roots vector		* Roots vector
	* Samples vector		* Samples vector

Line 12:		Line 12:
	* Addition		* Addition
	* Multiplication		* Multiplication





			[[Category:Math]]
			[[Category:Polynomials]]

Admin: Created page with "Start with overview of what we've covered so far: Polynomials are useful mathematical objects. We can represent them in three ways: * Coefficients vector * Roots vector * S..."

2017-08-15T22:47:42Z

Created page with "Start with overview of what we've covered so far: Polynomials are useful mathematical objects. We can represent them in three ways: * Coefficients vector * Roots vector * S..."

New page

Start with overview of what we've covered so far:

Polynomials are useful mathematical objects.

We can represent them in three ways:
* Coefficients vector
* Roots vector
* Samples vector

We also have three different algorithms/operations we wish to define:
* Evaluation
* Addition
* Multiplication