jak wymnożyć dwa kwartety w 8 mnożeniach?

Tradycyjnie mnożenie w tym przypadku wygląda tak:

(a3,a2,a1,a0).(b3,b2,b1,b0) =
a3.b3,
a3.b2 + a2.b3,
a3.b1 + a1.b3 + a2.b2,
a3.b0 + a0.b3 + a2.b1 + a1.b2,
a2.b0 + a0.b2 + a1.b1,
a1.b0 + a0.b1,
a0.b0
)

jak widać jest tu 4x4 - 16 mnożeń, co należy zredukować do 8.

Procedura produkowania takich 'szybkich' mnożeń jest następująca:
zamiast mnożyć to pojedynczo, tworzymy sumy/różnice, które produkują od razu kilka iloczynów prostych.

przykłady:
( a3 - a2).(b3 - b2) = a3.b3 - a3.b2 - a2.b3 + a2.b2
jak widać produkujemy tu w jednym mnożeniu aż 4 iloczyny (proste).

Takich kombinacji jest tu oczywiście bardzo dużo, zatem skecz polega na wybraniu tylko kilku,
takich których kombinacje (linowe) pozwolą odtworzyć te 7 współczynników z mnożenia czworaczków.

Być może wystarczą same takie 'pary', których jest tylko 6:
( a3 - a2).(b3 - b2)
( a3 - a1).(b3 - b1)
( a3 - a0).(b3 - b0)
( a2 - a1).(b2 - b1)
( a2 - a0).(b2 - b0)
( a1 - a0).(b2 - b0)

uwzględniając że tam może być '+' zamiast '-', otrzymamy chyba: 6*4 = 24 sztuki, co już jest grubo ponad 8.

Można używać bezpośrednich mnożeń oczywiście, w stylu: a3.a3 lub a1.b3, itp. ale limit wynosi 8, więc same takie na pewno nie wystarczą, bo razem jest 16.

potrójne i poczwórne kombinacje też są dozwolone:
( a3 + a3 + a2 + a0).(b3 + b2 + b1 + b0) = ... 16 sztuk od razu;
tylko że takie są gorsze od podwójnych, bo wymagają więcej operacji;
poza tym są zapewne grube setki takich kombinacji: z '+' lub '-' przy każdym współczynniku, więc problem wyboru byłby... zabójczy.

Tylko czy zastąpienie mnożeń większą ilością dodawań istotnie przyspieszy obliczenia na dzisiejszych procesorach? Niekoniecznie.
Na dodatek może pogorszyć dokładność obliczeń (dodawanie liczb zmiennoprzecinkowych jest mniej dokładne od mnożenia).

Raczej bym próbował użyć instrukcji SSE (jeśli mowa o x86) do tego typu operacji.

No chyba że chodzi o zadanie typu „zmniejsz ilość mnożeń do 8 za wszelką cenę”.

Azarien napisał(a):

Tylko czy zastąpienie mnożeń większą ilością dodawań istotnie przyspieszy obliczenia na dzisiejszych procesorach? Niekoniecznie.
Na dodatek może pogorszyć dokładność obliczeń (dodawanie liczb zmiennoprzecinkowych jest mniej dokładne od mnożenia).

Raczej bym próbował użyć instrukcji SSE (jeśli mowa o x86) do tego typu operacji.

No chyba że chodzi o zadanie typu „zmniejsz ilość mnożeń do 8 za wszelką cenę”.

Taki schemat mnożenia miałby złożoność: n^1.5, dla długich liczb.
Byłoby to aż tysiąc razy szybsze dla n = milion, od tradycyjnej metod: n^2.

No, a użycie oktetów: w wersji 16 mnożeń z 64, dałoby tu: n^1.333..., co jest już kosmicznie szybkie - szybsze nawet od FFT!

No chyba że chodzi o zadanie typu „zmniejsz ilość mnożeń do 8 za wszelką cenę”.

To też może być całkiem interesującym ćwiczeniem.

Przykład: jak wymnożyć dwa kwaterniony za pomocą tylko 8 mnożeń (skalarnych)?
(a3,ia2,ja1,ka0).(b3,ib2,jb1,kb0) = (a3.b3 - a2.b2-a1.b1-a0.b0, ...); co daje na piechotę też aż 4x4 = 16 mnożeń.

Taki schemat mnożenia miałby złożoność: n^1.5, dla długich liczb

Jak długich? Może opisz dokładniej co chcesz liczyć bo zaczyna to wyglądać na problem XY.

Azarien napisał(a):

Taki schemat mnożenia miałby złożoność: n^1.5, dla długich liczb

Jak długich? Może opisz dokładniej co chcesz liczyć bo zaczyna to wyglądać na problem XY.

Dla tysięcy cyfr i więcej.

Dowolny schemat mnożenia z podziałem na k części, które potem wymnażamy w 2k mnożeniach,
zamiast w k^2, daje złożoność: log(2k)/log(k) = 1 + 1/log(k);
k = 4: 1 + 1/2
k = 8: 1 + 1/3
k = 16: 1 + 1/4
itd.

minimum wynosi tu faktycznie 2k-1 mnożeń, ale ja wolę jedno więcej: 2k, bo wtedy sprawa się upraszcza.
https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication

Dla 2k-1 wzory są zbyt skomplikowane powyżej 3 - w zasadzie bezużyteczne.

O co tu chodzi, bo nie rozumiem. Czy Chcesz nam pokazać, że Toom - Cook multiplication jest najszybszą metodą mnożenia? Przecież nie jest i podlinkowany przez Ciebie artykuł to pokazuje:

"In general, Toom-k runs in Θ(c(k) ne), where e = log(2k − 1) / log(k), ne is the time spent on sub-multiplications, and c is the time spent on additions and multiplication by small constants."
Oraz:
"Although the exponent e can be set arbitrarily close to 1 by increasing k, the function c unfortunately grows very rapidly"
I jeszcze:
"An implementation described by Donald Knuth achieves the time complexity Θ(n 2√2 log n log n)"

Czy mamy odtworzyć ten algorytm? A może go ulepszyć?

Znowu Piszesz głupoty, na co Ci zwróciłem uwagę w innym wątku :

"Taki schemat mnożenia miałby złożoność: n^1.5, dla długich liczb.
Byłoby to aż tysiąc razy szybsze dla n = milion, od tradycyjnej metod: n^2.
No, a użycie oktetów: w wersji 16 mnożeń z 64, dałoby tu: n^1.333..., co jest już kosmicznie szybkie - szybsze nawet od FFT!"

Otóż nie(z Toom - Cook multiplication):
"Due to its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate-size multiplications, before the asymptotically faster Schönhage–Strassen algorithm (with complexity Θ(n log n log log n)) becomes practical"

Co z tego wynika? Metody Toom - Cook nie można poprawiać w nieskonczoność (znaczy do O(n)), bo faktor liniowy rośnie. Jest szybsza od innych metod, to tylko dla specyficznych liczb, średniej wielkości, tak na oko to będzie mniej więcej 10 do 30 tysięcy cyfr dziesietnych.
Zgodnie z tym postąpili, na przykład, programiści GMP:
https://gmplib.org/manual/Multiplication-Algorithms.html

lion137 napisał(a):

O co tu chodzi, bo nie rozumiem. Czy Chcesz nam pokazać, że Toom - Cook multiplication jest najszybszą metodą mnożenia? Przecież nie jest i podlinkowany przez Ciebie artykuł to pokazuje:
"In general, Toom-k runs in Θ(c(k) ne), where e = log(2k − 1) / log(k), ne is the time spent on sub-multiplications, and c is the time spent on additions and multiplication by small constants."
Oraz:
"Although the exponent e can be set arbitrarily close to 1 by increasing k, the function c unfortunately grows very rapidly"
I jeszcze:
"An implementation described by Donald Knuth achieves the time complexity Θ(n 2√2 log n log n)"

Czy mamy odtworzyć ten algorytm? A może go ulepszyć?

Znowu Piszesz głupoty, na co Ci zwróciłem uwagę w innym wątku :

"Taki schemat mnożenia miałby złożoność: n^1.5, dla długich liczb.
Byłoby to aż tysiąc razy szybsze dla n = milion, od tradycyjnej metod: n^2.
No, a użycie oktetów: w wersji 16 mnożeń z 64, dałoby tu: n^1.333..., co jest już kosmicznie szybkie - szybsze nawet od FFT!"

Otóż nie(z Toom - Cook multiplication):
"Due to its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate-size multiplications, before the asymptotically faster Schönhage–Strassen algorithm (with complexity Θ(n log n log log n)) becomes practical"

Co z tego wynika? Metody Toom - Cook nie można poprawiać w nieskonczoność (znaczy do O(n)), bo faktor liniowy rośnie. Jest szybsza od innych metod, to tylko dla specyficznych liczb, średniej wielkości, tak na oko to będzie mniej więcej 10 do 30 tysięcy cyfr dziesietnych.
Zgodnie z tym postąpili, na przykład, programiści GMP:
https://gmplib.org/manual/Multiplication-Algorithms.html

Mówiłem o tym, że Toom-k jest bezużyteczny dla dużych k, bo komplikacja rośnie zbyt szybko - nieliniowo z k, czyli inaczej to c.
Dlatego proponuję wersję 2k, zamiast 2k-1, a wtedy to c już nie rośnie tak drastycznie.

Wówczas metoda będzie zawsze chyba szybsza od FFT dla dowolnych n, bo im większe n tym większe k sobie wybieram!

W zasadzie FFT jest metodą opartą na podziałach binarnych, czyli to jest to samo co wersja kaskadowa 2k.
Tylko że w przypadku FFT musimy wykonywać kosztowne transformacje, i dlatego to przegra z bezpośrednim podziałem na k (w wersji z 2k mnożeniami).

"Dlatego proponuję wersję 2k, zamiast 2k-1, a wtedy to c już nie rośnie tak drastycznie.

Wówczas metoda będzie zawsze chyba szybsza od FFT dla dowolnych n, bo im większe n tym większe k sobie wybieram!

W zasadzie FFT jest metodą opartą na podziałach binarnych, czyli to jest to samo co wersja kaskadowa 2k.
Tylko że w przypadku FFT musimy wykonywać kosztowne transformacje, i dlatego to przegra z bezpośrednim podziałem na k (w wersji z 2k mnożeniami)."

Jakie 2k, jak tam jest 2k - 1; a z resztą, Podaj chociaż jakiś zarys dowodu, że jak tam będzie 2k, to stała będzie rosła na tyle wolno, że Toom - k będzie się zbliżał do O(n), ablo, że wyprzedzi Schonchage Strassen Algorytm czy dowolny inny. Bo jak nie to po co tracić czas.

lion137 napisał(a):

"Dlatego proponuję wersję 2k, zamiast 2k-1, a wtedy to c już nie rośnie tak drastycznie.

Wówczas metoda będzie zawsze chyba szybsza od FFT dla dowolnych n, bo im większe n tym większe k sobie wybieram!

W zasadzie FFT jest metodą opartą na podziałach binarnych, czyli to jest to samo co wersja kaskadowa 2k.
Tylko że w przypadku FFT musimy wykonywać kosztowne transformacje, i dlatego to przegra z bezpośrednim podziałem na k (w wersji z 2k mnożeniami)."

Jakie 2k, jak tam jest 2k - 1; a z resztą, Podaj chociaż jakiś zarys dowodu, że jak tam będzie 2k, to stała będzie rosła na tyle wolno, że Toom - k będzie się zbliżał do O(n), ablo, że wyprzedzi Schonchage Strassen Algorytm czy dowolny inny. Bo jak nie to po co tracić czas.

Na tym polega zadanie w tym temacie: wyprowadzić schemat mnożenia czwórek na bazie 8 mnożeń prostych.

A potem zrobimy oktety: k = 8, itd.
Gdy ktoś to rozwiąże, wtedy się okaże jak i co tu rośnie.

"Na tym polega zadanie w tym temacie: wyprowadzić schemat mnożenia czwórek na bazie 8 mnożeń prostych.
A potem zrobimy oktety: k = 8, itd.
Gdy ktoś to rozwiąże, wtedy się okaże jak i co tu rośnie."

Jak sie bawimy, stawiamy sobie hipotezy, a nie rozmawiamy poważnie, to powiem, że na logikę zmniejszenie liczby mnożeń spowoduje jeszcze szybszy wzrost czynnika liniowego i algorytm będzie bezużyteczny.
Więc nie ma to sensu, zwłaszcza, że istnieje O(n) - FFT algorytm (z dużą stałą, co prawda), asymptotycznie optymalny, dla długich liczb.

Jak sie bawimy, stawiamy sobie hipotezy, a nie rozmawiamy poważnie, to powiem, że na logikę zmniejszenie liczby mnożeń spowoduje jeszcze szybszy wzrost czynnika liniowego i algorytm będzie bezużyteczny.

Zmniejszenie jest niemożliwe: mnożenie wielomianów wymaga minimum 2k-1 mnożeń.

Ja zwiększam liczbę mnożeń z 2k-1 na 2k, i dlatego to się upraszcza drastycznie.

exp2 napisał(a):

Jak sie bawimy, stawiamy sobie hipotezy, a nie rozmawiamy poważnie, to powiem, że na logikę zmniejszenie liczby mnożeń spowoduje jeszcze szybszy wzrost czynnika liniowego i algorytm będzie bezużyteczny.

Zmniejszenie jest niemożliwe: mnożenie wielomianów wymaga minimum 2k-1 mnożeń.

Ja zwiększam liczbę mnożeń z 2k-1 na 2k, i dlatego to się upraszcza drastycznie.

Whatever, jak pisałem, Podaj, choćby jakiś cień dowodu, że czynnik liniowy nie będzie rósł dostatecznie szybko, żeby rozwalić algorytm, a jak nie, to jest to ciągle strata czasu (IMO, może ktoś w tym widzi sens, ale wydaje mi się, że już nikt tego watku nie czyta:))

lion137 napisał(a):

Ja zwiększam liczbę mnożeń z 2k-1 na 2k, i dlatego to się upraszcza drastycznie.

Whatever, jak pisałem, Podaj, choćby jakiś cień dowodu, że czynnik liniowy nie będzie rósł dostatecznie szybko, żeby rozwalić algorytm, a jak nie, to jest to ciągle strata czasu (IMO, może ktoś w tym widzi sens, ale wydaje mi się, że już nikt tego watku nie czyta:))

Wymnóż sobie te czwórki za pomocą 7 mnożeń-> Toom4, a potem za pomocą 2k=8 - i porównaj obie wersje.

W przypadku k = 4, zysk może być niewielki, o ile w ogóle, ale dla k=8, 16, 32, ... będzie już kosmiczny!

exp2 napisał(a):

lion137 napisał(a):

Ja zwiększam liczbę mnożeń z 2k-1 na 2k, i dlatego to się upraszcza drastycznie.

Whatever, jak pisałem, Podaj, choćby jakiś cień dowodu, że czynnik liniowy nie będzie rósł dostatecznie szybko, żeby rozwalić algorytm, a jak nie, to jest to ciągle strata czasu (IMO, może ktoś w tym widzi sens, ale wydaje mi się, że już nikt tego watku nie czyta:))

Wymnóż sobie te czwórki za pomocą 7 mnożeń-> Toom4, a potem za pomocą 2k=8 - i porównaj obie wersje.

W przypadku k = 4, zysk może być niewielki, o ile w ogóle, ale dla k=8, 16, 32, ... będzie już kosmiczny!

Właśnie, to Porównaj i Pokaż ten "kosmiczny" zysk, bo ja go nie widzę, nawet przez mikroskop elektronowy:-)

Właśnie, to Porównaj i Pokaż ten "kosmiczny" zysk, bo ja go nie widzę, nawet przez mikroskop elektronowy:-)

Nie znasz podstaw algebry?
rzucasz się jak kogut w bucie...

exp2 napisał(a):

Właśnie, to Porównaj i Pokaż ten "kosmiczny" zysk, bo ja go nie widzę, nawet przez mikroskop elektronowy:-)

Nie znasz podstaw algebry?
rzucasz się jak kogut w bucie...

Uhuhu, wyższa szkołą trolowania. "Ja mam rację, jak tego nie dostrzegasz to jesteś niedouczony. A teraz bądź tak łaskaw i wyprowadź za mnie wzór i przedstaw dowód, który pokaże, że się nie mylę.". Żenada.

Uhuhu, wyższa szkołą trolowania. "Ja mam rację, jak tego nie dostrzegasz to jesteś niedouczony. A teraz bądź tak łaskaw i wyprowadź za mnie wzór i przedstaw dowód, który pokaże, że się nie mylę.". Żenada.

Kolejny mistrz w gadaniu o niczym.
Wiesz w jakim temacie się wypowiadasz?
Nie? No to sprawdź sobie tytuł.

Nie ma pomysłów na rozwiązanie?

Może tak na piechotę:

Tworzymy kolejne bazy - po 8 wektorów, a potem sprawdzamy czy spełniają nie warunek - generują 7 te sztuk: ci.

Przykładowo:

wybieramy bazę typu:
v0=a3.b3
v1=(a3 - a2).(b3 - b2) = 33 - 32 - 23 + 22 // same indeksy wystarczą
v2=(a3 - a1).(b3 - b1) = 33 - 31 - 13 + 11
v3=(a3 - a0).(b3 - b0) = 33 - 30 - 03 + 00
v4=(a2 - a1).(b2 - b1) = 22 - 21 - 12 + 11
v5=(a2 - a0).(b2 - b0) = 22 - 20 - 02 + 00
v6=(a1 - a0).(b1 - b0) = 11 - 10 - 01 + 00
v7=a0.b0

kombinacja liniowa tych wektorów:
p0.33 + p1(33-32-23+22) + p2(33-31-13+11) + p3(33-30-03+00) + p4(22-21-12+11) + p5(22-20-02+00) + p6(11-10-01+00) + p7.00 =

33(p0+p1+p2+p3) + 32(-p1) + 23(-p1) + 31(-p2) + 13(-p2) + 22(p4+p5) + 30(-p3) + 03(-p3) +
21(-p4) + 12(-p4) + 20(-p5) + 02(-p5) + 11(p2+p4+p6) + 10(-p6) + 01(-p6) + 00(p3+p5+p6+p7)

stąd układ równań (ostatnia kolumna dla wektora: c3 = 30+03+21+12):
33: 1 1 1 1 0 0 0 0 = 0
32: 0-1 0 0 0 0 0 0 = 0
23: 0-1 0 0 0 0 0 0 = 0
31: 0 0-1 0 0 0 0 0 = 0

13: 0 0-1 0 0 0 0 0 = 0
22: 0 0 0 0 1 1 0 0 = 0
30: 0 0 0-1 0 0 0 0 = 1
03: 0 0 0-1 0 0 0 0 = 1

21: 0 0 0 0-1 0 0 0 = 1
12: 0 0 0 0-1 0 0 0 = 1
20: 0 0 0 0 0-1 0 0 = 0
02: 0 0 0 0 0-1 0 0 = 0

11: 0 0 1 0 1 0 1 0 = 0
10: 0 0 0 0 0 0-1 0 = 0
01: 0 0 0 0 0 0-1 0 = 0
00: 0 0 0 1 0 1 1 1 = 0

układ musi być spełniony na wszystkich siedmiu ci.

Pozostaje sprawdzić kolejno możliwe bazy.
Możliwości jest sporo:

• singletony - 16 sztuk: a3.b3, a3.b2, ...
• parami: 6 * 6 = 36, uwzględniając +/- wyjdzie chyba z milion możliwości.
• trójkami: (ai+aj+ak).(bi'+bj'+bk') - kilka tysięcy możliwości
• czwórkami: tych tylko

wybieramy tylko 8 sztuk z milionów, co daje (milion po 8) kombinacji do sprawdzenia.
Jak widać algorytm jest prosty. :)

• parami: 6 * 6 = 36, uwzględniając +/- wyjdzie chyba z milion możliwości.

Trochę przesadziłem - kombinacji parami, czyli typu:
(ai +/- aj).(bi' +/- bj'),
jest tylko 36 x 2^2 = 144 zaledwie.

Zatem w sumie będzie chyba kilka tysięcy możliwych wektorów bazowych, nie milionów.

To mi wygląda na kontynuację tego wątku: mnożenie wielkich liczb
I chyba ten wątek zakończy się tak samo jak poprzedni.

Rozwiązanie dla mnożenia kwaternionów:
https://www.mathworks.com/help/aeroblks/quaternionmultiplication.html

q.r = (q0 + q1i + q2j + q3k).(r0 + r1i + r2j + r3k) =
(r0q0−r1q1−r2q2−r3q3) +
(r0q1+r1q0−r2q3+r3q2)i +
(r0q2+r1q3+r2q0−r3q1)j +
(r0q3−r1q2+r2q1+r3q0)k

16 mnożeń.

a wersja która wymaga tylko 8 mnożeń wygląda następująco:

(q0+q1)(r0+r1)
(q1+q3)(r1+r2)
(q3-q2)(r2-r3)
(q1-q3)(r1-r2)
(q1-q0)(r2+r3)
(q0+q2)(r0-r3)
(q2+q3)(r1-r0)
(q0-q2)(r0+r3)

to jest baza wektorów - w każdej tylko jedno mnożenie, oraz:

w = q.r = kombinacja liniowa tych 8 wektorów bazowych, czyli tylko 8 mnożeń!

Proste? :)

Gdzie jest ta kombinacja liniowa wektorów?

Wibowit napisał(a):

Gdzie jest ta kombinacja liniowa wektorów?

oznaczasz sobie te wektory:
v0 = (q0+q1)(r0+r1)
v1 = (q1+q3)(r1+r2)
itd.
...

potem tworzysz kombinacje liniową, czyli takie coś:
sum ci.vi = c0.v0 + c1.v1 + ...

następnie wyznaczasz współczynniki ci, co daje tu macierz typu:
A =
0 0-1 0 0 0 0 0
0 1 1 1 0 0 0 0
0 0 1 0 0-1 0-1
0 1 0-1 0 0 1 0
0 0 0 0 1 0 0 0
0 0-1 0 0 0 0 0
0 0 0 0 0 0-1 0
0 0 0 0-1-1 0 1
0 0 0 0 0 0 1 0
0 1 0-1 1 0 0 0
0 0 0 0 0 1-1-1
0 0 0 0-1 0 0 0
1 1 0 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 1 0 1

potem podstawiasz kolejno szukane wektory - te 4 składowe z mnożenia: w = q.r = (w0 + w1i +....)
A.x = w_j;

czyli rozwiązujesz 4 układy równań - jeden dla każdej składowej w_j,
wtedy otrzymasz te szukane kombinacje, czyli:
wj = sum cij.vi => cij = ...

Np. pierwsza składowa: (00 - 11 - 22 - 33), czyli współczynniki w0 należy podstawić w postaci kolumny: (1,0,0,0,0 -1,0,0,0,0,0,0, -1,0,0, -1) -> 16 sztuk.

co daje rozwiązanie:
c = 0, -0.5, 1, -0.5, 0, 0.5, 0, 0.5 -> 8 sztuk

stąd pierwsza składowa: w0 = v2 + 0.5(-v1 -v3 + v5 + v7),
co można wyliczyć i sprawdzić czy się zgadza: w0 = (00 - 11 - 22 - 33)

No, nieźle... Sorki, nie czytałem, ale spokojnie... doceniam, i ogarniam problem... Sam rozwiązałeś problem, który sobie postawiłeś, więc to cenne... :) To jak czujesz bluesa w temacie, to zajmij się teraz może oktonionami, a jak już skończysz to może nawet i sedenionami... i możesz nam spokojnie referować... :)

hurgadion napisał(a):

No, nieźle... Sorki, nie czytałem, ale spokojnie... doceniam, i ogarniam problem... Sam rozwiązałeś problem, który sobie postawiłeś, więc to cenne... :) To jak czujesz bluesa w temacie, to zajmij się teraz może oktonionami, a jak już skończysz to może nawet i sedenionami... i możesz nam spokojnie referować... :)

Niestety, ale to jest tylko zgadywanie, a nie faktyczne rozwiązywanie.

Poprawne rozwiązanie wygląda z grubsza tak:
xTy - to jest forma dwuliniowa, czyli wielomian typu: sum xi.yj

I teraz, np. dla iloczynu par w stylu: (x0 + x1)(y0 + y1) = x0y0 + x1y0 + x0y1 + x1y1, otrzymujemy tu
T =
1 1
1 1

(x0 - x1)(y0 + y1) produkuje: T =
1 -1
1 -1

dla (x0 + x1)(y0 - y1) otrzymamy: T =
1 1
-1 -1

i jeszcze (x0 - x1)(y0 - y1) -> T =
1 -1
-1 1

A teraz zagadka: T =
1 1
1 -1

no i co to reprezentuje?

No dobrze, a jaka jest złożoność wyznaczenia współczynników dla wektorów w tej Twojej bazie v0..v7, którą sobie wyznaczasz za pomocą 8 mnożeń? ;-)

No to może ja zadam podstawowe pytanie: jak wymnożyć dwa kwartety w 8 mnożeniach? :D

Oczekuję gotowca w Javie.

Ja z tego opisu zrozumiałem po dłuższej zadumie, że kolega, np.

• Liczbę 3245 przestawia jako wartość wielomianu R(10), gdzie R(x) = <x^3,x^2,x,1>.<3,2,4,5> (gdzie <x^3, x^2, x, 1> jest bazą wielomianów 3 stopnia, a U.V to iloczyn skalarny)
• Liczbę 6785 przestawia jako wartość wielomianu Q(10), gdzie Q(x) = <x^3,x^2,x,1>.<6,7,8,5>

Wynik mnożenia 3245x6785 to (RQ)(10), i teraz to co chce zrobić to wyznaczyć ten wielomian RQ, ale używa innej bazy niż: x^0,x,x^2,x^3,x^4,..., x^8
I chce żeby w tej innej bazie było 8 mnożeń. Tę inną bazę jakoś zaproponował...

v0, ..., v7 - i tu nie jestem pewien, czy

v0 to współczynnik przy x^0, czy może v0, to: (q0+q1X)(r0+r1X) = q0r0 + q1r1X + q1r0 + q1r1x^2

Obstawiam, że to jest to drugie :P

Problemem jednak pozostaje to jak wyznaczyć te współczynniki nowej bazy, nawet jak sobie te 8 mnożeń wykona.
A druga sprawa, że wydaje się szukać optymalnego mnożenia liczb 4 cyfrowych :P