Division mit Rest bei Python selbst schreiben?

Hallöle, Es gibt bei Python den "mod"-Befehl, oder auch den %-Befehl, um eine Division mit Rest auszuführen. Wir sollen als Aufgabe eine Funktion selbst schreiben, die das kann, sprich nicht den bereits vorhandenen Operator nutzen. Ich bin jetzt im Internet auf der Suche nach einer Formel, mit der man den Rest genau bestimmen kann, bisher ohne Erfolg (vielleicht gibt's das ja auch gar nicht :D). Hat jemand eine andere Idee/Denkanstoß, wie ich das Problem lösen könnte?

Answer 1

[Suboptimierer]

mod gibt ja den Rest r, also a / b = c + r/b

Du erhöhst in einer Schleife x von 0 an solange um b, bis x>a werden würde.

Beispiel 17/3:
x1 = 0
x2 = 3
x3 = 6
...
x6 = 15

Dann nimmst du a - xn-1 = Rest

Im Beispiel:
17-15 = 2 = Rest

Woher ich das weiß: Studium / Ausbildung – Mathematik

Comments

[Suboptimierer]

Du kannst dir den Speicher für x auch sparen, wenn du einfach in einer Schleife immer

a := a-b 

rechnest, und zwar solange bis

a-b < 0 

ist. Dann steht in a der Rest. Das ist noch ein bisschen einfacher.

[Suboptimierer]

@Suboptimierer

In C sähe das so aus (ungetestet)

double Mod(double a, double b);
{
  return (a-b)<0 ? a : Mod(a-b, b);
}

[Luxemburgerli]

Merci :-) Hab's zwar am Ende ein wenig anders gelöst, aber deine Idee war der Auslöser!

[Suboptimierer]

@Luxemburgerli

Das freut mich zu hören.

Natürlich gibt es mehrere Möglichkeiten, das Problem zu lösen. Der Vorteil an meiner Methode ist, dass nur Additionen/Subtraktionen durchgeführt werden, was eine geringe Komplexität des Algorithmusses bewirkt. Der Nachteil ist die Rekursion. Die meisten Programme werden bei Problemen wie 734897894357845278 mod 3 mit obigem Algorithmus aufgeben, weil der Aufrufstack zu tief geschachtelt wird.

Wenn man allerdings mehr "Handwerkszeug" hat, kommt man schneller zum Ziel. Wenn man beispielsweise schon eine Funktion hat (nennen wir sie "int"), die die Kommastellen einer Gleitkommazahl vernachlässigt, dann hätte man auch folgendes schreiben können (C):

double Mod(double a, double b)
{
  return (a/b - int(a/b)) * b;
}

Oder, was im Beispiel "734897894357845278 mod 3" günstiger wäre:

Das 10^x fache von b immer von a abziehen, also erstmal b solange *10 nehmen wie es kleiner als a ist, dann aneu = a-bneu, dann wieder b verzehnfachen, usw. oder man versucht mit einer Logarithmusfunktion gleich die Anzahl der Stellen von a herauszubekommen.

Answer 2

[tobistenzel]

Erstmal ein paar Fragen:

Welche Python-Version? Von 2.x nach 3.x hat sich die Bedeutung von "/" geändert, deswegen.

mod gibts nicht, du meinst eher divmod für die Division mit Rest, oder? Das sollt ihr selber schreiben, oder?

% ist auch nicht erlaubt?