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

yarel napisał(a):

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ń? ;-)

W przypadku kwaternionów złożoność pozostanie taka sama, jedynie współczynnik spadnie do połowy, czyli 2 razy szybciej to wymnożysz.

Chodzi o generalny przypadek, znaczy taki w którym: q = (q0, q1, q2, q3), i teraz te współczynniki: qi są liczbami o dużej precyzji, np. po 1000 cyfr lub więcej.
Wówczas zamiast 16n^2 wymnożysz to w czasie 8n^2, n = liczba cyfr.

Niemniej to jest tylko preludium, ponieważ już dla: 8 = 2*4, masz 2 kwaterniony, więc mnożenie oktetów można realizować rekurencyjne, co zredukuje złożoność istotnie.

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

Ani jedno, ani drugie.

Współczynniki są tu zawsze skalarami!

liczby zespolone:
z = (x,y);

iloczyn zespolonych:
(x1 + iy1)(x2 + iy2) = (x1x2 - y1y2) + i(x1y2 + x2y1) = c1 + ic2 -> tu są dwa współczynniki, skalary.
i 4 mnożenia, które można zredukować do 3.

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

dla 4n cyfrowych, gdzie n = dowolne.

Wibowit napisał(a):

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

zwyczajne mnożenie w wersji form dwuliniowych, czyli: xMy

i dla zwyczajnego iloczynu wielomianów 4-tego stopnia mamy tu siedem macierzy M, 4x4 każda. :)
wielomian 6-tego stopnia ma 7 współczynników: c0 do c6.

x mul y = sum [x Mi y]; oraz i = 1 do 7.

możesz sobie wypisać te 7 macierzy, np.: M1 =
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

co produkuje x3.y3, pierwszy współczynnik - ten przy x^6, po prostu.

natomiast ten środkowy:
M4 =
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0

co daje: 30 + 03 + 21 + 12.

Jak spakować 7 macierzy w jednej?

To jest całkiem proste:
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

i tak to wygląda to mnożenie wielomianów 3-stopnia, czyli o 4 współczynnikach. :)

Teraz wystarczy to tylko przerobić na sumę 8 podobnych matriksów, no i gotowe!

Teraz wystarczy to tylko przerobić na sumę 8 podobnych matriksów, no i gotowe!

vs

Oczekuję gotowca w Javie.

@Wibowit exp<X> wymądrza się na forum od dłuższego czasu i nie widziałem ani jednej linijki kodu od niego.
Moim zdaniem oczekiwanie od niego jednej funkcji, która działa to marzenia ściętej głowy. Dostaniesz jedynie kolejne dziwne rozważania, których chyba nikt nie rozumie.

Hmm... to praktycznie tak samo jak z kolesiami, którym wydaje się, że wymyślili metodę na kompresję dowolnych danych.

Kompresja dowolnych danych == Universal Compression
http://mattmahoney.net/dc/dce.html#Section_11

MarekR22 napisał(a):

@Wibowit exp<X> wymądrza się na forum od dłuższego czasu i nie widziałem ani jednej linijki kodu od niego.
Moim zdaniem oczekiwanie od niego jednej funkcji, która działa to marzenia ściętej głowy. Dostaniesz jedynie kolejne dziwne rozważania, których chyba nikt nie rozumie.

No to dawaj tę kombinację: 8 mnożeń zamiast 16, na kwaetet.

Zobaczymy kto szybciej poda wynik: ja - szmaciarz algebraiczny, czy ty - mistrz programistyczny. :)

exp3 napisał(a):

Zobaczymy kto szybciej poda wynik: ja - szmaciarz algebraiczny, czy ty - mistrz programistyczny. :)

Ze spokojem olewam temat, bo i tak działającego kodu nie podasz :]

Wibowit napisał(a):

exp3 napisał(a):

Zobaczymy kto szybciej poda wynik: ja - szmaciarz algebraiczny, czy ty - mistrz programistyczny. :)

Ze spokojem olewam temat, bo i tak działającego kodu nie podasz :]

Kodu czego?

Dowolny algorytm - schemat obliczeniowy jest już kodem.

Natomiast samo zakodowaniu algorytmu w zadanym żargonie: c, java, asm, paskal, perl,... jest już jedynie translacją: S -> Z,
ale pod warunkiem że żargon: Z ogarnia S, czyli ma dostateczną bazę, która obejmuje S.

Wibowit napisał(a):

Oczekuję gotowca w Javie.

Wibowit napisał(a):

Wibowit napisał(a):

Oczekuję gotowca w Javie.

Ja pracuję w Nocy. :)

Hej,
jeżeli ktoś ma problemy z wyznaczaniem odpowiednich współczynników (patrz powyżej), to można się posłużyć losową metodą wyszukiwania rozwiązań... Bardzo przydatna metoda, wszędzie tam, gdzie mamy problemy z wyznaczeniem konkretnego rozwiązania analitycznie... Sorry @Wibowit, że nie w Javie, ale zajęłoby mi to co najmniej parę razy dłużej... Nie komentuję kodu, ponieważ nie jesteśmy w szkole... Jak ktoś chce niech testuje... i wyciąga wnioski...

import random

def f(q0, q1, q2, q3, r0, r1, r2, r3):
    return r0*q0 - r1*q1 - r2*q2 - r3*q3

def ff(a1, a2, a3, a4, a5, a6, a7, a8, q0, q1, q2, q3, r0, r1, r2, r3):
    q = a1 * (q0+q1) * (r0+r1) + a2 * (q1+q3) * (r1+r2)
    q += a3 * (q3-q2) * (r2-r3) + a4 * (q1-q3) * (r1-r2)
    q += a5 * (q1-q0) * (r2+r3) + a6 * (q0+q2) * (r0-r3)
    q += a7 * (q3+q2) * (r1-r0) + a8 * (q0-q2) * (r0+r3)
    return q

a = [[0, 0, 0, 0, 0, 0, 0, 0] for i in range(20)]



oszac = 10**10
for ii in range(50):
    for i in range(20000):
        for j in range(20):
            for k in range(8):
                a[j][k] = 4*random.random()
        a1 = -1+2*random.random()
        a2 = -1+2*random.random()
        a3 = -1+2*random.random()
        a4 = -1+2*random.random()
        a5 = -1+2*random.random()
        a6 = -1+2*random.random()
        a7 = -1+2*random.random()
        a8 = -1+2*random.random()
        roz = -1+2*random.random()
        for e in a:
            wynik = f(e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7])
            wyniksym = ff(a1, a2, a3, a4, a5, a6, a7, a8, e[0], e[1], e[2], e[3], e[4] ,e[5], e[6], e[7])
            roz += abs(wynik-wyniksym)
        if roz < oszac:
            wspol = [a1, a2, a3, a4, a5, a6, a7, a8]
            oszac = roz

print(wspol, oszac)

Miało być nudno... a zrobiło się ciekawie... ^^

PS. da się to zrobić lepiej, o ile wykorzystamy pewne założenie co do wartości współczynników... :)

I tą metodą wyznaczyłem współczynniki, sprawdź @exp3 czy dobrze...

[0, -0.5, 1, -0.5, 0, 0.5, 0, 0.5]
[1, -0.5, 0, -0.5, 0, -0.5, 0, -0.5]
[0, 0.5, 0, -0.5, -1, 0.5, 0, -0.5]
[0, 0.5, 0, -0.5, 0, -0.5, -1, 0.5]

O ile dobrze widzę to chcesz zaaproksymować funkcją ff robiącą co najmniej 8 mnożeń funkcję f robiącą tylko 4 mnożenia. A więc nie dość, że tylko aproksymujesz to jeszcze zwiększasz ilość mnożeń co najmniej dwukrotnie. Jaki w tym sens?

exp3 napisał(a):

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.
...

Co jest rozważaną przestrzenią i co jej bazą?

Pisałeś, że vX to skalary, co jest bez sensu bo istnieje takie k, że v0 * k = v1, czyli v0 i v1 nie mogły by byc elementami bazy.

hurgadion napisał(a):

Hej,
jeżeli ktoś ma problemy z wyznaczaniem odpowiednich współczynników (patrz powyżej), to można się posłużyć losową metodą wyszukiwania rozwiązań... Bardzo przydatna metoda, wszędzie tam, gdzie mamy problemy z wyznaczeniem konkretnego rozwiązania analitycznie... Sorry @Wibowit, że nie w Javie, ale zajęłoby mi to co najmniej parę razy dłużej... Nie komentuję kodu, ponieważ nie jesteśmy w szkole... Jak ktoś chce niech testuje... i wyciąga wnioski...

import random

def f(q0, q1, q2, q3, r0, r1, r2, r3):
    return r0*q0 - r1*q1 - r2*q2 - r3*q3

def ff(a1, a2, a3, a4, a5, a6, a7, a8, q0, q1, q2, q3, r0, r1, r2, r3):
    q = a1 * (q0+q1) * (r0+r1) + a2 * (q1+q3) * (r1+r2)
    q += a3 * (q3-q2) * (r2-r3) + a4 * (q1-q3) * (r1-r2)
    q += a5 * (q1-q0) * (r2+r3) + a6 * (q0+q2) * (r0-r3)
    q += a7 * (q3+q2) * (r1-r0) + a8 * (q0-q2) * (r0+r3)
    return q

a = [[0, 0, 0, 0, 0, 0, 0, 0] for i in range(20)]



oszac = 10**10
for ii in range(50):
    for i in range(20000):
        for j in range(20):
            for k in range(8):
                a[j][k] = 4*random.random()
        a1 = -1+2*random.random()
        a2 = -1+2*random.random()
        a3 = -1+2*random.random()
        a4 = -1+2*random.random()
        a5 = -1+2*random.random()
        a6 = -1+2*random.random()
        a7 = -1+2*random.random()
        a8 = -1+2*random.random()
        roz = -1+2*random.random()
        for e in a:
            wynik = f(e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7])
            wyniksym = ff(a1, a2, a3, a4, a5, a6, a7, a8, e[0], e[1], e[2], e[3], e[4] ,e[5], e[6], e[7])
            roz += abs(wynik-wyniksym)
        if roz < oszac:
            wspol = [a1, a2, a3, a4, a5, a6, a7, a8]
            oszac = roz

print(wspol, oszac)

Miało być nudno... a zrobiło się ciekawie... ^^

PS. da się to zrobić lepiej, o ile wykorzystamy pewne założenie co do wartości współczynników... :)

Bardzo dobrze, tyle że dla kwaternionów podałem już rozwiązanie.

Zadaniem jest wyznaczenie zwyczajnego mnożenia wielomianów, czyli coś takiego:

a mul b = ( // a = a3x^3 + a2x^2 + a1x + a0, b = ...
33, // x^6
32+23, // x^5
31+22+13, // ...
30+21+12+03,
20+11+02,
10+01,
00);

jak widać mamy tu 7 składowych - kombinacji współczynników... a dla kwaternionów były 4, tyle że tam każda składała się aż z 4.
1 + 2 + 3 + 4 + 3 + 2 + 1 = 16 = 4 x 4.

Pojawiło się pytanie: czy 8 mnożeń to minimum dla iloczynu kwaternionów?

Tak. W przypadku kwaternionów 8 mnożeń jest tu minimum - mniej nie da rady.

W przypadku wielomianów to minimum wynosi 7.

Różnica bierze się stąd, że 'mnożenie' kwaternionów nie jest przemienne: p mul q = -q mul p,
no a dla wielomianów jest to przemienne, podobnie jak i zwyczajnych liczb: a.b = b.a.

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

Co jest rozważaną przestrzenią i co jej bazą?

Pisałeś, że vX to skalary, co jest bez sensu bo istnieje takie k, że v0 * k = v1, czyli v0 i v1 nie mogły by byc elementami bazy.

Bazą tu jest {v0, v1, ... v7} - 8 sztuk, i tylko 8 mnożeń oczywiście.

No a przestrzeń ma tu 16 wymiarów = liczba możliwych par z mnożeń: 4x4,
stąd też ta macierz ma wymiary: 8 x 16.

Szukana jest tu ta baza z 8-oma mnożeniami... a że możliwości takich baz jest dość sporo: kilka milionów, czy miliardów,
więc na piechotę raczej trudno to wyznaczyć.

korekta:

p mul q = -q mul p,

tak jest dla iloczynu wektorowego, ale nie dla kwaternionów.

p mul q <> q mul p.

PS.
Teoria = analityka w praktyce.

Jeśli kogoś nie rozumiemy, wtedy nazywamy go... niemcem, albo teoretykiem. :)

exp3 napisał(a):

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

Co jest rozważaną przestrzenią i co jej bazą?

Pisałeś, że vX to skalary, co jest bez sensu bo istnieje takie k, że v0 * k = v1, czyli v0 i v1 nie mogły by byc elementami bazy.

Bazą tu jest {v0, v1, ... v7} - 8 sztuk, i tylko 8 mnożeń oczywiście.

No a przestrzeń ma tu 16 wymiarów = liczba możliwych par z mnożeń: 4x4,
stąd też ta macierz ma wymiary: 8 x 16.

Szukana jest tu ta baza z 8-oma mnożeniami... a że możliwości takich baz jest dość sporo: kilka milionów, czy miliardów,
więc na piechotę raczej trudno to wyznaczyć.

Wydaje mi się, że rozumiem ogólną ideę i wygląda mniej więcej tak, "jeśli umiemy rozwiązać X, to umiemy też Y", ale problemem jest to, że X nie umiemy, prawda?
Jeśli umiemy, to pokaż ten rozkład na v0..v7 i temat zamknięty.

Jak nie umiemy, to problem sprowadza się do przeszukania przestrzeni wszystkich kombinacji i za jakiś czas możesz ogłosić światu, "oto jest mój lepszy algorytm". Pewnie później można rozważać przestrzeń sedenionów (16 wymiarowe; z tego co pamiętam z wykładów, to nie istnieje "podobna" algebra, ale z większą ilością wymiarów) i iść w kierunku dekompozycji problemu na 16,8,4,2 i składać końcowy wynik.

Przeraża mnie jednak liczba kombinacji do sprawdzenia dla przypadku 8 :)

Bez przesady. Nawet na piechotę te kilka miliardów kombinacji można przeliczyć w kilka sekund.

W przypadku 4 mamy tylko tyle możliwości do sprawdzenia:

• ai -> 4 sztuki, i razy 4 bi, co daje 16 bezpośrednich iloczynów typu ai.bi;
• (ai +/- bj) - 6*2 = 12, czyli mnożymy parami: 144 możliwości tylko
• potrójne: 4*4 = 16, więc 256
• poczwórne: 8, czyli 64

a pozostałe kombinacje w stylu: (a + b)(a+b+c), czyli 2 x 3, 2x4, 1x3, itp. można pominąć, a jeśli nie, no to i tak tego jest niedużo.

Jeżeli weźmiemy 4 konie i 3 osły to można je tak poustawiać, że wyjdzie 8 krów.

Mimo wszystko próbuję to sobie poukładać po swojemu.

1. 4-ki <p3,p2,p1,p0> / <q3,q2,q1,q0> utożsamiasz z wielomianami

P(x) = p0+p1x+p2x^2+p3x^3
Q(x) = q0+q1x+q2x^2+q3x^3

Możemy rozważyć przestrzeń wielomianów stopnia <= 3, z bazą {1,x,x^2,x^3}, wówczas P,Q są kombinacjami liniowymi:

P(x) = p0+p1x+p2x^2+p3x^3 = {p0,p1,p2,p3}.{1,x,x^2,x^3} (. - iloczyn skalarny)
Q(x) = q0+q1x+q2x^2+q3x^3 = {q0,q1,q2,q3}.{1,x,x^2,x^3}

2. Mnożenie liczb odpowiada więc mnożeniu wielomianów.

P*Q(x) = p0 q0 + x (p0 q1 + p1 q0) + x^2 (p0 q2 + p1 q1 + p2 q0) + x^3 (p0 q3 + p1 q2 + p2 q1 + p3 q0) + x^4 (p1 q3 + p2 q2 + p3 q1) + x^5 (p2 q3 + p3 q2) + p3 q3 x^6

W przestrzeni liniowej wielomianów st. <=6 z bazą {1,x,x^2, ..., x^6} możemy przedstawić jako kombinację liniową:

P*Q(x) = {p0q0, p0q1+p1q0, p0q2+p1q1+p2q0, p0q3+p1q2+p2q1+p3q0, p1q3+p2q2+p3q1, p2q3+p3q2, p3q3 }.{1,x,x^2,x^3,x^4,x^5,x^6}

No i tu jest te 16 mnożeń.

3. Teraz mówisz tak "weźmy taką bazę, w której będzie tylko 8 mnożeń". Będzie to 7 wielomianów postaci:
   a + bX + cX^2 + dx^3 + ex^4 + fx^5 + gx^6 -> gdzie a..g to będą jakieś liczby

Czyli powstanie nam macierz 7x7, w wierszu będą współczynniki pierwszego wektora nowej bazy:
a b c d e f g
...
A B C D E F G

@hurgadion Ci tę bazę wyznaczył.

Tylko pozostaje wykonać... 7 dodatkowych mnożeń przez (nieznane?) współczynniki i mamy 8 mnożeń + 7 mnożeń = 15 mnożeń? :-)

Dla 7 mnożeń otrzymasz schemat Toom4 = zwyczajna interpolacja wielomianów, który jest do bani, bo wymaga skomplikowanych obliczeń (w tym dzielenie!).
Dlatego ja chcę użyć: 8 mnożeń. :)

exp3 napisał(a):

Dla 7 mnożeń otrzymasz schemat Toom4 = zwyczajna interpolacja wielomianów, który jest do bani, bo wymaga skomplikowanych obliczeń (w tym dzielenie!).
Dlatego ja chcę użyć: 8 mnożeń. :)

No dobrze, ale czy w tym przypadku dodanie 8-go mnożenia nie będzie tożsame z rozszerzeniem bazy o dodatkowy wektor (który będzie liniowo zależny od już istniejących wektorów, bo baza ma wymiar 7 i już rozpina przestrzeń wielomianów st.<=6, wiec dodanie nowego wektora niewiele wniesie), a przez to i tak skończysz z koniecznością wykonania 8 mnożeń (wynikających z dekompozycji na sumy pi+-pj) + 8 mnożeń wynikających z kombinacji liniowych ? Czyli skończysz, z 8+8=16 mnożeń?

yarel napisał(a):

exp3 napisał(a):

Dla 7 mnożeń otrzymasz schemat Toom4 = zwyczajna interpolacja wielomianów, który jest do bani, bo wymaga skomplikowanych obliczeń (w tym dzielenie!).
Dlatego ja chcę użyć: 8 mnożeń. :)

No dobrze, ale czy w tym przypadku dodanie 8-go mnożenia nie będzie tożsame z rozszerzeniem bazy o dodatkowy wektor (który będzie liniowo zależny od już istniejących wektorów, bo baza ma wymiar 7 i już rozpina przestrzeń wielomianów st.<=6, wiec dodanie nowego wektora niewiele wniesie), a przez to i tak skończysz z koniecznością wykonania 8 mnożeń (wynikających z dekompozycji na sumy pi+-pj) + 8 mnożeń wynikających z kombinacji liniowych ? Czyli skończysz, z 8+8=16 mnożeń?

Tak na pewno nie będzie.
Przestrzeń 8-wymiarowa ogarnia 7 - z nadmiarem.
Zatem możliwości jest tu więcej, więc mamy wybór - swobodę w doborze kombinacji (współczynników 8 zamiast 7).

W przypadku 7 z 7 nie ma wyboru - rozwiązanie jest tylko jedno.