Die ersten N Ziffern einer langen Zahl in konstanter Zeit?

Question

In einem Projekt Euler Problem muss ich mit Zahlen umgehen, die Hunderte von Ziffern haben können. Und ich muss eine Berechnung mit den ersten 9 Ziffern durchführen.

Meine Frage ist: Wie kann ich am schnellsten die ersten N Ziffern einer 100-stelligen ganzen Zahl bestimmen? Die letzten N Ziffern sind einfach mit Modulo/Rest. Für die ersten Ziffern kann ich Modulo 100 Mal anwenden, um Ziffer für Ziffer zu erhalten, oder ich kann die Zahl in String konvertieren und abschneiden, aber das ist alles lineare Zeit. Gibt es einen besseren Weg?

Answer 1

Mit dieser Funktion können Sie die Anzahl der Ziffern zählen:

(defn dec-digit-count [n]
  (inc (if (zero? n) 0
  (long (Math/floor (Math/log10 n))))))

Jetzt wissen wir, wie viele Ziffern es gibt, und wir wollen nur die ersten 9 übrig lassen. Dazu müssen wir die Zahl durch 10^(Ziffern-9) oder in Clojure teilen:

(defn first-digits [number digits]
  (unchecked-divide number (int (Math/pow 10 digits))))

Und nennen Sie es so: (first-digits your-number 9) und ich denke, es ist in konstanter Zeit. Ich bin mir nur nicht sicher über log10 Implementierung. Aber es ist sicher viel schneller als eine Modulo/Schleifen-Lösung.

Außerdem gibt es eine noch einfachere Lösung. Sie können einfach die ersten 9 Ziffern der Nummer kopieren und einfügen.

Answer 2

Vielleicht können Sie nicht eine lange Zahl, sondern ein Tupel aus zwei Zahlen verwenden: [erste-Zahlen, letzte-Zahlen]. Führen Sie Operationen mit beiden Zahlen durch, wobei Sie jedes Mal die erste Zahl rechts und die zweite Zahl links auf die erforderliche Länge (das Doppelte der Bedingung, in Ihrem Fall 9) abschneiden. Wie

222000333 * 666000555
147|852344988184|815

222111333 * 666111555
147|950925407752|815

Sie können also nur zwei kleine Berechnungen durchführen: 222 * 666 = 147[852] und 333 * 555 = [184]815

Aber die Bemerkung über die "a ha"-Lösung ist für das Projekt Euler am wichtigsten :)

Answer 3

In Java:

public class Main {
    public static void main(String[] args) throws IOException {
        long N = 7812938291232L;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
        N = 1234567890;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
        N = 1000000000;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
    }
}

ergibt

781293829
123456789
100000000

Answer 4

Es kann Ihnen helfen erste n Ziffern einer Potenzierung

und die Antwort auf diese Frage

Dieser Algorithmus hat eine Kompexität von O(b). Aber es ist einfach, ihn so zu ändern, dass er O(log b)