[Dla zabawy]Liczby pierwsze Mersenne?a

0

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

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?

0

Super :-)

0

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

0

Nie patrzyłem na to od tej strony. Teraz zauważyłem również jak będzie wyglądała zamiana.
10 => 02**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ę.

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.

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.

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]

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

0

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

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

Sposobem przechowywania ?baaardzo dużych liczb? jest tablica, w jednej komórce tablicy możemy umieścić jedną cyfrę, ale można umieścić ich tam kilka np. 4. Czwórka jest przyjemna, bo kwadrat takiej ?cyfry? mieści się w 32 bitach (99999999=99980001). Dzięki takiemu zabiegowi liczba obliczeń zmniejsza się czterokrotnie. Liczymy wtedy nie w układzie dziesiętnym, ale w układzie o podstawie = 10?000. Przejście na układ dziesiętny jest łatwe i szybkie.
Wykonując długie mnożenia, może przydać się jakiś sposób sprawdzenia poprawności wykonywanych obliczeń. Jeżeli zsumujemy ?cyfry? czynników i iloczynu modulo PODSTAWA, wtedy prawdziwy musi być warunek (SumMnożna
SumMnożnik) mod PODSTAWA == SumIloczyn. Nie jest to 100% sposób, ale daje nam 99,99% pewności (dla podstawy==10?000), a to już coś.

0

Podnoszenie do potęgi zrobić niby łatwo:

  //w=a^k
      w:= 1
      while k>0
          w:= w * a
          k:= k-1

Pętla obróci się K razy.

Można to zrobić dowcipniej:

      w:= 1
      repeat
          if (k and 1)==1 
              w:= w * a
          k:=k >> 1                       //SHR w Pascalu
          if (k == 0) BREAK
          a:= a * a

Teraz wynik otrzymamy po log2(K) iteracjach (tyle ile bitów ma K)

0

LPM[38], 2^6972593-1, 2?098?960 cyfr, 40 sekund

int m=754974721,N,t[1<<22],a,*p,i,e=4625195,j,s,b,c,U;f(d){for(s
=1<<23;s;s/=2,d=d*1LL*d%m)if(s<N)for(p=t;p<t+N;p+=s)for(i=s,c=1;
i;i--)b=*p+p[s],p[s]=(m+*p-p[s])*1LL*c%m,*p++=b%m,c=c*1LL*d%m;
for(j=0;i<N-1;){for(s=N/2;!((j^=s)&s);s/=2);if(++i<j)a=t[i],t[i]
=t[j],t[j]=a;}}main(){*t=2;U=N=1;while(e/=2){N*=2;U=U*1LL*(m+1)/
2%m;f(362);for(p=t;p<t+N;)*p++=*p*1LL**p%m*U%m;f(415027540);for(
a=0,p=t;p<t+N;)a+=*p<<(e&1),*p++=a%10,a/=10;}while(!*--p);t[0]--
;while(p>=t)printf("%d",*p--);}

magia

www,apfloat,org Liczy LPM[44] w 40 sekund.

0

Czy wie ktoś co w powyższym programie zmienić by uzyskać inne liczby Mersenne’a?
t[1<<24], e=30611555, for (s=1<<24... prowadzi do LPM[42] czyli do 2^25964951 – 1 (prawie 8 mln. cyfr).

0

do sprawdzania może posłużyć aplikacja prime95 i śmiem przypuszczać że będzie najszybsza. można tam sprawdzić dowolną liczbe mersenne'a wpisując odpowiedni wykładnik. Co ciekawsze można wziąć udział w szukaniu liczby ponad 10mln cyfrowej i wygrać troche pieniążków. Po miesiącu mam za sobą 50% iteracji dla jednej liczby mersenne'a :D

0

FFT jest trudne ale do zrobienia, a jak zrobić operacje modulo dla tak dużych liczb?
mi w Prime95 na Core2 0,063 sek zajmuje taka iteracja

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