Berechnung 16. Mersenne Primzahl dauerte ca. 234 Sek

Question

Läßt sich mit einem AMD Athlon(tm) 64 X2 Dual Core
Processor 6000+ die 16. Mersenne Primzahl noch
Schneller Berechen, als in innerhalb von ca. 234 Sekunden?

Hard- und Software:
AMD Athlon(tm) 64 X2 Dual Core Processor 6000+
Microsoft Windows 7 (6.1) Home Premium Edition 64-bit
SageMath 8.1

Berechnung der 16. Mersenne Primzahl, innerhalb
von 234.379883051 Sekunden, mit der Anwendung
der is_prime() Funktion.

600      -3       2               0.000977039337158
600      -2       3               0.000977039337158
600      -1       5               0.000977039337158
600       1       7               0.000977039337158
600       3       13             0.000977039337158
600       4       17             0.000977039337158
600       5       19             0.000977039337158
600       8        31            0.000977039337158
600       16      61            0.00195407867432
600       23      89            0.00293016433716
600       28      107          0.00586009025574
600       33      127          0.0087890625
600       138     521         1.15234398842
600       161     607         2.84375
600       341     1279       21.1552741528
600       587      2203      234.379883051

So Berechnete ich es, aber die is_prime() Funktion die ist wohl etwas

langsam? Obwohl ich die Rechzeit etwas Verbessert habe.

Ich Arbeite daran, die is_prime() Funktion durch die ist_kube_prime() Funktion

zu ersetzen.

Hard- und Software:
AMD Athlon(tm) 64 X2 Dual Core Processor 6000+
Microsoft Windows 7 (6.1) Home Premium Edition 64-bit

Berechnung der 16. Mersenne Primzahl, innerhalb von 234.379883051 Sekunden,
mit der Anwendung der is_prime() Funktion.

KubePrimZu MersenneTestV1  SageMath 23.02.2018 

# FxTeilerOffset = 0 -> 2, 3, 5  --> FxIndexTeiler  --> 0..2  
# FxTeilerOffset = 3 -> 1,  7, 11, 13, 17, .... --> FxIndexTeiler  --> 0..? 
def FxIndexZuZahl(FxIndexTeiler, FxTeilerOffset): 

    TeilerFunction = 1 
    TeilerIndexFunction = 1 
    RestIndexTeilerFunction = 1 
    SpaltenWerteArray = [1,  7, 11, 13, 17, 19, 23, 29] 
    TeilerWerte235Array = [ 2, 3, 5 ] 
    FxIndexTeiler=FxIndexTeiler+FxTeilerOffset 

    if FxIndexTeiler < 3: # Teiler 1,2,3,5 
    TeilerFunction=TeilerWerte235Array[FxIndexTeiler] 
    else:  
    RestIndexTeilerFunction = (FxIndexTeiler-3) % 8 #  % --> mod 
    TeilerFunction=int((FxIndexTeiler-RestIndexTeilerFunction)/8)*30 
    TeilerFunction=TeilerFunction+SpaltenWerteArray[RestIndexTeilerFunction] 
    return TeilerFunction 

#walltime  cputime 
IndexMaxFor=600 
FxIndexZuZahlOffset=0 
t = walltime() 
for i in range(0 , IndexMaxFor): 
    IndexZuZahl=FxIndexZuZahl(i, FxIndexZuZahlOffset) 
    if is_prime(IndexZuZahl): 
      wZahl=2IndexZuZahl-1 
      wZahlRest=wZahl%10 
      if (wZahlRest == 1) or (wZahlRest == 3) or (wZahlRest == 7) or (wZahlRest == 9): 
          if is_prime(wZahl): 
            print('%10s %10s %10s %20s' % (IndexMaxFor, i+(FxIndexZuZahlOffset-3), IndexZuZahl, walltime 

(t))) 

      600        -3          2    0.000977039337158 
      600        -2          3    0.000977039337158 
      600        -1          5    0.000977039337158 
      600          1          7    0.000977039337158 
      600          3        13    0.000977039337158 
      600          4        17    0.000977039337158 
      600          5        19    0.000977039337158 
      600          8        31    0.000977039337158 
      600        16        61    0.00195407867432 
      600        23        89    0.00293016433716 
      600        28        107    0.00586009025574 
      600        33        127        0.0087890625 
      600        138        521        1.15234398842 
      600        161        607              2.84375 
      600        341      1279        21.1552741528 
      600        587      2203        234.379883051 

Comments

KubePrims,

sollen wir daraus einen "Wissensartikel" (https://www.stacklounge.de/tag/wissensartikel) machen? 

Gruß

André

---

@KubePrims

Ich habe Deine "Frage" und den dazugehörigen Kommentar nun zusammengeführt und als "Wissensartikel" gekennzeichnet. Ist das in Deinem Sinne? Wünschst Du designtechnische Änderungen? 

Bitte beachte die Schreibregeln: https://www.stacklounge.de/schreibregeln

Darstellung von Wissen bitte als "Wissensartikel" kennzeichnen.

Fragen bitte so stellen, dass die potentiellen Antwortgeber eine Chance haben zu erkennen, was Du wissen willst. 

Danke.

---

Hiermit Bedanke ich mich, bei André Dalwigk.
Vor einigen Tagen wußte ich noch nicht dass
es die mathelounge gibt, und wie man SageMath
Programmiert. Was ein Wissensartikel ist wußte
ich auch noch nicht. Und die Frage,
"Wünschst Du designtechnische Änderungen?",
kann einfach Beantwortet werden. Ich weiß nicht.
Was ich jetzt weiß, das ist, dass die
is_prime() Funktion die meiste Rechenzeit braucht.

---

def FxZahlZuMaxExponent(FxZahlZuExponent, FxZahlTeiler):
    FxZahlExponentMax=1
    while FxZahlZuExponent>=FxZahlTeiler:
          FxZahlZuExponent=FxZahlZuExponent//FxZahlTeiler
          FxZahlExponentMax=FxZahlExponentMax+1
    return FxZahlExponentMax

# FxTeilerOffset = 0 -> 2, 3, 5  --> FxIndexTeiler  --> 0..2 
# FxTeilerOffset = 3 -> 1,  7, 11, 13, 17, .... --> FxIndexTeiler  --> 0..?
def FxIndexZuZahl(FxIndexTeiler, FxTeilerOffset):

    TeilerFunction = 1
    TeilerIndexFunction = 1
    RestIndexTeilerFunction = 1
    SpaltenWerteArray = [1,  7, 11, 13, 17, 19, 23, 29]
    TeilerWerte235Array = [ 2, 3, 5 ]
    FxIndexTeiler=FxIndexTeiler+FxTeilerOffset

    if FxIndexTeiler < 3: # Teiler 1,2,3,5
    TeilerFunction=TeilerWerte235Array[FxIndexTeiler]
    else: 
    RestIndexTeilerFunction = (FxIndexTeiler-3) % 8 #  % --> mod
    #TeilerFunction=int((FxIndexTeiler-RestIndexTeilerFunction)/8)*30
    TeilerFunction=((FxIndexTeiler-RestIndexTeilerFunction)//8)*30
    TeilerFunction=TeilerFunction+SpaltenWerteArray[RestIndexTeilerFunction]
    return TeilerFunction

RestWerteZuIndex=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29]
RestZuIndex=[0,0,2,3,4,5,6,1,8,9,10,2,12,3,14,15,
16,4,18,5,20,21,22,6,24,25,26,27,28,7]

p = [2,3,5,7,13,17,19,31,
61,89,107,127,521,607,1279,2203,
2281,3217,4253,4423,9689,9941,11213,19937,
21701,23209,44497,86243,110503,132049,216091,756839,
859433,1257787,1398269,2976221,3021377,6972593,13466917,20996011,
24036583,25964951,30402457,32582657,37156667,42643801,43112609,57885161,
74207281,77232917,0,0,0,0,0,0]

IndexAufArrayP=15
IndexMaxFor=((p[IndexAufArrayP] // 30)*8)+ RestZuIndex[p[IndexAufArrayP] % 30]
IndexMaxFor=IndexMaxFor+3+1


#walltime  cputime
IndexMinFor=0
#IndexMaxFor=50  # 345  -->  1279  591  -->  2203
FxIndexZuZahlOffset=0
t = walltime()
for i in range(IndexMinFor , IndexMaxFor):
    IndexZuZahl=FxIndexZuZahl(i, FxIndexZuZahlOffset)
    if is_prime(IndexZuZahl):
      wZahl=2^IndexZuZahl-1
      wZahlRest=wZahl % 10
      if (wZahlRest == 1) or (wZahlRest == 3) or (wZahlRest == 7) or (wZahlRest == 9):
          if is_prime(wZahl):
            IndexMinFor=FxIndexZuZahlOffset
            DezimalStellen=FxZahlZuMaxExponent(wZahl, 2)
            print('%10s %10s %10s %10s %20s' % (IndexMaxFor, i+(FxIndexZuZahlOffset-3), IndexZuZahl,

DezimalStellen%30, walltime(t)))

print""

for IndexP in range(0,IndexAufArrayP+1):
    HochZahl=p[IndexP]
    t = walltime()
    wZahl=2^HochZahl-1
    if is_prime(wZahl):
      print('%10s %35s' % (HochZahl, walltime(t)))

      591        -3          2          2                  0.0
      591        -2          3          3                  0.0
      591        -1          5          5                  0.0
      591          1          7          7                  0.0
      591          3        13        13                  0.0
      591          4        17        17                  0.0
      591          5        19        19                  0.0
      591          8        31          1                  0.0
      591        16        61          1                  0.0
      591        23        89        29                  0.0
      591        28        107        17    0.00781202316284
      591        33        127          7    0.00781202316284
      591        138        521        11            1.140625
      591        161        607          7            2.796875
      591        341      1279        19        20.4296870232
      591        587      2203        13        210.524414062

        2                                0.0
        3                                0.0
        5                                0.0
        7                                0.0
        13                                0.0
        17                                0.0
        19                                0.0
        31                                0.0
        61                                0.0
        89                                0.0
      107                                0.0
      127                    0.00781202316284
      521                            1.109375
      607                      1.64843797684
      1279                      17.3359370232
      2203                      210.766602039

---

Den Zeitvergleich, den habe ich auf Facebook Veröffentlicht!

Warum mache ich es jetzt der Öffentlichkeit zugänglich, mit dem (c)?

---

@André: Aus meiner Sicht kein Wissensartikel. Tag entfernt. 

Wissensartikel führen ins Thema ein, geben Beispiel, haben einen roten Faden mit Anfang und Ende. Dies hier ist mehr eine Frage.

Danke

---

Ich Arbeite daran, die is_prime() Funktion durch
die ist_kube_prime() Funktion zu ersetzen.

Die Bestimmung der Rechenzeit, für die Anzahl der möglichen
Primzahlpositionen (KubePrim). Bis Mersenne Primzahl 33.
Die Frage:
Darf ich die Funktion mit KubePrime Bezeichen?
Das darf doch nur der Autor?
http://www.kuberna.de/Mathe/Primzahl/primecube7NeuGross.gif
Alte Version war vom  23.01.2003.

KubePrimZu Anzahl_IsPrime25022018V1  SageMath 25.02.2018

(c) Hans-Peter Kuberna 25022018

def FxZahlZuMaxExponent(FxZahlZuExponent, FxZahlTeiler):
    FxZahlExponentMax=1
    while FxZahlZuExponent>=FxZahlTeiler:
          FxZahlZuExponent=FxZahlZuExponent//FxZahlTeiler
          FxZahlExponentMax=FxZahlExponentMax+1
    return FxZahlExponentMax

# FxTeilerOffset = 0 -> 2, 3, 5  --> FxIndexTeiler  --> 0..2 
# FxTeilerOffset = 3 -> 1,  7, 11, 13, 17, .... --> FxIndexTeiler  --> 0..?
def FxIndexZuZahl(FxIndexTeiler, FxTeilerOffset):

    TeilerFunction = 1
    TeilerIndexFunction = 1
    RestIndexTeilerFunction = 1
    SpaltenWerteArray = [1,  7, 11, 13, 17, 19, 23, 29]
    TeilerWerte235Array = [ 2, 3, 5 ]
    FxIndexTeiler=FxIndexTeiler+FxTeilerOffset

    if FxIndexTeiler < 3: # Teiler 1,2,3,5
    TeilerFunction=TeilerWerte235Array[FxIndexTeiler]
    else: 
    RestIndexTeilerFunction = (FxIndexTeiler-3) % 8 #  % --> mod
    #TeilerFunction=int((FxIndexTeiler-RestIndexTeilerFunction)/8)*30
    TeilerFunction=((FxIndexTeiler-RestIndexTeilerFunction)//8)*30
    TeilerFunction=TeilerFunction+SpaltenWerteArray[RestIndexTeilerFunction]
    return TeilerFunction

RestWerteZuIndex=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29]
RestZuIndex=[0,0,2,3,4,5,6,1,8,9,10,2,12,3,14,15,
16,4,18,5,20,21,22,6,24,25,26,27,28,7]

p = [2,3,5,7,13,17,19,31,
61,89,107,127,521,607,1279,2203,
2281,3217,4253,4423,9689,9941,11213,19937,
21701,23209,44497,86243,110503,132049,216091,756839,
859433,1257787,1398269,2976221,3021377,6972593,13466917,20996011,
24036583,25964951,30402457,32582657,37156667,42643801,43112609,57885161,
74207281,77232917,0,0,0,0,0,0]

IndexAufArrayP=32
IndexMaxFor=((p[IndexAufArrayP] // 30)*8)+ RestZuIndex[p[IndexAufArrayP] % 30]
IndexMaxFor=IndexMaxFor+3+1

#walltime  cputime
MersenneIndex=0
IndexMinFor=0
IndexMinForAlt=0
#IndexMaxFor=50  # 345  -->  1279  591  -->  2203
FxIndexZuZahlOffset=0
t = walltime()
for i in range(IndexMinFor , IndexMaxFor):
    IndexZuZahl=FxIndexZuZahl(i, FxIndexZuZahlOffset)
    if is_prime(IndexZuZahl):
      wZahl=2^IndexZuZahl-1
      wZahlRest=wZahl % 10
      if (wZahlRest == 1) or (wZahlRest == 3) or (wZahlRest == 7) or (wZahlRest == 9):
          if IndexZuZahl == p[MersenneIndex]: #if is_prime(wZahl):
            IndexMinFor=i
            IndexMinForAlt=i
            MersenneIndex=MersenneIndex+1
            DezimalStellen=FxZahlZuMaxExponent(wZahl, 10)
            print(' %4s %8s %8s %10s %10s %10s %20s' % (MersenneIndex, IndexMinFor, IndexMaxFor-

IndexMinForAlt, i+(FxIndexZuZahlOffset-3), IndexZuZahl, DezimalStellen, walltime(t)))

    1        0  229186        -3          2          1    0.00781297683716
    2        1  229185        -2          3          1    0.00781297683716
    3        2  229184        -1          5          2    0.00781297683716
    4        4  229182          1          7          3    0.00781297683716
    5        6  229180          3        13          4    0.00781297683716
    6        7  229179          4        17          6    0.00781297683716
    7        8  229178          5        19          6    0.00781297683716
    8      11  229175          8        31        10    0.00781297683716
    9      19  229167        16        61        19    0.00781297683716
  10      26  229160        23        89        27    0.00781297683716
  11      31  229155        28        107        33    0.00781297683716
  12      36  229150        33        127        39    0.00781297683716
  13      141  229045        138        521        157    0.00781297683716
  14      164  229022        161        607        183    0.00781297683716
  15      344  228842        341      1279        386    0.00781297683716
  16      590  228596        587      2203        664            0.015625
  17      611  228575        608      2281        687            0.015625
  18      860  228326        857      3217        969      0.0234379768372
  19    1137  228049      1134      4253      1281      0.0234379768372
  20    1182  228004      1179      4423      1332              0.03125
  21    2586  226600      2583      9689      2917      0.0546879768372
  22    2653  226533      2650      9941      2993              0.0625
  23    2993  226193      2990      11213      3376            0.078125
  24    5319  223867      5316      19937      6002                0.125
  25    5789  223397      5786      21701      6533              0.15625
  26    6192  222994      6189      23209      6987      0.195312976837
  27    11868  217318      11865      44497      13395            0.359375
  28    23001  206185      22998      86243      25962            0.859375
  29    29470  199716      29467    110503      33265              1.46875
  30    35216  193970      35213    132049      39751              2.28125
  31    57627  171559      57624    216091      65050        4.64843797684
  32  201826    27360    201823    756839    227832        33.1376960278
  33  229185        1    229182    859433    258716        62.4658210278

---

# FxExponent10zuTeiler26022018V5Test  Mo. 26022018
# SageMath 26.02.2018
# (c) Hans-Peter Kuberna 26022018

# sage -> Aktiviert sage:
# clear -> Loescht Eingaben
# exit  -> Beendet Eingaben

# -------------------------------------------------------------------------

# FxTeilerOffset = 0 -> 2, 3, 5  --> FxIndexTeiler  --> 0..2 
# FxTeilerOffset = 3 -> 1,  7, 11, 13, 17, .... --> FxIndexTeiler  --> 0..?
def FxIndexZuZahl(FxIndexTeiler, FxTeilerOffset):

    TeilerFunction = 1
    TeilerIndexFunction = 1
    RestIndexTeilerFunction = 1
    SpaltenWerteArray = [1,  7, 11, 13, 17, 19, 23, 29]
    TeilerWerte235Array = [ 2, 3, 5 ]
    FxIndexTeiler=FxIndexTeiler+FxTeilerOffset

    if FxIndexTeiler < 3: # Teiler 1,2,3,5
    TeilerFunction=TeilerWerte235Array[FxIndexTeiler]
    else: 
    RestIndexTeilerFunction = (FxIndexTeiler-3) % 8 #  % --> mod
    TeilerFunction=((FxIndexTeiler-RestIndexTeilerFunction)//8)*30
    TeilerFunction=TeilerFunction+SpaltenWerteArray[RestIndexTeilerFunction]
    return TeilerFunction

def FxExponent10zuTeiler(Exponent10,FxReturnTeilerMax):
   
    ReturnZahlTeiler=0
    ZahlTeiler=1
    IndexTeilerNeu=0
    Exponent10=Exponent10+1
    #Exponent10=0      # Exponent vom Vergleichswert
    ZahlExponent10=0  # Vergleichswert
    IndexTeiler=0
    ZahlTeilerGesamt=1
    ZahlTeilerGesamtAlt=1
    ZahlExponent10=10^Exponent10  # Erster Teiler 7 

    ZahlTeiler=FxIndexZuZahl(IndexTeiler , 3)
    ZahlTeilerGesamt=ZahlTeilerGesamt*ZahlTeiler
    ZahlIntTeiler=ZahlExponent10 // ZahlTeilerGesamt

    while ZahlIntTeiler> ZahlTeiler:
          ZahlTeilerAlt=ZahlTeiler
          ZahlTeiler=FxIndexZuZahl(IndexTeiler , 3)
          ZahlTeilerGesamtAlt=ZahlTeilerGesamt
          ZahlTeilerGesamt=ZahlTeilerGesamt*ZahlTeiler
          IndexTeiler=IndexTeiler+1
          ZahlIntTeiler=ZahlExponent10 // ZahlTeilerGesamt
          if ZahlTeilerGesamt>ZahlExponent10:
            ZahlTeilerGesamt=ZahlTeilerGesamtAlt
    if FxReturnTeilerMax == 0:
      ReturnZahlTeiler=ZahlTeilerAlt
    else:
      ReturnZahlTeiler=ZahlTeilerGesamtAlt
    return ReturnZahlTeiler

FxReturnMaxTeiler=0
for Exp10 in range (0,15):
    print('%6s %10s %25s %25s' % ("10 ^ ", Exp10, 10^Exp10, FxExponent10zuTeiler(Exp10,FxReturnMaxTeiler)))

print""

FxReturnMaxTeiler=1
for Exp10 in range (0,15):
    print('%6s %10s %25s %25s' % ("10 ^ ", Exp10, 10^Exp10, FxExponent10zuTeiler(Exp10,FxReturnMaxTeiler)))


10 ^          0                        1                        1
10 ^          1                        10                        7
10 ^          2                      100                        11
10 ^          3                      1000                        11
10 ^          4                    10000                        13
10 ^          5                    100000                        17
10 ^          6                  1000000                        19
10 ^          7                  10000000                        19
10 ^          8                100000000                        23
10 ^          9                1000000000                        29
10 ^          10              10000000000                        29
10 ^          11              100000000000                        31
10 ^          12            1000000000000                        37
10 ^          13            10000000000000                        37
10 ^          14          100000000000000                        41

10 ^          0                        1                        1
10 ^          1                        10                        7
10 ^          2                      100                        77
10 ^          3                      1000                        77
10 ^          4                    10000                      1001
10 ^          5                    100000                    17017
10 ^          6                  1000000                    323323
10 ^          7                  10000000                    323323
10 ^          8                100000000                  7436429
10 ^          9                1000000000                215656441
10 ^          10              10000000000                215656441
10 ^          11              100000000000                6685349671
10 ^          12            1000000000000              247357937827
10 ^          13            10000000000000              247357937827
10 ^          14          100000000000000            10141675450907

---

Es Fehlt die Umsetzung von 2^X auf 10^X. Damit Bestimmt werden kann, was der

Größte Teiler ( Dezimal ), von der Binaerzahl ist.

def FxZahlZuMaxExponent(FxZahlZuExponent, FxZahlTeiler):
    FxZahlExponentMax=1
    while FxZahlZuExponent>=FxZahlTeiler:
          FxZahlZuExponent=FxZahlZuExponent//FxZahlTeiler
          FxZahlExponentMax=FxZahlExponentMax+1
    return FxZahlExponentMax

---

# FxExponent10zuTeiler26022018V8Test  Mo. 26022018
# SageMath 26.02.2018
# (c) Hans-Peter Kuberna 26022018

# sage -> Aktiviert sage:
# clear -> Loescht Eingaben
# exit  -> Beendet Eingaben

# -------------------------------------------------------------------------

def FxZahlZuMaxExponent(FxZahlZuExponent, FxZahlTeiler):
    FxZahlExponentMax=1
    while FxZahlZuExponent>=FxZahlTeiler:
          FxZahlZuExponent=FxZahlZuExponent//FxZahlTeiler
          FxZahlExponentMax=FxZahlExponentMax+1
    return FxZahlExponentMax

# FxTeilerOffset = 0 -> 2, 3, 5  --> FxIndexTeiler  --> 0..2 
# FxTeilerOffset = 3 -> 1,  7, 11, 13, 17, .... --> FxIndexTeiler  --> 0..?
def FxIndexZuZahl(FxIndexTeiler, FxTeilerOffset):

    TeilerFunction = 1
    TeilerIndexFunction = 1
    RestIndexTeilerFunction = 1
    SpaltenWerteArray = [1,  7, 11, 13, 17, 19, 23, 29]
    TeilerWerte235Array = [ 2, 3, 5 ]
    FxIndexTeiler=FxIndexTeiler+FxTeilerOffset

    if FxIndexTeiler < 3: # Teiler 1,2,3,5
    TeilerFunction=TeilerWerte235Array[FxIndexTeiler]
    else: 
    RestIndexTeilerFunction = (FxIndexTeiler-3) % 8 #  % --> mod
    TeilerFunction=((FxIndexTeiler-RestIndexTeilerFunction)//8)*30
    TeilerFunction=TeilerFunction+SpaltenWerteArray[RestIndexTeilerFunction]
    return TeilerFunction

def FxExponent10zuTeiler(Exponent10,FxReturnTeilerMax):
   
    ReturnZahlTeiler=0
    ZahlTeiler=1
    IndexTeilerNeu=0
    Exponent10=Exponent10+1
    #Exponent10=0      # Exponent vom Vergleichswert
    ZahlExponent10=0  # Vergleichswert
    IndexTeiler=0
    ZahlTeilerGesamt=1
    ZahlTeilerGesamtAlt=1
    ZahlExponent10=10^Exponent10  # Erster Teiler 7 

    ZahlTeiler=FxIndexZuZahl(IndexTeiler , 3)
    ZahlTeilerGesamt=ZahlTeilerGesamt*ZahlTeiler
    ZahlIntTeiler=ZahlExponent10 // ZahlTeilerGesamt

    while ZahlIntTeiler> ZahlTeiler:
          ZahlTeilerAlt=ZahlTeiler
          ZahlTeiler=FxIndexZuZahl(IndexTeiler , 3)
          ZahlTeilerGesamtAlt=ZahlTeilerGesamt
          ZahlTeilerGesamt=ZahlTeilerGesamt*ZahlTeiler
          IndexTeiler=IndexTeiler+1
          ZahlIntTeiler=ZahlExponent10 // ZahlTeilerGesamt
          if ZahlTeilerGesamt>ZahlExponent10:
            ZahlTeilerGesamt=ZahlTeilerGesamtAlt
    if FxReturnTeilerMax == 0:
      ReturnZahlTeiler=ZahlTeilerAlt
    else:
      ReturnZahlTeiler=ZahlTeilerGesamtAlt
    return ReturnZahlTeiler

ExponentBasis2=32
ExponentBasis10=10
print""
ZahlZuExponentBasis2=(2^ExponentBasis2)-1
ZahlTeilerBasis=10
ZahlExponentBasis10=FxZahlZuMaxExponent(ZahlZuExponentBasis2, ZahlTeilerBasis)

print "Basis  2"
print('%6s %15s %25s' % (" 2 ^ ", ExponentBasis2, 2^ExponentBasis2))
print "Basis 10"
print('%6s %15s %25s' % ("10 ^ ", ZahlExponentBasis10, ExponentBasis10^ZahlExponentBasis10))

print""

Exp10=ZahlExponentBasis10

print "MaxTeiler    --> 1,7,11,13,17 ...."
FxReturnMaxTeiler=0
print('%6s %15s %25s %25s' % ("Bei 10 ^ ", Exp10, 10^Exp10, FxExponent10zuTeiler(Exp10,FxReturnMaxTeiler)))

print "TeilerGesamt  --> 1*7*11*13*17 ...."
FxReturnMaxTeiler=1
print('%6s %15s %25s %25s' % ("Bei 10 ^ ", Exp10, 10^Exp10, FxExponent10zuTeiler(Exp10,FxReturnMaxTeiler)))


Basis  2
  2 ^              32                4294967296
Basis 10
10 ^              10              10000000000

MaxTeiler    --> 1,7,11,13,17 ....
Bei 10 ^              10              10000000000                        29
TeilerGesamt  --> 1*7*11*13*17 ....
Bei 10 ^              10              10000000000                215656441

Answer 1

Hallo KubePrims,

da bist Du bei mir richtig!

Schon mein 1. Versuch mit Pari GP schafft mit 1 Zeile Code

p=2;g=0;while(g<16, if(ispseudoprime(u=2^p-1), g++;print1(g " " p " " u "\n"));p++)

in 1 Sekunde incl. Anzeige der großen Zahlen!

Und da ist noch nichts optimiert!!

Wie man unter http://www.pi-e.de/NextPrime-Benchmark.htm

nachlesen kann, wird das nach Optimierung (mit c++ 64...512 Bit) noch etwa 40 mal schneller...

Damit man richtig vergleichen kann, sollten größere Zeiten als 1 Sekunde, also etwa bis zur 30. Mersenne-Primzahl verglichen werden.

Außerdem sollte genau definiert sein, was angezeigt wird, und ob die Anzeige mit in die Zeitberechnung einfließen soll (da die Ausgabe allein schon zig Mio. Stellen werden kann).

Comments

Pari GP : Ist es die Anwendung, der GPU, die von den Hintergrundprozessen

nicht Gestört wird? So wie der Timer, oder so Ähnlich?

---

Die grafik engine, mit erweiterte Busbreite,
und damit erweiterten Integer Funktionen,
kann man auch für Schnelle Primzahlberechnungen anwenden.
Ohne die "Trödelei", von Windows, im Hintergrund!

---

Warum Beschäftige ich mich schon >30 Jahre mit Computer Hardware?

Die CPu kann niemals so schnell Rechnen wie die GPU.

---

grafik engine, ich möchte das für mich die primzahl bestimmst.
Und wenn der "Büro-Mensch" einige Zeichen, auf dem
Desktop sehen möchte, dann zeigst du Ihnen auch.
Die grafik engine, die stellt sich die Frage:
Gibt es hier etwas zu tun?

---

Nein! Gleich der 1. Suchbegriff von Google zu Pari GP ergibt:

https://pari.math.u-bordeaux.fr/

ein Interpreter, der analog zu SAGE & Julia

einfach nur fertige c++ Funktionen einer DLL aufruft.

Wenn man jedoch ein c++ Programm schreibt, was gleich direkt die Funktion aufruft und die Hardware der CPU besser nutzt (AVX-Befehle, mehrere Threads usw.), kann man noch viel schneller werden.

Eine GPU ist hier noch nicht nötig, solange man im Sekundenbereich ist.

Doch bevor man die Befehle & die Hardware optimiert, muss man den mathematischen Teil (Algorithmus) optimieren.

So weit ich weiß, benutzt auch SAGE die schnellen DLLs.

Versuche doch einfach mal, diese primitive while-Schleife in SAGE

und ich könnte wetten, dass Du schon damit unter 10 s kommst...

...noch dazu, wo Du nicht mal die großen Zahlen selbst, sondern nur die Exponenten ausgibst.

§1: Dein Vorfilter mit %10 und den Arrays sind nicht nötig.

§2: ispseudoprime reicht völlig aus, da diese Funktionen erst so ab 4000stellige Zahlen unsicher wird. Es kann sein, dass Sages is_prime zu streng ist und daher viel Zeit braucht.

probier mal den Befehl  is_pseudoprime

Beschreibung unter http://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html

Bei der Original c-Funktion kann man noch die Stärke (also ab welcher 2^n Wahrscheinlichkeit ein Fehler auftreten darf) einstellen.

Im 1. LINK ist beim Test 2 noch eine weitere Abkürzung (noch schneller), die bei 2^x-1 Zahlen ausreichend streng sein sollte. Aber das erst, wenn Dein  is_pseudoprime

Test immer noch zu langsam sein sollte.

---

Sage gibt Nebenbei die Anzahl der Dezimalstellen, der Mersenne Primzahl, aus.

Aber die is_prime(), die ist extrem langsam.

Und ob Pari GP jegliche Hintergrundprozesse stoppt, das weiß ich nicht!

Der Timer (CPU), der darf nicht Verändert werden, aber die Parasitärenen Programme,

wie Virenscanner, nach Hause Telefonieren und etc ist Unwichtig.

Wer die Windows Plattform Anwendet, für Mathematische Probleme,

wer Denkt daran ist Internet zu gehen?

Das Internet, das steht Momentan nicht zur Verfügung, weil die nächste Primzahl

Berechnet wird.

---

Der Interupt Handler, oder der Vektor mit der Höchsten Priorität, entscheidet

welche Programme ausgeführt werden.

Der Intel 8259 ist ein programmierbarer Unterbrechungs-Steuerbaustein.

---

Ich bin Elektroinstallateur, aber auch

Staatlich Geprüfter Techniker der Fachrichtung Elektrotechnik.

---

Meine Ergebnisse ohne jegliche Optimierung:

1 2 0
2 3 0
3 5 0
4 7 0
5 13 0
6 17 0
7 19 0
8 31 0
9 61 0
10 89 0
11 107 0
12 127 0
13 521 0.016000
14 607 0.016000
15 1279 0.14000
16 2203 0.70200

Also 0,7 Sekunden statt was mit 210 Sekunden.

Leider bist Du nicht auf eine einzige meiner Anregungen eingegangen, sondern berichtest nur über Hardware.

Hardware-Optimierung bringt oft nur winzige Verbesserungen (wenn man nicht gerade einen Q-Bit-Rechner hat -> aber die schummeln nur, das sind keine echten frei programmierbaren Rechner, sondern sind mit Compiler vergleichbar).

Softwareoptimierung hingegen bringt oft mehr als Faktor 1000 Verbesserung.

Da Werte bis zur 23. Mersenne-Primzahl ohne Optimierung im Sekundenbereich liegen:

17 2281 0.71700000
18 3217 2.58900000
19 4253 7.33200000
20 4423 8.43900000
21 9689 140.534000
22 9941 154.935000
23 11213 233.58600

lohnt eine Optimierungsarbeit erst ab der 24. Mersenne-Primzahl.

---

Auf primesdemystified habe dieses Gefunden:

"The fastest method, Croft, is over 1000 times faster than the slowest."

Aber nur weil das Bild dort mich an etwas Erinnert hat. An KubePrimeTestKreis1Gross.

Was in den 15 Jahren, seitdem ich mein Wissen, bezüglich
der Primzahlen, im Internet Veröffentlich habe, was mit
Wissen gemacht worden ist, das war mir bis jetzt egal!

Eine Zahl durch 1*7*11...*47... zu Teilen, das geht bei
(2^41)-1 nicht. Die Zahl ist 13367*164511353.
Es muß das Programm verändert werden, wenn es keinen
Teiler gibt! Auf durch 1.. 7 .. 11.. .
Dazu den Maximalen Index Bestimmen: 0 --> 1 ; 1 --> 7 ....
Die Wurzel aus (2^{41})-1 bestimmen. Es ist ca. 2^{21}.
Die aus Wurzel 2^x ist ca. 2^{x/2}.
Daraus den Maximalen Index Berechnen.

Welche Primzahl*Primzahl hat die Endziffer 1?
( 2199023255551 ) => ...7 * ...13
 
' Index  0,  1,  2,  3,  4,  5,  6,  7
' Zahl    1,  7, 11, 13, 17, 19, 23, 29

' Index 1, 4
'  7*13=  91 ;  7*23= 161 ;  7*43= 301 ;  7*53= 371 ;  7*63= 441
' 17*13= 221 ; 17*23= 391 ; 17*43= 731 ; 17*53= 901 ; 17*63=1071

Geht die Teilung nicht, dann die Endziffer Beachten!