4. Nachkommastellen

Nachkommastellen

  • ?

    Also ich bin wohl ein Anfänger und hoffe ihr seit nicht sauer, da ich wohl triviale Fragen stelle.
    Ich möchte herausfinden ob eine Zahl durch die andere Teilbar ist.
    Das wäre auch kein Problem mit %.
    Doch % funktioniert nur mit Integer, zumindest kam er mit double nicht klar.
    Also dachte ich Teil ich die erste Zahl durch die zweite Zahl und sehe mir die Nachkommastellen an.
    Keine->Teilbar
    Welche->Unteilbar ohne Rest

    Als Hinweis: Die Zahlen bewegen sich in der Größenordnung 2^1 bis 2^3600.
    (Hält das überhaupt irgendein Datentyp aus?)

    Vielen Dank!

    0
  • ?

    Ich nehme an, du beziehst dich auf C(++)?
    fmod kann auch mit Fließkommazahlen benutzt werden.

    Als Hinweis: Die Zahlen bewegen sich in der Größenordnung 2^1 bis 2^3600.
    (Hält das überhaupt irgendein Datentyp aus?)

    Kein Standarddatentyp.
    double kann +/-1.7*10^308 ab, allerdings mit sinkender Genauigkeit.

    0
  • ?

    Ja ich beziehe mich auf C.
    Vielen Dank erstmal für den fmod-Tipp!

    Aber die Genauigkeit ist mir sehr wichtig, gibt es eine Möglichkeit genau mit großen Zahlen zu rechnen ohne auf GMP zurückzugreifen?
    Mir geht es darum es ohne externes zu Lösen das ich nicht verstehen kann.

    0
  • C

    falls du mit gcc arbeitest, kannst du auch long double benutzen. damit kannst du zahlen bis 2^16383 darstellen.

    0
  • V

    Ölscheich schrieb:

    Als Hinweis: Die Zahlen bewegen sich in der Größenordnung 2^1 bis 2^3600.

    gibt's noch mehr hinweise zu den zahlen?

    0
  • ?

    volkard schrieb:

    Ölscheich schrieb:

    Als Hinweis: Die Zahlen bewegen sich in der Größenordnung 2^1 bis 2^3600.

    gibt's noch mehr hinweise zu den zahlen?

    Es ist eine Aufgabe aus Monoid, falls das jemand kennt, aber ich will mir nicht einfach die Aufgabe von euch lösen lassen 😉

    Es geht um Wieferich Primzahlen das bedeutet man soll die 2 Stück die es unter 3600 gibt angeben und falls möglich eine dritte.
    Wieferich Primzahl bedeutet:
    (2^n-1)-1/n²=x
    Wenn x eine natürliche Zahl ist ist die Primzahl n eine Wieferich Primzahl.
    Also dachte ich mir ich löse es mit brutaler Gewalt und rechne einfach alles durch, aber da machen wohl die Datentypen nicht mit...

    0
  • V

    also haste gewonnen, wenn du eine saugeile methode findest, (2 hoch n) mod m zu rechnen.
    das geht schnell mit normalen ints.

    ich rechne mal 2^15 mod 100 aus.
    2^1 == 2
    (quadrieren)
    2^2 == 4
    (modden)
    2^2==4
    (quadrieren)
    2^4 == 16
    (modden)
    2^4 == 16
    (quadrieren)
    2^8 == 256
    (modden)
    2^8 == 56

    und dann rechne ich 28*24*22*21 und kriege 2^15 raus. natürlich wieder mit modden bei jedem zwischenergebnis.

    oder anders:

    2 hoch n ==
    wenn n ungerade, dann (2 hoch (n-1) )* n
    wenn n gerade ist, dann (2 hoch (n/2) ) hoch 2

    und bei jedem rechenschritt rechnet man gleich auch mod m rein, und dann läuft das ergebnis überhaupt nicht über.

    0
  • B

    Ölscheich schrieb:

    (2^n-1)-1/n²=x

    hä? das einzige n wo für x eine natürliche zahl rauskommt ist 1.

    edit: hab grad nachgeguckt was eine Wieferich-Primzahl ist 😃
    du solltest deine klammersetzung überdenken, gesucht ist
    (2(n-1)-1)/n2 = x 🙄

    aber volkard hat schon recht. gesucht ist eine primzahl p, für die gilt:

    **********************

    also *** ausrechnen und volkards tip zum modulorechnen anwenden 👍

    edit: nagut, lösung ist unkenntlich gemacht 💡
    habs doch nur gut gemeint 🙄

    0
  • V

    borg schrieb:

    aber volkard hat schon recht. gesucht ist eine primzahl p, für die gilt:
    *********************************
    also ***************** und volkards tip zum modulorechnen anwenden 👍

    ich wollte ihm die feinen umformungen ja nicht gleich abnehmen, wenn er so drum bettelt, es selber zu machen. wenn's nicht klappt, kann er ja nach weiteren tipps fragen.

    0
  • ?

    borg schrieb:

    Ölscheich schrieb:

    (2^n-1)-1/n²=x

    hä? das einzige n wo für x eine natürliche zahl rauskommt ist 1.

    edit: hab grad nachgeguckt was eine Wieferich-Primzahl ist 😃
    du solltest deine klammersetzung überdenken, gesucht ist
    (2(n-1)-1)/n2 = x 🙄

    Ja, ganz klarer Fall! Sorry!

    [quote]
    aber volkard hat schon recht. gesucht ist eine primzahl p, für die gilt:

    **********************
    [\quote]
    Ich verstehe zwar Volkards Methode um 2^15 mod 100 zu rechnen (um mal beim Beispiel zu bleiben). Aber wie kann ich 2^15-1 mod 100 rechnen, ihr hab ja wohl ne Lösung, aber gebt mir doch einfach nur noch mal so nen guten Tipp.
    Mein Problem ist das ich über die Zahl 2^15-1 nichts weis, außer das wenn man 1 hinzuzählt sie aus lauter 2en als Primfaktoren besteht.
    Oder stehe ich momentan mächtig auf dem Schlauch?

    0
  • C

    wenn du a mod b kennst, ist (a-1) mod b trivial.

    0
  • V

    wenn 2^15 mod 100==86, dann 2^15 mod 100 - 1 == 85.

    0
  • ?

    Das mit dem 1 abziehen ist mir jetzt absolut klar! Vielen Dank!
    Doch ich bin ein wenig über

    volkard schrieb:

    wenn 2^15 mod 100==86, dann 2^15 mod 100 - 1 == 85.

    verwundert. Mein Rechner sagt dazu 68. Aber das ist dann wohl nur ein Zahlendreher oder?
    Allerdings verstehe ich nicht wie man auf den Rest kommt.
    Klar wenn es einen Rest gibt kommt bei a mod b ein Rest raus der ungleich a ist.
    Aber wie kann ich feststellen wie hoch der Rest ist.
    Sorry für meinen Fragen und mein nicht vorhandenes Verständnis!

    0
  • V

    ja, zahlendreher. habs im kopf gemacht und verdreht.

    Aber wie kann ich feststellen wie hoch der Rest ist.

    der rest, der bei a/b rauskommt, ist doch genau a mod b.

    oder versteh ich dir frage nicht? dann mach beispiele.

    0
  • ?

    volkard schrieb:

    ich rechne mal 2^15 mod 100 aus.
    2^1 == 2
    (quadrieren)
    2^2 == 4
    (modden)
    2^2==4
    (quadrieren)
    2^4 == 16
    (modden)
    2^4 == 16
    (quadrieren)
    2^8 == 256
    (modden)
    2^8 == 56

    Aber der Rest ist natürlich nicht 56 sondern 68.
    Wie komme ich auf 68?

    0
  • V

    Ölscheich schrieb:

    volkard schrieb:

    ich rechne mal 2^15 mod 100 aus.
    2^1 == 2
    (quadrieren)
    2^2 == 4
    (modden)
    2^2==4
    (quadrieren)
    2^4 == 16
    (modden)
    2^4 == 16
    (quadrieren)
    2^8 == 256
    (modden)
    2^8 == 56

    Aber der Rest ist natürlich nicht 56 sondern 68.
    Wie komme ich auf 68?

    ich muss noch rechnen
    (alles mod 100)
    2^15 = 2^8 * 2^4 * 2^2 * 2^1

    = 56 * 16 * 4 * 2
    = 96 * 4 * 2
    = 84 * 2
    = 64

    0
  • ?

    volkard schrieb:

    Ölscheich schrieb:

    volkard schrieb:

    ich rechne mal 2^15 mod 100 aus.
    2^1 == 2
    (quadrieren)
    2^2 == 4
    (modden)
    2^2==4
    (quadrieren)
    2^4 == 16
    (modden)
    2^4 == 16
    (quadrieren)
    2^8 == 256
    (modden)
    2^8 == 56

    Aber der Rest ist natürlich nicht 56 sondern 68.
    Wie komme ich auf 68?

    ich muss noch rechnen
    (alles mod 100)
    2^15 = 2^8 * 2^4 * 2^2 * 2^1

    = 56 * 16 * 4 * 2
    = 96 * 4 * 2
    = 84 * 2
    = 64

    Also vielen Dank für die Mühe die ihr euch gemacht habt, aber ich hab das Programm geschrieben(auch wenn ihr über die effizienz und struktur schmunzeln werdet) und mit Testzahlen arbeitet es einwandfrei aber es liefert mir keine einzige Wieferich Primzahl.
    Hier ist der Code:

    #include "stdafx.h"
#include "math.h"

int exponent,h,i,letztesgesetztesarray,zahl2,mod,x,n,faktor[1000];

int main()
{
for(n=3;n<3600;n++)
{
i=0;
mod=1;
zahl2=n*n;
exponent=n-1;
h=2;
while(pow(2,h)<zahl2)
{
h=h+1;
}
while(exponent>0)
{
faktor[i]=pow(2,h);
i++;
exponent=exponent-h;
if(h=exponent)
{
h=exponent;
}
}

letztesgesetztesarray=i-1;
for(x=letztesgesetztesarray;x>=0;x--)
{
mod=mod*fmod(faktor[x],zahl2);
}
mod=mod%zahl2;
if(mod==1)
{

	printf("%i\n",n);

}
}
	return 0;
}
    0
  • B

    Ölscheich schrieb:

    auch wenn ihr über die effizienz und struktur schmunzeln werdet

    welche struktur? 😋

    #include <iostream>

int nextPrim( int p )
{
    return Nächste Primzahl nach p; // <- pseudocode, bitte implementieren!
}

bool wieferichPrim( int p )
{
    return ( 2^(p-1) Modulo p*p ) == 1; // <- pseudocode, bitte implementieren!
}

int main( )
{
    int prim = 3;
    while( prim < 3600 )
    {
        if( wieferichPrim( prim ) )
            std::cout << prim << " ist eine Wieferich-Primzahl!";
        prim = nextPrime( prim );
    }
}

    ich geb dir mal einen strukturierten rahmen, jetzt brauchst du nur noch Volkards trick implementieren und dir überlegen wie du an die nächste primzahl kommst 👍

    edit: oh, schreibst du in c oder cpp? wenn du c willst musst du die cout zeile austauschen durch "printf( "%i ist eine Wieferich-Primzahl!", prim );" und die include zeile durch "#include <stdio.h>".

    0
  • ?

    Ich hab es in das Gerüst eingebaut, aber es funktioniert immernoch nicht...
    wenn ich für exponent und zahl2 Werte eingeben rechnet er korrekt, aber er gibt mir keine Einzige Wieferich Primzahl 😡
    Bitte helft mir und sagt mir wo mein Denkfehler liegt!

    #include "stdafx.h"
#include "math.h"
int nextPrim( int p ) 
{ 
	int z=0;
	int h,keineprim=0;
	while(z==0)
	{
		p=p+2;
		h=2;
		keineprim=0;
		while(p>h*2-1)
		{
			if(p%h==0)
			{
			keineprim=1;
			}
			h=h+1;
		}
		if (keineprim==0)
		{
			z=1;
		}	
	}

    return(p);
} 

bool wieferichPrim( int p ) 
{
int exponent,h,i,letztesgesetztesarray,zahl2,mod,x;
double faktor[1000];
i=0;
mod=1;
zahl2=p*p;
exponent=p-1;
h=2;
while(pow(2,h)<zahl2)
{
h=h+1;
}
while(exponent>0)
{
faktor[i]=pow(2,h);
i++;
exponent=exponent-h;
if(h=exponent)
{
h=exponent;
}
}

letztesgesetztesarray=i-1;
for(x=letztesgesetztesarray;x>=0;x--)
{
mod=mod*fmod(faktor[x],zahl2);
}
mod=mod%zahl2;
if(mod==1)
{
	return 1;
}
return 0;

} 

int main() 
{ 
    int prim = 3;
    while( prim < 3600 ) 
    { 

        if( wieferichPrim( prim ) ) 
           printf( "%i ist eine Wieferich-Primzahl!\n", prim );

        prim = nextPrim( prim ); 

    } 
	return 0;
}
    0
  • B
     

    #include <stdio.h>

int nextPrim( int p )
{
    int z=0;
    int h,keineprim=0;
    while(z==0)
    {
        p=p+2;
        h=2;
        keineprim=0;
        while(p>h*2-1)
        {
            if(p%h==0)
            {
            keineprim=1;
            }
            h=h+1;
        }
        if (keineprim==0)
        {
            z=1;
        }   
    }
    return p; 
}

bool wieferichPrim( int p )
{
    int result = 1;
    int i;
    for( i = 0; i < p-1; i++ )
        result = ( result * 2 ) % ( p*p );

    return result == 1;
}

int main( )
{
    int prim = 3;
    while( prim < 3600 )
    {
        if( wieferichPrim( prim ) )
            printf( "%i ist eine Wieferich-Primzahl!\n", prim );
        prim = nextPrim( prim );
    }
}

    schade das du es nicht hinbekommen hast. deine primzahlfunktion funktioniert aber, ich hab sie einfach mal übernommen, auch wenn sie nicht die flotteste ist 🙂
    also auf meinem laptop(celeron 800mhz) findet er 2 wieferich-primzahlen: 1093 und 3511.
    dauert so ca. 2 sekunden.

    ps: ich hätte ja deine lösung gern korrigiert, leider versteh ich sie nicht 🙄

    0
Anmelden zum Antworten