On 22.04.2015 20:49, gyansorova@gmail.com wrote:> On Wednesday, April 22, 2015 at 2:39:01 PM UTC+12, robert bristow-johnson wrote: >> On 4/21/15 5:26 PM, Evgeny Filatov wrote: >>> On 22.04.2015 0:01, gyansorova@gmail.com wrote: >>>> On Wednesday, April 22, 2015 at 7:28:28 AM UTC+12, Evgeny Filatov wrote: >>>>> On 21.04.2015 21:50, gyansorova@gmail.com wrote: >>>>> >>>>> (snip) >>>>> >>>>>> I think it's more the otehr way around. They have a Toeplitz matrix >>>>>> and they are looking for a fast way to invert it and find that this >>>>>> involves polynomials. >>>>>> For example in an abstract >>>>> >>>>> Thanks, that certainly helps. Curiously enough, there's a 1994 book by >>>>> Bini and Pan named "Polynomial and Matrix Computations: Fundamental >>>>> Algorithms". I have no idea if it's good, though. >>>>> >>>> >>>> and I just found this simpler method using 2 FFTs to do convolution >>>> >>>> >>>> http://icereijo.com/fft-based-multiplication-algorithm/ >>>> >> >> cool trick. >> >>> >>> True. However, the method just combines a complex signal from two real >>> signals and computes an FFT of the complex signal. But then, one has to >>> ask what was initially meant by "two FFTs"? >> >> it's similar to asking what is meant by a length-N real FFT? you can do >> a length-N real FFT with a length-(N/2) complex FFT by putting the N/2 >> even samples in the real parts and the N/2 odd samples in the imaginary >> parts of N/2 complex samples. and untangle the results on the other >> end. is it a length-N FFT or a length-(N/2) FFT? >> >> in both cases you're getting two-for-one. two reals for one complex. >> >> -- >> >> r b-j rbj@audioimagination.com >> >> "Imagination is more important than knowledge." > > what does BCD adj mean at the last step of their algorithm? >They call that stage "BCD adjustment". BCD means "binary-coded decimal". They use BCD to encode numbers as sequences of decimal digits. After the convolution they get a sequence of multiplications of pairs of digits, and each may require up to two digits to be written down. Like, 6*7 = 42 requires 2 digits. So to get the final result in decimal form they must sum up all such 2-digit numbers. Not sure I've explained it better than they did in their source code file "mul.cc", "Let us consider A and B sequences as polynomial coefficients. Then the convolution operation of both signals will represent the polynomial product. Knowing that none of the coefficients can be greather than their base, if we do a decimal adjustement consisting in propagate the carry values towards higher weight digits, the final sequence will be the multiplication of both numbers. Thus, the multiplication can be performed with a convolution operation with BCD adjustment." Regards, Evgeny.
Polynomials - Interesting
Started by ●April 16, 2015
Reply by ●April 22, 20152015-04-22
Reply by ●April 22, 20152015-04-22
On Thursday, April 23, 2015 at 7:33:51 AM UTC+12, Evgeny Filatov wrote:> On 22.04.2015 20:49, gyansorova@gmail.com wrote: > > On Wednesday, April 22, 2015 at 2:39:01 PM UTC+12, robert bristow-johnson wrote: > >> On 4/21/15 5:26 PM, Evgeny Filatov wrote: > >>> On 22.04.2015 0:01, gyansorova@gmail.com wrote: > >>>> On Wednesday, April 22, 2015 at 7:28:28 AM UTC+12, Evgeny Filatov wrote: > >>>>> On 21.04.2015 21:50, gyansorova@gmail.com wrote: > >>>>> > >>>>> (snip) > >>>>> > >>>>>> I think it's more the otehr way around. They have a Toeplitz matrix > >>>>>> and they are looking for a fast way to invert it and find that this > >>>>>> involves polynomials. > >>>>>> For example in an abstract > >>>>> > >>>>> Thanks, that certainly helps. Curiously enough, there's a 1994 book by > >>>>> Bini and Pan named "Polynomial and Matrix Computations: Fundamental > >>>>> Algorithms". I have no idea if it's good, though. > >>>>> > >>>> > >>>> and I just found this simpler method using 2 FFTs to do convolution > >>>> > >>>> > >>>> http://icereijo.com/fft-based-multiplication-algorithm/ > >>>> > >> > >> cool trick. > >> > >>> > >>> True. However, the method just combines a complex signal from two real > >>> signals and computes an FFT of the complex signal. But then, one has to > >>> ask what was initially meant by "two FFTs"? > >> > >> it's similar to asking what is meant by a length-N real FFT? you can do > >> a length-N real FFT with a length-(N/2) complex FFT by putting the N/2 > >> even samples in the real parts and the N/2 odd samples in the imaginary > >> parts of N/2 complex samples. and untangle the results on the other > >> end. is it a length-N FFT or a length-(N/2) FFT? > >> > >> in both cases you're getting two-for-one. two reals for one complex. > >> > >> -- > >> > >> r b-j rbj@audioimagination.com > >> > >> "Imagination is more important than knowledge." > > > > what does BCD adj mean at the last step of their algorithm? > > > > They call that stage "BCD adjustment". > > BCD means "binary-coded decimal". They use BCD to encode numbers as > sequences of decimal digits. After the convolution they get a sequence > of multiplications of pairs of digits, and each may require up to two > digits to be written down. Like, 6*7 = 42 requires 2 digits. So to get > the final result in decimal form they must sum up all such 2-digit numbers. > > Not sure I've explained it better than they did in their source code > file "mul.cc", > > "Let us consider A and B sequences as polynomial coefficients. Then the > convolution operation of both signals will represent the polynomial > product. Knowing that none of the coefficients can be greather than > their base, if we do a decimal adjustement consisting in propagate the > carry values towards higher weight digits, the final sequence will be > the multiplication of both numbers. Thus, the multiplication can be > performed with a convolution operation with BCD adjustment." > > Regards, > Evgeny.I followed the integer version example - so this probably means that if a number is greater than 9 they do a carry to the next digit along.. Thanks
