Rata-rata 3 bilangan bulat panjang

103

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 #.

Ulugbek Umirov
sumber
1
mengapa tidak menghitung diff rata-rata keseluruhan dan mengurangi dari max?
Andreas Niedermair
6
@AndreasNiedermair Tidak akan berfungsi jika saya memiliki long.MinValuedan di long.MaxValueantara nilai.
Ulugbek Umirov
tangkapan yang bagus, memang :)
Andreas Niedermair
Apakah Anda yakin kami perlu khawatir tentang ini, bukankah ini harus ditangani oleh kerangka kerja?
Bolu
11
Apakah ada alasan sebenarnya yang BigIntegeratau decimaldikecualikan, atau hanya untuk membuat ini sulit?
jpmc26

Jawaban:

142

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);
}
Patrick Hofman
sumber
3
@DavidG Tidak. Dalam matematika (x + y + z) / 3 = x / 3 + y / 3 + z / 3,.
Kris Vandermotten
4
Saya menggunakan Z3 untuk membuktikan ini benar untuk semua jumlah variabel antara 1 dan 5.
usr
5
Tentu saja ini tampaknya berhasil, tetapi cara pemotongan integer beroperasi akan mengacaukan Anda. f(1,1,2) == 1sementaraf(-2,-2,8) == 2
KevinZ
11
Perhatikan bahwa karena semantik operasi modulo yang rusak otak, ini dapat memberikan hasil yang salah, yaitu dibulatkan ke atas daripada ke bawah, jika nilai negatif untuk variabel diperbolehkan. Misalnya jika x, y adalah kelipatan positif dari 3, dan z adalah -2, Anda mendapatkan (x+y)/3yang terlalu banyak.
Marc van Leeuwen
6
@KevinZ: ... yang efeknya kemudian harus dibatalkan oleh seorang programmer yang tidak pernah menginginkan perilaku kasus khusus itu sejak awal. Membiarkan programmer menentukan modulus daripada harus menurunkannya dari sisa yang mungkin diturunkan dari modulus akan tampak membantu.
supercat
26

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;
James S
sumber
1
Ini tidak akan terjadi untuk long, tetapi untuk tipe yang lebih kecil, perhatikan bahwa jumlah kedua dapat melimpah.
pengguna541686
7

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;
phuclv.dll
sumber
2
Saya menyarankan bahwa cara yang baik untuk membagi nilai 32-bit unsigned dengan 3 adalah mengalikannya dengan 0x55555555L, menambahkan 0x55555555, dan menggeser ke kanan dengan 32. Metode divideby3 Anda, sebagai perbandingan, terlihat seolah-olah akan membutuhkan banyak langkah terpisah.
supercat
@supercat ya saya tahu metode itu. Metode menurut kesenangan peretas bahkan lebih tepat tetapi saya akan menerapkannya untuk lain waktu
phuclv
Saya tidak yakin apa artinya "lebih benar". Pengalian timbal balik dalam banyak kasus dapat menghasilkan nilai yang tepat secara langsung, atau menghasilkan nilai yang dapat disaring dalam satu atau dua langkah. BTW, saya pikir saya seharusnya menyarankan mengalikan dengan 0x55555556, yang kemudian akan menghasilkan hasil yang tepat tanpa perlu "menambahkan". Juga, apakah kondisi loop Anda sudah benar? Apa yang mengubah H dan L dalam loop?
supercat
Kebetulan, bahkan jika seseorang tidak memiliki perkalian perangkat keras, seseorang dapat dengan cepat memperkirakan x=y/3melalui unsigned x=y>>2; x+=x>>2; x+=x>>4; x+=x>>8; x+=x>>16; x+=x>>32;. Hasilnya akan sangat mendekati x, dan dapat dibuat presisi dengan menghitung delta=y-x-x-x;dan menggunakan penyesuaian xsesuai kebutuhan.
supercat
1
@ gnasher729 Saya ingin tahu apakah ia dapat menggunakan pengoptimalan itu di komputer 32-bit karena sering tidak dapat melakukan perkalian 64x64 → 128 bit
phuclv
7

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));
}
La-comadreja
sumber
2
Lihat komentar @ UlugbekUmirov: Tidak akan berfungsi jika saya memiliki nilai yang panjang.MinValue dan long.MaxValue di antara nilai
Bolu
@Bolu komentar hanya berlaku untuk long.MinValue. Jadi saya menambahkan persyaratan ini agar berfungsi untuk kasus kami.
La-comadreja
Bagaimana Anda bisa menggunakan median jika belum diinisialisasi?
phuclv
@ LưuVĩnhPhúc, median adalah nilai antara minimum dan maksimum.
La-comadreja
1
tidak (double)(2 / 3)sama dengan 0,0?
phuclv
5

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].

supercat
sumber
Setelah menambahkan 0x8000000000000000UL bukankah luapan mempengaruhi hasilnya?
phuclv
@ LưuVĩnhPhúc Tidak ada luapan. Pergi ke jawaban saya untuk implementasi. Pemisahan menjadi 2 32 bit int tidak diperlukan.
KevinZ
@KevinZ: Memisahkan setiap nilai menjadi bagian 32-bit atas dan bawah lebih cepat daripada membaginya menjadi hasil bagi-oleh-tiga dan sisa.
supercat
1
@ LưuVĩnhPhúc: Tidak seperti nilai bertanda yang berperilaku semantik seperti angka dan tidak diizinkan untuk meluap dalam program C yang sah, nilai unsigned umumnya berperilaku seperti anggota cincin aljabar abstrak yang membungkus, sehingga semantik pembungkus didefinisikan dengan baik.
supercat
1
Tupel mewakili -3, -2, -1. Setelah menambahkan 0x8000U ke setiap nilai, nilainya kemudian harus dibagi menjadi dua: 7F + FF 7F + FE 7F + FD. Tambahkan bagian atas dan bawah, menghasilkan 17D + 2FA. Tambahkan jumlah setengah atas ke jumlah setengah bagian bawah menghasilkan 477. Kalikan 17D dengan 55 menghasilkan 7E81. Bagilah 477 dengan tiga menghasilkan 17D. Tambahkan 7E81 ke 17D menghasilkan 7FFE. Kurangi 8000 dari itu dan dapatkan -2.
supercat
5

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.

KevinZ
sumber
1
Saya menerjemahkan kode AvgN ke Z3 dan membuktikannya benar untuk semua ukuran input yang masuk akal (misalnya 1 <= args.Length <= 5 dan ukuran bitvector 6). Jawaban ini benar.
usr
Jawaban luar biasa Kevin. Terima kasih atas kontribusi Anda! meta.stackoverflow.com/a/303292/993547
Patrick Hofman
4

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 );
    }
}
Sumurai8
sumber
4

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);
}
abelenky
sumber
ini sama dengan solusi Patrick Hofman, jika tidak kurang benar dari versi final
phuclv
2

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.

maaartinus
sumber
1

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;
}
Řrřola
sumber
0

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));
}
Khaled.K
sumber
untuk kumpulan {1,2,3}jawabannya adalah 2, tetapi kode Anda akan kembali 1.
Ulugbek Umirov
@UlugbekUmirov kode tetap, harus menggunakan tipe ganda untuk diproses
Khaled.K
1
Itulah yang ingin saya hindari - penggunaan double, karena kita akan kehilangan ketepatan dalam kasus seperti itu.
Ulugbek Umirov
0

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);
trinalbadger587
sumber