Rata-rata 3 bilangan bulat panjang

Saya memiliki 3 bilangan bulat bertanda tangan yang sangat besar.

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

Saya ingin menghitung rata-rata terpotongnya. Nilai rata-rata yang diharapkan adalah long.MaxValue - 1, yaitu 9223372036854775806.

Tidak mungkin menghitungnya sebagai:

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

Catatan: Saya membaca semua pertanyaan tentang rata-rata 2 angka, tetapi saya tidak melihat bagaimana teknik itu dapat diterapkan pada rata-rata 3 angka.

Ini akan sangat mudah dengan penggunaan BigInteger, tapi mari kita asumsikan saya tidak bisa menggunakannya.

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

Jika saya mengonversi ke double, maka, tentu saja, saya kehilangan presisi:

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

Jika saya mengonversi ke decimal, itu berfungsi, tetapi juga anggaplah saya tidak dapat menggunakannya.

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

Pertanyaan: Apakah ada cara untuk menghitung rata-rata terpotong dari 3 bilangan bulat yang sangat besar hanya dengan penggunaan longtipe? Jangan anggap pertanyaan itu spesifik C #, hanya lebih mudah bagi saya untuk memberikan contoh dalam C #.

Kode ini akan berfungsi, tetapi tidak terlalu bagus.

Ini pertama-tama membagi ketiga nilai (itu mendasarkan nilai, jadi Anda 'kehilangan' sisanya), dan kemudian membagi sisanya:

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

Perhatikan bahwa contoh di atas tidak selalu berfungsi dengan baik bila memiliki satu atau lebih nilai negatif.

Seperti yang didiskusikan dengan Ulugbek, karena banyaknya komentar di bawah ini, berikut adalah solusi TERBAIK saat ini untuk nilai positif dan negatif.

Terima kasih atas jawaban dan komentar Ulugbek Umirov , James S , KevinZ , Marc van Leeuwen , gnasher729 inilah solusi terkini:

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);
}

NB - Patrick telah memberikan jawaban yang bagus . Memperluas ini, Anda dapat melakukan versi umum untuk sejumlah bilangan bulat seperti:

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;

Patrick Hofman telah memposting solusi hebat . Namun bila diperlukan masih bisa diimplementasikan dengan beberapa cara lain. Menggunakan algoritme di sini saya punya solusi lain. Jika diterapkan dengan hati-hati, ini mungkin lebih cepat daripada beberapa divisi dalam sistem dengan pembagi perangkat keras yang lambat. Ini dapat lebih dioptimalkan dengan menggunakan teknik divide by constants dari kesenangan peretas

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;

Di C / C ++ pada platform 64-bit, ini jauh lebih mudah __int128

int64_t average = ((__int128)x + y + z)/3;

Anda dapat menghitung rata-rata angka berdasarkan perbedaan antara angka-angka daripada menggunakan jumlah.

Misalkan x adalah maks, y adalah median, z adalah min (seperti yang Anda miliki). Kami akan menyebutnya max, median dan min.

Pemeriksa bersyarat ditambahkan sesuai komentar @ UlugbekUmirov:

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));
}

Karena C menggunakan pembagian berlantai daripada pembagian Euclidian, mungkin lebih mudah untuk menghitung rata-rata yang dibulatkan dengan benar dari tiga nilai tak bertanda tangan daripada tiga nilai bertanda. Cukup tambahkan 0x8000000000000000UL ke setiap angka sebelum mengambil rata-rata unsigned, kurangi setelah mengambil hasilnya, dan gunakan cast back yang tidak dicentang Int64untuk mendapatkan rata-rata yang ditandatangani.

Untuk menghitung rata-rata unsigned, hitung jumlah 32 bit teratas dari tiga nilai. Kemudian hitung jumlah 32 bit terbawah dari tiga nilai, ditambah jumlah dari atas, ditambah satu [nilai tambah satu untuk menghasilkan hasil yang bulat]. Rata-rata akan menjadi 0x55555555 kali jumlah pertama, ditambah sepertiga dari jumlah kedua.

Kinerja pada prosesor 32-bit dapat ditingkatkan dengan menghasilkan tiga nilai "jumlah" yang masing-masing sepanjang 32 bit, sehingga hasil akhirnya adalah ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; itu mungkin lebih ditingkatkan dengan mengganti sumL/3dengan ((sumL * 0x55555556UL) >> 32), meskipun yang terakhir akan tergantung pada pengoptimal JIT [mungkin tahu bagaimana mengganti pembagian dengan 3 dengan perkalian, dan kodenya mungkin sebenarnya lebih efisien daripada operasi perkalian eksplisit].

Menambal solusi Patrick Hofman dengan koreksi supercat , saya berikan Anda yang berikut:

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);
}

Dan kasus elemen N:

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 ) );
}

Ini selalu memberikan floor () dari mean, dan menghilangkan setiap kemungkinan kasus edge.

Anda dapat menggunakan fakta bahwa Anda dapat menulis setiap angka sebagai y = ax + b, di mana xadalah konstanta. Masing a- masing akan menjadi y / x(bagian integer dari divisi itu). Setiap b akan menjadi y % x(sisa / modulo dari divisi itu). Jika Anda memilih konstanta ini dengan cara yang cerdas, misalnya dengan memilih akar kuadrat dari bilangan maksimum sebagai konstanta, Anda bisa mendapatkan rata-rata xangka tanpa mengalami masalah overflow.

Rata-rata dari daftar angka yang berubah-ubah dapat ditemukan dengan menemukan:

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

dimana %menunjukkan modulo dan /menunjukkan bagian 'keseluruhan' dari divisi.

Programnya akan terlihat seperti:

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 );
    }
}

Jika Anda tahu Anda memiliki nilai N, dapatkah Anda membagi setiap nilai dengan N dan menjumlahkannya?

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);
}

Saya juga mencobanya dan menemukan solusi yang lebih cepat (meskipun hanya dengan faktor sekitar 3/4). Ini menggunakan satu divisi

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;
}

dimana smallDiv3pembagian dengan 3 menggunakan perkalian dan bekerja hanya untuk argumen kecil

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

Ini seluruh kode termasuk tes dan patokan, hasilnya tidak terlalu mengesankan.

Fungsi ini menghitung hasil dalam dua divisi. Ini harus menggeneralisasi dengan baik ke pembagi dan ukuran kata lain.

Ia bekerja dengan menghitung hasil penjumlahan dua kata, kemudian mengerjakan pembagian.

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;
}

Matematika

(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

Kode

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));
}

Coba ini:

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