Wyzwanie polega na napisaniu szybkiego kodu, który może wykonać trudną obliczeniowo nieskończoną sumę.
Wkład
n
Przez n
matrycę P
z pozycji całkowitych, które są mniejsze niż 100
wartości bezwzględnej. Podczas testowania z przyjemnością dostarczam dane wejściowe do Twojego kodu w dowolnym rozsądnym formacie, jakiego chce Twój kod. Domyślnie będzie to jeden wiersz na wiersz matrycy, oddzielone spacją i zapewnione na standardowym wejściu.
P
będzie pozytywnie określony, co oznacza, że zawsze będzie symetryczny. Poza tym tak naprawdę nie musisz wiedzieć, co oznacza pozytywny zdecydowanie, aby odpowiedzieć na wyzwanie. Oznacza to jednak, że faktycznie będzie odpowiedź na sumę zdefiniowaną poniżej.
Musisz jednak wiedzieć, czym jest produkt macierz-wektor .
Wydajność
Twój kod powinien obliczyć nieskończoną sumę:
w granicach plus lub minus 0,0001 poprawnej odpowiedzi. Oto Z
zestaw liczb całkowitych, podobnie jak Z^n
wszystkie możliwe wektory z n
elementami liczb całkowitych i e
jest to słynna stała matematyczna, która w przybliżeniu wynosi 2,71828. Zauważ, że wartość wykładnika jest po prostu liczbą. Poniżej wyraźny przykład.
Jak to się ma do funkcji Riemanna Thety?
W notacji tego artykułu o aproksymacji funkcji Riemanna Thety próbujemy obliczyć . Nasz problem jest szczególnym przypadkiem z co najmniej dwóch powodów.
- Ustawiamy parametr początkowy wywoływany
z
w powiązanym papierze na 0. - Matrycę tworzymy
P
w taki sposób, aby minimalny rozmiar wartości własnej wynosił1
. (Zobacz poniżej, jak tworzona jest macierz).
Przykłady
P = [[ 5., 2., 0., 0.],
[ 2., 5., 2., -2.],
[ 0., 2., 5., 0.],
[ 0., -2., 0., 5.]]
Output: 1.07551411208
Bardziej szczegółowo, zobaczmy tylko jeden termin w sumie dla tego P. Weźmy na przykład tylko jeden termin w sumie:
a x^T P x = 30
. Zauważ, że e^(-30)
to jest około 10^(-14)
i dlatego jest mało prawdopodobne, aby było ważne dla uzyskania prawidłowej odpowiedzi do danej tolerancji. Przypomnij sobie, że nieskończona suma faktycznie wykorzysta każdy możliwy wektor długości 4, gdzie elementy są liczbami całkowitymi. Właśnie wybrałem jeden, aby podać wyraźny przykład.
P = [[ 5., 2., 2., 2.],
[ 2., 5., 4., 4.],
[ 2., 4., 5., 4.],
[ 2., 4., 4., 5.]]
Output = 1.91841190706
P = [[ 6., -3., 3., -3., 3.],
[-3., 6., -5., 5., -5.],
[ 3., -5., 6., -5., 5.],
[-3., 5., -5., 6., -5.],
[ 3., -5., 5., -5., 6.]]
Output = 2.87091065342
P = [[6., -1., -3., 1., 3., -1., -3., 1., 3.],
[-1., 6., -1., -5., 1., 5., -1., -5., 1.],
[-3., -1., 6., 1., -5., -1., 5., 1., -5.],
[1., -5., 1., 6., -1., -5., 1., 5., -1.],
[3., 1., -5., -1., 6., 1., -5., -1., 5.],
[-1., 5., -1., -5., 1., 6., -1., -5., 1.],
[-3., -1., 5., 1., -5., -1., 6., 1., -5.],
[1., -5., 1., 5., -1., -5., 1., 6., -1.],
[3., 1., -5., -1., 5., 1., -5., -1., 6.]]
Output: 8.1443647932
P = [[ 7., 2., 0., 0., 6., 2., 0., 0., 6.],
[ 2., 7., 0., 0., 2., 6., 0., 0., 2.],
[ 0., 0., 7., -2., 0., 0., 6., -2., 0.],
[ 0., 0., -2., 7., 0., 0., -2., 6., 0.],
[ 6., 2., 0., 0., 7., 2., 0., 0., 6.],
[ 2., 6., 0., 0., 2., 7., 0., 0., 2.],
[ 0., 0., 6., -2., 0., 0., 7., -2., 0.],
[ 0., 0., -2., 6., 0., 0., -2., 7., 0.],
[ 6., 2., 0., 0., 6., 2., 0., 0., 7.]]
Output = 3.80639191181
Wynik
Przetestuję twój kod na losowo wybranych macierzach P o rosnącym rozmiarze.
Twój wynik jest po prostu największy, n
dla którego otrzymuję poprawną odpowiedź w mniej niż 30 sekund, gdy uśrednia się ponad 5 przebiegów z losowo wybranymi matrycami P
tego rozmiaru.
A co z krawatem?
W przypadku remisu zwycięzcą zostanie ten, którego kod działa najszybciej, uśredniony w ciągu 5 przebiegów. Jeśli czasy te są równe, zwycięzcą jest pierwsza odpowiedź.
Jak powstanie losowe wejście?
- Niech M będzie losową macierzą m na n macierzą m <= n i pozycjami -1 lub 1. W Pythonie / numpy
M = np.random.choice([0,1], size = (m,n))*2-1
. W praktyce będzie ustawićm
na okołon/2
. - Niech P będzie macierzą tożsamości + M ^ T M. W Pythonie / numpy
P =np.identity(n)+np.dot(M.T,M)
. Mamy teraz gwarancję, żeP
jest pozytywnie określony, a wpisy są w odpowiednim zakresie.
Zauważ, że oznacza to, że wszystkie wartości własne P wynoszą co najmniej 1, co sprawia, że problem jest potencjalnie łatwiejszy niż ogólny problem aproksymacji funkcji Riemanna Thety.
Języki i biblioteki
Możesz użyć dowolnego języka lub biblioteki, którą lubisz. Jednak do celów punktacji uruchomię Twój kod na moim komputerze, więc podaj jasne instrukcje, jak uruchomić go na Ubuntu.
Moja maszyna Czasy zostaną uruchomione na moim komputerze. Jest to standardowa instalacja Ubuntu na 8-rdzeniowym procesorze AMD FX-8350 8 GB. Oznacza to również, że muszę być w stanie uruchomić Twój kod.
Wiodące odpowiedzi
n = 47
w C ++ przez Ton Hospeln = 8
w Python autorstwa Maltysen
źródło
x
od[-1,0,2,1]
. Czy możesz to rozwinąć? (Wskazówka: nie jestem guru matematyki)Odpowiedzi:
C ++
Nigdy więcej naiwnego podejścia. Oceniaj tylko wewnątrz elipsoidy.
Korzysta z bibliotek armadillo, ntl, gsl i pthread. Zainstaluj za pomocą
Skompiluj program używając czegoś takiego:
W niektórych systemach może być konieczne dodanie
-lgslcblas
później-lgsl
.Uruchom z rozmiarem macierzy, po której następują elementy na STDIN:
matrix.txt
:Lub wypróbować dokładność 1e-5:
infinity.cpp
:źródło
-lgslcblas
flagi do skompilowania. Nawiasem mówiąc, niesamowita odpowiedź!Python 3
12 sekund n = 8 na moim komputerze, rdzeń Ubuntu 4.
Naprawdę naiwny, nie mam pojęcia, co robię.
Będzie to zwiększało zakres wykorzystywanych zasobów
Z
, dopóki nie uzyska wystarczająco dobrej odpowiedzi. Napisałem własne mnożenie macierzy, powinienem używać numpy.źródło