@@ -73,31 +73,41 @@ std::string GetBigOString(BigO complexity) {
7373// - time : Vector containing the times for the benchmark tests.
7474// - fitting_curve : lambda expression (e.g. [](int64_t n) {return n; };).
7575
76- // For a deeper explanation on the algorithm logic, look the README file at
77- // http://github.com/ismaelJimenez/Minimal-Cpp-Least-Squared-Fit
76+ // This algorithm works like this:
77+ //
78+ // Let the execution times t_i for input sizes n_i be the function
79+ // t_i = f(n_i) = c*g(n_i), where c is a coefficient. The coefficient
80+ // c is compued by assuming that t_i and f(n_i) are the same function
81+ // with different coefficients t_i = c_1*g(n_i) and f(n_i) = c_2*g(n_i).
82+ // Since t_i and f(n_i) are the same function, they only differ in
83+ // proportionality: c_2 = c_1 * g(n_i) / g(n_i)
84+ //
85+ // If, t_i and f(n_i) is not the same function, the Root Mean Square
86+ // (RMS) error will be large and dominated by n.
87+ // Example t_i = c_1*O(n^2) and f(n_i) = c_2*O(n*log(n)):
88+ // ||e|| = sqrt(1/numSamples*sum((t_i - f(n_i))^2))
89+ // ||e|| = sqrt(1/numSamples*sum((c_1*n_i^2 - c_2*n_i*log(n_i))^2))
90+ // ||e||^2*numSamples = sum((c_1*n_i^2 - c_2*n_i*log(n_i)^2)
91+ // which is dominated by the difference (n_i^2 - n_i*log(n_i))^2
7892
7993LeastSq MinimalLeastSq (const std::vector<int64_t >& n,
8094 const std::vector<double >& time,
8195 BigOFunc* fitting_curve) {
8296 double sigma_gn = 0.0 ;
83- double sigma_gn_squared = 0.0 ;
8497 double sigma_time = 0.0 ;
85- double sigma_time_gn = 0.0 ;
8698
8799 // Calculate least square fitting parameter
88100 for (size_t i = 0 ; i < n.size (); ++i) {
89101 double gn_i = fitting_curve (n[i]);
90102 sigma_gn += gn_i;
91- sigma_gn_squared += gn_i * gn_i;
92103 sigma_time += time[i];
93- sigma_time_gn += time[i] * gn_i;
94104 }
95105
96106 LeastSq result;
97107 result.complexity = oLambda;
98108
99109 // Calculate complexity.
100- result.coef = sigma_time_gn / sigma_gn_squared ;
110+ result.coef = sigma_time / sigma_gn ;
101111
102112 // Calculate RMS
103113 double rms = 0.0 ;
0 commit comments