Forum Coders' city Strona Gwna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UytkownicyUytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj si, by sprawdzi wiadomociZaloguj si, by sprawdzi wiadomoci   ZalogujZaloguj 

Potrzebuj szybkiej odpowiedzi na moje pytanie... Zasady

kubit stochastyczny... co Wy na to ??

Id do strony 1, 2, 3, 4  Nastpny

 
Odpowiedz do tematu    Forum Coders' city Strona Gwna -> Algorytmy + inynieria oprogramowania
Zobacz poprzedni temat :: Zobacz nastpny temat  
Autor Wiadomo
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Nie Kwi 08, 2018 11:30 am  OP    Temat postu: kubit stochastyczny... co Wy na to ?? Odpowiedz z cytatem Pisownia

Hej,
mam pomysa, by moe gupi, ale tematyka mechaniki kwantowej, jak i informatyki kwantowej interesuje mnie od duszego czasu... ale nie znam si na tym dobrze, wic kada uwaga cenna:

w mechanice kwantowej wany jest objekt tzw. kubitu (uoglnienie bitu, moe przyjmowa wartoci inne ni 0, 1), ale definicja jest postawiona na bazie analizy zespolonej... zastanawiam si czy nie da si poda definicji czysto stochastycznej (probabilistycznej), aby traktowa kubit jako zmienn losow, czyli najprostszy dwulementowy kubit byby to objekt postaci:
Kod:

a * |0> + b * |1>, gdzie a+b=1, a, b nieujemne...


no i ten objekt mona prbowa analizowa... tworzy nawet jakie bramki kwantowo-stochastyczne, itd... skd si wzi pomys... ?? to duga droga... ale pomogo mi skojarzenie m. in. standardowej logki z logik rozmyt, co truem kiedy na ten temat ciut... ^^

Natomiast ciekawy jest (???) pomys kodowania liczby dla takiego stochastycznego kubitu... tylko pytanie czy to ma sens, i daoby si to w ogle zaimplementowa... ???

Podam jeden przykad, rozmwamy kubit postaci
Kod:

a0 * |1> + a1 * |2> + a2 * |4> + ... + an * |2^n>


dla ustalonego n, odpowiednio duego...

Zamy, e chcemy zakodowa liczb 2018... szukamy max m dla ktrego 2^m < 2018, czyli m = 10, czyli warto 2018 si mieci midzy elementem |1024>, a elementem |2048>... nastpnie szukamy parametru c, dla ktrego
Kod:

c * |1024> + (1-c) * |2048> = 2018


okazuje si, e c = 30/1024, i wystarczy wykona same odejmowania... ^^

Jakie s plusy ?? do kodowania liczby np. o 100000 bitach skupiamy si tylko na dwch elementach tego kubitu... pojawiaj si oczywicie pytania, jak to zaimplementowa, o ile to moliwe... no, i jak magazynowa dane... ?? bo tutaj cigw zerojedynkowych raczej niet... ^^ co Wy na to... ?? ^^

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Pi Kwi 13, 2018 11:54 am  OP    Temat postu: Odpowiedz z cytatem Pisownia

Kompresja Tekstu i Struktury Danych… wstpne spostrzeenia... (sorki, e tak nawijam, ale chc przekaza swoje przemylenia, dopki mam jeszcze si)...

Majc kubit, powiedzmy

Kod:

a1 * |A> + a2 * |Z>



moemy zakodowa kad literk uywajc tego kubitu…

Natomiast mam propozycj kodowania tekstu (jego kompresji, jest taka, nie wiem czy sensowna):

dzielimy tekst na kawaki, powiedzmy stuelementowe (dugoci kawakw trzeba jako dobiera do kodowanego tekstu) i tworzymy sownik przechowujcy pozycje literek, wystarczy w sumie tablic, przechowujc pozycje elementw w tekcie… plus jest taki, e aby si dobra do kocowej czci tekstu, nie trzeba przechodzi przez cay tekst, ani go magazynowa caego w pamici… co wicej, by moe tak te warto jako magazynowa i tworzy struktury danych, aby np. Technika MapReduce w systemach przetwarzania rwnolegego danych nie musiaa naraz przeszukiwa wszystkich zasobw… (!!!)… Ale to temat chyba raczej trudny… wydaje mi si, e bardzo wane w tego typu zagadnieniach s odpowiednie struktury danych, by moe sowniki, jakie struktury grafowe oraz by moe jakie mapy hashujce, przerabiajce dane we wstpnych fazach gromadzenia danych i porzdkujce je w jak sensown cao umoliwiajc szybsze wyszukiwanie… (!!!)
____________________________________________________________
Przykadowy kod w Pythonie:

Kod:

a = "asdfgjkk asdghjkhsa asdfhjfs afsekvvnnjccb"
a = 100 * a
V = {}

al = len(a)
ile = 50
a5 = al // 50
lista = []
for j in range(a5+1):
    w = a[ile*j:ile*j+ile]
    V = {}      
    for i in range(len(w)):
        x = w[i]
        if x in V.keys():
            V[x].append(i)
        else:
            V[x] = [i]
    lista.append(V)

print(lista)



Te uwagi mog by istotne nie tylko przy ujciu kubitowym…


Natomiast jak mogaby wyglda baza danych w rozproszonym (celowo nie pisz rwnolegym !!!) ujciu kubitowym… ??

Wstpny szkic (prosty przykad):

Zamy, e chcemy mie baz gromadzc sowa: PEACE, WAR, WAR, PEACE, LOVE, LOVE, LOVE, PEACE, WAR, LOVE

Tworzymy kubitow sie komputerw:

Kod:

a1 * |P> + a2 * |L> + a3 * |W>



gromadzimy dane tak:

Kod:

|P>: PEACE, PEACE, PEACE
|W>: WAR, WAR, WAR
|L>: LOVE, LOVE, LOVE, LOVE



I teraz… Aby zliczy ilo sw PEACE w naszej (teoretycznej) bazie danych uywajc techniki MapReduce… musielibymy przeglda wszystkie zasoby, tak mi si przynajmniej wydaje… natomiast w tak postawionej definicji skupialibymy si na „tylko” na elemencie „P” tak utworzonej sieci… Myl, e to wane spostrzeenie… zamiast tworzy pliki gromadzce danych po rnych serwerach… lepiej chyba umieszcza dane po rnych serwerach wedug jakiego klucza (reguy segregujcej dane)…

Wniosek
Zamiast jednolitej struktury danych warto si zastanowi nad rozproszon struktur danych… Nie wiem czy takie pojcie istnieje...
____________________________________________________________
Ciut bardziej skomplikowana struktura (np. dla ksiki telefonicznej):
Kod:

a1 * |A, B, C> + a2 * |D, E, F> + a3 * |G, H, I>…


i dalej idc element |A, B, C> jest take kubitem, np. postaci:
Kod:

b1 * |A> + b2 * |B> + b3 * |C>


Natomiast mona i ciut dalej i przedstawi element |A> np. jako kubit taki:
Kod:

a1 * |A>|A, B, C> + a2 * |A>|D, E, F> + a3 * |A>|G, H, I> + …


gdzie element |A>|A, B, C> gromadziby dane ksiki telefonicznej z przedrostkami „AA”, „AB”, AC”
Wniosek (z powyszego przykadu dotyczcego ksiki telefonicznej): zamiast techniki obliczania rwnolegego moe warto zastanowi si nad struktur grafow oblicze w wersji rozproszonej…

____________________________________________________________
Generalnie: temat rzeka…
Cel: tworzenie (lub prba tworzenia) optymalnych struktur danych…

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Sob Kwi 14, 2018 9:33 am  OP    Temat postu: Odpowiedz z cytatem Pisownia

Dodawanie i Mnoenie stochastycznych kubitw...

Zamy, e chcemy doda liczby 15 i 31... W ukadzie kubitw:

Kod:

a1 * |1> + a2 * |2> +a3 * |4> + a4 * |8> + ...



Przedstawiamy 15 jako

Kod:

7/8 * |16> + 1/8 * |8>



oraz 31 jako:

Kod:

15/16 * |32> + 1/16 * |16>



Okazuje si, e mona zaprezentowa te liczby np. tak:

Kod:

15 ~ [0, 0, 7, 1, 0, 0, 0]
31 ~ [0, 15, 1, 0, 0, 0, 0]



A moe lepiej wykonywa obliczenia wykorzystujc wspczynniki kubitu... ??

I w takiej sytuacji dodaje si do prosto, otrzymujc:

Kod:

[0, 15, 16, 0, 0, 0, 0]


A po przesuniciu w lewo o jeden otrzymujemy:
Kod:

[15, 16, 0, 0, 0, 0, 0]


Poniewa 15+16 < 32, std musimy bity nieco zmieni i dostajemy ukad:
Kod:

[14, 18, 0, 0, 0, 0, 0]


co odpowiada liczbie w ujciu kubitowym:
Kod:

14/32 * |64> + 18/32 * |32>


co odpowiada stochastycznemu ujciu liczby 465, co jest raczej zgodne z rzeczywistoci... :)

Sprbujmy wymnoy te liczby... Majc reprezentacj liczb 15 i 31 w postaci:

Kod:

15 ~ [0, 0, 0, 0, 0, 0, 7, 1, 0, 0, 0]
31 ~ [0, 0, 0, 0, 0, 15, 1, 0, 0, 0, 0]


Po wymnoeniu standardowym wspczynnikw mamy:

(w wykonywaniu mnoenia by moe warto rekurencyjnie wywoywa mnoenie w ujciu kubitowym, lub trzyma w sowniku zestaw odpowiednich, podrcznych, iloczynw, komentarz na kocu tych wypocin)...
Kod:

[0, 105, 22, 1, 0, 0, 0, 0, 0, 0, 0]


I przesuwamy o 1 miejsce w lewo, odpowiednio zwikszajc i transformujc wspczynniki:
Kod:

[210, 45, 0, 0, 0, 0, 0, 0, 0, 0, 0]


Poniewa 210 + 45 < 256 dokonujemy zmiany wspczynnikw na:
Kod:

[209, 47, 0, 0, 0, 0, 0, 0, 0, 0, 0]


otrzymujc kubitowe przedstawienie liczby w postaci:
Kod:

209/256 * |512> + 47/256 * |256>


co odpowiada liczbie 465... :)

Przykadowy kod w Pythonie dla dodawania (mog by bdy, i na pewno da si go uproci)… procedurka dla mnoenia jest podobna, ale ciut bardziej skomplikowana...
Kod:

import math

def dodaj_us_kubit(a, b):
    if b < a:
        a, b = b, a
    n1 = math.log(a, 2)
    n = int(n1)
    if n != n1:
        n += 1
    m1 = math.log(b, 2)
    m = int(m1)
    if m != m1:
        m += 1
    x = 2 + max(m, n)    
    aa = [0 for i in range(x+1)]
    bb = [0 for i in range(x+1)]

    aa[x-n] = 2**n - a
    aa[x-n-1] = 2**(n-1) - aa[x-n]
    bb[x-m] = 2**m - b
    bb[x-m-1] = 2**(m-1) - bb[x-m]
    if a == b:
        bb[x-m-1] *= 2
        bb[x-m] *= 2
    else:
        bb[x-m] += 2 * aa[x-n-1] + aa[x-n]
  
    while bb[x-m] + bb[x-m-1] != 2**m:
        if bb[x-m] + bb[x-m-1] < 2**m:
            bb[x-m-1] -= 1
            bb[x-m] += 2
        else:
            bb[x-m-1] += 1
            bb[x-m] -= 2
    return 2*bb[x-m-1]+bb[x-m]

print(dodaj_us_kubit(15, 31))



Z odejmowaniem raczej nie powinno by problemu... Problem pojawia si chyba z dzieleniem, na razie nie mam pomysy jak to ugry...

Natomiast warto ciut czasu spdzi nad potgowaniem... Aby podnie liczbe 2 do 31 potgi wykonujemy 30 mnoe; umiejtnie przedstawiajc wykadnik mona t liczb znacznie zmniejszy... Nie mam pojcia, czy da si wykona jakie kubitowe potgowanie, pewnie si nie da... ale mona znacznie zmniejszy ilo mnoe w wersji kubitowej...

Ot:
Kod:

31 = 2^4 + 2^3 + 2^2 + 2 + 1


Korzystajc z tej wasnoci mamy:
Kod:

2^19 = (((2^2)^2)^2^2) * ((2^2)^2^2) * (2^2)^2 * 2^2 * 2


I wtedy wykonujemy tylko 14 mnoe, a w zasadzie, jeeli pamitamy wyniki, to wystarczy tylko wykona 8 mnoe, o ile si nie pomyliem... ^^

Jeszcze jedna uwaga...
Aby komputer nie powiela wielu oblicze powinnimy w nim trzyma w jakim sowniku najczciej pojawiajce si dziaania, aby za kadym razem nie powiela oblicze... Czyli np. sownik mgby zawiera wyniki wszystkie potgi dwjki np. do n=10000 i przechowywa je w odpowiednim miejscu... nastpnie wszystkie iloczyny typu a * b, dla a, b < 10000, a, b naturalne... Wtedy dostp do wyniku byby z czasem O(1), o ile si dobrze orientuj...

Na razie tyle... :)

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Sob Kwi 14, 2018 3:52 pm  OP    Temat postu: Odpowiedz z cytatem Pisownia

Dzielenie (jednak si udao, moe ma to sens ??), troch niestandardowo... Sprbujmy podzieli liczby 169 oraz 13... Przedstawiamy liczb 169 w postaci kubitowej:
Kod:

87/128 * |128> + 41/128 * |256>


oraz liczb 13:
Kod:

13 = 3/8 * |8> + 5/8 * |16>


Liczba 13 ley w kubicie
Kod:

a * |8 > + b * |16>


wic na pewno jest mniejsza od 16... dla a = 0, b = 1... Nastpnie
dzielimy liczb 169 w wersji kubitowej przez |16> otrzymujc:
Kod:

87/128 * |8> + 41/128 * |16>


Ta liczba (niekoniecznie cakowita) jest w kubicie:
Kod:

a * |8 > + b * |16>


Uruchamiamy nastpn procedur wyszukiwania liczby wykorzystujc
mnoenie kubitowe (!) oraz, aby przyspieszy wyszukiwanie, metod
bisekcji... Szkic algorytmu (wykorzystujemy funkcj mnoenia liczb
w wersji kubitowej pomnoz_liczby(a, b)):
Kod:

a = 8 (dolna granica kubitu wyniku)
b = 16 (grna granica kubitu wyniku)
dzielna = 169
dzielnik = 13
while 1:
    x = int(a/2 + b/2)
    s = pomnoz_liczby(x, dzielnik)
    if s == dzielna:
        return x
    elif a == b:
        return "no solution"
    elif s > dzielna:
        b = x
    else:
        a = x


Ta procedura dziaa dla liczb cakowitych, ale ze wzgldu na metod bisekcji mona t metod take stosowa dla liczb niecakowitych... z dowoln dokadnoci... szybko dziaania, wykadnicza...
___________________________________________________________________________

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Sob Kwi 14, 2018 5:00 pm  OP    Temat postu: Odpowiedz z cytatem Pisownia

Hmmm... pracowity dzie... Uzyskaem jaki odpowiednik algorytmu Shora (ale by moe to zbyt due sowo, dopuszczam moliwo, e to zwyky Sheet, ale cao moim zdaniem trzyma si... no wiecie czego si trzyma)...

Idea rozkadu iloczynu liczb pierwszych w ujciu kubitowym…

Zamy, e mamy liczb 290123…

1. Obliczamy pierwiastek z tej liczby, jest rwny ~540…
2. wypisujemy tablic liczb pierwszych mniejszych od 540…

Kod:

a = [2 3 5 7 11 13 17 19 23 ... 79 83 89 97 101 103 ... 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 ... 503 509 521 523]



Nastpnie zapisujemy liczb 290123 w wersji kubitowej:
Kod:

a*|2^18> + b*|2^19>


Wspczynniki tak naprawd… nie s potrzebne... !!! I teraz dla kadej liczby pierwszej z tablicy wykonujemy nastpujc procedur…

Na przykadzie np. liczby 223 (jedna z liczb w rozkadzie)…

Zapisujemy liczb 223 w wersji kubitowej:
Kod:

33/128 * |128 > + 95/128 * |256>


I nastpnie wykonujemy procedur dzielenia kubitowego… Zgodnie z poprzednim wpisem… Czyli dzielimy 2^18 przez 2^7 i szukamy rozwizania w kubicie:
Kod:

a * |2^11> + (1-a) * |2^12>


I tak naprawd dopiero po znalezieniu rozwizania cakowitego, sprawdzamy czy to rozwizanie jest liczb pierwsz… jeeli jest, to OK… jeeli nie, procedura jest przerywana… poniewa mielibymy w takim razie liczb bdc iloczynem co najmniej trzech liczb pierwszych… ^^

________________________________________
Chyba wyczerpaem na razie temat... ^^
________________________________________

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
karolinavb
Site Admin


Doczy: 25 Maj 2005
Posty: 7871

PostWysany: Nie Kwi 15, 2018 7:29 pm      Temat postu: Odpowiedz z cytatem Pisownia

Cytat:
Chyba wyczerpaem na razie temat...
Ja jednak bd dalej czekaa z zapartym tchem ;-)) na dalsze Twoje rozwaania.
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Pon Kwi 16, 2018 5:12 am  OP    Temat postu: Odpowiedz z cytatem Pisownia

mio, e kto to czyta... :) musz troch odpocz, ciutk ochon... i ogarn to wszystko... to wersja robocza, nazwijmy j on-line... jest bardzo duo pyta, wtpliwoci, itd., temat jest wiey jak w bueczki w piekarni, ale jest to efekt wieloletnich przemyle, kursw on-line, i dziaalnoci programistycznej, take na tym forum... dzisiaj moe wrzuc implementacj mnoenia... samo kodowanie raczej nie jest trudne w podstawowej, klasycznej, wersji... pozdrawiam... :)
_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Pon Kwi 16, 2018 11:21 am  OP    Temat postu: Odpowiedz z cytatem Pisownia

a to wpis dedykowany karolinie, tej vb... :)

Majc kubit, najprostszy kubit:
Kod:

a1 * |0> + a2 * |1>


mona zauway, e przyjmuje on wartoci midzy zerem, a jeden, o ile zaoymy, e |0> jest zwykym zerem, a |1> zwyk jedynk... natomiast, jeeli 0 bdziemy interpretowa jako warto logiczn FALSE, a 1 jako TRUE... to wtedy dostaniemy wszystkie wartoci porednie midzy TRUE, a FALSE... czyli mamy prezentacj logiki rozmytej na podstawie najprostszego kubitu... ten kubit mona take interpretowa jako prosty model sterownika rozmytego... na razie tyle w tematyce, nazwijmy j rozmyt... :)

PS1. ale to tylko idea, w tematyk AI raczej nie planuj wchodzi, raczej interesuj mnie deterministyczne rozwizania, ewentualnie jakie stochastyczne symulacje... ale mona chyba systemy AI modelowa w tym ujciu, o ile kto bdzie mia tak potrzeb...
PS2. jak si wyrobi to jeszcze dzisiaj kod mnoenia w moim (chyba ulubionym) jzyku programowania...

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Wto Kwi 17, 2018 10:53 am  OP    Temat postu: Odpowiedz z cytatem Pisownia

no i obiecane mnoenie, w prostej wersji...
Kod:

def multi_kubit(a, b):
    if b < a:
        a, b = b, a
    n1 = math.log(a, 2)
    n = int(n1)
    if n != n1:
        n += 1
    m1 = math.log(b, 2)
    m = int(m1)
    if m != m1:
        m += 1
    x = 2 + max(m, n)    
    aa = [0 for i in range(x+1)]
    bb = [0 for i in range(x+1)]

    aa[x-n] = 2**n - a
    aa[x-n-1] = 2**(n-1) - aa[x-n]
    bb[x-m] = 2**m - b
    bb[x-m-1] = 2**(m-1) - bb[x-m]

    aabb = [0 for i in range(2*x+2)]
    aabb[2*x-m-n-2] = aa[x-n-1]*bb[x-m-1]
    aabb[2*x-m-n-1] = aa[x-n-1]*bb[x-m]+aa[x-n]*bb[x-m-1]
    aabb[2*x-m-n] = aa[x-n]*bb[x-m]
    return 4*aabb[2*x-m-n-2]+2*aabb[2*x-m-n-1] + aabb[2*x-m-n]


Pojawia si oczywicie naturalny problem duych wspczynnikw dla odpowiednio duych n... Zastanawiaem si, czy wtedy nie dzieli tych wielkich kubitw na jakie podkubity... tylko pytanie jak... Nastpna idea, to moe praca na wspczynnikach postaci kubitowej danej liczby... tylko jest jeden problem... moemy traci dokadno przy zaokrgleniach...

Druga idea to tworzenie kubitw bardziej rwnomiernych... no, ale wtedy tracilibymy wasno eksponencjalnoci kubitu... Take pomys jest... Pytanie czy da si to efektywnie, i lepiej kodowa...

_____________________________________________________________________________________________________

Skd sie wzia idea... ?? Od paru lat interesuje mnie ciut Mechanika Kwantowa... i zakakujce jest dla mnie to, e jest opisana "urojonym" aparatem matematycznym, a my chyba yjemy w wiecie Trjwymiarowo-Rzeczywistym... a poniewa pojawiaj si tam prawdopodobiestwa, zaczem si zastanawia, czy nie da si tego opisa probabilistycznie... Oczywicie ten temat na razie jest dla mnie za trudny, i to zdecydowanie... Natomiast zaczem podchodzi do tematu od ciut innej strony... Ot... Mamy Komputery Kwantowe, ktre teoretycznie (i chyba nawet ju co nieco praktycznie) maj przynie now jako szybkoci w obliczaniu... Natomiast pojawiaj si problemy z tworzeniem struktur (procesorw) kwantowych ze wzgldu, m. in. na "ujarzmieniu" odpowiednich struktur fizycznych tak, aby pracoway zgodnie z oczekiwaniem... No i zastanawiam si czy nie daoby si zasymulowa zachowania si Komputera Kwantowego przy uyciu procesora dziaajcego na zasadach probabilistycznych (jakie metody stochastyczne, metody mechaniki statystycznej lub moe ten kubt, a uj wie)... czyli w skrcie: rozgldam si za metodami, ktre umoliwiyby stworzenie procesora dziaajcego podobnie jak kwantowy, ale w oparciu o metody deterministyczno-stochastyczne... natomiast nie znam kompletnie metod tworzenia komputera kwantowego... wic moje ujcie moe by ciut lamerskie, na razie to wszystko co mam do powiedzenia na ten temat... Miego Czytania... i ewentualnego analizowania...
_____________________________________________________________________________________________________

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
hurgadion



Doczy: 06 Kwi 2011
Posty: 852
Skd: Web :)

PostWysany: Wto Kwi 17, 2018 7:57 pm  OP    Temat postu: Odpowiedz z cytatem Pisownia

i kolejny odcinek... da si troch przyspieszy dziaanie mnoenia w ujciu kubitowym na nastpujcej zasadzie...

1. V[i]=2**i
2. W[i]= V[i]+V[i-1]

Jeeli chcemy pomnoy liczby a, b wykonujemy nastpujce kroki:

1. obliczamy n = int(log(a, 2)) oraz m = int(log(b, 2))
2 przedstawiamy liczby w postaci:
Kod:

a = V[n] + ra
b = V[m] + rb


jeeli ra > V[n-1] zastpujemy ra = ra1+V[n-1] otrzymujc:
Kod:

a = W[n]+ra1


podobnie postpujemy z b... Nastpnie wykonujemy mnoenie:
Kod:

a * b = W[n] * V[m] + W[n] * rb + V[n] * ra1 + rb * ra1


gdzie odpowiednie mnoenia wykonujemy rekurencyjnie... natomiast atwo zauway, e:
Kod:

W[n] * V[m] = W[n+m]


Takie ujcie mnoenia umoliwia zapisanie liczby bdcej w kubicie (przedziale [2^n, 2^{n+1}]) tak, aby wykorzysta rodek cikoci kubitu (tutaj rodek przedziau) do oblicze...

Kod:
Kod:

import math
import sys

sys.setrecursionlimit(1000000)
V={}
W={}
W[0]=1
for i in range(-1,1000):
    V[i] = 2**i
    if i>0:
        W[i] = V[i]+V[i-1]


def d(x, rx, t):
    if rx <= 0:
        return 0
    xx = int(math.log(rx, 2))
    ry = rx - V[xx]
    rxbool = ry < V[xx-1]
    
    if rxbool:
        if t==1:
            return V[x]*V[xx] + d(x, ry, 1)
            ## V[x]*V[xx] = V[x+xx]
        else:
            return W[x]*V[xx] + d(x, ry, 0)
            ## W[x]*V[xx] = W[x+xx]
    else:
        if t==1:
            return V[x+xx] + d(x, ry, 1)
        
        else:
            return W[x] * W[xx] + d(x, ry-V[xx-1], 0)
            ## W[x] * W[xx] = V[x*xx]+V[m+n-1]+W[m+n-1]
    
def f(a, b):
    if a * b < 100:
        return a * b
    x = int(math.log(a, 2))
    y = int(math.log(b, 2))
    rx = a - V[x]
    ry = b - V[y]
    rxbool = rx < V[x-1]
    rybool = ry < V[y-1]
    if rxbool and rybool:
        return V[x+y] + d(x, ry, 1) + d(y, rx, 1) + f(rx, ry)
    elif not rxbool and rybool:
        return W[x]*V[y] + d(x, ry, 0) + d(y, rx-V[x-1], 1) + f(rx-V[x-1], ry)    
    elif rxbool and not rybool:      
        return V[x]*W[y] + d(x, ry-V[y-1], 1) + d(y, rx, 0) + f(rx, ry-V[y-1])
    else:
        return W[x]*W[y] + d(x, ry-V[y-1], 0) + d(y, rx-V[x-1], 0) + f(rx-V[x-1], ry-V[y-1])
    

print(f(129, 129))


__________________________________

_________________
miasto nauki praktycznej
Powrt do gry
Zobacz profil autora Wylij prywatn wiadomo Odwied stron autora Numer GG
Wywietl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Gwna -> Algorytmy + inynieria oprogramowania Wszystkie czasy w strefie CET (Europa)
Id do strony 1, 2, 3, 4  Nastpny
Strona 1 z 4

 
Skocz do:  
Moesz pisa nowe tematy
Moesz odpowiada w tematach
Nie moesz zmienia swoich postw
Nie moesz usuwa swoich postw
Nie moesz gosowa w ankietach
Moesz dodawa zaczniki na tym forum
Moesz pobiera pliki z tego forum




Debug: strone wygenerowano w 0.16277 sekund, zapytan = 11
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |