Restbestimmung bei grossen Zahlen |
05.04.2013, 02:29 | telli | Auf diesen Beitrag antworten » |
Restbestimmung bei grossen Zahlen Hallo MatheBoard Freunde, Ich habe mir einige Gedanken zur Restberechnung bei grossen Zahlen gemacht. Das ist wahrscheinlich Stoff der Zahlentheorie kenne mich aber in diesem Bereich nur knapp aus. Meine Frage ist: Wie kann ich bei einer Division den Rest bestimmen, ohne die Division durchführen zu müssen? Also: wobei Als Beispiel: (c = 3) Ich kann mir vorstellen, dass die konventionelle Methodik für Zahlen mit 100'000 Ziffern nicht mehr so effizient funktionieren wird. Gibt es hierfür Möglichkeiten, wie mann das subtiler lösen kann? Kann mir das jemand anhand des Beispiels erklären? Danke! Meine Ideen: habe keine.. |
||
05.04.2013, 09:47 | lgrizu | Auf diesen Beitrag antworten » |
RE: Restbestimmung bei grossen Zahlen Additive Zerlegung: So kann man dann weiter fortfahren.... |
||
05.04.2013, 19:06 | telli | Auf diesen Beitrag antworten » |
Danke für deine Antwort! Hmm verstehe ich das richtig, es gilt also: (u+v)mod x = (u)mod x + (v)mod x ? Ich suche eine zerlegung für die gilt: (u)mod x = 0 so dass (u+v)mod x = (v)mod x ? Wie finde ich aber eine solche Zerlegung? in dem Beispiel ist (u)mod x = 15'000'000 mod x Der erste Schritt ist mir klar und das 15*10^6 ein Vielfaches von 15 ist auch einleuchtend, was aber wenn der Teiler ebenfalls eine grosse Zahl ist? Sagen wir dann wird es doch schwierig eine solche Zerlegung zu finden? |
||
05.04.2013, 19:57 | Helferlein | Auf diesen Beitrag antworten » |
Die Größe der Zahlen ändert aber nichts am Prinzip der schrittweisen Verkleinerung, bis wir eine offensichtliche Größe haben. Zum Beispiel so: 28.925.583 - 36.542*500 = 28.925.583 - 18.271.000 = 10.654.583 10.654.583 - 36.542*200 = 10.654.583 - 7.308.400 = 3.346.183 3.346.183 - 36.542*50 = 3.346.183 - 1.827.100 = 1.519.083 1.519.083 - 36.542*20 = 1.519.083 - 730.840 = 788.243 788.243 - 36.542*20 = 788.243 - 730.840 = 57.403 Dabei habe ich bewusst einfache Rechnungen genutzt. Wenn man genauer teilt, braucht das Verfahren natürlich weniger Schritte. Alternativ kannst Du auch mit negativen Ergebnissen arbeiten, um größere Schritte zu verwenden. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|