[Dla zabawy]Liczby pierwsze Mersenne?a

Odpowiedz Nowy wątek
2006-09-28 20:09
0

Jak szybko policzyć dziesiętnie 2756839 - 1
"
" oznacza potęgowanie
Łatwo to zrobić w 2 minuty, a powiedzmy w 2 sekundy?

Pozostało 580 znaków

2006-09-28 20:20
0

Da radę, ale czemu uparłeś się na system dziesiętny? Dwójkowo możesz to policzyć bardzo szybko:
Dec Bin
21 ->10
2
2 ->100
2**3 ->1000
Proste?


"Jeżeli będę zajmował się tym, co myślą głupcy, nie będę miał czasu na to, o czym myślą ludzie inteligentni",Eric-Emmanuel Schmitt

Pozostało 580 znaków

2006-09-28 20:29
0

Super :-)


Pozostało 580 znaków

2006-09-28 20:31
0

Korbi masz trochę racji, ale...
Ta liczba ma 227'832 cyfr dziesiętnych. Ile czasu zajmie konwersja bin=>dec?

Pozostało 580 znaków

2006-09-28 20:57
0

Nie patrzyłem na to od tej strony. Teraz zauważyłem również jak będzie wyglądała zamiana.
10 => 0*2*0+121=2
czyli przy tej liczbie i tak będziesz musiał wykonać obliczenie 2
756839
Czyli nic to nie zmieni :(
Tak czy inaczej będziesz musiał zaimplementować własny moduł do obsługi tak dużej liczby i zrobić szybkie potęgowanie.
Jak coś mi przyjdzie do głowy to napiszę.


"Jeżeli będę zajmował się tym, co myślą głupcy, nie będę miał czasu na to, o czym myślą ludzie inteligentni",Eric-Emmanuel Schmitt

Pozostało 580 znaków

2006-09-29 17:55
0

Niedawno odkryto kolejną Liczbę Pierwszą Mersenne'a (LPM), znamy już 44 takie liczby. Najnowsza ma 9'808'358 cyfr. Za odkrycie liczby pierwszej o więcej niż 10 milionach cyfr jest premia, starczy na dobry komputer i zostanie jeszcze na jakieś Ferrari ;-)
Liczby Mersenne?a to liczby o postaci 2^N - 1, gdzie N jest liczbą pierwszą (dwa do potęgi N minus jeden).
Więcej o tych liczbach można znaleźć w Wikipedii, choć jak to zwykle wersja angielska jest zrobiona lepiej.
Badanie czy liczba Mersenne?a jest liczbą pierwszą jest poważnym problemem, zacznijmy od czegoś prostszego.
Obliczmy ją. W układzie dziesiętnym, tak byśmy mogli ją wyświetlić czy policzyć sumę jej cyfr.
Ósmą LPM jest liczba 2^31 ? 1 równa 2'147'483'647. Tyle zmieści nam się w całkowitym, 32 bitowym typie. Ale to dopiero LPM[8]. Z kolejnymi trzeba już trochę pokombinować. Program jest prosty i krótki, 50 wierszy.

  1. W pierwszej wersji LPM[30] (czyli 2^132'049 - 1, liczba ta ma 39'751 cyfr) program liczył przez 327 sekund (prawie 5,5 minuty!).
  2. Zmieniając jedną stałą czas zmniejszył się do 82 sekund.
  3. Po dopisaniu jednej linijki czas spadł do 4,5 sekundy.
    Ponad 70 krotne przyśpieszenie! Ale gdy liczę LPM[35] trwa to już 503 sekundy, czyli ponad 8 minut.

Pascal, full debug, 1 GHz. W kolejnych obliczeniach nie korzystałem z wcześniej otrzymanych wyników. Po godzinie i 38 minutach obliczeń otrzymałem takie coś:

 # |     N    |  #cyfr  | pierwsza  Mersenne'a |sekundy
---+----------+---------+----------------------+--------
  1|        2 |       1 |                    3 |    0.0
  2|        3 |       1 |                    7 |    0.0
  3|        5 |       2 |                   31 |    0.0
  4|        7 |       3 |                  127 |    0.0
  5|       13 |       4 |                 8191 |    0.0
  6|       17 |       6 |               131071 |    0.0
  7|       19 |       6 |               524287 |    0.0
  8|       31 |      10 |           2147483647 |    0.0
  9|       61 |      19 |  2305843009213693951 |    0.0
 10|       89 |      27 | 61897001....49562111 |    0.0
 11|      107 |      33 | 16225927....10288127 |    0.0
 12|      127 |      39 | 17014118....84105727 |    0.0
 13|      521 |     157 | 68647976....15057151 |    0.0
 14|      607 |     183 | 53113799....31728127 |    0.0
 15|     1279 |     386 | 10407932....68729087 |    0.0
 16|     2203 |     664 | 14759799....97771007 |    0.0
 17|     2281 |     687 | 44608755....32836351 |   -0.0
 18|     3217 |     969 | 25911708....09315071 |   -0.0
 19|     4253 |    1281 | 19079700....50484991 |    0.0
 20|     4423 |    1332 | 28554254....08580607 |   -0.0
 21|     9689 |    2917 | 47822027....25754111 |    0.0
 22|     9941 |    2993 | 34608828....89463551 |    0.0
 23|    11213 |    3376 | 28141120....96392191 |    0.0
 24|    19937 |    6002 | 43154247....68041471 |    0.1
 25|    21701 |    6533 | 44867916....11882751 |    0.1
 26|    23209 |    6987 | 40287411....79264511 |    0.1
 27|    44497 |   13395 | 85450982....11228671 |    0.5
 28|    86243 |   25962 | 53692799....33438207 |    1.9
 29|   110503 |   33265 | 52192831....65515007 |    3.1
 30|   132049 |   39751 | 51274027....30061311 |    4.5
 31|   216091 |   65050 | 74609310....15528447 |   12.1
 32|   756839 |  227832 | 17413590....44677887 |  147.3
 33|   859433 |  258716 | 12949812....00142591 |  190.9
 34|  1257787 |  378632 | 41224577....89366527 |  407.7
 35|  1398269 |  420921 | 81471756....51315711 |  502.8
 36|  2976221 |  895932 | 62334007....29201151 | 2286.9
 37|  3021377 |  909526 | 12741168....24694271 | 2357.9
---+----------+---------+----------------------+--------
                                                 5916.1

Liczbę cyfr wyniku łatwo przewidzieć: TRUNC(N * LN(2)/LN(10)) + 1.
Poprosiłem kolegę Fourier?a o pomoc, LPM[33] policzyliśmy w kilka sekund, ale LPM[34] już się wykrzacza. Czyli jeszcze gdzieś siedzi jakieś licho.

Cały post to nie prośba o pomoc (na razie, bo FFT coś się stawia, ale jeszcze z nią powalczę), to raczej zaproszenie do zabawy. Oczywiście łatwo wziąć ze z kądyś jakiegoś gotowca, dopisać parę linijek i zakrzyknąć HEUREKA.
Powiedzmy 300 wiersz kodu.

Pozostało 580 znaków

2006-09-30 11:35
0

Szlak. Kto to przeniósł?
W prostym wydaniu to temat do ?NEWBIE?, i tak miało być!!!
Tu chyba prawie nikt nie zagląda (?Nietuzinkowe tematy?)
Choć gdyby było i tu i tam, było by jakoś krzepiące, zapładniające, itp.
Ja tam wolę gadać o takich drobiazgach, a nie o walkach z jakimś LISTBOXEM czy innym takim.
Interesuje mnie podejście początkujących, ale także i ludzi z doświadczeniem i wiedzą.
Dla młodszych kolegów i koleżanek to miał być temat ?do przemyślenia?, dla ?starszych? miejsce do podpowiedzenia czegoś ciekawego. A TU boję się że skiśnie i pies z kulawą nogą o nim nie wspomni.

Pozostało 580 znaków

2006-09-30 12:47
0
Xitami napisał(a)

Jak szybko policzyć dziesiętnie 2756839 ? 1
?
? oznacza potęgowanie
Łatwo to zrobić w 2 minuty, a powiedzmy w 2 sekundy?

# calc '2^756839-1'

Mniej niż 6 sekund na Pentium M 1.6GHz.

/ Zgodnie z życzeniem przenoszę do newbie /

// zyczenie zyczeniem, ale ja sam przeniosłem to do nietuzinkowych po to zeby nie zginęło. to nie jest byle jaki wątek. [mf]


Jest jeszcze jeden błąd :)
Unix is user friendly. It's just very particular about who it's friends are.

Pozostało 580 znaków

2006-09-30 18:54
0

Problem mnie zainteresował i właśnie szukam metody na szybkie potegowanie. W sumie to opieram się na tym, że to jest potegowanie tylko dwójki. Jak będę miał jakieś wyniki to sie pochwalę :D


"Jeżeli będę zajmował się tym, co myślą głupcy, nie będę miał czasu na to, o czym myślą ludzie inteligentni",Eric-Emmanuel Schmitt

Pozostało 580 znaków

2006-10-01 22:34
0

Zauwazcie, ze 2^n - 1 to n jedynek w zapisie binarnym, wystarzy "tylko" znalezc szybki sposob na wypisanie dziesietnej reprezentacji

Pozostało 580 znaków

2006-10-03 04:34
0

Tak przy okazji i dla przypomnienia.
Z liczbami pierwszymi Mersenne?a związane są liczby doskonałe. Załączam programik testujący pierwszość liczb Mersenne?a i wyświetlający odpowiadającą im liczbę doskonałą

var
  p, i, n: longword;   //32 bity
  s, n1: int64;        //64 bity

begin
 //jezeli 2^p-1 jest liczbą pierwszą (Mersenne'a),
 //  wtedy (2^p-1)(2^(p-1)) jest liczba doskonala
 //    przy okazji "p" jest takze liczba pierwsza
  p:=2;
  n:=3;  // n  = 2^p - 1
  n1:=2; // n1 = 2^(p-1)
  repeat

    s:=4;                   // Lucas-Lehmer test
    for i:=3 to p do        //
      s:=(s*s - 2) mod n;   //
    if (s=0) or (p=2) then  //

      writeln('Mersenne=2^', p:2, '-1=', n:12, ',  perfect number = ', n1*n);
    p+=1;
    n1:=n+1;
    n:=2*n+1;
  until p>31;
end.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0