expression for lower bound al of binary search

[liarrn]

In the paper, the al=sqrt(n/m)/2, while in the code implementation, e.g. line 303 of anms.h, the al is calculated as int low = floor(sqrt((double)keyPoints.size()/numRetPoints));. Could the author clarify the discrepancy?

[BAILOOL]

@liarrn I think the difference between the code and the paper is that in the paper a_l represents half of the square length, while in the code it corresponds to the full length.

[liarrn]

@BAILOOL Thank you for the quick reply!
For the calculation of a_h, starting from line 294 of anms.h, it is the same with equation (5) in the paper. The a_l in the code is 2 times larger than the equation (6) in the paper. Would this be a bug in the code?

    int exp1 = rows + cols + 2*numRetPoints;
    long long exp2 = ((long long) 4*cols + (long long)4*numRetPoints + (long long)4*rows*numRetPoints + (long long)rows*rows + (long long) cols*cols - (long long)2*rows*cols + (long long)4*rows*cols*numRetPoints);
    double exp3 = sqrt(exp2);
    double exp4 = (2*(numRetPoints - 1));

    double sol1 = -round((exp1+exp3)/exp4); // first solution
    double sol2 = -round((exp1-exp3)/exp4); // second solution

    int high = (sol1>sol2)? sol1 : sol2; //binary search range initialization with positive solution
    int low = floor(sqrt((double)keyPoints.size()/numRetPoints));

[BAILOOL]

@liarrn You are right. I think I have made a copy-paste mistake when preparing code for this repository since the original version we used for the experiments in the paper was too messy to deal with. Thank you for pointing it out.