Wie schnell können wir alle Vierquadratkombinationen finden, die sich zu N summieren?

12

Bei Stack Overflow wurde eine Frage gestellt ( hier ):

Bei einer gegebenen Ganzzahl N werden alle möglichen Kombinationen von Ganzzahlwerten von A,B,C und D ausgedruckt, die die Gleichung lösen A2+B2+C2+D2=N.

Diese Frage steht natürlich im Zusammenhang mit Bachets zahlentheoretischer Vermutung (manchmal wegen seines Beweises auch Lagranges Vierquadrat-Theorem genannt). Es gibt einige Artikel, in denen diskutiert wird, wie eine einzige Lösung gefunden werden kann, aber ich habe nichts gefunden, was darüber spricht, wie schnell wir alle Lösungen für ein bestimmtes N (dh alle Kombinationen , nicht alle Permutationen ).

Ich habe ziemlich viel darüber nachgedacht und es scheint mir, dass es in Zeit und Raum gelöst werden kann , wobei N die gewünschte Summe ist. Da ich jedoch keine vorherigen Informationen zu diesem Thema habe, bin ich mir nicht sicher, ob dies ein erheblicher Anspruch meinerseits oder nur ein triviales, offensichtliches oder bereits bekanntes Ergebnis ist.O(N)N

Die Frage ist also, wie schnell wir alle Vierquadratsummen für ein gegebenes .N


OK, hier ist der (fast) O (N) -Algorithmus, an den ich gedacht habe. Die ersten beiden unterstützenden Funktionen, eine nächste Ganzzahl-Quadratwurzelfunktion:

    // the nearest integer whose square is less than or equal to N
    public int SquRt(int N)
    {
        return (int)Math.Sqrt((double)N);
    }

Und eine Funktion, die alle TwoSquare-Paare zurückgibt, die von 0 nach N summieren:

    // Returns a list of all sums of two squares less than or equal to N, in order.
    public List<List<int[]>> TwoSquareSumsLessThan(int N)
    {
        //Make the index array
        List<int[]>[] Sum2Sqs = new List<int[]>[N + 1];

        //get the base square root, which is the maximum possible root value
        int baseRt = SquRt(N);

        for (int i = baseRt; i >= 0; i--)
        {
            for (int j = 0; j <= i; j++)
            {
                int sum = (i * i) + (j * j);
                if (sum > N)
                {
                    break;
                }
                else
                {
                    //make the new pair
                    int[] sumPair = { i, j };
                    //get the sumList entry
                    List<int[]> sumLst;
                    if (Sum2Sqs[sum] == null)
                    {   
                        // make it if we need to
                        sumLst = new List<int[]>();
                        Sum2Sqs[sum] = sumLst;
                    }
                    else
                    {
                        sumLst = Sum2Sqs[sum];
                    }
                    // add the pair to the correct list
                    sumLst.Add(sumPair);
                }
            }
        }

        //collapse the index array down to a sequential list
        List<List<int[]>> result = new List<List<int[]>>();
        for (int nn = 0; nn <= N; nn++)
        {
            if (Sum2Sqs[nn] != null) result.Add(Sum2Sqs[nn]);
        }

        return result;
    }

Schließlich der Algorithmus selbst:

    // Return a list of all integer quads (a,b,c,d), where:
    //      a^2 + b^2 + c^2 + d^2 = N,
    // and  a >= b >= c >= d,
    // and  a,b,c,d >= 0
    public List<int[]> FindAllFourSquares(int N)
    {
        // get all two-square sums <= N, in descending order
        List<List<int[]>> Sqr2s = TwoSquareSumsLessThan(N);

        // Cross the descending list of two-square sums <= N with
        // the same list in ascending order, using a Merge-Match
        // algorithm to find all combinations of pairs of two-square
        // sums that add up to N
        List<int[]> hiList, loList;
        int[] hp, lp;
        int hiSum, loSum;
        List<int[]> results = new List<int[]>();
        int prevHi = -1;
        int prevLo = -1;

        //  Set the Merge sources to the highest and lowest entries in the list
        int hi = Sqr2s.Count - 1;
        int lo = 0;

        //  Merge until done ..
        while (hi >= lo)
        {
            // check to see if the points have moved
            if (hi != prevHi)
            {
                hiList = Sqr2s[hi];
                hp = hiList[0];     // these lists cannot be empty
                hiSum = hp[0] * hp[0] + hp[1] * hp[1];
                prevHi = hi;
            }
            if (lo != prevLo)
            {
                loList = Sqr2s[lo];
                lp = loList[0];     // these lists cannot be empty
                loSum = lp[0] * lp[0] + lp[1] * lp[1];
                prevLo = lo;
            }

            // do the two entries' sums together add up to N?
            if (hiSum + loSum == N)
            {
                // they add up, so cross the two sum-lists over each other
                foreach (int[] hiPair in hiList)
                {
                    foreach (int[] loPair in loList)
                    {
                        // make a new 4-tuple and fill it
                        int[] quad = new int[4];
                        quad[0] = hiPair[0];
                        quad[1] = hiPair[1];
                        quad[2] = loPair[0];
                        quad[3] = loPair[1];

                        // only keep those cases where the tuple is already sorted
                        //(otherwise it's a duplicate entry)
                        if (quad[1] >= quad[2]) //(only need to check this one case, the others are implicit)
                        {
                            results.Add(quad);
                        }
                        //(there's a special case where all values of the 4-tuple are equal
                        // that should be handled to prevent duplicate entries, but I'm
                        // skipping it for now)
                    }
                }
                // both the HI and LO points must be moved after a Match
                hi--;
                lo++;
            }
            else if (hiSum + loSum < N)
            {
                lo++;   // too low, so must increase the LO point
            }
            else    // must be > N
            {
                hi--;   // too high, so must decrease the HI point
            }
        }
        return results;
    }

Wie ich zuvor sagte, sollte es ziemlich nahe an O (N) liegen, wie Yuval Filmus jedoch betont, da die Anzahl der Vierquadratlösungen für N in Ordnung sein kann (N ln ln N), dann könnte es dieser Algorithmus nicht sein weniger als das.

RBarryYoung
quelle
Ja, bitte poste es. Ich arbeite noch an den Details des linearen Algorithmus, bin mir aber ziemlich sicher, dass er gültig ist.
RBarryYoung
5
Ω(NloglogN)O(N)
1
i=0N/2|hiListNi||loListi|
Ja, das ist richtig, aber Ihre Formel ist ein bisschen abweichend, weil ich zuerst von 0 bis ca. reicht. N PI / 8 und zweitens nur ein Bruchteil der Werte von i erfüllen hiList (Ni) + loList (i) = N, daher werden sie nicht alle hinzugefügt. Auf jeden Fall gibt es keine Möglichkeit, dies zu beheben, und ich bin hübsch Stellen Sie sicher, dass dies die minimal mögliche Komplexität von O (N log (log (N))) ergibt .
RBarryYoung
Aber wir können einen Algorithmus haben, der in O läuft (max (N, "Anzahl der Lösungen") und O (n) Platz einnimmt.
gnasher729

Antworten:

15

O(N)A,BNM=A2+B2N(A,B)TNMM,NMT

Ω(NloglogN)N8σ(N)σ(N)(eγϵ)NloglogN

N

Yuval Filmus
quelle
Hmm, das "Meet-in-the-Middle" -Ding klingt sehr ähnlich zu dem, woran ich gerade arbeite (fast fertig). Dabei handelt es sich um einen aufsteigenden / absteigenden Merge-Match-Algorithmus über die TwoSquare-Paare. Klingt das genauso?
RBarryYoung
1
Es ist wahrscheinlich dasselbe, Meet-in-the-Middle ist eine so verbreitete Heuristik, dass sie viele verschiedene Namen haben muss.
Yuval Filmus
σ(N)
σ(N)ο(N)
1
Die Summe der Teiler funktioniert tatsächlich.
Yuval Filmus
5

o(N2)A,B,C,DNO(N2)

O(log2n)O(log2nloglogn)


[1] MO Rabin, JO Shallit, Randomisierte Algorithmen in der Zahlentheorie , Mitteilungen zur reinen und angewandten Mathematik 39 (1986), Nr. S1, S. S239 – S256 .

Juho
quelle
Für einen einfachen Algorithmus benötigen Sie nur Schleifen für A, B und C, berechnen dann D und überprüfen, ob es sich um eine Ganzzahl handelt. Wenn Sie A ≤ B ≤ C ≤ D benötigen, sollten Sie O (N ^ 1,5) mit einer ziemlich kleinen Konstante erhalten.
gnasher729
Ungefähr 0,04 N ^ 1,5 Tripel (A, B, C) und die Überprüfung, ob N - A ^ 2 - B ^ 2 - C ^ 2 ein Quadrat ist, können sehr schnell durchgeführt werden.
gnasher729
-2

8ddn

Gast
quelle
1
Und wie beantwortet das die Frage? Die Aufgabe ist es, all diese Vierfachen zu geben!
Raphael
1
Dies ist bereits in meiner Antwort erwähnt.
Yuval Filmus