Wie kann man diesen Code sauberer und effizienter schreiben?

Guten Abend,

ich arbeite gerade an einem Projekt, bei dem ich unter anderem schnell, effizient und sicher (also nicht nur probabilistisch) prüfen muss, ob eine Zahl prim ist oder nicht. Dafür verwende ich den Fermat'schen Primzahltest - der wirkt mir für das Projekt am schlauesten (oder?), weil er einfach ist und mir Listen mit Pseudoprimzahlen bis zu ausreichender Größe vorliegen, sodass der Primzahltest sicher ist.

Je nachdem, bis wohin ich Primzahlen prüfen will, enthält die Liste pseudoprimes alle Pseudoprimzahlen bis zu einer gewissen Größe.

def exponentiateModular(a: int, b: int, n: int) -> int: # calculates a^b mod n
    powersModN = [a] # a^k for each k <= b
    while 2 ** len(powersModN) <= b:
        powersModN.append(powersModN[-1] ** 2 % n)
    binaryString = bin(b)[2:] # binary string without 0b
    res = 1
    for index, digit in enumerate(reversed(binaryString)):
        if digit == '1':
            res *= powersModN[index] # powersModN[x] = 3^(2^x) mod n
    return res % n

def isPrime(p: int) -> bool: # Fermat
    return exponentiateModular(2, p - 1, p) == 1 and p not in pseudoprimes

Kann ich diesen Code noch optimieren? (Python) Wie kann die exponentiateModular-Methode mit der momentan logarithmischen Laufzeit noch schneller laufen?

Vielen Dank schon mal im Voraus.

LG

PC, Computer, Technik, programmieren, Programmierung, Primzahlen, Python, Technologie
4 Antworten
Java Ellipse aus Linien zeichnen - Fehler wegen nur ganzzahlig möglichen Winkeln?

Hallo,

ich möchte in Java einen Farbkreis in Form eines Ellipse zeichnen; dafür zeichne ich Linien verschiedener Farben vom Mittelpunkt aus in einem bestimmten Winkel zum Endpunkt, der auf der imaginären Form einer Ellipse liegt. So weit so gut, das funktioniert auch.

Mein Problem allerdings ist, dass die Farbkreis-Ellipse nach dem Zeichnen ganz und gar nicht so aussieht, wie sie aussehen sollte:

Ich vermute, dass es daran liegt, dass die Berechnungen Gleitkommazahlen ergeben, die ich aber ganzzahlig runden muss, damit ich damit das Ende einer Linie als Punkt kennzeichnen kann. Dadurch liegen die Linien womöglich an manchen Stellen aufeinander und an anderen Stellen existieren keine Linien (ist das so?).

Hier der Code zum Definieren der Linien mit Farbe und Index:

Line[] lines = new Line[3*255]; 
int[] color = {255,0,0}; 
for(int i=0; i<3; i++) 
   for(int j=0; j<255; j++){ 
      color[i]--; color[(i+1)%3]++; 
      lines[i*255 + j] = new Line(i*255 + j + 1, new Color(color[0], color[1], color[2])); 
} 

Zeichne ich die Linien mit aufsteigender Länge nebeneinander, funktioniert der Farbübergang so wie geplant - nur die Farbellipse macht Probleme.

Hier der Konstruktor der Line-Klasse (mehr enthält sie mom. noch nicht):

Line(int index, Color color){
	this.index = index;
	this.color = color;
	this.angle = this.index*360./765; //3*255 Farben
    int a = Ellipse.a, b = Ellipse.b;
    double x = (a*b/Math.sqrt(b*b+Math.pow(a*Math.tan(angle), 2))),
           y = x*Math.tan(angle);
    if(angle > 90 && angle < 270) x = -x;
    this.end = new Point((int) x, (int) y);
    this.length = Point.distance(0, 0, end.x, end.y);
}

Die paint-Methode der Frame Klasse (ja, ich programmiere in Swing, die Ellipse ist eher ein quick&dirty-Projekt):

@Override public void paint(Graphics g){
	for(int i=0; i<3*255; i++){ 
       g.setColor(lines[i].color); 
       g.drawLine(m.x, m.y, lines[i].end.x+m.x, lines[i].end.y+m.y); 
    } 
} 

Warum sieht die gezeichnete Ellipse so grausam im Gegensatz zum Dreieck aus und separiert optisch so stark zwischen rot und blau? Woran liegt das bzw. wie kann ich es beheben?

Vielen Dank schon mal im Voraus.

LG

Computer, Mathematik, zeichnen, Mathe, programmieren, Java, Programmierung, Swing, Ellipse
5 Antworten