Uzun bir dizinin tam toplamı

long[] tam özetini almak için aşağıdaki kod parçasını kullanıyorum.Uzun bir dizinin tam toplamı

public static BigInteger sum(long[] a) { 
    long low = 0; 
    long high = 0; 
    for (final long x : a) { 
     low += (x & 0xFFFF_FFFFL); 
     high += (x >> 32); 
    } 
    return BigInteger.valueOf(high).shiftLeft(32).add(BigInteger.valueOf(low)); 
}

iki yarım sayılar bölünmeye işleme ve son olarak kısmi toplam birleştirerek iyi çalışır. Şaşırtıcı bir şekilde, bu yöntem de çalışır:

public static BigInteger fastestSum(long[] a) { 
    long low = 0; 
    long high = 0; 
    for (final long x : a) { 
     low += x; 
     high += (x >> 32); 
    } 
    // We know that low has the lowest 64 bits of the exact sum. 
    // We also know that BigInteger.valueOf(high).shiftLeft(32) differs from the exact sum by less than 2**63. 
    // So the upper half of high is off by at most one. 
    high >>= 32; 
    if (low < 0) ++high; // Surprisingly, this is enough to fix it. 
    return BigInteger.valueOf(high).shiftLeft(64).add(BigInteger.valueOf(low)); 
}

Ben olduğu gibi fastestSumçalışması gerektiğini inanmıyor yapmak . Bunun işe yarayabileceğine inanıyorum ama son adımda daha fazlası yapılması gerekiyor. Ancak, tüm testlerimi (büyük rastgele testler dahil) geçiyor. Bu yüzden soruyorum: Birisi çalışmasını veya bir counterexample olduğunu kanıtlayabilir mi?

kaynak

2015-06-07 maaartinus

Çalışmalı, ancak bilgime göre tanımlanmamış davranışa bağlısınız. En önemlisi [** Tamsayı operatörleri herhangi bir şekilde taşma veya taşma belirtmezler **] (https://docs.oracle.com/javase/specs/jls/se8/html/jls-4.html#jls-4.2 0,2 # jls-4.2.2). – dhke

@dhke, belki de Java'yı C. ile karıştırıyorsunuz. JLS 15.18.2, kısmen, diyor ki "Bir tamsayı ilavesi taşarsa, sonuç, yeterince büyük ikide temsil edilen matematiksel toplamın düşük sıralı bitleridir. -complement format Eğer overflow oluşursa, sonuç işareti iki işlenen değerin matematiksel toplamının işareti ile aynı değildir. " Java dili, en azından tek iş parçacıklı programlar için hiç tanımlanmamış bir davranışa sahiptir. –

@JohnBollinger Anlaşıldı. Dhke yazdığı gibi, taşma göstergesi yok, ama ben hiç kullanmıyorum. Ve sonuç doğru mod 2 ** 64, bu yüzden en az 64 bit doğru. Sadece daha yüksek 32 bit için endişeleniyorum. – maaartinus

fastestSum(new long[]{+1, -1}) => -18446744073709551616

kaynak

2015-06-07 18:14:17 ZhongYu

Bu bir cevap mı? :) –

@DmitryGinzburg İnanılmaz, ama gerçek! Ve benim "akıllı" test davalarım kaçırdı ve bir milyon rastgele test yaptı! Aslında, bu cevabı kabul etmeliyim, ama bu sıkıcı geliyor ve bunun nasıl düzeltileceğini soracağım. – maaartinus

@ bayou.io, yöntemin çalışmadığı problar .. bunun enteresan bir algoritma olduğunu düşünmeme rağmen, bu cevap, sorunuza cevap verin. – Victor

Bu iş gibi görünüyor. Testlerimin önemsiz versiyonumla ilgili problemi kaçırdığı düşünüldüğünde, doğru olup olmadığından emin değilim. Bunu analiz etmek isteyenler şu soruları yanıtlayabilir:

public static BigInteger fastestSum(long[] a) { 
    long low = 0; 
    long control = 0; 
    for (final long x : a) { 
     low += x; 
     control += (x >> 32); 
    } 
    /* 
    We know that low has the lowest 64 bits of the exact sum. 
    We also know that 2**64 * control differs from the exact sum by less than 2**63. 
    It can't be bigger than the exact sum as the signed shift always rounds towards negative infinity. 
    So the upper half of control is either right or must be incremented by one. 
    */ 
    final long x = control & 0xFFFF_FFFFL; 
    final long y = (low >> 32); 
    long high = (control >> 32); 
    if (x - y > 1L << 31) ++high; 
    return BigInteger.valueOf(high).shiftLeft(64).add(BigInteger.valueOf(low)); 
}

Belki de sane versiyonundan% 30 daha hızlıdır.

kaynak

2015-06-07 20:53:00 maaartinus

cevap

İlgili konular