Ich möchte eine beliebige Zahl im Dezimalsystem in ein beliebige anderes Zahlensystem umrechnen. Wie das geht, weiß ich.
Jedoch interessiert mich im neuen Zahlensystem nur die letze Ziffer.
Beispiel:
Ich rechne 8679809789 in das 5er-System umrechnen; dabei kommt 120234012403124 heraus. Doch möchte ich eigentlich nur die letze Ziffer, die „4“, erhalten.
Muss ich immer die gesammte Zahl ausrechnen oder gibt es einen Trick, wie man nur an die letzte Ziffer ohne den Rechenaufwand für die übrigen Ziffern kommt?
Ich habe schon den Ganzen Tag drüber nachgedacht und hatte ein paar Ideen, die aber alle nicht funktioniert haben.
Vielleicht könnt ihr mir ja weiterhelfen,
Gruß
Paul
ich weiß jetzt nicht so ganz was Du willst, und welche Möglichkeiten Du zur Verfügung hast, aber viele Programmiersprachen stellen eine Modulo-Funktion (MOD) zur Verfügung. Die liefert den Rest einer Division. Damit kannst Du mit X MOD Y den Rest für das Y-System berechnen, und der entspricht genau der letzten Ziffer.
Danke für die extrem schnelle Antwort!
Das hat mir schonmal weitergeholfen.
Ich habe es eben in Python ausprobiert und für eine Division wird tatsächlich mehr Zeit als für die Modulo-Operation benötigt.
Aber wie schafft der Computer das? Wie errechnet er das Ergebnis von Modulo?
Soweit ich weiss ganz ähnlich wie die schriftliche Division,
die man in der Schule lernt, nur dass der Computer das ganze
binär macht.
Wie erklärst du dann den Zeitunterschied zwischen normaler Division und der Modulo-Operation?
Er muss es noch anders als eine normale Division machen. Aber ich weiß nicht wie; man kann bei der Division nicht einfach bei der letzten Ergebnisstelle anfangen, sondern muss von vorne jede Ziffer ermitteln um zum Schluss auf die letzte zu stoßen.
Soweit ich weiss ganz ähnlich wie die schriftliche Division,
die man in der Schule lernt, nur dass der Computer das ganze
binär macht.
Wobei mir auch die binäre Division Schwierigkeiten bereitet. Ich habe heute morgen mal versucht, die binären Grundrechenarten zu verstehen. Addition und Subtraktion habe ich verstanden; die Multiplikation auch. Die ist sogar im Vergleich zur dezimalen Entsprechung extrem einfach!
Doch die Division habe ich nicht ganz begriffen; sie ist auch nirgends ausfürhlich erklärt. Ich kann sie zwar Schritt für Schritt wie die dezimale durchführen, doch bekomme ich nicht heraus, wie oft der Divisor in die entsprechende Zwischenzahl passt. Dazu muss ich die binären Zahlen wieder in dezimale Zahlen umrechnen und dann wieder zurück. Kann man vielleicht schon anhand der binären Zahlen sehen, wie oft zB 110 in 11010 passt?
Aber wie schafft der Computer das? Wie errechnet er das
Ergebnis von Modulo?
Also Juristen können ja grundsätzlich nicht rechnen (dafür war die Antwort aber dann doch nicht so schlecht), aber Google bedienen, und da findet man ganz schnell http://mizar.org/JFM/Vol15/radix_6.html für eine schnelle Berechnungsvariante.
Soweit ich weiss ganz ähnlich wie die schriftliche Division,
die man in der Schule lernt, nur dass der Computer das ganze
binär macht.
Wie erklärst du dann den Zeitunterschied zwischen normaler
Division und der Modulo-Operation?
Welchen Zeitunterschied?
soweit ich mich erinnere gibt es auf Assembler-Level für den i386 eine Anweisung, die die Division ausführt, und in einem Register wird das Ergebnis gespeichert, in einem anderen der Rest. In sofern würde es mich wirklich wundern, wenn eine gute Implementierung einen meßbaren Zeitunterschied hätte.
(Was allerdings die wenigsten Hochsprachen können, ist beides (also Ergebnis und Rest der Division) auf einmal zur Verfügung zu stellen).
Kann man vielleicht
schon anhand der binären Zahlen sehen, wie oft zB 110 in 11010
passt?
11010 : 110 = 1
-110
--------------
0
11010 : 110 = 10
-110
--------------
01
11010 : 110 = 100
-110
--------------
010
Jetzt kann keine 0 mehr herunter gezogen werden,
also müsste man hier ein Komma setzen.
Wenn man bei Ganzzahlenarithmetik bleibt, schreibt
man stattdessen:
11010 : 110 = 100 Rest 010
In sofern würde es mich wirklich wundern, wenn eine gute
Implementierung einen meßbaren Zeitunterschied hätte.
Bei meinem ersten Versuch gab es einen messbaren Zeitunterschied. Ich habe jetzt aber nochmal ein paar Versionen durchgespielt; dabei ist der Zeitunterschied geschrumpft. Je nach der Größe des Divisors ist sogar manchmal die einfache Division in Python schneller. Gleich sind die Zeiten jedoch nie.
Danke für den Link!
Das habe ich bei meiner Suche nicht gefunden. Auf den ersten Blick war es recht unverständlich aber ich werde mal versuchen, mich durchzuarbeiten.
Das hatte ich so eigentlich schon verstanden.
Mein eigentlicher Denkfehler war aber zu kompliziert, um ihn zu erklären. Ich dachte unteranderem, dass eine Dualzahl mit n Stellen in eine Dualzahl mit n+1 Stellen mehr als 1-Mal hineinpassen könnte. Ich bin mit deiner Antwort als Denkanstoß darauf gekommen und habe bemerkt, dass die Division doch extrem einfach ist.
Wieso haben wir eigentlich je mit dem Dezimalsystem angefangen? Es hätte so viel einfacher sein können…
Ein Problem habe ich aber noch; ich habe alle Rechnungen hinbekommen bis auf die hier:
Ich vermute, dass die Auflösung von time() bei weitem nicht ausreicht um eine einzelne arithmetische Operation aufzulösen, und du vor allem rauschen misst. Ausserdem könnte ein cleverer Optimizer sowohl Division also auch Modulo wegoptimieren, weil ihr Ergebnis nicht benutzt wird.
Wenn du derart kleine Zeiten messen willst, musst du die Operation sehr oft widerholen um zu sinnvollen Eregbnissen zu kommen.
Grüße,
Moritz
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Das liefert dir denke ich nie die richtige Zeit. Dazu liefert die time() Methode die Zeit nicht genau genug.
Du musst die Division/Modulo-Operation sehr oft ausführen, damit ein ausreichend langes Zeit-Intervall entsteht, welches du mit der time() Methode genau genug messen kannst. Also beispielsweise die Operationen jeweils 1 Mio. mal ausführen und messen, wie lange das dauert.
Ich kann die Python Syntax nicht, daher Pseudocode:
t1=time()
Wiederhole 1 Mio mal:
x / y
Ende der Wiederholung
t2=time()
Wiederhole 1 Mio mal:
x % y
Ende der Wiederholung
t3=time()
print t2-t1
print t3-t2
Und dann müsstest du das ganze ein paar mal (zumindest 10x) wiederholen und die Werte mitteln, da sonst Einflüsse wie z.B. Hintergrundaktivität des Systems das Ergebnis verfälschen können.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Ich möchte eine beliebige Zahl im Dezimalsystem in ein
beliebige anderes Zahlensystem umrechnen. Wie das geht, weiß
ich.
Jedoch interessiert mich im neuen Zahlensystem nur die letze
Ziffer.
Hallo Paul,
ich sehe da ein grundsätzliches Problem: was in einem System eine endliche Ziffernfolge ist, kann in einem anderen unendlich sein. In einem System auf Basis 3 ist 1/3 eine kurze Ziffernfolge, im Zehnersystem dagegen 0.333… mit unendlich vielen Stellen. Du suchst also etwas, was es im mathematischen Sinn ev. garnicht gibt.