Bei der Challenge vom letzten Monat musste ich vermeiden, eine Situation zu schaffen, in der ein Überlauffehler zusätzliche Komplikationen verursachen könnte. Tatsächlich basiert der Algorithmus zur modularen Potenzierung auf Miller-Rabin isPrime Um dieses Problem zu vermeiden, wurde eine Routine geschrieben. Unabhängig von der Programmiersprache werden Sie zwangsläufig auf dieses Problem stoßen.
Ein Überlauffehler tritt auf, wenn Sie versuchen, eine Operation auszuführen, die mehr Bits erfordert, als zur Darstellung der Ergebnisse verfügbar sind. Dies tritt häufig, aber nicht ausschließlich, bei der Arbeit mit großen ganzen Zahlen auf. Probieren Sie zum Beispiel die folgenden Beispiele aus:
//Example 1
x = 9007199254740992;
For(i=1,i<=10,i++,Print(x+i));
x = 9007199254740992;
For(i=1,i<=10,i++,Print(x-i));
//Example 2
n1 = 9007199254740999;
n2 = 1;
Print(n1-n2);
2 53 ist die größte ganze Zahl, die JMP kann darstellen, bevor ein Überlauf auftritt. Hier ist eine schöne Erklärung der Gleitkommadarstellung (Alle Zahlen in JMP sind Gleitkommazahlen). Für die Herausforderung dieses Monats würde ich mich freuen, wenn Sie Methoden zum Addieren und Subtrahieren von Zahlen entwickeln würden, die die Darstellung ganzer Zahlen in JMP überfordern würden. Erstellen Sie zwei Funktionen
- subtractBig ( n1 , n2 ) Wo n1 Und n2 sind beide ganze Zahlen (positiv, negativ oder 0) in Textform. Gibt einen Wert in Textform zurück.
- addBig ( n1 ,< n2 >) wo
n1 – Ganzzahl in Textform oder, falls n2 ist leer, eine Liste von ganzen Zahlen (positiv, negativ oder 0) in Textform.
n2 – Ganzzahl in Textform
Gibt einen Wert in Textform zurück.
Beispiele
subtractBig („9007199254740999“, „9007199254740998“) gibt „1“ zurück
addBig („9007199254740992“, „7“) gibt „9007199254740999“ zurück
addBig („9007199254740999“, „-1“, „11“}) gibt „9007199254741009“ zurück
Wertung
- 5 Punkte für eine Version von addBig Das kann 1) zwei Zahlen mit höchstens 1000 Ziffern in weniger als 30 Sekunden addieren und 2) die Summe einer Liste mit höchstens 100 100-stelligen Zahlen in weniger als 30 Sekunden ermitteln. Teil 1) wird mit 10 verschiedenen Zahlensätzen getestet. Die Anzahl der Ziffern in jeder Zahl muss nicht unbedingt gleich sein. Für alle Einsendungen wird derselbe 10er-Satz verwendet.
- 3 zusätzliche Punkte für subtractBig , das (x – y) in weniger als 30 Sekunden berechnen muss, wobei x und y Zahlen mit höchstens 1000 Stellen sind. Es werden zehn verschiedene Zahlensätze verwendet. Die Anzahl der Ziffern für jede Zahl muss nicht unbedingt gleich sein. Für alle Einsendungen wird derselbe 10er-Satz verwendet.
- 3 Bonuspunkte für die addBig Einreichung, die die größte (Anzahl der Ziffern) korrekt addieren kann n1 Und n2 gleicher Länge in weniger als 5 Sekunden. (2 Punkte für 2 nd , 1 für die 3 rd )
- 3 Bonuspunkte für die addBig Einreichung, die die meisten 1000-stelligen Zahlen in weniger als 5 Sekunden richtig addieren kann (2 Punkte für 2 nd , 1 Punkt für 3 rd ).
- Jeweils 3 Extrapunkte, wenn eine Einreichung genauso schnell oder schneller ist als die Einreichung eines JMP-Mitarbeiters.
Einsendeschluss ist Montag, der 15. Juni, 23:59 Uhr Eastern Time (US). Viel Glück!
Nur eine Erinnerung. Heute Abend ist die Frist für die Einreichung von Challenge 3.
Es ist wahrscheinlich eine Klarstellung wert, da dies etwas verwirrend ist. Beide Funktionen (und beide Fälle für addBig ) sollte in der Lage sein, Zahlen unterschiedlicher Länge und Vorzeichen zu verarbeiten. Ich werde das testen. Bei der Ermittlung der Punkte für Bonusgeschwindigkeit und -größe verwende ich Zahlen gleicher Länge.
Don
Ich habe Ihre Herausforderungsbeschreibung gestern Abend noch einmal gelesen und denke, dass Sie die Anforderungen klar erläutern.Fühlen Sie sich frei, meine Fragen zu ignorieren.Das tut mir leid!
-Dave
Als Antwort auf meine Frage – ich habe gerade Ihr drittes Beispiel gelesen – würde dies vorschlagen (ich) dass wir nicht davon ausgehen können, dass alle Zahlen in der n1-Liste die gleiche Anzahl von Ziffern haben.Auch, (ii) es könnte sein, dass die n1-Liste negative Zahlen enthält.Vermutlich dann (iii) Für den Fall zweier Zahlen n1 und n2 könnte eine oder beide davon negativ sein?
Vielleicht können Sie die drei Punkte, die ich erwähnt habe, einfach klarstellen. Danke.
Können wir für den Fall, dass wir die Liste der Zahlen hinzufügen, davon ausgehen, dass jede Zahl die gleiche Länge hat, oder müssen wir dies testen? (Müssen wir also den allgemeinen Fall behandeln oder nur das von Ihnen beschriebene Testszenario?)
