Jump to content
Forum Kopalni Wiedzy

Recommended Posts

9 minut temu, Jajcenty napisał:

założył że rozwiązanie ma postać: x^3 + (-x/2)^3 + z^3 = 42. Jeśli dobrze zrouzmiałem....

A to ja inaczej zrozumiałem bo widzę u niego 3 zmienne :)

 

Ps.

Cofam pytanie o wydajność, python jest w tym gówniany, to już java bije go na głowę. (muszę przepisać :) )

ps.

A teraz u Ciebie widzę już dwie zmienne :) 

Share this post


Link to post
Share on other sites
27 minut temu, Afordancja napisał:

A teraz u Ciebie widzę już dwie zmienne

Nieporozumienie. Pogo chce by przemiatać y od -1 do -x/2. A to nie to samo co funkcja jednej zmiennej. Jednakże jeśli założyć, rozwiązanie w postaci: x^3 + f(x)^3 + g(x)^3 = 42

to wogóle samograj. To chyba postulat Wilka - szybkie znalezienie przybliżenia i dokładne sprawdzenie otoczenia. Na f i g już nałożyliśmy  pewne warunki f= (a-x)^3; g=(b-x)^3

To tylko luźne pomysły. Niestety nie ma czasu by je jakoś weryfikować

Share this post


Link to post
Share on other sites
17 minut temu, Jajcenty napisał:

"The total computation used approximately 23 core-years over one month of real time."

uuuu, tak właśnie coś mi się wydawało, że mi to wolno liczy ;) 

No ale spoko, do jutra wieczora, może do końca weekendu kombinuję, bo trochę mam inne podejście i chcę przeszukać pewien podzbiór, tylko muszę przedefiniować problem 

Share this post


Link to post
Share on other sites
Posted (edited)
12 godzin temu, pogo napisał:
  • Za x podstawiamy 1014 i zaczynamy dodawać 1 w każdym kółku - może i tu da się coś z góry wyeliminować?
  • Za y zawsze podstawiamy liczbę ujemną z zakresu od -1 do -x/2 (drugą połowę sprawdzimy szukając z)
  • Szukamy liczby z, która da wynik możliwie najbliższy 42 lub -42 (tu jest jeszcze pole do popisu, jak to zrobić optymalnie). Jak nie uzyskamy równo 42 ani -42 to do x dodajemy 1 i zaczynamy od nowa.

Ja przeszukuję podobnie, nawet udało mi się wyeliminować potęgowanie i pierwiastkowanie, ale pozostaje kwestia precyzji.

Weźcie sobie nawet rozwiązanie dla 33, 8866128975287520^3 niby się wykonuje, ale obcina końcówkę, więc do d takie liczenie.

Aproksymacja też jest ok, ale na razie też idzie wolno.

"Z" można szukać, a można nie "szukać". Bierzesz  x^3-y^3-/+42 = A, i sprawdzasz czy cbrt(A) daje integera.

Ja mam jeszcze inny sposób...

Przepisuję to teraz do C i odpale z CUDA, tylko kwestia obsługi dużych liczb.

a propos, to jest jakaś nagroda za to oprócz fejmu ? :) 

 

Edited by radar

Share this post


Link to post
Share on other sites

hm..ciekawe, że ta druga liczba to liczba pierwsza, taki przypadek?

i ciekawe, że jak dodamy (Bez potęgowania) to też otrzymujemy liczbę pierwszą. 

Share this post


Link to post
Share on other sites
10 godzin temu, radar napisał:

 

Weźcie sobie nawet rozwiązanie dla 33, 8866128975287520^3 niby się wykonuje, ale obcina końcówkę, więc do d takie liczenie.

hm.. u mnie liczy ja najbardziej ok. (java i python)

 

Share this post


Link to post
Share on other sites
44 minuty temu, Afordancja napisał:

hm.. u mnie liczy ja najbardziej ok. (java i python)

Python liczy na dowolnych długościach. Ja piszę głównie C# i tu wybór typu jest kluczowy, decimal  to 29 cyfr - tu śmiesznie za mało. Trzeba się posiłkować  BigInteger - niby bez granic ale nie jestem przekonany :) wolałbym jakie dwa decimale złączyć.

Share this post


Link to post
Share on other sites
4 godziny temu, Afordancja napisał:

m.. u mnie liczy ja najbardziej ok. (java i python)

 

3 godziny temu, Jajcenty napisał:

Python liczy na dowolnych długościach

Liczy, liczy, jak się po drodze nie skorzysta z excela a ten k...n zmienil mi koncówkę z 528 na 520, to i ^3 źle liczyło. Teraz liczy już dobrze :)

Nie będę się jednak wczuwał w pythona, bo jak wspomniałem przepisuję na C, chociaż już teraz w pythonie zrobiłem dużo optymalizacji i liczy jakieś 10^8 na sekundę na CPU, co jednak przy 10^16^3 dalej jest słabe :)

Share this post


Link to post
Share on other sites

Widzę jeden drobny problem. 

Osiągnięcie liczb na poziomie 1015 zajmie 9 razy tyle czasu co przeszukanie wszystkich 1014... 

Więc mówicie miesiąc na 23 rdzeniach... Zakładam, że jesteśmy lepsi od oryginalnego programisty (co już kilka razy pokazaliśmy), więc pewnie szukanie TYLKO dla 42 w zakresie do 1014 zrobilibyśmy w max 2 dni (też łatwiej się liczy dla jednego celu, niż dla wszystkich w przedziale 1-100, bo odpada zapisywanie "zbędnych" wyników).

I nie... nie zacząłem nawet pisać i myśleć o wydajności. I patrząc na mój plan zajęć pozapracowych nie widzę szans by się za to zabrać... 

Share this post


Link to post
Share on other sites
2 godziny temu, pogo napisał:

Więc mówicie miesiąc na 23 rdzeniach...

Źle czytasz. 23 rdzenio-lata w ciągu miesiąca, czyli 23*12 miesięcy. W zaokrągleniu - ponad miesiąc na 256 rdzeniach.

Share this post


Link to post
Share on other sites
3 godziny temu, pogo napisał:

Widzę jeden drobny problem. 

Osiągnięcie liczb na poziomie 1015 zajmie 9 razy tyle czasu co przeszukanie wszystkich 1014..

Ja bym w ogóle nie liczył 1014, bo zakładając, że gość dobrze policzył do 1016 to można zacząć od 1017, a ponieważ sprawa jest medialna, inni ludzie oraz inni naukowcy "przypomnieli" sobie o problemie i na pewno więcej ludzi nad tym pracuje już na 1017 to w związku z tym zacząłbym od 1018;)

 

  • Haha (0) 1
  • Upvote (+1) 1

Share this post


Link to post
Share on other sites
Posted (edited)
7 godzin temu, radar napisał:

na pewno więcej ludzi nad tym pracuje już na 1017 to w związku z tym zacząłbym od 1018

No ale rozwiązanie może być gdzieś tam właśnie (albo nie) ;)

No i dylemat jest taki czy np. 2 pierwsze są powyżej 10**16 a trzecie nie musi, czy jednak szukać od razu wszystkie powyżej, bo inni pewnie już sprawdzili.

Więc ja dla pewności szukam trochę inaczej. 

I w tym wariancie (potem trochę go rozszerzę a teraz liczę na sępa ;) )sprawdzam liczby dwie 10**23  i trzecia 10**16 . Z czego różnica między pierwszymi dwoma jest stała. 

 

[edit]

Teraz kombinuję jak zoptymalizować pozostałe różnice, bo niektóre różnice między liczbami nie mają sensu dla danej liczby (im większa różnica tym rzadziej występują rozwiązania)

Ogólnie przekształciłem problem do 

N*(N-p) = (X**3 + 33 - p**3) / (3 * p) 
Gdzie X to trzecie liczba, a N to większa liczba z dwóch  a p to różnica między większą a drugą. 
Wzór może wydrawać się gorszy, ale przy przepisaniu, jest dla mnie o wiele bardziej efektywny (szukam binarnie) niż po prostu no i ten dzielnik potem wyklucza mi od razu albo X albo różnice(p) zależy jak do tego podejdę

[edit2]

Zerknąłem pobieżnie, i wychodzi na to, że te liczby pierwsze nie są przypadkiem, widzę, że podobną ścieżką co autor ale troszkę inną, (u niego d, u mnie p), problemem są tylko liczby pierwsze bo dla wielkich liczb jest coraz trudniej. a z drugiej strony, można użyć algorytmu na wyszukiwanie dzielników i potem moje dalsze wyszukiwanie binarne do pewnego punktu.(który będzie wyliczany od poprzednich wyliczeń) .

 

O kurcze ale chaotycznie napisałem i nic nie będzie wiadomo o co chodzi... no ale olać już ;) 

 

ok, algorytm do wyszukiwania dzielników nie różni się niczym od wyszukiwania liczb pierwszych w sumie ;) 

Edited by Afordancja

Share this post


Link to post
Share on other sites

No właśnie miałem mówić, że równianie jak u autora odkrycia , bo...

3 godziny temu, Afordancja napisał:

N*(N-p) = (X**3 + 33 - p**3) / (3 * p) 

...nawet szukasz 33 zamiast 42:)

Share this post


Link to post
Share on other sites
12 minut temu, radar napisał:

nawet szukasz 33 zamiast 42:)

a nie nie, hehe, szukam 42, skopiowałęm z kodu testowego (bo sprawdzałem czy pasuje dla 33)

Share this post


Link to post
Share on other sites

Z przykrością stwierdzam, że nie napisałem nawet linijki kodu w ten weekend... ale myślami jestem z problemem :)

Jakieś postępy?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×