Durchschnitt von 3 langen ganzen Zahlen

103

Ich habe 3 sehr große vorzeichenbehaftete Ganzzahlen.

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

Ich möchte ihren abgeschnittenen Durchschnitt berechnen. Der erwartete Durchschnittswert ist long.MaxValue - 1, das heißt 9223372036854775806.

Es ist unmöglich, es zu berechnen als:

long avg = (x + y + z) / 3; // 3074457345618258600

Hinweis: Ich habe all diese Fragen zum Durchschnitt von 2 Zahlen gelesen, sehe aber nicht, wie diese Technik auf den Durchschnitt von 3 Zahlen angewendet werden kann.

Es wäre sehr einfach mit der Verwendung von BigInteger, aber nehmen wir an, ich kann es nicht verwenden.

BigInteger bx = new BigInteger(x);
BigInteger by = new BigInteger(y);
BigInteger bz = new BigInteger(z);
BigInteger bavg = (bx + by + bz) / 3; // 9223372036854775806

Wenn ich konvertiere double, verliere ich natürlich die Präzision:

double dx = x;
double dy = y;
double dz = z;
double davg = (dx + dy + dz) / 3; // 9223372036854780000

Wenn ich zu konvertiere decimal, funktioniert es, aber nehmen wir auch an, dass ich es nicht verwenden kann.

decimal mx = x;
decimal my = y;
decimal mz = z;
decimal mavg = (mx + my + mz) / 3; // 9223372036854775806

Frage: Gibt es eine Möglichkeit, den abgeschnittenen Durchschnitt von 3 sehr großen Ganzzahlen nur unter Verwendung des longTyps zu berechnen ? Betrachten Sie diese Frage nicht als C # -spezifisch, nur ist es für mich einfacher, Beispiele in C # bereitzustellen.

Ulugbek Umirov
quelle
1
Warum nicht den Gesamtdurchschnittsdiff berechnen und diesen von max abziehen?
Andreas Niedermair
6
@AndreasNiedermair Würde nicht funktionieren, wenn ich long.MinValueund long.MaxValueunter Werten habe.
Ulugbek Umirov
Guter Fang, in der Tat :)
Andreas Niedermair
Sind Sie sicher, dass wir uns darüber Sorgen machen müssen, sollte dies nicht vom Framework erledigt werden?
Bolu
11
Gibt es einen tatsächlichen Grund, BigIntegeroder decimalausgeschlossen ist , oder ist es nur um diese schwer zu machen?
jpmc26

Antworten:

142

Dieser Code wird funktionieren, ist aber nicht so hübsch.

Es teilt zuerst alle drei Werte (es legt die Werte fest, sodass Sie den Rest "verlieren") und teilt dann den Rest:

long n = x / 3
         + y / 3
         + z / 3
         + ( x % 3
             + y % 3
             + z % 3
           ) / 3

Beachten Sie, dass das obige Beispiel bei einem oder mehreren negativen Werten nicht immer ordnungsgemäß funktioniert.

Wie mit Ulugbek besprochen, ist hier die aktuelle BEST-Lösung für positive und negative Werte, da die Anzahl der Kommentare unten explodiert.

Dank der Antworten und Kommentare von Ulugbek Umirov , James S. , Kevin Z. , Marc van Leeuwen , gnasher729 ist dies die aktuelle Lösung:

static long CalculateAverage(long x, long y, long z)
{
    return (x % 3 + y % 3 + z % 3 + 6) / 3 - 2
            + x / 3 + y / 3 + z / 3;
}

static long CalculateAverage(params long[] arr)
{
    int count = arr.Length;
    return (arr.Sum(n => n % count) + count * (count - 1)) / count - (count - 1)
           + arr.Sum(n => n / count);
}
Patrick Hofman
quelle
3
@DavidG Nein. In Mathe , (x + y + z) / 3 = x / 3 + y / 3 + z / 3.
Kris Vandermotten
4
Ich habe Z3 verwendet, um dies für alle Variablenzählungen zwischen 1 und 5 zu beweisen.
usr
5
Natürlich scheint dies zu funktionieren, aber die Art und Weise, wie die Ganzzahlkürzung funktioniert, wird Sie durcheinander bringen. f(1,1,2) == 1währendf(-2,-2,8) == 2
KevinZ
11
Beachten Sie, dass dies aufgrund der gehirngeschädigten Semantik der Modulo-Operation zu einem Ergebnis führen kann, das um eins abweicht, nämlich eher aufgerundet als verringert, wenn negative Werte für die Variablen zulässig sind. Wenn zum Beispiel x, y positive Vielfache von 3 sind und z -2 ist, erhalten Sie, (x+y)/3was zu viel ist.
Marc van Leeuwen
6
@ KevinZ: ... dessen Wirkung dann von einem Programmierer rückgängig gemacht werden muss, der dieses Sonderfallverhalten überhaupt nicht wollte. Es erscheint hilfreich, den Programmierer den Modul angeben zu lassen, anstatt ihn aus einem Rest ableiten zu müssen, den der Compiler möglicherweise aus dem Modul abgeleitet hat.
Superkatze
26

NB - Patrick hat bereits eine großartige Antwort gegeben . Wenn Sie dies erweitern, können Sie eine generische Version für eine beliebige Anzahl von Ganzzahlen erstellen:

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

long[] arr = { x, y, z };
var avg = arr.Select(i => i / arr.Length).Sum() 
        + arr.Select(i => i % arr.Length).Sum() / arr.Length;
James S.
quelle
1
Dies ist nicht der Fall long, aber bei kleineren Typen ist zu beachten, dass die zweite Summe überlaufen kann.
user541686
7

Patrick Hofman hat eine großartige Lösung veröffentlicht . Bei Bedarf kann es jedoch auf verschiedene andere Arten implementiert werden. Mit dem Algorithmus hier habe ich eine andere Lösung. Bei sorgfältiger Implementierung ist es möglicherweise schneller als die Mehrfachaufteilung in Systemen mit langsamen Hardware-Teilern. Es kann weiter optimiert werden , indem die Technik der Division durch Konstanten aus der Freude des Hackers verwendet wird

public class int128_t {
    private int H;
    private long L;

    public int128_t(int h, long l)
    {
        H = h;
        L = l;
    }

    public int128_t add(int128_t a)
    {
        int128_t s;
        s.L = L + a.L;
        s.H = H + a.H + (s.L < a.L);
        return b;
    }

    private int128_t rshift2()  // right shift 2
    {
        int128_t r;
        r.H = H >> 2;
        r.L = (L >> 2) | ((H & 0x03) << 62);
        return r;
    }

    public int128_t divideby3()
    {
        int128_t sum = {0, 0}, num = new int128_t(H, L);
        while (num.H || num.L > 3)
        {
            int128_t n_sar2 = num.rshift2();
            sum = add(n_sar2, sum);
            num = add(n_sar2, new int128_t(0, num.L & 3));
        }

        if (num.H == 0 && num.L == 3)
        {
            // sum = add(sum, 1);
            sum.L++;
            if (sum.L == 0) sum.H++;
        }
        return sum; 
    }
};

int128_t t = new int128_t(0, x);
t = t.add(new int128_t(0, y));
t = t.add(new int128_t(0, z));
t = t.divideby3();
long average = t.L;

In C / C ++ auf 64-Bit-Plattformen ist dies viel einfacher __int128

int64_t average = ((__int128)x + y + z)/3;
phuclv
quelle
2
Ich würde vorschlagen, dass eine gute Möglichkeit, einen vorzeichenlosen 32-Bit-Wert durch 3 zu teilen, darin besteht, mit 0x55555555L zu multiplizieren, 0x55555555 zu addieren und mit 32 nach rechts zu verschieben.
Superkatze
@supercat ja ich kenne diese Methode. Die Methode von Hacker's Freude ist noch korrekter, aber ich werde die Implementierung für ein anderes Mal
phuclv
Ich bin mir nicht sicher, was "korrekter" bedeutet. Reziproke Multiplikationen können in vielen Fällen direkt exakte Werte ergeben oder Werte, die in ein oder zwei Schritten verfeinert werden können. Übrigens, ich denke, ich hätte vorschlagen sollen, mit 0x55555556 zu multiplizieren, was dann genaue Ergebnisse liefern würde, ohne dass ein "Add" erforderlich wäre. Ist Ihre Schleifenbedingung auch korrekt? Was verändert H und L in der Schleife?
Superkatze
Selbst wenn man keine Hardware-Multiplikation hat, kann man sich übrigens schnell einem vorzeichenlosen x=y/3Via annähern x=y>>2; x+=x>>2; x+=x>>4; x+=x>>8; x+=x>>16; x+=x>>32;. Das Ergebnis liegt sehr nahe bei x und kann durch Berechnung delta=y-x-x-x;und Anpassung xnach Bedarf präzisiert werden .
Superkatze
1
@ gnasher729 Ich frage mich, ob es diese Optimierung in 32-Bit-Computern verwenden kann, da es oft keine 64x64 → 128-Bit-Multiplikation durchführen kann
phuclv
7

Sie können den Mittelwert von Zahlen basierend auf den Unterschieden zwischen den Zahlen berechnen, anstatt die Summe zu verwenden.

Angenommen, x ist das Maximum, y ist der Median, z ist das Min (wie Sie). Wir werden sie max, median und min nennen.

Bedingter Prüfer hinzugefügt gemäß @ UlugbekUmirovs Kommentar:

long tmp = median + ((min - median) / 2);            //Average of min 2 values
if (median > 0) tmp = median + ((max - median) / 2); //Average of max 2 values
long mean;
if (min > 0) {
    mean = min + ((tmp - min) * (2.0 / 3)); //Average of all 3 values
} else if (median > 0) {
    mean = min;
    while (mean != tmp) {
        mean += 2;
        tmp--;
    }
} else if (max > 0) {
    mean = max;
    while (mean != tmp) {
        mean--;
        tmp += 2;
    }
} else {
    mean = max + ((tmp - max) * (2.0 / 3));
}
La-comadreja
quelle
2
Siehe @ UlugbekUmirovs Kommentar: Würde nicht funktionieren, wenn ich long.MinValue und long.MaxValue unter Werten habe
Bolu
@Bolu Der Kommentar gilt nur für long.MinValue. Also habe ich diese Bedingung hinzugefügt, damit sie für unseren Fall funktioniert.
La-Comadreja
Wie können Sie den Median verwenden, wenn er nicht initialisiert wurde?
Phuclv
@ LưuVĩnhPhúc, der Median ist der Wert zwischen dem Minimum und dem Maximum.
La-Comadreja
1
ist nicht (double)(2 / 3)gleich 0.0?
Phuclv
5

Da C anstelle der euklidischen Division eine Bodenteilung verwendet, ist es möglicherweise einfacher, einen richtig gerundeten Durchschnitt aus drei vorzeichenlosen Werten als drei vorzeichenbehafteten Werten zu berechnen. Fügen Sie einfach 0x8000000000000000UL zu jeder Zahl hinzu, bevor Sie den vorzeichenlosen Durchschnitt nehmen, subtrahieren Sie ihn nach der Aufnahme des Ergebnisses und verwenden Sie einen ungeprüften Cast zurück Int64, um einen vorzeichenbehafteten Durchschnitt zu erhalten.

Um den vorzeichenlosen Durchschnitt zu berechnen, berechnen Sie die Summe der obersten 32 Bits der drei Werte. Berechnen Sie dann die Summe der unteren 32 Bits der drei Werte plus die Summe von oben plus eins [das Plus eins ergibt ein gerundetes Ergebnis]. Der Durchschnitt beträgt 0x55555555 mal die erste Summe plus ein Drittel der zweiten.

Die Leistung auf 32-Bit-Prozessoren kann verbessert werden, indem drei "Summen" -Werte erzeugt werden, von denen jeder 32 Bit lang ist, so dass das Endergebnis ist ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; es könnte möglicherweise weiter durch den Austausch verstärkt werden sumL/3mit ((sumL * 0x55555556UL) >> 32), obwohl letztere auf den JIT - Optimierer abhängen würde [es vielleicht wissen , wie eine Division durch 3 mit einem mehrfach zu ersetzen und seinen Code könnte in der Tat effizienter sein als eine explizite Multiplikationsoperation].

Superkatze
quelle
Hat der Überlauf nach dem Hinzufügen von 0x8000000000000000UL keinen Einfluss auf das Ergebnis?
Phuclv
@ LưuVĩnhPhúc Es gibt keinen Überlauf. Gehen Sie zu meiner Antwort für eine Implementierung. Die Aufteilung in 2 32-Bit-Int war jedoch nicht erforderlich.
KevinZ
@ KevinZ: Das Aufteilen jedes Werts in einen oberen und einen unteren 32-Bit-Teil ist schneller als das Aufteilen in einen durch drei dividierten Quotienten und Rest.
Superkatze
1
@ LưuVĩnhPhúc: Im Gegensatz zu vorzeichenbehafteten Werten, die sich semantisch wie Zahlen verhalten und in einem legitimen C-Programm nicht überlaufen dürfen, verhalten sich vorzeichenlose Werte im Allgemeinen wie Mitglieder eines abstrakten algebraischen Ringes, sodass die Semantik des Umbruchs gut definiert ist.
Supercat
1
Das Tupel steht für -3, -2, -1. Nachdem zu jedem Wert 0x8000U hinzugefügt wurde, sollten die Werte in zwei Hälften geteilt werden: 7F + FF 7F + FE 7F + FD. Fügen Sie die obere und untere Hälfte hinzu, was 17D + 2FA ergibt. Addiere die Summe der oberen Hälfte zur Summe der unteren Hälfte, was 477 ergibt. Multipliziere 17D mit 55, was 7E81 ergibt. Teilen Sie 477 durch drei, was 17D ergibt. Addiere 7E81 zu 17D, was 7FFE ergibt. Subtrahiere 8000 davon und erhalte -2.
Superkatze
5

Patching Patrick Hofman ‚s Lösung mit supercat ‘ s Korrektur, gebe ich Ihnen folgendes:

static Int64 Avg3 ( Int64 x, Int64 y, Int64 z )
{
    UInt64 flag = 1ul << 63;
    UInt64 x_ = flag ^ (UInt64) x;
    UInt64 y_ = flag ^ (UInt64) y;
    UInt64 z_ = flag ^ (UInt64) z;
    UInt64 quotient = x_ / 3ul + y_ / 3ul + z_ / 3ul
        + ( x_ % 3ul + y_ % 3ul + z_ % 3ul ) / 3ul;
    return (Int64) (quotient ^ flag);
}

Und der N-Element-Fall:

static Int64 AvgN ( params Int64 [ ] args )
{
    UInt64 length = (UInt64) args.Length;
    UInt64 flag = 1ul << 63;
    UInt64 quotient_sum = 0;
    UInt64 remainder_sum = 0;
    foreach ( Int64 item in args )
    {
        UInt64 uitem = flag ^ (UInt64) item;
        quotient_sum += uitem / length;
        remainder_sum += uitem % length;
    }

    return (Int64) ( flag ^ ( quotient_sum + remainder_sum / length ) );
}

Dies gibt immer den Boden () des Mittelwerts an und eliminiert jeden möglichen Randfall.

KevinZ
quelle
1
Ich habe AvgN in Z3-Code übersetzt und dies für alle vernünftigen Eingabegrößen (z. B. 1 <= args.Length <= 5 und Bitvektorgröße 6) als richtig erwiesen. Diese Antwort ist richtig.
Usr
Wunderbare Antwort Kevin. Vielen Dank für Ihren Beitrag! Meta.stackoverflow.com/a/303292/993547
Patrick Hofman
4

Sie könnten die Tatsache nutzen, dass Sie jede der Zahlen als schreiben können y = ax + b, wobei xes sich um eine Konstante handelt. Jeder awäre y / x(der ganzzahlige Teil dieser Division). Jedes b wäre y % x(der Rest / Modulo dieser Division). Wenn Sie diese Konstante auf intelligente Weise auswählen, indem Sie beispielsweise die Quadratwurzel der maximalen Anzahl als Konstante auswählen, können Sie den Durchschnitt von erhaltenx Zahlen erhalten, ohne Probleme mit dem Überlauf zu haben.

Der Durchschnitt einer beliebigen Liste von Zahlen kann wie folgt ermittelt werden:

( ( sum( all A's ) / length ) * constant ) + 
( ( sum( all A's ) % length ) * constant / length) +
( ( sum( all B's ) / length )

wobei %modulo und /den "ganzen" Teil der Teilung bezeichnet.

Das Programm würde ungefähr so ​​aussehen:

class Program
{
    static void Main()
    {
        List<long> list = new List<long>();
        list.Add( long.MaxValue );
        list.Add( long.MaxValue - 1 );
        list.Add( long.MaxValue - 2 );

        long sumA = 0, sumB = 0;
        long res1, res2, res3;
        //You should calculate the following dynamically
        long constant = 1753413056;

        foreach (long num in list)
        {
            sumA += num / constant;
            sumB += num % constant;
        }

        res1 = (sumA / list.Count) * constant;
        res2 = ((sumA % list.Count) * constant) / list.Count;
        res3 = sumB / list.Count;

        Console.WriteLine( res1 + res2 + res3 );
    }
}
Sumurai8
quelle
4

Wenn Sie wissen, dass Sie N Werte haben, können Sie jeden Wert durch N teilen und summieren?

long GetAverage(long* arrayVals, int n)
{
    long avg = 0;
    long rem = 0;

    for(int i=0; i<n; ++i)
    {
        avg += arrayVals[i] / n;
        rem += arrayVals[i] % n;
    }

    return avg + (rem / n);
}
abelenky
quelle
Dies ist genau das gleiche wie Patrick Hofmans Lösung, wenn auch nicht weniger korrekt als die endgültige Version
phuclv
2

Ich habe es auch versucht und eine schnellere Lösung gefunden (allerdings nur um einen Faktor von 3/4). Es wird eine einzelne Abteilung verwendet

public static long avg(long a, long b, long c) {
    final long quarterSum = (a>>2) + (b>>2) + (c>>2);
    final long lowSum = (a&3) + (b&3) + (c&3);
    final long twelfth = quarterSum / 3;
    final long quarterRemainder = quarterSum - 3*twelfth;
    final long adjustment = smallDiv3(lowSum + 4*quarterRemainder);
    return 4*twelfth + adjustment;
}

Dabei smallDiv3wird durch Multiplikation durch 3 dividiert und nur für kleine Argumente gearbeitet

private static long smallDiv3(long n) {
    assert -30 <= n && n <= 30;
    // Constants found rather experimentally.
    return (64/3*n + 10) >> 6;
}

Hier ist der gesamte Code einschließlich eines Tests und eines Benchmarks, die Ergebnisse sind nicht so beeindruckend.

Maaartinus
quelle
1

Diese Funktion berechnet das Ergebnis in zwei Unterteilungen. Es sollte sich gut auf andere Teiler und Wortgrößen verallgemeinern lassen.

Es funktioniert, indem das Ergebnis der Doppelwortaddition berechnet und dann die Division berechnet wird.

Int64 average(Int64 a, Int64 b, Int64 c) {
    // constants: 0x10000000000000000 div/mod 3
    const Int64 hdiv3 = UInt64(-3) / 3 + 1;
    const Int64 hmod3 = UInt64(-3) % 3;

    // compute the signed double-word addition result in hi:lo
    UInt64 lo = a; Int64 hi = a>=0 ? 0 : -1;
    lo += b; hi += b>=0 ? lo<b : -(lo>=UInt64(b));
    lo += c; hi += c>=0 ? lo<c : -(lo>=UInt64(c));

    // divide, do a correction when high/low modulos add up
    return hi>=0 ? lo/3 + hi*hdiv3 + (lo%3 + hi*hmod3)/3
                 : lo/3+1 + hi*hdiv3 + Int64(lo%3-3 + hi*hmod3)/3;
}
Řrřola
quelle
0

Mathematik

(x + y + z) / 3 = x/3 + y/3 + z/3

(a[1] + a[2] + .. + a[k]) / k = a[1]/k + a[2]/k + .. + a[k]/k

Code

long calculateAverage (long a [])
{
    double average = 0;

    foreach (long x in a)
        average += (Convert.ToDouble(x)/Convert.ToDouble(a.Length));

    return Convert.ToInt64(Math.Round(average));
}

long calculateAverage_Safe (long a [])
{
    double average = 0;
    double b = 0;

    foreach (long x in a)
    {
        b = (Convert.ToDouble(x)/Convert.ToDouble(a.Length));

        if (b >= (Convert.ToDouble(long.MaxValue)-average))
            throw new OverflowException ();

        average += b;
    }

    return Convert.ToInt64(Math.Round(average));
}
Khaled.K
quelle
für den Satz {1,2,3}der Antwort ist 2, aber Ihr Code wird zurückkehren 1.
Ulugbek Umirov
@UlugbekUmirov Code behoben, sollte doppelte Typen für die Verarbeitung verwendet werden
Khaled.K
1
Das möchte ich vermeiden - die Verwendung von double, da wir in einem solchen Fall an Präzision verlieren werden.
Ulugbek Umirov
0

Versuche dies:

long n = Array.ConvertAll(new[]{x,y,z},v=>v/3).Sum()
     +  (Array.ConvertAll(new[]{x,y,z},v=>v%3).Sum() / 3);
trinalbadger587
quelle