public long cardinality()
    {
        if (isExact()) {
            return minhash.size();
        }

        // Intuition is: get the stored hashes' density, and extrapolate to the whole Hash output range.
        // Since Hash output range (2^64) cannot be stored in long type, I use half of the range
        // via Long.MAX_VALUE and also divide the hash values' density by 2. The "-1" is bias correction
        // detailed in "On Synopses for Distinct-Value Estimation Under Multiset Operations" by Beyer et. al.
        long hashesRange = minhash.lastLongKey() - Long.MIN_VALUE;
        double halfDensity = Long.divideUnsigned(hashesRange, minhash.size() - 1) / 2D;
        return (long) (HASH_OUTPUT_HALF_RANGE / halfDensity);
    }
@Test
    public void testCardinality()
            throws Exception
    {
        int trials = 1000;
        for (int indexBits = 4; indexBits <= 12; indexBits++) {
            Map<Integer, StandardDeviation> errors = new HashMap<>();
            int numberOfBuckets = 1 << indexBits;
            int maxCardinality = numberOfBuckets * 2;

            for (int trial = 0; trial < trials; trial++) {
                KHyperLogLog khll = new KHyperLogLog();
                for (int cardinality = 1; cardinality <= maxCardinality; cardinality++) {
                    khll.add(ThreadLocalRandom.current().nextLong(), 0L);

                    if (cardinality % (numberOfBuckets / 10) == 0) {
                        // only do this a few times, since computing the cardinality is currently not
                        // as cheap as it should be
                        double error = (khll.cardinality() - cardinality) * 1.0 / cardinality;

                        StandardDeviation stdev = errors.computeIfAbsent(cardinality, k -> new StandardDeviation());
                        stdev.increment(error);
                    }
                }
            }

            double expectedStandardError = 1.04 / Math.sqrt(1 << indexBits);

            for (Map.Entry<Integer, StandardDeviation> entry : errors.entrySet()) {
                // Give an extra error margin. This is mostly a sanity check to catch egregious errors
                double realStandardError = entry.getValue().getResult();
                assertTrue(realStandardError <= expectedStandardError * 1.1,
                        String.format("Failed at p = %s, cardinality = %s. Expected std error = %s, actual = %s",
                                indexBits,
                                entry.getKey(),
                                expectedStandardError,
                                realStandardError));
            }
        }
    }