C++ implementation for fast computing of the distance covariance or distance correlation. Implementation based on the article “Fast Computing for Distance Covariance” written by Xiaoming Huo and Gábor J. Székely and published in Technometrics (Volumne 58, 2016 – Issue 4). [pastacode lang=”cpp” manual=”%23ifndef%20FASTDISTANCECORRELATION_H%0A%23define%20FASTDISTANCECORRELATION_H%0A%0A%23include%20%3Ctuple%3E%0A%23include%20%3Ccmath%3E%0A%23include%20%3Calgorithm%3E%0A%23include%20%3Cvector%3E%0A%0Anamespace%20FastDistanceCorrelation%20%7B%0A%0A%20%20%20%20double%20fastDistanceCorrelation(const%20std%3A%3Avector%3Cdouble%3E%20%26x%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20bool%20unbiased%20%3D%20false)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20fastDistanceCovariance(const%20std%3A%3Avector%3Cdouble%3E%20%26x%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20bool%20unbiased%20%3D%20false%2C%20bool%20allParameters%20%3D%20false)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20fastDistanceCovarianceSums(const%20std%3A%3Avector%3Cdouble%3E%20%26x%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20bool%20allSums%20%3D%20false)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20partialSum2D(const%20std%3A%3Avector%3Cdouble%3E%20%26x%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26c%2C%20const%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20%26x_orderStatistics_orderIndices_rank_cummulativeSum%2C%20const%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20%26y_orderStatistics_orderIndices_rank_cummulativeSum)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20binaryTreeSums(const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26c)%3B%0A%0A%20%20%20%20bool%20sortAscendingOnFirstElementOfTupleAndThenOnSecondElementOfTuple(const%20std%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%26element1%2C%20const%20std%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%26element2)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20createVector_orderStatistics_orderIndices_rank_cummulativeSum(const%20std%3A%3Avector%3Cdouble%3E%20vector)%3B%0A%0A%20%20%20%20double%20variance(const%20std%3A%3Avector%3Cdouble%3E%20%26vector)%3B%0A%0A%20%20%20%20double%20mean(const%20std%3A%3Avector%3Cdouble%3E%20%26vector)%3B%0A%0A%7D%0A%0A%23endif%20%2F%2F%20FASTDISTANCECORRELATION_H” message=”fastdistancecorrelation.h” highlight=”” provider=”manual”/] [pastacode lang=”cpp” manual=”%23include%20%22fastdistancecorrelation.h%22%0A%0Adouble%20FastDistanceCorrelation%3A%3AfastDistanceCorrelation(const%20std%3A%3Avector%3Cdouble%3E%20%26x%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20bool%20unbiased)%0A%7B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20parameters%20%3D%20FastDistanceCorrelation%3A%3AfastDistanceCovariance(x%2C%20y%2C%20unbiased%2C%20true)%3B%0A%0A%20%20%20%20double%20xDistanceVariance%20%3D%20parameters.at(1)%3B%0A%0A%20%20%20%20double%20yDistanceVariance%20%3D%20parameters.at(2)%3B%0A%0A%20%20%20%20return%20std%3A%3Asqrt(parameters.at(0)%20%2F%20std%3A%3Asqrt(xDistanceVariance%20*%20yDistanceVariance))%3B%0A%0A%7D%0A%0Astd%3A%3Avector%3Cdouble%3E%20FastDistanceCorrelation%3A%3AfastDistanceCovariance(const%20std%3A%3Avector%3Cdouble%3E%20%26x%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20bool%20unbiased%2C%20bool%20allParameters)%0A%7B%0A%0A%20%20%20%20if%20(x.size()%20!%3D%20y.size())%20%7B%0A%0A%20%20%20%20%20%20%20%20if%20(allParameters)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20std%3A%3Avector%3Cdouble%3E(3%2C%20std%3A%3Anumeric_limits%3Cdouble%3E%3A%3Aquiet_NaN())%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20std%3A%3Avector%3Cdouble%3E(1%2C%20std%3A%3Anumeric_limits%3Cdouble%3E%3A%3Aquiet_NaN())%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20sums%20%3D%20FastDistanceCorrelation%3A%3AfastDistanceCovarianceSums(x%2C%20y%2C%20allParameters)%3B%0A%0A%20%20%20%20double%20n%20%3D%20static_cast%3Cdouble%3E(x.size())%3B%0A%0A%20%20%20%20double%20d1%3B%0A%0A%20%20%20%20double%20d2%3B%0A%0A%20%20%20%20double%20d3%3B%0A%0A%20%20%20%20if%20(unbiased)%20%7B%0A%0A%20%20%20%20%20%20%20%20d1%20%3D%20n%20*%20(n%20-%203.0)%3B%0A%0A%20%20%20%20%20%20%20%20d2%20%3D%20d1%20*%20(n%20-%202.0)%3B%0A%0A%20%20%20%20%20%20%20%20d3%20%3D%20d2%20*%20(n%20-%201.0)%3B%0A%0A%20%20%20%20%7D%20else%20%7B%0A%0A%20%20%20%20%20%20%20%20d1%20%3D%20n%20*%20n%3B%0A%0A%20%20%20%20%20%20%20%20d2%20%3D%20n%20*%20n%20*%20n%3B%0A%0A%20%20%20%20%20%20%20%20d3%20%3D%20n%20*%20n%20*%20n%20*n%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20if%20(allParameters)%20%7B%0A%0A%20%20%20%20%20%20%20%20std%3A%3Avector%3Cdouble%3E%20results(3)%3B%0A%0A%20%20%20%20%20%20%20%20results%5B0%5D%20%3D%20(sums.at(0)%20%2F%20d1)%20-%20(2.0%20*%20sums.at(1)%20%2F%20d2)%20%2B%20(sums.at(2)%20%2F%20d3)%3B%0A%0A%20%20%20%20%20%20%20%20results%5B1%5D%20%3D%20(sums.at(3)%20%2F%20d1)%20-%20(2.0%20*%20sums.at(5)%20%2F%20d2)%20%2B%20(sums.at(7)%20%2F%20d3)%3B%0A%0A%20%20%20%20%20%20%20%20results%5B2%5D%20%3D%20(sums.at(4)%20%2F%20d1)%20-%20(2.0%20*%20sums.at(6)%20%2F%20d2)%20%2B%20(sums.at(8)%20%2F%20d3)%3B%0A%0A%20%20%20%20%20%20%20%20return%20results%3B%0A%0A%20%20%20%20%7D%20else%20%7B%0A%0A%20%20%20%20%20%20%20%20std%3A%3Avector%3Cdouble%3E%20results(1)%3B%0A%0A%20%20%20%20%20%20%20%20results%5B0%5D%20%3D%20(sums.at(0)%20%2F%20d1)%20-%20(2.0%20*%20sums.at(1)%20%2F%20d2)%20%2B%20(sums.at(2)%20%2F%20d3)%3B%0A%0A%20%20%20%20%20%20%20%20return%20results%3B%0A%0A%20%20%20%20%7D%0A%7D%0A%0Astd%3A%3Avector%3Cdouble%3E%20FastDistanceCorrelation%3A%3AfastDistanceCovarianceSums(const%20std%3A%3Avector%3Cdouble%3E%20%26x%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20bool%20allSums)%0A%7B%0A%0A%20%20%20%20if%20(x.size()%20!%3D%20y.size())%20%7B%0A%0A%20%20%20%20%20%20%20%20if%20(allSums)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20std%3A%3Avector%3Cdouble%3E(9%2C%20std%3A%3Anumeric_limits%3Cdouble%3E%3A%3Aquiet_NaN())%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20std%3A%3Avector%3Cdouble%3E(3%2C%20std%3A%3Anumeric_limits%3Cdouble%3E%3A%3Aquiet_NaN())%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20xSortedOrderedRanked%20%3D%20FastDistanceCorrelation%3A%3AcreateVector_orderStatistics_orderIndices_rank_cummulativeSum(x)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20ySortedOrderedRanked%20%3D%20FastDistanceCorrelation%3A%3AcreateVector_orderStatistics_orderIndices_rank_cummulativeSum(y)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20×1(x.size())%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20y1(y.size())%3B%0A%0A%20%20%20%20×1%5B0%5D%20%3D%20std%3A%3Aget%3C0%3E(xSortedOrderedRanked.at(0))%3B%0A%0A%20%20%20%20y1%5B0%5D%20%3D%20y.at(std%3A%3Aget%3C1%3E(xSortedOrderedRanked.at(0)))%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%201%3B%20i%20%3C%20x.size()%3B%20%2B%2Bi)%20%7B%0A%0A%09%09const%20std%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%26tuple(xSortedOrderedRanked.at(i))%3B%0A%0A%20%20%20%20%20%20%20%20×1%5Bi%5D%20%3D%20std%3A%3Aget%3C0%3E(tuple)%3B%0A%0A%20%20%20%20%20%20%20%20y1%5Bi%5D%20%3D%20y.at(std%3A%3Aget%3C1%3E(tuple))%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20adot(x.size())%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20bdot(x.size())%3B%0A%0A%20%20%20%20double%20adotdot%20%3D%200.0%3B%0A%0A%20%20%20%20double%20bdotdot%20%3D%200.0%3B%0A%0A%20%20%20%20double%20sum2%20%3D%200.0%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%200%3B%20i%20%3C%20x.size()%3B%20%2B%2Bi)%20%7B%0A%0A%20%20%20%20%20%20%20%20unsigned%20long%20xalphai%20%3D%20std%3A%3Aget%3C2%3E(xSortedOrderedRanked.at(i))%20-%201%3B%0A%0A%20%20%20%20%20%20%20%20unsigned%20long%20yalphai%20%3D%20std%3A%3Aget%3C2%3E(ySortedOrderedRanked.at(i))%20-%201%3B%0A%0A%0A%20%20%20%20%20%20%20%20const%20std%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%26xTuple(xSortedOrderedRanked.at(xalphai))%3B%0A%0A%20%20%20%20%20%20%20%20const%20std%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%26yTuple(ySortedOrderedRanked.at(yalphai))%3B%0A%0A%0A%20%20%20%20%20%20%20%20double%20adoti%20%3D%20std%3A%3Aget%3C3%3E(xSortedOrderedRanked.back())%20%2B%20(2.0%20*%20static_cast%3Cdouble%3E(xalphai)%20-%20static_cast%3Cdouble%3E(x.size()))%20*%20x.at(i)%20-%202.0%20*%20(std%3A%3Aget%3C3%3E(xTuple)%20-%20std%3A%3Aget%3C0%3E(xTuple))%3B%0A%0A%20%20%20%20%20%20%20%20double%20bdoti%20%3D%20std%3A%3Aget%3C3%3E(ySortedOrderedRanked.back())%20%2B%20(2.0%20*%20static_cast%3Cdouble%3E(yalphai)%20-%20static_cast%3Cdouble%3E(y.size()))%20*%20y.at(i)%20-%202.0%20*%20(std%3A%3Aget%3C3%3E(yTuple)%20-%20std%3A%3Aget%3C0%3E(yTuple))%3B%0A%0A%20%20%20%20%20%20%20%20adot%5Bi%5D%20%3D%20adoti%3B%0A%0A%20%20%20%20%20%20%20%20bdot%5Bi%5D%20%3D%20bdoti%3B%0A%0A%20%20%20%20%20%20%20%20sum2%20%2B%3D%20adoti%20*%20bdoti%3B%0A%0A%20%20%20%20%20%20%20%20adotdot%20%2B%3D%20adoti%3B%0A%0A%20%20%20%20%20%20%20%20bdotdot%20%2B%3D%20bdoti%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20double%20sum3%20%3D%20adotdot%20*%20bdotdot%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20y1SortedOrderedRanked%20%3D%20FastDistanceCorrelation%3A%3AcreateVector_orderStatistics_orderIndices_rank_cummulativeSum(y1)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20gamma_1%20%3D%20FastDistanceCorrelation%3A%3ApartialSum2D(x1%2C%20y1%2C%20std%3A%3Avector%3Cdouble%3E(x.size()%2C%201.0)%2C%20xSortedOrderedRanked%2C%20y1SortedOrderedRanked)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20gamma_x%20%3D%20FastDistanceCorrelation%3A%3ApartialSum2D(x1%2C%20y1%2C%20×1%2C%20xSortedOrderedRanked%2C%20y1SortedOrderedRanked)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20gamma_y%20%3D%20FastDistanceCorrelation%3A%3ApartialSum2D(x1%2C%20y1%2C%20y1%2C%20xSortedOrderedRanked%2C%20y1SortedOrderedRanked)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20x1y1(x.size())%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%200%3B%20i%20%3C%20x1y1.size()%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20x1y1%5Bi%5D%20%3D%20×1.at(i)%20*%20y1.at(i)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20gamma_xy%20%3D%20FastDistanceCorrelation%3A%3ApartialSum2D(x1%2C%20y1%2C%20x1y1%2C%20xSortedOrderedRanked%2C%20y1SortedOrderedRanked)%3B%0A%0A%20%20%20%20double%20sum1%20%3D%200.0%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%200%3B%20i%20%3C%20x.size()%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20sum1%20%2B%3D%20(x.at(i)%20*%20y.at(i)%20*%20gamma_1.at(i))%20%2B%20gamma_xy.at(i)%20-%20(x.at(i)%20*%20gamma_y.at(i))%20-%20(y.at(i)%20*%20gamma_x.at(i))%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20sums(9%2C%20std%3A%3Anumeric_limits%3Cdouble%3E%3A%3Aquiet_NaN())%3B%0A%0A%20%20%20%20sums%5B0%5D%20%3D%20sum1%3B%0A%0A%20%20%20%20sums%5B1%5D%20%3D%20sum2%3B%0A%0A%20%20%20%20sums%5B2%5D%20%3D%20sum3%3B%0A%0A%20%20%20%20if%20(allSums)%20%7B%0A%0A%20%20%20%20%20%20%20%20double%20n%20%3D%20static_cast%3Cdouble%3E(x.size())%3B%0A%0A%20%20%20%20%20%20%20%20sums%5B3%5D%20%3D%202%20*%20n%20*%20(n%20-%201)%20*%20FastDistanceCorrelation%3A%3Avariance(x)%3B%0A%0A%20%20%20%20%20%20%20%20sums%5B4%5D%20%3D%202%20*%20n%20*%20(n%20-%201)%20*%20FastDistanceCorrelation%3A%3Avariance(y)%3B%0A%0A%20%20%20%20%20%20%20%20double%20sum1%20%3D%200.0%3B%0A%0A%20%20%20%20%20%20%20%20double%20sum2%20%3D%200.0%3B%0A%0A%20%20%20%20%20%20%20%20for%20(unsigned%20long%20i%20%3D%200%3B%20i%20%3C%20x.size()%3B%20%2B%2Bi)%20%7B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20sum1%20%2B%3D%20std%3A%3Apow(adot.at(i)%2C%202)%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20sum2%20%2B%3D%20std%3A%3Apow(bdot.at(i)%2C%202)%3B%0A%0A%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20%20%20%20%20sums%5B5%5D%20%3D%20sum1%3B%0A%0A%20%20%20%20%20%20%20%20sums%5B6%5D%20%3D%20sum2%3B%0A%0A%20%20%20%20%20%20%20%20sums%5B7%5D%20%3D%20std%3A%3Apow(adotdot%2C%202.0)%3B%0A%0A%20%20%20%20%20%20%20%20sums%5B8%5D%20%3D%20std%3A%3Apow(bdotdot%2C%202.0)%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20return%20sums%3B%0A%0A%7D%0A%0Astd%3A%3Avector%3Cdouble%3E%20FastDistanceCorrelation%3A%3ApartialSum2D(const%20std%3A%3Avector%3Cdouble%3E%20%26x%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26c%2C%20const%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20%26x_orderStatistics_orderIndices_rank_cummulativeSum%2C%20const%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20%26y_orderStatistics_orderIndices_rank_cummulativeSum)%0A%7B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20xPartialSums(x.size()%2C%200.0)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20yPartialSums(y.size()%2C%200.0)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20yRanked(y.size())%3B%0A%0A%20%20%20%20yRanked%5B0%5D%20%3D%20std%3A%3Aget%3C2%3E(y_orderStatistics_orderIndices_rank_cummulativeSum.at(0))%3B%0A%0A%20%20%20%20double%20cdot%20%3D%20c.at(0)%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%201%3B%20i%20%3C%20c.size()%3B%20%2B%2Bi)%20%7B%0A%0A%20%20%20%20%20%20%20%20cdot%20%2B%3D%20c.at(i)%3B%0A%0A%20%20%20%20%20%20%20%20xPartialSums%5Bi%5D%20%3D%20xPartialSums.at(i%20-%201)%20%2B%20c.at(i%20-%201)%3B%0A%0A%20%20%20%20%20%20%20%20yPartialSums%5Bi%5D%20%3D%20yPartialSums.at(i%20-%201)%20%2B%20c.at(%20std%3A%3Aget%3C1%3E(y_orderStatistics_orderIndices_rank_cummulativeSum.at(i%20-%201)))%3B%0A%0A%20%20%20%20%20%20%20%20yRanked%5Bi%5D%20%3D%20std%3A%3Aget%3C2%3E(y_orderStatistics_orderIndices_rank_cummulativeSum.at(i))%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20binaryTreeSums%20%3D%20FastDistanceCorrelation%3A%3AbinaryTreeSums(yRanked%2C%20c)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20gamma(x.size())%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%200%3B%20i%20%3C%20x.size()%3B%20%2B%2Bi)%20%7B%0A%0A%20%20%20%20%20%20%20%20unsigned%20long%20xI%20%3D%20std%3A%3Aget%3C2%3E(x_orderStatistics_orderIndices_rank_cummulativeSum.at(i))%20-%201%3B%0A%0A%20%20%20%20%20%20%20%20gamma%5Bi%5D%20%3D%20cdot%20-%20c.at(xI)%20-%202.0%20*%20yPartialSums.at(std%3A%3Aget%3C2%3E(y_orderStatistics_orderIndices_rank_cummulativeSum.at(xI))%20-%201)%20-%202.0%20*%20xPartialSums.at(xI)%20%2B%204.0%20*%20binaryTreeSums.at(xI)%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20return%20gamma%3B%0A%7D%0A%0Astd%3A%3Avector%3Cdouble%3E%20FastDistanceCorrelation%3A%3AbinaryTreeSums(const%20std%3A%3Avector%3Cdouble%3E%20%26y%2C%20const%20std%3A%3Avector%3Cdouble%3E%20%26c)%0A%7B%0A%0A%20%20%20%20unsigned%20long%20n%20%3D%20y.size()%3B%0A%0A%20%20%20%20unsigned%20long%20L%20%3D%20static_cast%3Cunsigned%20long%3E(std%3A%3Aceil(std%3A%3Alog2(static_cast%3Cdouble%3E(n))))%3B%0A%0A%09std%3A%3Avector%3Cunsigned%20long%3E%20powersOfTwo(L%20%2B%201)%3B%0A%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20L%20%2B%201%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20powersOfTwo%5Bi%5D%20%3D%20static_cast%3Cunsigned%20long%3E(std%3A%3Apow(2.0%2C%20static_cast%3Cdouble%3E(i)))%3B%0A%0A%09std%3A%3Avector%3Cdouble%3E%20s(powersOfTwo.at(L%20%2B%201)%2C%200.0)%3B%0A%0A%20%20%20%20std%3A%3Avector%3Cdouble%3E%20binaryTreeSums(n%2C%200.0)%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%201%3B%20i%20%3C%20n%3B%20%2B%2Bi)%20%7B%0A%0A%09%09double%20y_iminusone%20%3D%20y.at(i%20-%201)%3B%0A%0A%20%20%20%20%20%20%20%20double%20c_iminusone%20%3D%20c.at(i%20-%201)%3B%0A%0A%09%09unsigned%20long%20pos%20%3D%20static_cast%3Cunsigned%20long%3E(std%3A%3Aceil(y_iminusone))%3B%0A%0A%20%20%20%20%20%20%20%20s%5Bpos%20-%201%5D%20%2B%3D%20c_iminusone%3B%0A%0A%20%20%20%20%20%20%20%20for%20(unsigned%20long%20l%20%3D%201%3B%20l%20%3C%20L%3B%20%2B%2Bl)%20%7B%0A%0A%09%09%09pos%20%3D%20static_cast%3Cunsigned%20long%3E(std%3A%3Aceil(y_iminusone%20%2F%20powersOfTwo.at(l)))%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20unsigned%20long%20scale%20%3D%20l%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(scale%20!%3D%200)%20%7B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%09–scale%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pos%20%2B%3D%20powersOfTwo.at(L%20-%20scale)%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20s%5Bpos%20-%201%5D%20%2B%3D%20c_iminusone%3B%0A%0A%20%20%20%20%20%20%20%20%7D%0A%0A%09%09double%20%26binaryTreeSums_i(binaryTreeSums%5Bi%5D)%3B%0A%0A%20%20%20%20%20%20%20%20double%20y_i_minusone%20%3D%20y.at(i)%20-%201.0%3B%0A%0A%20%20%20%20%20%20%20%20pos%20%3D%20static_cast%3Cunsigned%20long%3E(y_i_minusone)%3B%0A%0A%20%20%20%20%20%20%20%20if%20((static_cast%3Cdouble%3E(pos)%20%2F%202.0)%20%3E%20static_cast%3Cunsigned%20long%3E(pos%20%2F%202))%0A%20%20%20%20%20%20%20%20%20%20%20%20binaryTreeSums_i%20%2B%3D%20s.at(pos%20-%201)%3B%0A%0A%20%20%20%20%20%20%20%20for%20(unsigned%20long%20l%20%3D%201%3B%20l%20%3C%20L%3B%20%2B%2Bl)%20%7B%0A%0A%09%09%09pos%20%3D%20static_cast%3Cunsigned%20long%3E(y_i_minusone%20%2F%20powersOfTwo.at(l))%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20((static_cast%3Cdouble%3E(pos)%20%2F%202.0)%20%3E%20static_cast%3Cunsigned%20long%3E(pos%20%2F%202))%20%7B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%09unsigned%20long%20scale%20%3D%20l%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20(scale%20!%3D%200)%20%7B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%09–scale%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pos%20%2B%3D%20powersOfTwo.at(L%20-%20scale)%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20binaryTreeSums_i%20%2B%3D%20s.at(pos%20-%201)%3B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20return%20binaryTreeSums%3B%0A%09%0A%7D%0A%0Abool%20FastDistanceCorrelation%3A%3AsortAscendingOnFirstElementOfTupleAndThenOnSecondElementOfTuple(const%20std%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%26element1%2C%20const%20std%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%26element2)%0A%7B%0A%0A%20%20%20%20if%20(std%3A%3Aget%3C0%3E(element1)%20%3C%20std%3A%3Aget%3C0%3E(element2))%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%0A%20%20%20%20if%20(std%3A%3Aget%3C0%3E(element1)%20%3D%3D%20std%3A%3Aget%3C0%3E(element2))%0A%20%20%20%20%20%20%20%20return%20std%3A%3Aget%3C1%3E(element1)%20%3C%20std%3A%3Aget%3C1%3E(element2)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%0A%7D%0A%0Astd%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20FastDistanceCorrelation%3A%3AcreateVector_orderStatistics_orderIndices_rank_cummulativeSum(const%20std%3A%3Avector%3Cdouble%3E%20vector)%0A%7B%0A%0A%20%20%20%20std%3A%3Avector%3Cstd%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%3E%20vector_orderStatistics_orderIndices_rank_cummulativeSum%3B%0A%0A%20%20%20%20vector_orderStatistics_orderIndices_rank_cummulativeSum.reserve(vector.size())%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%200%3B%20i%20%3C%20vector.size()%3B%20%2B%2Bi)%20%7B%0A%0A%20%20%20%20%20%20%20%20const%20double%20%26value(vector.at(i))%3B%0A%0A%20%20%20%20%20%20%20%20vector_orderStatistics_orderIndices_rank_cummulativeSum.push_back(%7Bvalue%2C%20i%2C%201%2C%20value%7D)%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20std%3A%3Asort(vector_orderStatistics_orderIndices_rank_cummulativeSum.begin()%2C%20vector_orderStatistics_orderIndices_rank_cummulativeSum.end()%2C%20FastDistanceCorrelation%3A%3AsortAscendingOnFirstElementOfTupleAndThenOnSecondElementOfTuple)%3B%0A%0A%20%20%20%20std%3A%3Aget%3C2%3E(vector_orderStatistics_orderIndices_rank_cummulativeSum%5Bstd%3A%3Aget%3C1%3E(vector_orderStatistics_orderIndices_rank_cummulativeSum.first())%5D)%20%3D%201%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%201%3B%20i%20%3C%20vector_orderStatistics_orderIndices_rank_cummulativeSum.size()%3B%20%2B%2Bi)%20%7B%0A%0A%20%20%20%20%20%20%20%20std%3A%3Atuple%3Cdouble%2C%20unsigned%20long%2C%20unsigned%20long%2C%20double%3E%20%26tuple(vector_orderStatistics_orderIndices_rank_cummulativeSum%5Bi%5D)%3B%0A%0A%20%20%20%20%20%20%20%20std%3A%3Aget%3C2%3E(vector_orderStatistics_orderIndices_rank_cummulativeSum%5Bstd%3A%3Aget%3C1%3E(tuple)%5D)%20%3D%20i%20%2B%201%3B%0A%0A%20%20%20%20%20%20%20%20std%3A%3Aget%3C3%3E(tuple)%20%3D%20std%3A%3Aget%3C3%3E(vector_orderStatistics_orderIndices_rank_cummulativeSum.at(i%20-%201))%20%2B%20std%3A%3Aget%3C0%3E(tuple)%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20return%20vector_orderStatistics_orderIndices_rank_cummulativeSum%3B%0A%09%0A%7D%0A%0Adouble%20FastDistanceCorrelation%3A%3Avariance(const%20std%3A%3Avector%3Cdouble%3E%20%26vector)%0A%7B%0A%0A%20%20%20%20if%20(vector.empty()%20%7C%7C%20(vector.size()%20%3D%3D%201))%0A%20%20%20%20%20%20%20%20return%20std%3A%3Anumeric_limits%3Cdouble%3E%3A%3Aquiet_NaN()%3B%0A%0A%20%20%20%20double%20m%20%3D%20mean(vector)%3B%0A%0A%20%20%20%20double%20ep%20%3D%200.0%3B%0A%0A%20%20%20%20double%20variance%20%3D%200.0%3B%0A%0A%20%20%20%20double%20n%20%3D%20vector.size()%3B%0A%0A%20%20%20%20for%20(unsigned%20long%20i%20%3D%200%3B%20i%20%3C%20vector.size()%3B%20%2B%2Bi)%20%7B%0A%0A%20%20%20%20%20%20%20%20double%20sum%20%3D%20vector.at(i)%20-%20m%3B%0A%0A%20%20%20%20%20%20%20%20ep%20%2B%3D%20sum%3B%0A%0A%20%20%20%20%20%20%20%20variance%20%2B%3D%20sum%20*%20sum%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20return%20(variance%20-%20ep%20*%20ep%20%2F%20n)%20%2F%20(n%20-%201.0)%3B%0A%0A%7D%0A%0Adouble%20FastDistanceCorrelation%3A%3Amean(const%20std%3A%3Avector%3Cdouble%3E%20%26vector)%0A%7B%0A%20%20%20%20double%20sum%20%3D%200.0%3B%0A%0A%20%20%20%20for%20(const%20double%20%26value%20%3A%20vector)%0A%20%20%20%20%20%20%20%20sum%20%2B%3D%20value%3B%0A%0A%20%20%20%20return%20sum%20%2F%20static_cast%3Cdouble%3E(vector.size())%3B%0A%0A%7D” message=”fastdistancecorrelation.cpp” highlight=”” provider=”manual”/]